Если ломаная линия, образующая цикл, пересекается, то точки самопересечения не являются вершинами

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

Для этого необходимо переместить грузы в пределах клеток, являющихся вершинами цикла по следующим правилам:

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

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

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

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

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

Итак, процесс нахождения решения транспортной задачи методом потенциалов включает следующие этапы:

1. Находят опорный план. При этом число заполненных клеток должно быть равно .

2. Находят потенциалы и соответственно пунктов назначения и отправления.

3. Для каждой свободной клетки определяют число . Если среди чисел нет положительных, то получен оптимальный план транспортной задачи; если же они имеются, то переходят к новому опорному плану.

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

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

Найдем оптимальный план методом потенциалов для задачи, рассмотренной в примере 3.1. Пусть для данной задачи построен опорный план (Табл. 3.3), например методом северо-западного угла. Для проверки оптимальности данного плана рассчитаем потенциалы складов и предприятий . Положим , поскольку, как уже было отмечено, в системе уравнений (3.8) , составляющейся для занятых клеток количество неизвестных и (всего 7) на одну больше, чем количество занятых клеток и, соответственно, чем количество уравнений.

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

Зная , с помощью уравнения для занятой клетки с тарифом найдем : или , откуда .

Таблица 3.3.

						Запасы
	Склады	Предприятия
A	B	C	D
0	I		8 _				+
	II			5 +	9 _
	III					3 +	6 _
-11	-3
	Потребности

С помощью найденного и уравнения для занятой клетки с тарифом найдем : или , откуда .

Из уравнения для найдем : или , откуда .

Из уравнения для последней занятой клетки с тарифом найдем : , или .

Стоимость перевозок для начального опорного плана:

.

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

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

Для построения цикла пометим загружаемую незанятую клетку знаком «+». Остальные вершины цикла должны находиться только в занятых клетках. Двигаясь вниз по столбцу находим в третьей строке занятую клетку с . Помечаем ее знаком «-». Слева от нее также находится занятая клетка, которую помечаем знаком «+» и т.д. Наименьшее число груза среди клеток, помеченных знаком «-», достигается для .

Таблица 3.4.

			-5	-1		Запасы
	Склады	Предприятия
A	B	C	D
0	I	7 _					2 +
-13	-2
-10	II		+		9 _
-4	III					3 +	6 _
	-3
	Потребности

Именно это количество необходимо передвинуть по циклу, то есть прибавить к объемам перевозок, стоящих в клетках со знаком «+» и вычесть из клеток со знаком «-». В результате этих перемещений получается следующий допустимый план (Табл. 3.4).

Стоимость перевозок:

.

Положив , рассчитаем последовательно потенциалы с помощью системы уравнений (3.8) для занятых клеток:

С помощью найденных потенциалов для проверки оптимальности найденного плана рассчитаем для свободных клеток:

Найденный план также не является оптимальным, так как содержит положительные . Выберем максимальное и построим цикл пересчета (Табл.3.4). Переместив по циклу минимальное количество груза среди клеток, помеченных знаком «-» (), получим следующий допустимый план (Табл. 3.5).

Таблица 3.5.

						Запасы
	Склады	Предприятия
A	B	C	D
	I	7 _				+
	II	4 +		9 _
-9
	III
-11	-3	-13
	Потребности

Стоимость перевозок:

.

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

Таблица 3.6.

						Запасы
	Склады	Предприятия
A	B	C	D
0	I	7 _			1 +
	II	4 +	5 _
-11	-9
-2	III				+	3 _
		-2
	Потребности

Стоимость перевозок:

.

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

Таблица 3.7.

		-1				Запасы
	Склады	Предприятия
A	B	C	D
	I
-8	-8
-5	II
-3	-1
-2	III
-8	-2
	Потребности

Стоимость перевозок при оптимальном плане составляет величину , что, как видим, примерно в 2,5 раза меньше стоимости перевозок, соответствующей начальному опорному плану, составленному методом северо-западного угла.