 |
|
РОЗРАХУНКОВІ МАТЕРІАЛИ
Формування транспортної таблиці.
Першим етапом формування МММ є складання масиву відстаней між сусідніми вузлами ТМ.
Масив відстаней між сусідніми вузлами ТМ
| № п/п | ПП | КП | Номер ребра | Відстань |
| B1 | B2 | |||
| B2 | B3 | |||
| B3 | B4 | |||
| B1 | B4 | |||
| A2 | А3 | |||
| A1 | А3 | |||
| A1 | B2 | |||
| A2 | B2 | |||
| A2 | B3 | |||
| A2 | B4 | |||
| A3 | B4 | |||
| A3 | B1 | |||
| A1 | B1 |
На другому етапі будується матриця транспортних кореспонденцій між всіма вузлами ТМ. Відстань між не сусідніми (суміжними) вузлами проставляється рівним нескінченності. Матриця щодо її головної діагоналі має симетричний характер, тому що ми маємо справу з неорієнтованою транспортною мережею.
Матриця транспортних кореспонденцій
Між всіма вузлами ТМ
| A1 | A2 | A3 | B1 | B2 | B3 | B4 | |
| A1 | ∞ | ∞ | ∞ | ∞ | |||
| A2 | ∞ | ∞ | ∞ | ||||
| A3 | ∞ | ∞ | ∞ | ||||
| B1 | ∞ | ∞ | ∞ | ||||
| B2 | ∞ | ∞ | ∞ | ||||
| B3 | ∞ | ∞ | ∞ | ∞ | |||
| B4 | ∞ | ∞ | ∞ |
Третій етап - формування МММ. Цей метод (модифікований метод Дейкстри), використовуючи дані матриці кореспонденцій, знаходить як значення найкоротших відстаней на ТМ від кожного постачальника вантажу до кожного його споживача, так і відповідні цим відстаням маршрути, які можуть містити проміжні пункти на шляхах переміщення вантажу.
Маршрути найкоротших відстаней
| №п/п | Маршрут | Відстань |
| A1àB1 | ||
| A1àB2 | ||
| A1àB1àB4àB3 | ||
| A1àB1àB4 | ||
| A2àB4àB1 | ||
| A2à B2 | ||
| A2àB3 | ||
| A2à B4 | ||
| A3àB1 | ||
| A3àA2àB2 | ||
| A3àВ4àB3 | ||
| A3àB4 |
Матриця найкоротших відстаней на ТМ
| B1 | B2 | B3 | B4 | |
| A1 | ||||
| A2 | ||||
| A3 |
Реалізація в EXCEL
Четвертий етап полягає в складанні опорного плану перевезень методом північно – східного кута.
Опорний план
| B1 | B2 | B3 | B4 | Запаси | |
| A1 | |||||
| A2 | |||||
| A3 | |||||
| Заявки |
Вартість перевезень
В=24+5+6+10+18+56=119.
Реалізація в EXCEL. Опорний план
.
2.2 Пошук оптимального плану симплекс - методом.
Оптимальний план перевезень знаходимо за допомогою симплекс-методу/. Транспортна таблиця має вигляд
Транспортна таблиця
| B1 | B2 | B3 | B4 | Запаси (ai) | |
| A1 | c1 = 4 x1 | c2 = 6 x2 | c3 =9 x3 | c4 = 7 x4 | |
| A2 | c5 = 5 x5 | c6 = 1 x6 | c7 = 2 x7 | c8 = 2 x8 | |
| A3 | c9 = 3 x9 | c10 = 5 x10 | c11 = 4 x11 | c12 = 2 x12 | |
| Заявки (bj) |
Запишемо умову ТЗ у термінах ЗЗЛП.
Вводимо додаткові змінні x13, x14, x15, x16, x17, x18. Значення відповідних коефіцієнтів впливу вибираємо набагато більші ніж існують. Приймемо за цю величину суму всіх коефіцієнтів, тобто 50. Завдяки цьому перемінні x13, x14, x15, x16, x17, x18 з базисних поступово будуть переведені у вільні, що забезпечує тим самим мінімум цільової функції. Маємо цільову функцію:
L = 4× x1 +6 × x2 +9× x3 +7 × x4 +5 × x5 + 1× x6 +2×x7+2× x8 +3 × x9 +5× x10 + 4× x11 +2×x12+50 × x13 +50 × x14 +50× x15 + 50× x16 +50×x17+50× x18, → min,
за обмежень
Остаточна кількість рівнянь k = 6; кількість змінних l = 18.
За базисні обираємо x13, x14, x15, x16, x17, x18 і отримуємо перше базисне рішення X = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 10, 12, 8, 9, 6, 7}, що забезпечує L = 2600 у.г.о.
Складемо першу симплекс-таблицю (СТ1) У першому рядку цієї таблиці знаходяться значення коефіцієнтів cj при невідомих цільової функції; у першій графі СТ розташовані значення коефіцієнтів cбі при базових невідомих цільової функції; друга графа містить самі базові невідомі хбі; третя – значення базових невідомих bбi (у першій СТ це значення правих частин останньої системи рівнянь) і частина СТ, що залишилася, крім останнього рядка, зайнята коефіцієнтами aij при невідомих також останньої системи рівнянь.
Останній рядок (індексний ряд) служить для розрахунків індексів ∆j, що є характеристиками оптимальності отриманого плану. Індекси розраховуються за допомогою наступних формул:
Вважається, що отримане рішення хбі 
є оптимальним, якщо 
.
Очевидно, що базове рішення не є оптимальним, тому що усі індекси від ∆1 до ∆18 позитивні, продовжимо поліпшення (оптимізацію) базового плану далі.
У якості ключового стовпця, який містить внесену в базу вільну змінну, вибираємо стовпець, що має максимальне позитивне значення. Для визначення ключового рядка рахуємо відповідні відношення значень базових невідомих bбi на не нульові значення елементів обраного ключового стовпця.
Перша симплекс-таблиця -СТ1
| cij | xij | bij | x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | x11 | x12 | x13 | x14 | x15 | x16 | x17 | x18 |
| x13 | ||||||||||||||||||||
| x14 | ||||||||||||||||||||
| x15 | ||||||||||||||||||||
| x16 | ||||||||||||||||||||
| x17 | ||||||||||||||||||||
| x18 | ||||||||||||||||||||
Ключовий стовпець – x6
Ключовий рядок – x17.
Складаємо нову таблицю – СТ2.
Друга симплекс-таблиця - СТ2
| cij | xij | bij | x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | x11 | x12 | x13 | x14 | x15 | x16 | x17 | x18 |
| x13 | ||||||||||||||||||||
| x14 | -1 | -1 | -1 | |||||||||||||||||
| x15 | ||||||||||||||||||||
| x16 | ||||||||||||||||||||
| x6 | ||||||||||||||||||||
| x18 | ||||||||||||||||||||
| -5 | -4 | -99 |
Ключовий стовпець – x7
Ключовий рядок – x14.
Складаємо нову таблицю – СТ3.
Третя симплекс-таблиця - СТ3
| cij | xij | bij | x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | x11 | x12 | x13 | x14 | x15 | x16 | x17 | x18 |
| x13 | ||||||||||||||||||||
| x7 | -1 | -1 | -1 | |||||||||||||||||
| x15 | ||||||||||||||||||||
| x16 | ||||||||||||||||||||
| x6 | ||||||||||||||||||||
| x18 | -1 | -1 | -1 | |||||||||||||||||
| -3 | -50 | -98 | -1 |
Ключовий стовпець – x9
Ключовий рядок – x15.
Складаємо нову таблицю – СТ4
Четверта симплекс-таблиця - СТ4
| cij | xij | bij | x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | x11 | x12 | x13 | x14 | x15 | x16 | x17 | x18 |
| x13 | ||||||||||||||||||||
| x7 | -1 | -1 | -1 | |||||||||||||||||
| x9 | ||||||||||||||||||||
| x16 | -1 | -1 | -1 | -1 | ||||||||||||||||
| x6 | ||||||||||||||||||||
| x18 | -1 | -1 | -1 | |||||||||||||||||
| -3 | -50 | -3 | -1 | -49 | -98 | -97 | -1 |
Ключовий стовпець – x1
Ключовий рядок – x16.
Складаємо нову таблицю – СТ5.
П’ята симплекс-таблиця - СТ5
| cij | xij | bij | x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | x11 | x12 | x13 | x14 | x15 | x16 | x17 | x18 |
| x13 | -1 | -1 | ||||||||||||||||||
| x7 | -1 | -1 | -1 | |||||||||||||||||
| x9 | ||||||||||||||||||||
| x1 | -1 | -1 | -1 | -1 | ||||||||||||||||
| x6 | ||||||||||||||||||||
| x18 | -1 | -1 | -1 | |||||||||||||||||
| -99 | -50 | -98 | -1 | -96 | -1 |
Ключовий стовпець – x2, ключовий рядок – x18. Складаємо нову таблицю – СТ6.
Шоста симплекс-таблиця СТ6
| cij | xij | bij | x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | x11 | x12 | x13 | x14 | x15 | x16 | x17 | x18 |
| x13 | -1 | -1 | -1 | |||||||||||||||||
| x7 | ||||||||||||||||||||
| x9 | ||||||||||||||||||||
| x1 | -1 | -1 | -1 | -1 | ||||||||||||||||
| x6 | -1 | -1 | -1 | |||||||||||||||||
| x2 | -1 | -1 | -1 | |||||||||||||||||
| -2 | -6 | -5 | -1 | -96 | -94 | -93 |
Ключовий стовпець – x12, ключовий рядок – x13. Складаємо нову таблицю – СТ7.
Сьома симплекс-таблиця - СТ7
| cij | xij | bij | x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | x11 | x12 | x13 | x14 | x15 | x16 | x17 | x18 |
| x12 | -1 | -1 | -1 | |||||||||||||||||
| x7 | ||||||||||||||||||||
| x9 | -1 | -1 | -1 | -1 | ||||||||||||||||
| x1 | -1 | -1 | -1 | -1 | ||||||||||||||||
| x6 | -1 | -1 | -1 | |||||||||||||||||
| x2 | -1 | -1 | -1 | |||||||||||||||||
| -2 | -4 | -6 | -4 | -47 | -52 | -48 | -49 | -47 | -46 |
Очевидно, що отримане рішення є оптимальним, тому що усі індекси від ∆1 до ∆18 менші або рівні нулю. Маємо оптимальний план перевезення вантажу. Вартість перевезення L = 93 у.г.о.
Оптимальний план перевезень вантажу
| B1 | B2 | B3 | B4 | Запаси (ai) | |
| A1 | c1 = 4 x1=9 | c2 = 6 x2=1 | c3 =9 x3 | c4 = 7 x4 | |
| A2 | c5 = 5 x5 | c6 = 1 x6=5 | c7 = 2 x7=7 | c8 = 2 x8 | |
| A3 | c9 = 3 x9 | c10 = 5 x10 | c11 = 4 x11 | c12 = 2 x12=8 | |
| Заявки (bj) |
Реалізація в EXCEL.
