3). Нахождение оптимального плана транспортной задачи.

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

, если ; (для занятых клеток)

или

, если . (для свободных клеток)

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

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

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

Пусть , тогда получим:

, , ,

, , .

Проверяем опорный план на оптимальность по свободным клеткам, определяя, выполняется ли соотношение :

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

В данной задаче для клетки условие не выполняется, следовательно, построенный план перевозок не является оптимальным. Стоимость перевозок уменьшится, если перераспределить груз для потребителей так, чтобы некоторую его часть транспортировать из пункта A₁ в пункт B₄. В табл. 20 клетку помечаем знаком «+» и строим цикл перераспределения поставок.

Циклом в таблице условий транспортной задачи называется ломаная линия, начинающаяся и заканчивающаяся в свободной клетке максимальной неоптимальности «+», вершины которой расположены в занятых клетках, причем в каждой вершине встречаются только два звена, одно из них располагается по строке, другое – по столбцу.

Если ломаная линия, образующая цикл, пересекается, то точки пересечения не являются вершинами. В нашей задаче цикл имеет следующий вид (табл. 20):

Таблица 20

Поставщик	Потребитель								Запасы ai
	B1		B2		B3		B4
A1		7		8		1		2	170
					170
A2		4		5		9		8	150
	125						25
A3		9		2	+	3		6	180
			60		3 0		90
Потребности bj	125		60		200		115

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

1). Каждой из клеток, связанных циклом, приписываем определенный знак «+» или «», начиная со свободной клетки. Клетки, отмеченные знаком «+» назовем загружаемой клеткой, знак «»  разгружаемой.

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

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

Таблица 21

Поставщик	Потребитель								Запасы ai
	B1		B2		B3		B4
A1		7		8		1		2	170
					80		90
A2		4		5		9		8	150
	125						25
A3		9		2		3		6	180
			60		120
Потребности bj	125		60		200		115

.

Как видно, полученный план лучше предыдущего, так как на нем значение функции, описывающей расходы при перевозке грузов, меньше.

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

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

Для всех занятых клеток последней таблицы составляем уравнения вида :