Третье приближение.. Четвертое приближение.

Третье приближение.

					Запасы
	2 10		2 70
		1 90	5 80
	1 110			0 70
Потребности

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

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

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

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

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

u₂ + v₃ = 5; 2 + u₂ = 5; u₂ = 3

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

	v₁=2	v₂=-2	v₃=2	v₄=1
u₁=0	2 10		2 70
u₂=3		1 90	5 80
u₃=-1	1 110			0 70

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

(1;4): 0 + 1 > 0; ∆₁₄ = 0 + 1 - 0 = 1

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

max(1,4) = 4

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

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

					Запасы
	2 10 -		2 70 +
		1 90	5 80 -	0 +
	1 110 +			0 70 -
Потребности

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

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

Четвертое приближение.

					Запасы
			2 80
		1 90	5 70	0 10
	1 120			0 60
Потребности

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

u₂ + v₃ = 5; 2 + u₂ = 5; u₂ = 3

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

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

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

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

	v₁=-2	v₂=-2	v₃=2	v₄=-3
u₁=0			2 80
u₂=3		1 90	5 70	0 10
u₃=3	1 120			0 60

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

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

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

					Запасы
			2 80
		1 90	5 70 -	0 10 +
	1 120		4 +	0 60 -
Потребности

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

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

⇐ Предыдущая 123 Следующая ⇒