Для зайнятих клітин повинні виконуватися рівності.
Тому беремо в таблиці клітку, зайняту в результаті зсуву, і виправляємо для неї потенціали так, щоб їх різниця дорівнювала тарифом. Краще змінювати один з них - той, який стоїть в рядку або стовпці з меншим числом зайнятих клітин.
Потім відчуваємо інші зайняті клітини і коригуємо послідовно інші потенціали. Зміні піддаються, як правило, не всі числа, і такий порядок скорочує розрахунки.
6. Виробляємо дослідження нової системи на потенційність, тобто дослідження знайденого плану на оптимальність. Для цього перевіряємо виконання нерівностей v j - u i ≤ a ij для всіх незайнятих клітин. Якщо для них нерівності виконуються, то система потенціальна і план оптимальний, тобто рішення закінчено. Якщо для якихось клітин нерівності не виконуються, обчислюємо різниці d ij і робимо знову спільний крок і т.д., до тих пір, поки не буде отриманий оптимальний план. Виродження в транспортній задачі проявляється в тому, що серед ( k + l -1) Х -відмічених клітин виявляється клітина з нульовою перевезенням. Якщо ця клітина не влучає у цикл, на неї не звертаємо уваги. Якщо вона потрапляє в позитивну полуцепь циклу, то на наступному кроці замість нуля отримаємо в цій клітці позитивне число. Якщо ж нульова клітина опиняється в негативною полуцепі, то Q = 0, тобто зсув треба робити на число нуль. Такий нульовий зсув плану не змінює, але нуль переходить в іншу клітку, змінюється набір Х-відмічених клітин і система потенціалів. Це дає можливість на черговому кроці здійснити вже не нульовий зсув і змінити план у бік його поліпшення. Контроль обчислень здійснюється таким чином. У процесі рішення задачі на кожному кроці отриманий план перевіряється на допустимість. Для цього компоненти плану підсумовуються по рядках і стовпчиках; суми повинні рівнятися відповідно запасам і потребам пунктів. Остаточний (оптимальний) план перевіряється за формулою, що випливає з докази основної теореми:
,
при цьому контролюються і потенціали. [5]
12. Транспортна задача з обмеженнями на пропускну здатність
Транспортна задача з обмеженими пропускними спосо6ностямі комунікацій вирішується з додатковим обмеженням:, де d ij - пропускна здатність ланки ( i , j ) в одиницю часу. Математична модель задачі така:
,
при обмеженнях
В
Це завдання можна залагодити при виконанні умов
.
Для транспортної задачі з обмеженими пропускними здатностями справедливі наступні умови оптимальності отриманого розв'язку:
В В
[8]
13. Транспортна задача за критерієм часу
Крім транспортної задачі за критерієм вартості існує завдання транспорт...
