Методичні вказівки до виконання курсового проекту 4 страница

Таблиця42

Четверта ітерація ТТ

Оскільки у таблиці 43 перший і другий стовпці містять по одному елементу, то різниця у цьому випадку знаходиться між ними, тобто дорівнює 0. У першої єдиної строчці знаходимо мінімальний елемент – це 4 у клітинці А₁В₁. Тому поміщаємо у цю клітинку максимально можливий обсяг вантажу – 70, при цьому виключаємо з подальшого розгляду перший стовпець, поставивши нижче різниці – букву К (кінець), тому що повністю задоволена уся заявка вантажу першого споживача.

У таблиці 44 заповнюється остання вільна клітинка ТТ, а саме А₁В₂ обсягом вантажу рівним 30 одиницям.

Таблиця43

П’ята ітерація ТТ

Таблиця44

Шоста ітерація ТТ

В результаті одержано (m + n - 1) = 6 перевезень вантажу, отже складений опорний план не вироджений і ми можемо порахувати вартість його реалізації:

у.г.о.

4. МЕТОДИ ЗНАХОДЖЕННЯ ОПТІМАЛЬНИХ ПЛАНІВ

ПЕРЕВЕЗЕНЬ ВАНТАЖУ

4.1. Симплексний метод оптимізації транспортних перевезень

Існує безліч методів оптимізації ТЗ, а точніше приведення до оптимального плану перевезень складеного раніше опорного (базисного) плану. До основних належать розподільний метод, метод потенціалів, метод диференційних рент.

Оскільки ТЗ є окремим випадком загальної задачі ЛП (ЗЗЛП), то до неї також цілком можливо застосувати всі стандартні методи її розв’язання (зокрема найвідоміший з них – симплексний метод), попередньо привівши ТЗ до вигляду задачі ЛП і врахувавши її специфічність. Для цього необхідно провести над математичною моделлю ТЗ ряд перетворень. Ці перетворення будемо здійснювати на конкретному прикладі ТЗ, а саме для m постачальників (m=3) і n споживачів продукції (n=4) (див. табл. 1).

а) спочатку запишемо вихідну систему рівнянь ТЗ у такому вигляді:

|| || || ||

b₁ b₂ b₃ b₄

де: x_ij –кількість продукції, відправленої від і-го постачальника до j-го споживача;

а_i – обсяг продукції наявної у і-го постачальника ( i=1, 2, 3);

b_j –обсяг продукції необхідної j-ому споживачу (j=1, 2, 3, 4).

б) подамо її у вигляді системи (т + n)лінійних рівнянь таким чином:

в) замінимо x₁₁ на x₁, x₁₂ на x₂, x₁₃ на x₃, . . ., x₃₄ на x₁₂. Маємо:

г) додамо, як того вимагає симплексний метод, до всіх рівнянь додаткові перемінні, які становитимуть початковий базисний розв’язок ТЗ:

У результаті цих перетворень ми утворили систему (т + п)лінійних рівнянь з (m´п + т+ n)позитивними перемінними, розв’язати яку можна за допомогою симплекс-методу. Оскільки сума рівнянь системи в рядках дорівнює сумі рівнянь системи в стовпцях, то ми одержали лінійно-залежну систему рівнянь. Щоб привести її до нормального (лінійно-незалежного) виду, одне з рівнянь системи (переважно останнє) можна без шкоди для кінцевого результату розв’язку ТЗ відкинути. Тоді ми матимемо (т + п – 1)лінійних рівнянь і (m´п + т+ n - 1) перемінних.

Необхідно також відзначити те, що у класичній ТЗ перевезти продукцію від усіх постачальників (а_i)потрібно так, щоб усі замовлення були виконані (b_j),а загальна вартість (L) транспортних перевезень була б мінімальною, тобто:

,

де: с₁ , с₂, ... с_k –вартість перевезення одиниці продукції від кожного постачальника до кожного споживача (k = 1,т´ п).

Розглянемо розв'язання ТЗ на конкретному прикладі, умови якого дані у вигляді ТТ (табл. 45) , де т = 3 , n = 4. Відповідно, кількість рівнянь становитиме (m + n – 1 ) = 6, кількість вихідних перемінних – (m × n) = 12 і кількість додаткових перемінних – (т + п – 1) = 6.

Таблиця45

Дані ТЗ у вигляді ТТ

Запишемо умову нашої ТЗ у термінах ЗЗЛП.

Необхідно мінімізувати цільову функцію L = 4× x₁ +7 × x₂ +2 × x₃ +5 × x₄ +3 × x₅ + 6 × x₆ +1×x₇+8 × x₈ +9 × x₉ +3 × x₁₀ + 6 × x₁₁ +2×x₁₂,

за таких обмежень:

тобто кількість рівнянь становить 6, а кількість вихідних перемінних дорівнює 12.

Вводимо до обмежень нові змінні x₁₃, x₁₄, x₁₅, x₁₆, x₁₇, x₁₈. Значення відповідних коефіцієнтів впливу вибираємо набагато більші ніж існують. У нашому випадку приймемо за цю величину суму всіх коефіцієнтів при невідомих у початковій цільовій функції, тобто 56. Завдяки цьому перемінні x₁₃, x₁₄, x₁₅, x₁₆, x₁₇, x₁₈ з базисних поступово будуть переведені у вільні, що забезпечує тим самим мінімум цільової функції. Після введення нових перемінних маємо:

L = 4× x₁ +7 × x₂ +2 × x₃ +5 × x₄ +3 × x₅ + 6 × x₆ +1×x₇+8 × x₈ +9 × x₉ +3 × x₁₀ + 6 × x₁₁ +2×x₁₂+56 × x₁₃ +56 × x₁₄ +56 × x₁₅ + 56 × x₁₆ +56×x₁₇+56 × x₁₈, → min,

за обмежень

Остаточна кількість рівнянь k = 6; кількість перемінних l = 18.

За базисні обираємо x₁₃, x₁₄, x₁₅, x₁₆, x₁₇, x₁₈ і отримуємо перше базисне рішення X = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 100, 120, 140, 80, 100, 110}, що забезпечує L = 56 × 100 + 56 × 120 +56 × 140 + 56 × 80 + 56 × 100 +56 × 110 = 36400 у.г.о.

Складемо першу симплекс-таблицю (СТ) – табл. 46. У першому рядку цієї таблиці знаходяться значення коефіцієнтів c_j при невідомих цільової функції; у першій графі СТ розташовані значення коефіцієнтів c_бі при базових невідомих цільової функції; друга графа містить самі базові невідомі х_бі; третя – значення базових невідомих b_бi (у першій СТ це значення правих частин останньої системи рівнянь) і частина СТ, що залишилася, крім останнього рядка, зайнята коефіцієнтами a_ij при невідомих також останньої системи рівнянь.

Останній рядок (індексний ряд) служить для розрахунків індексів ∆_j, що є характеристиками оптимальності отриманого плану. Індекси розраховуються за допомогою наступних формул:

Таблиця46

Перша СТ

Вважається, що отримане рішення х_бі є оптимальним, якщо .

Порахуємо значення індексів для першої СТ:

∆₀= 56 × 100 + 56 × 120 +56 × 140 + 56 × 80 +56 × 100 + 56 × 110 = 36400 у.г.о.

∆₁= 56 × 1 + 56 × 0 +56 × 0 + 56 × 1 +56 × 0 + 56 × 0 – 4 = 108

∆₂= 56 × 1 + 56 × 0 +56 × 0 + 56 × 0 +56 × 1 + 56 × 0 – 7 = 105

∆₃= 56 × 1 + 56 × 0 +56 × 0 + 56 × 0 +56 × 0 + 56 × 1 – 2 = 110

∆₄= 56 × 1 + 56 × 0 +56 × 0 + 56 × 0 +56 × 0 + 56 × 0 – 5 = 51

∆₅= 56 × 0 + 56 × 1 +56 × 0 + 56 × 1 +56 × 0 + 56 × 0 – 3 = 109

∆₆= 56 × 0 + 56 × 1 +56 × 0 + 56 × 0 +56 × 1 + 56 × 0 – 6 = 106

∆₇= 56 × 0 + 56 × 1 +56 × 0 + 56 × 0 +56 × 0 + 56 × 1 – 1 = 111

∆₈= 56 × 0 + 56 × 1 +56 × 0 + 56 × 0 +56 × 0 + 56 × 0 – 8= 48

∆₉= 56 × 0 + 56 × 0 +56 × 1 + 56 × 1 +56 × 0 + 56 × 0 – 9 = 103

∆₁₀= 56 × 0 + 56 × 0 +56 × 1 + 56 × 0 +56 × 1 + 56 × 0 – 3 = 109

∆₁₁= 56 × 0 + 56 × 0 +56 × 1 + 56 × 0 +56 × 0 + 56 × 1 – 6 = 106

∆₁₂= 56 × 0 + 56 × 0 +56 × 1 + 56 × 0 +56 × 0 + 56 × 0 – 2 = 54

∆₁₃= 56 × 1 + 56 × 0 +56 × 0 + 56 × 0 +56 × 0 + 56 × 0 – 56 = 0

∆₁₄= 56 × 0 + 56 × 1 +56 × 0 + 56 × 0 +56 × 0 + 56 × 0 – 56 = 0

∆₁₅= 56 × 0 + 56 × 0 +56 × 1 + 56 × 0 +56 × 0 + 56 × 0 – 56 = 0

∆₁₆= 56 × 0 + 56 × 0 +56 × 0 + 56 × 1 +56 × 0 + 56 × 0 – 56 = 0

∆₁₇= 56 × 0 + 56 × 0 +56 × 0 + 56 × 0 +56 × 1 + 56 × 0 – 56 = 0

∆₁₈= 56 × 0 + 56 × 0 +56 × 0 + 56 × 0 +56 × 0 + 56 × 1 – 56 = 0

Очевидно, що базове рішення не є оптимальним, тому що усі індекси від ∆₁ до ∆₁₈ позитивні, тому продовжимо поліпшення (оптимізацію) базового плану далі.

У якості ключового стовпця, який містить внесену в базу вільну змінну, вибираємо стовпець х₇, що має максимальне позитивне значення ∆₇ = 111. Для визначення ключового рядка рахуємо відповідні відношення значень базових невідомих b_бi на не нульові значення елементів обраного ключового стовпця, а саме:

; і вибираємо з них мінімальне, тобто друге.

Тоді ключовим рядком буде шостий і він містить базову змінну х₁₈ , що виводиться з базису. Тобто змінна ключового шостого рядка базису х₁₈ має бути замінена на вільну змінну ключового стовпця х₇ , при цьому ключове число a₆₇= 1 (це число відмічено у СТ більшим розміром). Складаємо нову СТ (див. табл. 47).

Спочатку введемо в базис замість змінної х₁₈ змінну х₇ зі значенням її коефіцієнта c₇ = 1 і розділимо всі елементи цього рядка на ключове число a₆₇= 1. Після цього перерахуємо значення частини елементів таблиці, що залишилася, таким способом:

,

де: НЕ і СЕ – відповідно будь-який новий елемент (a_ij^н або b_i^н) з не ключового рядка і той же старий елемент (a_ij або b_i) СТ, що перетворюється;

ЕК_р і ЕК_ст – відповідно елементи ключового рядка і ключового стовпчику СТ, що перетворюється;

К – ключовий елемент СТ, що перетворюється (у нашому випадку для першої СТ це a₆₇).

Порахуємо як приклад по цій формулі нові значення b₂ , a₂₃ і a₂₇:

.

Інші елементи перенесемо в нову СТ без демонстрації аналогічних детальних розрахунків.

Як видно з таблиці 47 нове значення цільової функції дорівнює 24190 у.г.о., що значно менше попереднього її значення і, що, у свою чергу, свідчить про нормальний плин процесу оптимізації. Індексний рядок нової СТ містить позитивні елементи – це означає, що отримане значення не є оптимальним і план перевезень вимагає поліпшення. Відзначимо в СТ ключовий елемент a₂₅ і опускаючи всі розрахунки перейдемо до наступної СТ (див. табл. 48).

Таблиця47

Друга СТ

Із цієї СТ також видно, що процес оптимізації триває (нове значення цільової функції дорівнює 23100), але в індексному рядку ще присутні позитивні елементи – це означає, що план перевезень вимагає подальшого поліпшення. Відзначимо також у СТ ключовий елемент a_5,10 і перейдемо до наступної СТ (див. табл. 49).

Таблиця48

Третя СТ

У цій таблиці також присутні позитивні елементи в індексному рядку, тому переходимо до нового СТ із новим ключовим елементом –a₄₁(див. табл. 50).

• ⇐ Назад
• 1
• 2
• 3
• 4
• 567
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• Далее ⇒