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

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

 

Рассмотрим, в какие клетки можно разместить нулевую поставку. Для неизвестного потенциала 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		1	2	3	4	ui
		15	16	15	20
1	14	6 14	10 -	7 -	5 -	0
2	11	10 -	7 11	6 -	9 -
3	20	13 -	14 5	5 15	7 -
4	21	5 1	10 -	6	4 20	-1
vj		6		7	5

 

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

 

bj ai		1	2	3	4	ui
		15	16	15	20
1	14	6 14	10 -	7 -	5 -	0
2	11	10 -	7 11	6 -	9 -
3	20	13 -	14 5	5 15	7 -	–2
4	21	5 1	10 -	6	4 20	-1
vj		6		7	5

 

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

 

bj ai		1	2	3	4	ui
		15	16	15	20
1	14	6 14	10 -	7 -	5 -	0
2	11	10 -	7 11	6 -	9 -
3	20	13 -	14 5	5 15	7 -	–2
4	21	5 1	10 -	6	4 20	-1
vj		6	16	7	5

 

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

 

bj ai		1	2	3	4	ui
		15	16	15	20
1	14	6 14	10 -	7 -	5 -	0
2	11	10 -	7 11	6 -	9	–9
3	20	13	14 5	5 15	7 -	–2
4	21	5 1	10 -	6	4 20	-1
vj		6	16	7	5

 

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

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		1	2	3	4	ui
		15	16	15	20
1	14	6 14	10 (6)	7 (0)	5 (0)	0
2	11	10 (–13)	7 11	6 (–8)	9 (–13)	–9
3	20	13 (–9)	14 5	5 15	7 (–4)	–2
4	21	5 1	10 (5)	6	4 20	-1
vj		6	16	7	5

 

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

 

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

Поделиться: