Согласно  методу улучшения плана после разложения вводимого вектора (вектора ) по векторам старого базиса разыскивается величина

                                                        

.                                              (3.2)

Здесь - коэффициент при i-м векторе базиса в разложении вектора ограничений (вводимого вектора) по векторам старого базиса; минимум берется по тем индексам i, для которых . Если , то из базиса удаляется его r-й вектор.

    Базисные  компоненты нового плана определяются по формуле

                                               

                                       (3.3)

Для транспортной задачи коэффициенты равны нулю или . При этом в том и только в том случае, если i-й вектор базиса соответствует коммуникации, которая занимает нечетную (четную) позицию в построенном маршруте. Поэтому формула (3.2) в случае транспортной задачи может быть заменена правилом: - минимальная нечетная перевозка маршрута, связывающего пункты и . Это правило и используется в методе потенциалов. Формула (3.3) применительно к транспортной задаче превращается в правило изменения плана перевозок, употребляемое в методе потенциалов: перевозки, запланированные по нечетным (четным) коммуникациям, уменьшаются (увеличиваются) на величину , перевозка между и полагается равной , остальные перевозки сохраняют свои значения.

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

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

 

      Алгоритм  метода потенциалов складывается из предварительного этапа и конечного числа однотипных итераций. На предварительном этапе строится исходный опорный план задачи T и составляется матрица

      

,

где и - предварительные потенциалы, отвечающие исходному плану .

    На  каждой итерации рассматриваются и  преобразуются две матрицы

    

и .

Матрица представляет собой опорный план задачи T, построенный в результате k-й итерации. Матрица составлена из оценок векторов относительно базиса плана , т.е.

где и - предварительные потенциалы, отвечающие плану .

    Вначале будем предполагать задачу T невырожденной. Необходимые замечания относительно вырожденного случая будут сделаны ниже.

    Предварительный этап. С помощью метода северо-западного угла или метода минимального элемента определяется исходный опорный план исследуемой задачи T. Далее, согласно правилам, изложенным при описании 1-го этапа метода потенциалов, вычисляем величины , , , и составляем матрицу

    

.

    Если  все элементы неотрицательны, то - решение задачи T. В противном случае переходим ко второму этапу, описание которго приводится ниже. Процесс вычисления предварительных потенциалов формализуется следующим образом. Пусть - номера тех столбцов матрицы С, которые содержат -существенные элементы в 1-й строке; - номера строк матрицы С, которые содержат -существенные элементы в столбцах с номерами . Если множества и для уже определены, то объединяет номера тех столбцов матрицы С, не принадлежащих , которые содержат -существенные элементы в строках с номерами , а состоит из номеров строк этой матрицы, не включенных в и содержащих -существенные элементы в столбцах с номерами . Образование множеств и производится до тех пор, пока процесс не прерывается получением пустого множества. Если , то под будем понимать такой элемент множества , что - -существенный элемент С. Аналогично, для определим как элемент , при котором является -существенным элементом С. Из опорности плана следует, что множества , равно как и множества , не пересекаются. Невырожденность плана приводит к тому, что объединение всех множеств есть , а объединение всех множеств составляет .

    Полагаем  и вычисляем

    

 для  .

Далее определяем

    

 для  .

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

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

    

.

Целью - й итерации является формирование матрицы и либо установление оптимальности плана , либо построение нового, более экономичного плана . Рассмотрим каждый из этапов - й итерации.

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

    

.

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

    После l – 1 шагов все ненулевые - существенные элементы оказываются принадлежащими . Пусть l – нечетное (четное) число. Поскольку - пустое множество, все - существенные элементы матрицы, полученной после вычитания (прибавления) величины из строк (к столбцам) элементов , равны нулю. Итак, величины , удовлетворяют системе (1.3), соответствующей плану .

    Следовательно, - предварительные потенциалы, соответствующие плану , а

    

.

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

.

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

    Если  все элементы матрицы  неотрицательны, - искомое решение. Если же среди величин имеются отрицательные, необходим переход к этапу 2.

    Этап 2. На этапе 2 производится улучшение плана . Основой этапа является процесс составления цепочки из положительных элементов этого плана. Выберем наименьший элемент матрицы , расположенный, скажем, на пересечении - й строки и - го столбца, и обозначим его через . По условию . Переходим к поиску цепочки из положительных элементов матрицы , замыкающейся на элементе (очевидно, =0). Соединим стрелками со всеми положительными элементами его строки, совокупность которых обозначим через . Затем каждый из элементов соединим стрелками со всеми положительными элементами, расположенными в его столбце. Совокупность всех таких элементов обозначим через . Процесс образования множеств продолжается до тех пор, пока при некотором p (p – нечетное число) среди столбцов, содержащих элементы , обнаружится столбец с номером . Заметим, что в силу опорности плана множества , не пересекаются, ибо в противном случае существовала бы замкнутая цепочка из ненулевых перевозок плана . Это обстоятельство, а также то, что любые два пункта невырожденной задачи T могут быть соединены коммуникациями с ненулевыми перевозками, служит доказательством существования введенного выше числа . Теперь уже нетрудно образовать искомую цепочку. От элемента перейдем по столбцу к элементу . От по строке перейдем к соединенному с ним стрелкой элементу и т.д. Двигаясь таким образом вдоль намеченных стрелок по строкам и столбцам матрицы , получим в конце концов последовательность положительных элементов этой матрицы вида

                                      

,                           (4.1)

образующую  цепочку, которая замыкается на элементе .

    Построение цепочки (4.1) можно осуществить также с помощью метода вычеркивания строк. Для этого вводится множество Г, состоящее из положительных элементов матрицы и ее элемента .

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

    Элементы матрицы , оставшиеся после процесса вычеркивания, составляют искомую цепочку. Построив цепочку (4.1), легко сформировать новый план .

    Обозначим совокупность пар индексов , через , а множество пар индексов вида , через . Положим

                                                     

.                                        (4.2)

Новый план определяется согласно правилу

                                        

                                 (4.3)

Другими словами, из нечетных элементов цепочки  (4.1) вычитается , к четным элементам цепочки и к элементу величина прибавляется, остальные элементы плана сохраняют свои прежние значения.

    Итак, в результате - й итерации мы перешли от плана и матрицы оценок

    

к улучшенному  плану  и к новой матрице

.

    Из  способа построения плана  следует, что среди - существенных элементов лишь один не равен нулю.

Блок-схема  алгоритма метода потенциалов.