Неединственность решения ТЗ

Неединственное решение получается, если цена какой-нибудь свободной клетки равна нулю. В этом случае для клетки с нулевой ценой необходимо пересчитать цикл и найти другое решение, при котором стоимость плана будет та же самая, т.е. найти другое оптимальное решение.

Может оказаться так, что клеток с нулевой ценой несколько, тогда имеем несколько оптимальных планов с одинаковой стоимостью перевозок.

Для полного ответа ТЗ, необходимо выписать все возможные матрицы оптимальных планов.

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

bj ai						Ui
			9 4	6 3	5 2
	5 10	6 8			8 2
	9 11	7 9		4 4
		10 12		8 7	8 6
Vj

Z₀=712 д.е.

m+n-1=8

k=min {13, 18} =13

k* ₁₃=13*(-5)=-65

Z₁^ож=712-65=647 д.е.

Bj ai						Ui
			9 9	6 8	5 7
		6 3			8 2	-5
	9 6	7 4		4 4		-4
	14 9	10 7		8 7	8 6	-1
Vj

Z₁=647 д.е.

k=min {4, 14} =4

k* ₁₄=4*(-2)=-8

Z₂^ож=647-8=639 д.е.

bj ai						Ui
	10 8		9 7		5 5
		6 5			8 2	-3
	9 6	7 6		4 4		-2
	14 9	10 9		8 7	8 6
Vj

Z₂=639 д.е.

Ответ: Х₁^*=

План оптимальный, т.к. не , то неединственный. Существует еще два оптимальных плана.

k=min {24, 5, 4} =4

k* ₁₅=4*(0)=0

Z₃^ож=639-0=639 д.е.

bj ai						Ui
	10 8		9 7	6 6
		6 5			8 2	-3
	9 6	7 6		4 4		-2
	14 9	10 9		8 7	8 6
Vj

Z₃=647 д.е.

2 решение: Х₂^*=

k=min {20, 14} =14

k* ₃₄=14*(0)=0

Z₄^ож=639-0=639 д.е.

Bj ai						Ui
	10 8		9 7	6 6
		6 5		3 3	8 2	-3
	9 6	7 6				-2
	14 9	10 9		8 7	8 6
Vj

Z₄=639 д.е.

3 решение: Х₃^*=

Раздел 4. Графовые модели. Алгоритмы на графах