.

Учитывая  далее отрицательность уклонения  и положительность , имеем

    

    

.

Итак, составленный новый план перевозок  , соответствующий меньшему значению линейной формы транспортной задачи. Этап 2, а вместе с ним и -я итерация закончены.

    Покажем, что вновь составленный план обладает свойством опорности. Действительно, если это не так, то из основных коммуникаций можно составить замкнутый маршрут . Очевидно маршрут должен содержать коммуникацию (В противном случае план оказался бы не опорным). Коммуникации замкнутого маршрута , за исключением , являются основными коммуникациями плана . Поскольку из таких коммуникаций можно составить единственный маршрут, соединяющий пункты , (план - опорный!), приходим к выводу, что состоит из и маршрута, построенного в процессе улучшения плана . Но в силу определения числа одна из перевозок

                                ,  ,                    (1.4)

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

    Заметим, что в силу предположения о  невырожденности только одна перевозка последовательности (1.4) равна нулю. Система основных коммуникаций плана путем замены одной коммуникации.

    Итак, в невырожденном случае метод  потенциалов позволяет, отправляясь  от некоторого исходного опорного плана, построить последовательность опорных  планов задачи Т, которым отвечают монотонно убывающие значения транспортных расходов. Поскольку число таких планов заведомо конечно, то через несколько итераций продолжение последовательности окажется невозможным из-за того, что на первом этапе очередной итерации выявится оптимальность соответствующего плана. Конечность метода потенциалов для невырожденного случая доказана. 
 
 
 
 
 
 
 
 
 

2. Вырожденность.

    До  сих пор исследуемая задача T предполагалась невырожденной. В этом пункте мы освободимся от этого ограничительного допущения, распространив метод потенциалов на вырожденные транспортные задачи.

    Вырожденные опорные планы задачи Т содержат меньше чем n+ m – 1 положительных перевозок. Поэтому среди базисных перевозок вырожденного плана имеются нулевые перевозки. Это обстоятельство может в свою очередь привести к тому, что при переходе по методу потенциалов к следующему плану величина окажется равной нулю и, следовательно, суммарные транспортные издержки не уменьшатся. Таким образом, монотонное убывание транспортных расходов может быть нарушено и для вывода о конечности метода не будет достаточных оснований.

    При построении базиса нового плана нам, как и в случае общей задачи линейного программирования, необходимо знать ответ на два вопроса: какой  вектор необходимо ввести в старый базис, какой вектор (один!) необходимо из него вывести? При ответе на первый вопрос случай вырожденности не приводит ни к каким дополнительным трудностям. Что касается второго вопроса, то критерий, который использовался для ответа на него в невырожденном случае: нулевыми могут стать сразу несколько перевозок, отвечающих нечетным коммуникациям маршрута этапа 2.

    Можно было бы, конечно, выводить из старого  базиса произвольный вектор коммуникаций из числа удовлетворяющих указанному критерию. Однако при таком подходе  не исключен возврат через несколько  итераций к старому базису, т.е. появляется возможность зацикливания. Необходимо иметь дополнительное правило исключения векторов из старых базисов, которое во всех случая застраховало бы нас от возможности зацикливания. Выводом этого правила мы сейчас и займемся.

    Рассмотрим  произвольную транспортную задачу Т. Свяжем с ней семейство транспортных задач , объемы производства и потребления которых выражаются через соответствующие величины задачи Т по формулам

    

,

    

    Правило выбора перевозки, подлежащей исключению из числа базисных, основывается на двух утверждениях, формулировки которых приводятся ниже.

     Существует  такое число  , что при любом , удовлетворяющем условию

                                                            ,                                               (2.1)

    задача  обладает свойством невырожденности.

      Существует такое число , что при любых и , удовлетворяющих условиям

                                                          ,                                            (2.2)

справедливы следующие утверждения:

    а) если - опорный план задачи , то - опорный план задачи ;

    б) если - опорное решение задачи , то - оптимальный опорный план задачи .

    Здесь под  понимается матрица, составленная из нулей и коэффициентов разложения вектора

    

по базису плана  . Матрица строится аналогичным образом, исходя из вектора

    

.

Доказывать  эти утверждения мы не будем.

    Допустим  теперь, что нам необходимо найти  решение некоторой транспортной задачи T (быть может вырожденной!). Отмеченные свойства транспортных задач при достаточно малых (точнее при , удовлетворяющих условиям (2.1) и (2.2)) позволяют применить для этой цели алгоритм метода потенциалов. В самом деле, будем решать вместо задачи T вспомогательную задачу , предполагая достаточно малой величиной. Поясним последнее допущение. При решении задачи методом потенциалов необходимо сравнивать между собой величины перевозок. Пусть  ,   - любая пара перевозок задачи .

    Будем считать число удовлетворяющим условиям (2.1) и (2.2) и настолько малым, что неравенство оказывается эквивалентным соблюдению одного из следующих соотношений: либо , либо , но ; при достаточно малом - невырожденная задача (утверждение ). Поэтому метод потенциалов через конечное число итераций приведет к ее решению. Полагая в полученном оптимальном плане , приходим к искомому оптимальному плану задачи T (утверждение для ).

    В соответствии с утверждением любой план задачи при , удовлетворяющим условию (2.2), порождает семейство планов задач , где . Все эти планы могут быть единственным образом представлены в виде

    

, где 

не зависят  от . Это обстоятельство позволяет опускать при вычислении оптимального плана задачи величину и оперировать лишь с составляющими плана :

    

и .

    Введем  предварительно несколько определений. Пару матриц

    

,

назовем обобщенным планом задачи T, если при всех достаточно малых

    

является  планом задачи . Обобщенный план удобно записывать в виде одной матрицы

    

.

Элементы  матрицы  будем называть обобщенными перевозками.

    Между двумя обобщенными перевозками  введем соотношение «больше, меньше», полагая  , если либо , либо , но . Очевидно, что условие эквивалентно равенствам

    

, .

В частности, обобщенная перевозка  считается положительной, если либо , либо , однако .

    Пусть - два обобщенных плана задачи T. Будем говорить, что первый план соответствует меньшим транспортным издержкам по сравнению со вторым, если либо

    

,

либо

    

,

но

    

.

Обобщенным  решением задачи T считается такой план, который соответствует минимальным транспортным издержкам. Вычисление оптимального обобщенного плана задачи T, первая составляющая которого является искомым решением этой задачи, можно привести, пользуясь методом потенциалов, если все встречающиеся при этом понятия (такие, как план, положительная перевозка и т. д.) рассматривать в обобщенном смысле. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

3.Метод  потенциалов и  метод последовательного  улучшения плана

 

    Пусть - некоторый опорный план задачи T. Обозначим через совокупность векторов , отвечающих основным коммуникациям плана . Наши рассуждения будут вестись в предположении невырожденности задачи T. Поэтому состоит из m+n-1 векторов и является базисом опорного плана .

    На  первом этапе метода потенциалов  вычисляются предварительные потенциалы

    

удовлетворяющие системе уравнений

                                                  

для .                                 (3.1)

(Здесь  - множество пар индексов векторов, составляющих базис плана .)

    Переименуем векторы базиса и обозначим l-й вектор через

    

Учитывая, что все компоненты вектора  , кроме двух, равных единице, равны нулю, можно переписать систему (3.1) в эквивалентном виде

.

Здесь

;

- стоимость единичной перевозки  по коммуникации, соответствующей  вектору  .

    Таким образом, предварительные потенциалы составляют вектор оценок условий задачи относительно данного базиса ,который определяется во втором алгоритме метода улучшения плана. Если для любого вектора условий

    

,

То в  соответствии с критерием оптимальности метода улучшения плана данный план - решение задачи. Это же заключение следует из критерия оптимальности, используемого в методе потенциалов.

    Предположим, что при некоторых i,j

    

.

    Тогда в соответствии с методом последовательного улучшения плана выбирается такая пара индексов , на которой величина

    

(оценка  вектора условий  ) достигает минимума, и осуществляется переход к новому базису путем замены одного из векторов системы вектором . Та же операция осуществляется и в методе потенциалов (этап 2). Переход к новому базису связан с разложением вводимого вектора (вектора ) по векторам базиса , что эквивалентно решению системы линейных уравнений. Благодаря простой структуре векторов решение этой системы существенно облегчается по сравнению с общим случаем.