Второе приближение

Выберем ячейку (3,1). В ней сумма потециалов намного превышает цену 5>1

Наша задача - максимально "загрузить" эту ячейку, используя три другие,

занятые ячейки так, чтобы не нарушился общий баланс.

Используем занятые ячейки (2,1), (2,2) и (3,2). Вместе с ячейкой (3,1) они образуют "цикл". Товар внутри цикла нужно перемещать не нарушая баланс.

40	90

В данном случае основным ограничителем являетя баланс первой строки.

Мы не можем переместить в пустую ячейку больше 40 единиц товара.

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

сохранения баланса первой строки придется писать -5. А мы работаем

только с положительными значениями количества товара.

Перемещаем 40 единиц товара из ячейки (2,1) в ячейку (3,1).

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

	90
40

Подставим эти значения в таблицу

	120	90	150	70
80	2 80 2	6 -3	2 1	0 0	= 0
170	6 6	1 90 1	5 40 5	0 0	= 4
180	1 40 5	4 0	4 110 4	0 70 0	= 3
	= 2	= -3	=1	= -3

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

F=80*2+0*6+40*5+90*1+40*5+110*4 = 1090

Это стоимость всех перевозок при использовании плана второго

приближения.

Этот план перевозок на 40 дешевле, чем план

перевозок первого приближения.

Но является ли он оптимальным? Снова применяем метод потенциалов.

Аналогично первому приближения найдём потенциалы.

u₁ + v₁ = 2; 0 + v₁ = 2; v₁ = 2

u₃ + v₁ = 1; 2 + u₃ = 1; u₃ = -1

u₃ + v₃ = 4; -1 + v₃ = 4; v₃ = 5

u₂ + v₃ = 5; 5 + u₂ = 5; u₂ = 0

u₂ + v₂ = 1; 0 + v₂ = 1; v₂ = 1

u₃ + v₄ = 0; -1 + v₄ = 0; v₄ = 1

	120	90	150	70
80	2 80 2	6 1	2 5	0 0	= 0
170	6 2	1 90 1	5 40 5	0 0	= 0
180	1 40 1	4 0	4 110 4	0 70 0	= -1
	= 2	= 1	=5	= 1

Выберем ячейку (1,3). В ней сумма потециалов намного превышает цену 5>2

Наша задача - максимально "загрузить" эту ячейку, используя три другие,

занятые ячейки так, чтобы не нарушился общий баланс.

Используем занятые ячейки (2,2), (2,3) и (1,2). Вместе с ячейкой (1,3) они образуют "цикл". Товар внутри цикла нужно перемещать не нарушая баланс.

40	90

Проверим оптимальность сформированного плана перевозок. Найдем предварительные потенциалы u_i, v_j. по занятым клеткам таблицы, в которых u_i + v_j = c_ij, полагая, что u₁ = 0.

u₁ + v₁ = 2; 0 + v₁ = 2; v₁ = 2

u₂ + v₁ = 6; 2 + u₂ = 6; u₂ = 4

u₂ + v₂ = 1; 4 + v₂ = 1; v₂ = -3

u₂ + v₃ = 5; 4 + v₃ = 5; v₃ = 1

u₃ + v₃ = 4; 1 + u₃ = 4; u₃ = 3

u₃ + v₄ = 0; 3 + v₄ = 0; v₄ = -3

	v1=2	v2=-3	v3=1	v4=-3
u1=0	2 80	6	2	0
u2=4	6 40	1 90	5 40	0
u3=3	1	4	4 110	0 70

Сформированный план перевозок не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_j > c_ij

(2;4): 4 + -3 > 0; ∆₂₄ = 4 + -3 - 0 = 1

(3;1): 3 + 2 > 1; ∆₃₁ = 3 + 2 - 1 = 4

max(1,4) = 4

Выбираем максимальную оценку свободной клетки (3;1): 1

Для этого в перспективную клетку (3;1) поставим знак «+», а в остальных«-», «+», «-».

	1	2	3	4	Запасы
1	2 80	6	2	0	80
2	6 40 -	1 90	5 40 +	0	170
3	1 +	4	4 110 -	0 70	180
Потребности	120	90	150	70

Цикл приведен в таблице (3,1 → 3,3 → 2,3 → 2,1).

Из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 1) = 40. Прибавляем 40 к объемам грузов, стоящих в плюсовых клетках и вычитаем 40 из Х_ij, стоящих в минусовых клетках. В результате получаем новую таблицу.