Методика преодоления вырожденности решения

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

Рассмотрим, в какие клетки можно разместить нулевую поставку. Для неизвестного потенциала u₂ нулевую поставку можно разместить в клетках (2, 1) и (2, 4), для которых известны потенциалы v₁ = 6 и v₄ =5 соответственно. Для неизвестного потенциала u₃ нулевую поставку можно разместить в клетках (3, 1) и (3, 4), для которых известны те же потенциалы v₁ = 6 и v₄ =5 соответственно. Для неизвестного потенциала v₂ нулевую поставку можно разместить в клетках (1, 2) и (4, 2), для которых известны потенциалы u ₁ = 0 и u ₄ = -1 соответственно. Для неизвестного потенциала v₃ нулевую поставку можно разместить в клетках (1, 3) и (4, 3), для которых известны те же потенциалы u₁ = 0 и u₄ = -1 соответственно.

Среди клеток (2, 1), (2, 4), (3, 1), (3, 4), (1, 2), (4, 2), (1, 3) и (4, 3), в которых может быть размещена нулевая поставка, наименьший тариф имеет клетка (4, 3) с c₄₃ = 6. Следовательно, нулевую поставку размещаем в клетку (4, 3), и она становится условно занятой и для нее выполняется условие u₄ + v₃ = c₄₃, откуда v₃ = c₄₃ – u₄ = 6 – (-1) = 7:

bj ai					ui
			-	-	-
		-		-	-
		-			-
			-			-1
vj

Для клетки (3, 3): u₃ + v₃ = c₃₃, откуда u₃ = c₃₃ – v₃ = 5 – 7 = –2:

bj ai					ui
			-	-	-
		-		-	-
		-			-	–2
			-			-1
vj

Для клетки (3, 2): u₃ + v₂ = c₃₂, откуда v₂ = c₃₂ – u₃ = 14 – (–2) = 16:

bj ai					ui
			-	-	-
		-		-	-
		-			-	–2
			-			-1
vj

Для клетки (2, 2): u₂ + v₂ = c₂₂,, откуда u₂ = c₂₂ – v₂ = 7 – 16 = –9. Таким образом, найдены все значения потенциалов:

bj ai					ui
			-	-	-
		-		-		–9
					-	–2
			-			-1
vj

Вычисляем оценки свободных клеток:

D ₁₂ = u₁ + v₂ - c₁₂ = 0 + 16 – 10 = 6 > 0,

D ₁₃ = u₁ + v₃ - c₁₃ = 0 + 7 – 7 = 0,

D ₁₄ = u₁ + v₄ - c₁₄ = 0 + 5 – 5 = 0,

D ₂₁ = u₂ + v₁ - c₂₁ = – 9 + 6 – 10 = –13 < 0,

D ₂₃ = u₂ + v₃ - c₂₃ = – 9 + 7 – 6 = –8 < 0,

D ₂₄ = u₂ + v₄ - c₂₄ = – 9 + 5 – 9 = –13 < 0,

D ₃₁ = u₃ + v₁ - c₃₁ = – 2 + 6 – 13 = –9 < 0,

D ₃₄ = u₃ + v₄ - c₃₄ = – 2 + 5 – 7 = –4 < 0,

D ₄₂ = u₄ + v₂ - c₄₂ = – 1 + 16 – 10 = 5 > 0.

В распределительной таблице оценки клеток проставлены в нижнем левом углу в скобках:

bj ai					ui
			(6)	(0)	(0)
		(–13)		(–8)	(–13)	–9
		(–9)			(–4)	–2
			(5)			-1
vj

 

Получили две положительные оценки свободных клеток: D ₁₂ = 6 > 0 D ₄₂ = 5 > 0. Следовательно, исходное опорное решение не является оптимальным и его можно улучшить.