Рассчитываются характеристические разности

Й этап

Алгоритм итерационный. На каждой итерации выполняются следующие действия:

1. Рассчитываются потенциалы каждого склада и потребителя как предельные доходы на единицу товара: u_i – потенциал i-го склада, v_j – потенциал j-го потребителя.

Для элементов опорного плана

u_i + v_j = C_ij. Получается система из m + n -1 уравнений относительно m + n неизвестных. Полагаем u₁ = С₁₁ и тогда v₁ = 0 и система решается однозначно.

Пример 2

Пусть

Матрица стоимостей транспортировки С_ij Табл.7

i j

Потенциалы Табл. 8

ui vj

Потенциалы Табл. 9

ui vj

Потенциалы Табл. 10

ui vj			-3

2. Рассчитываются двойственные оценки Z_ij для всех элементов i и j:

Z_ij = u_i + v_j.

Рассчитываются характеристические разности

Z_ij – С_ij.

Если все они не положительны (т.е. Z_ij – С_ij ≤ 0), то план – оптимальный и расчеты заканчиваем. В противном случае переход к п.3.

3. Преобразование плана.

Элементу с наибольшей Z_ij – С_ij присваивается неизвестное значение Q.

Среди элементов опорного плана строится цепочка наименьшей длины, состоящая из элементов x_ij + Q или x_ij – Q так, чтобы имел место баланс между потребностями и возможностями: добавление (вычитание) Q в строке в каком-то столбце должно быть компенсировано вычитанием (добавлением) Q в каком-то другом столбце, а вычитание (добавление) Q в строке в каком-то столбце должно быть компенсировано добавлением (вычитанием) Q в данном столбце в другой строке. В результате образуются разности x_ij – Q. Находим среди них такую, что x_ij – Q = 0, а остальные были бы неотрицательными. Соответствующее значение Q является максимально возможным. Приняв значение x_ij = Q для элемента с наибольшей характеристической разностью, получим новый опорный план, у которого по сравнению с предыдущим одни элементы будут уменьшены на Q, некоторые будут увеличены на Q, один или несколько равны 0 (те, для которых x_ij – Q = 0), остальные останутся неизменными.

Если нулевыми станут более чем одна переменная предыдущего опорного плана, то сохраняем в новом плане ту (или те) компоненту (-ты), у которой (ых) C_ij меньше.

Далее переход к очередной итерации, т.е. к п. 1 данного алгоритма.

Пример 2, продолжение.

Для опорного плана табл. 6 выполним п.3 алгоритма.

Табл.11

i j
	4 - Q	Q
	4 + Q	2 - Q

Q = arg min [4-Q,2-Q] = 2

Строим новый опорный план, табл. 12

Табл.12

i j

1-я итерация 2-го этапа.

п.1. Расчет потенциалов

Потенциалы Табл. 13

ui vj		-1	-6
u1 = C11 = 3	3 – 3 = 0	2 – 3 = -1
	4 – 0 = 4
		10 – (-1) = 11	5 – 11 = -6

п.2. Расчет характеристических разностей, табл. 14

Характеристические разности u_i + v_j – С_ij Табл. 14

ui vj		-1	-6
			3-6-1=-4
		4-1-6=-3	4-6-8=-10
	11+0-10=+1

Характеристическая разность Z₃₁ – C₃₁ больше 0 и следовательно данный опорный план не оптимален

п.4. Построение нового опорного плана, табл. 15.

Табл.15

i j

2-я итерация 2-го этапа.

п.1. Расчет потенциалов

Потенциалы Табл. 16

ui vj		-1	-5

п.2. Расчет характеристических разностей.

Характеристические разности u_i + v_j – С_ij Табл. 17

ui vj		-1	-5
			-3
		-3	-9
		-1

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

Оптимальное значение линейной формы (1) задачи равно 92. Значение линейной формы (1) для начального плана задачи равно 100, для плана 1-й итерации равно 94.