5. Алгоритм методу потенціалів

Транспортна задача – це задача вибору оптимального варіанта доставки товару від пунктів виробництва до пунктів споживання з урахуванням усіх реальних можливостей. Для визначення оптимальності побудованого плану часто використовують метод потенціалів. Він полягає у тому, що для перевірки на оптимальність припустимого плану перевіряється умова існування кращого плану порівняно з даним з використанням чисел, визначених спеціальним способом.

Алгоритм методу потенціалів складається з таких операцій:

1. Узяти будь-який опорний план перевезень, в якому відмічені m + n - 1 базисних змінних (решта клітин вільна).

2. Визначити для цього плану небазисні змінні (a_i і b_j ) виходячи з умови, щоб в будь-якій базисній клітинці були рівні вартостям. Одну з вільних змінних можна позначити довільно, наприклад, покласти рівним нулю.

3. Підрахувати c_ij = a_i + b_j для всіх вільних клітин. Якщо опиниться, що всі вони не перевищують вартостей, то план оптимальний.

4. Якщо хоч би в одній вільній клітинці псевдовартість перевищує вартість, слід приступити до поліпшення плану шляхом перекидання перевезень по циклу, відповідному будь-якій вільній клітинці з негативною ціною (для якої псевдовартість більше вартості).

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