>
WXYZФА141906000В922803000С61730300015002500270033002000 Вирішуємо поставлену задачу методом лінійного програмування за допомогою табличного редактора Microsoft Excel
Підбір рішення здійснюємо за допомогою команди «Сервіс / пошук рішення» і введенням параметрів в діалоговому вікні.
6. Результати рішення
Математична модель транспортної задачі:
=?? c ij x ij, (1)
за умов:
? x ij=ai, i=1,2, ..., m, (2)
? x ij=bj, j=1,2, ..., n, (3)
З метою складання двоїстої задачі змінні x ij в умові (2) замінимо на u 1, u 2, ui, .., um, а змінні x ij в умови (3) на v 1, v 2, vj, .., vn.
Оскільки кожна змінна x ij входить в умови (2,3) і цільову функцію (1) по одному разу, то двоїсту задачу по відношенню до прямої транспортної задачі можна сформулювати наступним чином.
Потрібно знайти не негативні числа ui (при i=1,2, ..., m) і vj (при j=1,2, .., n), що звертають в максимум цільову функцію
=? a i u i +? b j v j
за умови
u i + v j? c ij, i=1,2, .., m; j=1,2, .., n (4)
У систему умов (4) буде mxn нерівностей. По теорії подвійності для оптимальних планів прямої та двоїстої задачі для всіх i, j повинно бути: i + vj? c ij, якщо x ij=0, i + vj=c ij, якщо x ij? 0,
Ці умови є необхідними і достатніми ознаками оптимальності плану транспортної задачі.
Числа ui, vj називаються потенціалами. Причому число ui називається потенціалом постачальника, а число vj - потенціалом споживача.
За перший теоремі подвійності в оптимальному рішенні значення цільових функцій прямої та двоїстих задач збігаються: F=G.
Вартість доставки одиниці вантажу з кожного пункту відправлення у відповідні пункти призначення задана матрицею тарифів
1234Запасы114196000292283000361733000Потребности1500250027003300
Перевіримо необхідна і достатня умова розв'язання задачі.
? a=6000 + 3000 + 3000=12000
? b=1500 + 2500 + 2700 + 3300=10000
Як видно, сумарна потреба вантажу в пунктах призначення перевищує запаси вантажу на базах. Отже, модель вихідної транспортної задачі є відкритою. Щоб отримати закриту модель, введемо додаткову (фіктивну) базу з запасом вантажу, рівним 2000 (12000-10000). Тарифи перевезення одиниці вантажу з бази в усі магазини вважаємо дорівнюють нулю.
Занесемо вихідні дані в розподільну таблицю.
12345Запасы114190600029228030003617303000Потребности15002500270033002000
Етап I. Пошук першого опорного плану.
. Використовуючи метод найменшої вартості, побудуємо перший опорний план транспортної задачі. Суть методу полягає в тому, що з усієї таблиці вартостей вибирають найменшу, і в клітку, яка їй відповідає, поміщають менше з чисел ai, або bj.
Потім, з розгляду виключають або рядок, відповідну постачальнику, запаси якого повністю витрачен...
