ТЕМА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), вона обирається для включення до базису.
Як і в симплексному методі, після вибору змінної, яка підлягає включенню до базису, з числа поточних базисних змінних має бути обрана змінна для виключення з базису. Для того, щоб новий розв’язок задачі був допустимим, необхідно застосувати спеціальне правило, що дозволить вибрати змінну для виключення з базису та побудови допустимого базисного розв’язку. Це правило визначається так званим розподільчим методом.
25 26 27 28 29 30 Наверх ↑