65. Сформулювати економічний сенс попередніх перетворень при рішення задач угорським методом.

Ідея методу полягає у здійсненні послідовного переходу від деякого недопустимого плану (не всі потреби задоволені і не вся продукція вивезена) до допустимого, що є розв’язком задачі. Цей перехід здійснюється за скінченну кількість ітерацій (але невідому до кінця обчислень), що пов’язані з перетвореннями матриці вартостей і поточного плану .

Назвемо умовно-оптимальним планом (псевдопланом) транспортної задачі (5.1)—(5.4) таку сукупність невід’ємних чисел , яка задовольняє задану систему нерівностей:

(5.27)

(5.28)

і такі наступні умови для змінних двоїстої задачі — потенціалів:

, якщо ;

, якщо .

Мірою недопустимості (умовою неоптимальності) умовно-оптимального плану може бути наявність різниці між сумою всіх запасів (чи потреб, що те саме) і сумою всіх перевезень умовно-оптимального плану, тобто:

(5.29)

Зрозуміло, що чим менша нев’язка , тим ближче умовно-оптимальний план до найкращого плану транспортної задачі, а у разі, коли  = 0, він збігається з оптимальним планом.

Звідси легко збагнути ідею розглядуваного методу розв’я­зування транспортної задачі: починаючи з деякого початкового плану задачі, подвійної до транспортної , можна знайти послідовність оптимальних планів ряду допоміжних задач на мінімізацію (5.29) за обмежень (5.27) і (5.28), кожний наступний план якої надає нев’язці (5.29) меншого значення у зіставленні з попереднім, а останній план цієї послідовності надає нев’язці нульового значення, збігаючись у такий спосіб з оптимальним планом транспортної задачі.

Отже, кожна ітерація методу означатиме розв’язування допоміжної задачі (5.27)—(5.28) і зменшення при цьому значення цільової функції (5.29) порівняно з попереднім розв’язком цієї задачі.

Щоб сформулювати допоміжну задачу, треба, крім використання величин і , що їх містить задана транспортна задача, побудувати ще деякий план двоїстої задачі , . Для початку першої ітерації це легко зробити, узявши, наприклад:

, (5.30)

причому даний план задовольняє умову:

+ , (5.31)

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

.

У наступних ітераціях утворену систему потенціалів змінюємо, але так, що вона завжди залишається планом подвійної задачі.

Наведені вище обмеження для змінних двоїстої задачі:

, якщо ;

, якщо

означають, що клітини, в яких для визначеної на k-му кроці системи потенціалів виконується строга нерівність , не заповнюють. Отже, розв’язуючи задачу, будемо використовувати лише ті клітини, для яких .

Зауважимо, що мінімізація цільової функції (5.29) рівнозначна максимізації другого її доданка

(5.32)

при тій самій системі обмежень. Зрозуміло, що , а при матимемо: .