Вырожденность в транспортных задачах

При решении транспортной задачи может оказаться, что число занятых клеток меньше, чем m + n – 1. В этом случае задача имеет вырожденное решение. Для возможного его исключения целесообразно поменять местами поставщиков и потребителей или ввести в свободную клетку с наименьшим тарифом нулевую поставку. Нуль помещают в такую клетку, чтобы в каждой строке и столбце было не менее одной занятой клетки. Такая клетка становится условно занятой, она должна иметь наименьший тариф по сравнению с другими клетками, которые могут быть условно занятыми.

Рассмотрим вырожденность транспортной задачи на примере.

Пример. Фирма осуществляет поставки бутылок на четыре завода, занимающихся производством прохладительных напитков. Она имеет три склада, причем на складе 1 находится 6000 бутылок, на складе 2 – 3000 бутылок и на складе 3 – 4000 бутылок. Первому заводу требуется 4000 бутылок, второму заводу – 5000 бутылок, третьему заводу – 1000 бутылок. Матрица стоимости перевозок одной бутылки от каждого склада к каждому заводу: .

Как следует организовать доставку бутылок на заводы, чтобы стоимость перевозки была минимальной?

Решение. Запишем исходные данные в распределительную таблицу, найдем исходное опорное решение по методу минимального тарифа.

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

Число заполненных клеток равно 5, m + n – 1 = 6, следовательно, задача является вырожденной.

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

Так, для нахождения потенциала u₃ поместим нулевую поставку в клетку (1, 3), после чего представляется возможным вычислить остальные потенциалы.

Оценки свободных клеток будут равны:

D₁₁ = – 3, D₁₃ = – 6, D₂₁ = – 3, D₂₄ = – 1, D₃₃ = – 4, D₃₄ = – 1.

Все оценки отрицательные, следовательно, получено оптимальное решение:

.

Стоимость транспортных расходов составит:

L(X)_min = 3000×4 + 3000×8 + 2000×3 + 1000×2 + 4000×2 = 28000 ден. ед.

Замечание. В некоторых случаях, поставка перераспределяемая по циклу, может оказаться равной нулю. Это возможно тогда, когда клетка со знаком «–» содержала нулевую поставку. В этом случае по циклу передается нулевая поставка. В результате свободная клетка, для которой был построен цикл, становится заполненной (нулевой поставкой), а клетка с нулевой поставкой – свободной.

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