Контрольная работа: Задачі математичного програмування

30

u4 = -2

vj

v1 =1

v2 =2

v3 =4

v4 =4

V5 =2

В результаті отримано перший опорний план, який є допустимим, оскільки всі вантажі з баз вивезені, потреба магазинів задоволена, а план відповідає системі обмежень транспортної задачі.

Підрахуємо число зайнятих клітин таблиці, їх 8, а має бути m+n-1=8. Отже, опорний план є невироджених.

Перевіримо оптимальність опорного плану, складемо систему рівнянь (для заповнених клітин таблиці) для визначення потенціалів першого опорного плану:

Записана система рівнянь є невизначеною, і один з її розв’язків дістанемо, узявши, наприклад, u1 = 0. Тоді всі інші потенціали однозначно визначаються з цієї системи рівнянь: u1 =0, u2 = -3, u3 = -1, u4=-2, v1 =1, v2 =2, v3 =4 v4=4, v5=2. Ці значення потенціалів першого опорного плану записуємо у транспортну таблицю.

Потім згідно з алгоритмом методу потенціалів перевіряємо виконання другої умови оптимальності ui + vj ≤ cij (для порожніх клітинок таблиці):

А1B4 : u1 + v4 = 0 + 4 = 4 > 1;

А1B5 : u1 + v5 = 0 + 2 = 2 < 5;

А2B1 : u2 + v1 = -3 + 1 = -2 < 1;

А2B2 : u2 + v2 = -3 + 2 = -1 < 2;

А2B4 : u2 + v4 = -3 + 4 = 1 < 3;

А2B5 : u2 + v5 = -3 + 2 = -1 < 1;

А3B1 : u3 + v1 = -1 + 1 = 0 < 2;

А3B2 : u3 + v2 = -1 + 2 = 1 = 1;

А4B1 : u4 + v1 = -2 + 1 = -1 < 0;

А4B2 : u4 + v2 = -2 + 2 = 0 = 0;

А4B3 : u4 + v3 = -2 + 4 = 2 > 0;

А4B4 : u4 + v4 = -2 + 4 = 2 > 0.

Опорний план не є оптимальним, тому що існують оцінки вільних клітин для яких ui + vi > cij

А1B4 : u1 + v4 = 0 + 4 = 4 > 1;

А4B3 : u4 + v3 = -2 + 4 = 2 > 0;