2.2. Знаходження оптимального розв’язку транспортної задачі методом потенціалів.

Після того як побудований початковий опорний план перевезень по одному з вищевикладених правил, послідовно проводиться його поліпшення до отримання оптимального плану. Це можна зробити, наприклад, за допомогою методу потенціалів.

Суть методу потенціалів складається в наступному. Після того як знайдений початковий план перевезень, кожному постачальнику А_i (кожному рядку) ставиться у відповідність деяке число u_i, (i= 1,…, m), а кожному споживачеві B_j (кожному стовпцю) - деяке число v_j, (j= 1,…, n). Числа u_i і v_j називаються потенціалами і вибираються так, щоб в будь-якій заповненій клітці їх сума дорівнювала тарифу цієї клітки, тобто u_i + v_j= c_ij. Оскільки всіх потенціалів m+n, а зайнятих кліток m+n-1, то для визначення чисел u_i і v_j доведеться вирішувати систему з m+n-1 рівняння з m+n невідомими. У цьому разі одній з невідомих можна надати довільне значення, і тоді система буде мати єдиний розв’язок, т е. всі інші m+n-1 невідомих визначаються однозначно. Потім для перевірки оптимальності плану переглядаються вільні клітки і для кожної з них обчислюється різниця _ij між сумою u_i+ v_j потенціалів рядка і стовпця і тарифом c_ij. План оптимальний, коли для кожної вільної клітки різниця _ij є величина непозитивна,

_ij= u_i+ v_j- c_ij 0.

Отримані різниці називаються оцінками (характеристиками) вільних кліток. Позитивні оцінки вказують на перспективність кліток, завантаження їх приведе до поліпшення плану. Перехід до нового опорного плану здійснюється за такими правилами: для найбільш перспективної клітки будується замкнений контур, вершинам якого приписуються знаки, що чергуються (вільній клітці приписується позитивний знак). У клітках відповідних негативним вершинам, відшукується найменший вантаж, який і “переміщається" по клітках замкненого циклу, тобто Додається до кліток зі знаком плюс, включаючи вільну, і віднімається з кліток зі знаком мінус.

У новому плані знову визначаються потенціали рядків і стовпців і обчислюються оцінки для всіх вільних кліток. Коли серед оцінок не виявиться позитивних, отриманий план буде оптимальним.

Отже, тепер опишемо кроки методу потенціалів.

Алгоритм методу:

1. Будуємо систему потенціалів:

u_i, i= 1,…, m для пунктів відправлення,

v_j, j= 1,…, n для пунктів споживання.

Для цього використовуємо умова

u_i + v_j= c_ij,

де c_ij - вартість перевезення одиниці вантажу зайнятої клітки.

2. Перевіряємо виконання умови оптимальності для незайнятих кліток:

_ij= u_i+ v_j- c_ij 0.

3. Вибираємо клітку, в яку необхідно послати перевезення: серед всіх позитивних чисел _ij вибираємо максимальне.

4. Будуємо цикл перерахунку і визначаємо величину перерозрахунку вантажу.

Властивості циклу перерахунку:

а) замкнуть (починається і закінчується з тієї клітки, куди посилається перевезення);

б) повинен спиратися тільки на базисні вершини;

в) вершини циклу помічаються знаками “+” та “-“: в клітинку в яку посилається перевозка ставлять “+”, далі знаки чередуються;

г) цикл завжди єдиний.