ною ціною вже не залишиться. При поліпшенні плану циклічними переносами, як правило, користуються прийомом, запозиченим з симплекс-методу: при кожному кроці (циклі) замінюють одну вільну змінну на базисну, тобто заповнюють одну вільну клітину і натомість того звільняють одну з базисних клітин. При цьому загальне число базисних клітин залишається незмінним і рівним m + n - 1. Цей метод зручний тим, що для нього легше знаходити відповідні цикли. Можна довести, що для будь-якої вільної клітці транспортної таблиці завжди існує цикл і притому єдиний, одна з вершин якого лежить в цій вільній клітці, а всі інші в базисних клітинах. Якщо ціна такого циклу, з плюсом у вільній клітці, негативна, то план можна поліпшити переміщенням перевезень по даного циклу. Кількість одиниць вантажу k, яке можна перемістити, визначається мінімальним значенням перевезень, що стоять в негативних вершинах циклу (якщо перемістити більше число одиниць вантажу, виникнуть негативні перевезення). p align="justify"> Застосований вище метод відшукання оптимального рішення транспортної задачі називається розподіленим; він полягає у безпосередньому знаходженні вільних клітин з негативною ціною циклу й у переміщенні перевезень по цьому циклу.
Розподільчий метод вирішення транспортної задачі, з яким ми познайомилися, володіє одним недоліком: потрібно відшукувати цикли для всіх вільних клітин і знаходити їх ціни. Від цієї трудомісткої роботи нас позбавляє спеціальний метод вирішення транспортної задачі, який називається методом потенціалів. p align="justify"> транспортний опорний план перевезення
Глава II. Метод потенціалів розв'язання транспортної задачі
.1 Рішення транспортної задачі методом потенціалів
Цей метод дозволяє автоматично виділяти цикли з негативною ціною і визначати їх ціни. Нехай є транспортна задача з балансовими умовами
В В В
Вартість перевезення одиниці вантажу з A i в B j дорівнює C ij ; таблиця вартостей задана. Потрібно знайти план перевезень x ij , який задовольняв < span align = "justify"> б балансовим умов, і при цьому вартість всіх перевезень була мінімальна.
Ідея методу потенціалів для вирішення транспортної задачі зводитися до наступного. Уявімо собі що кожен з пунктів відправлення A i вносить за перевезення одиниці вантажу (все одно куди) якусь суму a i
