мане таким чином нове базисне рішення буде краще вихідного - витрати на його реалізацію будуть меншими. Для нового рішення також перевіряють здійснимість критерію оптимальності і в разі необхідності знову скоюють перерахунок по циклу для однієї з клітин з негативною алгебраїчною сумою тарифів і т. д.
Через кінцеве число кроків приходять до шуканого оптимального базисного рішенням.
У разі якщо алгебраїчні суми тарифів для всіх вільних клітин позитивні, ми маємо єдине оптимальне рішення; якщо ж алгебраїчні суми тарифів для всіх вільних клітин ненегативні, але серед них є алгебраїчні суми тарифів, рівні нулю, то оптимальне рішення не єдине: при перерахунку по циклу для клітини з нульовою алгебраїчною сумою тарифів ми отримаємо оптимальне ж рішення, але відмінне від вихідного (Витрати за обома планам будуть однаковими). ​​p> Залежно від методів підрахунку алгебраїчних сум тарифів для вільних клітин розрізняють два методи відшукання оптимального рішення транспортної задачі:
1. Розподільчий метод. При цьому методі для кожної порожній клітини будують цикл і для кожного циклу безпосередньо обчислюють алгебраїчну суму тарифів.
2. Метод потенціалів. При цьому методі попередньо знаходять потенціали баз і споживачів, а потім обчислюють для кожної порожній клітини алгебраїчну суму тарифів за допомогою потенціалів.
Переваги методу потенціалів в порівнянні з розподільчим методом полягають у тому, що відпадає необхідність побудови циклів для кожної з порожніх клітин і спрощується обчислення алгебраїчних сум тарифів. Цикл будується тільки один - той, за яким здійснюється перерахунок. p> Застосовуючи метод потенціалів, можна говорити не про знак алгебраїчних сум тарифів, а про порівняння непрямих тарифів з істинними. Вимога неотрицательности алгебраїчних сум тарифів замінюється умовою, що непрямі тарифи не перевершують істинних.
Слід мати на увазі, що потенціали (так само як і цикли) для кожного нового базисного плану визначаються заново.
Вище розглядалася закрита модель транспортної завдання, з правильним балансом, коли виконується умова (1.3). У разі виконання (1.4) (відкрита модель) баланс транспортної задачі може порушуватися в 2-ух напрямках:
1. Сума запасів у пунктах відправлення перевищує суму поданих заявок (транспортна задача з надлишком запасів):
ГҐ а i > ГҐ b j (де i = 1, ..., m; j = 1, ..., n);
2. Сума поданих заявок перевищує наявні запаси (транспортна задача з надлишком заявок):
ГҐ а i <ГҐ b j (Де i = 1, ..., m; j = 1, ..., n);
Розглянемо послідовно ці два випадки:
Транспортна задача з надлишком запасів.
Зведемо її до раніше розглянутої транспортної завданню з правильним балансом. Для цього, понад наявні n пунктів призначення В 1 , B 2 , ... , B n , введемо ще один, фіктивний, пункт пр...
