ТЕМА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, що має найбільшу позитивну оцінку  (порівняйте з умовою оптимальності при розв’язанні задачі на мінімум за допомогою сиплексного методу). 

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

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

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

 ,  ,  ,

 ,

 . 

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

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