1. Метод потенциалов для решения транспортной задачи линейного программирования.

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

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

,  , ,                             (1)

,  .                                         (2)

и называются потенциалами соответствующих пунктов отправления  и пунктов назначения. Условия (1)-(2) называются условиями потенциальности.

План будем называть потенциальным, если для него существует система и , удовлетворяющая (1)-(2). Тогда теорема коротко формулируется следующим образом.

Теорема. Для оптимальности плана транспортной задачи необходимо и достаточно, чтобы он был потенциален.

Доказательство:

Достаточность. Пусть план потенциален, так что существует система и , удовлетворяющая (1)–(2). Тогда для любого допустимого плана

для потенциального плана

,

т.е. стоимость перевозок по любому плану не меньше стоимости перевозок по потенциальному плану . Следовательно, план оптимален.

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

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

	0= –	…	0= –	…	0= –	0= –	…	0= –	…	0= –	1
x11  y11 =	-1	…	0	…	0	1	…	0	…	0	c11
…	…	…	…	…	…	…	…	…	…	…	…
x1n  y1n =	-1	…	0	…	0	0	…	0	…	1	c1n
…	…	…	…	…	…	…	…	…	…	…	…
xi1  yi1 =	0	…	-1	…	0	1	…	0	…	0	ci1
…	…	…	…	…	…	…	…	…	…	…	…
xij  yij =	0	…	-1	…	0	0	…	1	…	0	cij
…	…	…	…	…	…	…	…	…	…	…	…
xin  yin =	0	…	-1	…	0	0	…	0	…	1	cin
…	…	…	…	…	…	…	…	…	…	…	…
xm1  ym1 =	0	…	0	…	-1	1	…	0	…	0	Cm1
…	…	…	…	…	…	…	…	…	…	…	…
xmn  ymn =	0	…	0	…	-1	0	…	0	…	1	Cmn
1   w=	a1	…	ai	…	an	b1	…	bj	…	bn	0

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

Получаем, что двойственная задача имеет вид:

при ограничениях

,   , ,

т.е. ,   , .

     Пусть – оптимальное решение транспортной задачи. Тогда на основании первой теоремы двойственности двойственная задача имеет оптимальное решение

.

Убедимся, что эти числа являются потенциалами соответствующих пунктов транспортной задачи. Действительно, все как опорное решение двойственной задачи удовлетворяют неравенствам (1).

     Если , то по второй теореме двойственности соответствующее ограничение двойственной задачи

обращается в строгое равенство

.

Теорема доказана.

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

Алгоритм метода потенциалов состоит из предварительного этапа и повторяющегося основного этапа.

Предварительный этап.

1. Каким-либо способом ищется допустимый план (методом северо-западного угла или минимального элемента).

2. Для полученного плана строится система m+n чисел , , таких, что ,  .

3. Построенная система и исследуется на потенциальность, то есть, план исследуется на оптимальность. Для этого проверяется , .

    Если система не потенциальна, то переходят к основному этапу (т.к. план не оптимален), иначе оптимальный план найден.

Основной этап.

1. Улучшаем план, то есть от плана переходим к плану такому, что .

2. Для плана строим новую систему , , , такую, что ,  .

3. Исследуем систему на потенциальность. Если система не потенциальна, то переходим на п.1. Иначе найден оптимальный план.

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

Определение 5. Если допустимый опорный план содержит менее элементов , то он называется вырожденным, а транспортная задача называется вырожденной транспортной задачей.

Следующая теорема позволяет определить вырожденность задачи до ее решения.

Теорема. Для невырожденной транспортной задачи необходимо и достаточно отсутствие такой неполной группы пунктов производства, суммарный объем производства которой точно совпадает с суммарными потребнос­тями некоторой группы пунктов потребления.

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

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

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

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