Особые случаи при решении ТЗ

1. В некоторых случаях поставка перевозимая по циклу может оказаться равной 0. это возможно тогда, когда клетка цикла со знаком «-» содержит нулевую поставку (в случае вырожденности опорного плана). Тогда по циклу передается нулевая поставка, в результате чего свободная клетка (для которой был построен цикл) становится базисной, заполненной нулевой поставкой. А клетка с нулевой поставкой становится свободной. Общая стоимость перевозок не изменится.

2. Если при перевозке по циклу имеем нулевую поставку в нескольких заполненных клетках, то свободной следует считать, только одну из них (любую), а остальные в которых поставка стала нулевой следует считать базисными заполненными нулевыми поставками.

Рассмотрим этот случай на примере:

bj ai				Ui
			3 2
	3 1
	4 1	1 3
Vj

k=min {0, 10} =0

k* ₃₂=0*(-2)=0

Z₀^ож=130 д.е.

Получили первый особый случай, когда по циклу необходимо перевозить нулевую поставку, тогда стоимость не изменится, но клетка (3,2), для которой делается пересчет, станет базисной, а (2,2) – свободной.

bj ai				Ui
			3 4
	3 -1	3 1		-2
	4 -1			-2
Vj

Z₀=130 д.е.

k=min {10, 10} =10

k* ₁₃=10*(-1)=-10

Z₁^ож=130-10=120 д.е.

bj ai				Ui
		3 2
	3 0	3 1		-1
	4 0			-1
Vj

Z₁=120 д.е.

Клеток с отрицательной ценой нет, план оптимальный.

Ответ: Х^*=

Z^*=120 д.е.