ТЕМА7. ЗНАХОДЖЕННЯ ОПТИМАЛЬНОГО РОЗВ’ЯЗКУ ТРАНСПОРТНОЇ ЗАДАЧІ. ЗАДАЧА ПРО ПРИЗНАЧЕННЯ

Процедура пошуку оптимального розвязку ТЗ реалізується за допомогою комбінації двох методів: розподільчого та методу потенціалів.

7.1. Метод потенціалів (знаходження змінної, що включається до базису).

Сутність методу полягає в наступному. Кожному i-му рядку та кожному j-му стовпцю транспортної таблиці ставиться у відповідність деяка змінна Ui або Vj (потенціал). При цьому значення потенціалів такі, що для будь-якої базисної змінної xij має виконуватися рівність: Ui +Vj= Cij. Ця вимога призводить до системи (m+n-1) лінійних рівнянь (по числу базисних змінних) із (m+n) невідомими. Значення потенціалів можна визначити з цієї системи, приписавши одному з них довільне значення (як правило, змінна U1 покладається рівною 0) і потім розв’язуючи систему (m+n-1) рівнянь відносно (m+n-1) решти потенціалів. У результаті розв’язання системи рівнянь знаходять значення інших потенціалів. Далі для кожної небазисної змінної xpq обчислюють її двоїсту оцінку , що характеризує величину зменшення значення цільової функції в результаті збільшення xpq на одиницю. Такі оцінки розраховуються за формулою:

 =Up+Vq-Cpq.

При цьому величини  не залежать від вибору змінної, якій приписано довільне значення й від самого цього значення. Далі для включення до базису обирається небазисна змінна xpq, що має найбільшу позитивну оцінку  (порівняйте з умовою оптимальності при розв’язанні задачі на мінімум за допомогою сиплексного методу).

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

Розв’язання цієї системи при U1=0 приводить до таких значень решти потенціалів: V1=3, V2=2, U2=6, V3=1, U3=1, V4=-1.

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

 ,  ,  ,

 ,

 .

Оскільки змінна x31 вона має максимальну додатню оцінку ( =15), вона обирається для включення до базису.

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