Розділ 2. Метод потенціалів розв'язання транспортної задачі

2.1 Рішення транспортної задачі методом потенціалів

Цей метод дозволяє автоматично виділяти цикли з негативною ціною і визначати їх ціни. Нехай є транспортна задача з балансовими умовами:

Вартість перевезення одиниці вантажу з ; таблиця вартостей задана. Потрібно знайти план перевезень , який задовольняв балансовим умов, і при цьому вартість всіх перевезень була мінімальна.

Ідея методу потенціалів для розв՚язання транспортної задачі зводитися до наступного. Уявімо собі що кожен з пунктів відправлення вносить за перевезення одиниці вантажу (все одно куди) якусь суму ; в свою чергу кожен з пунктів призначення також вносить за перевезення вантажу (куди завгодно) суму . Ці платежі передаються деякого третій особі (перевізнику). Позначимо (i = 1,...,m; j = 1,...,n) і будемо називати величину псевдовартість перевезення одиниці вантажу з . Зауважимо, що платежі  не обов'язково повинні бути позитивними; не виключено, що перевізник "сам платить того чи іншого пункту якусь премію за перевезення.

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