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

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

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

задана стоимость перевозки одной бутылки от каждого склада к каждому заводу.

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

РЕШЕНИЕ. Запишем исходные данные в распределительную таблицу, найдём исходное опорное решение по методу минимального тарифа. Число заполненных клеток равно 5, m+n–1=6, следовательно, задача является вырожденной.

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

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

B j Ai	1	2	3	4	ui
	4000	5000	1000	3000
1 6000	6	4 3000	9	8 3000	0
2 3000	5	3 2000	2 1000	8	-1
3 4000	2 4000	3 0	6	8	-1
vj	3	4	3	8

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

.

Стоимость транспортных расходов при данном оптимальном решении составит 52000 усл. ед.

Открытая транспортная задача

При открытой транспортной задаче сума запасов не совпадает с суммой потребностей, т. е.

.

При этом:

а) если , то объём запасов превышает объём потребления, все потребители будут удовлетворены полностью и часть запасов останется на складах. Для решения задачи вводят фиктивного (п + 1)-го потребителя, потребности которого .

Модель такой задачи будет иметь вид

при ограничениях:

б) если , то объём потребления превышает объём запасов, часть потребностей останется неудовлетворённой. Для решения задачи вводят фиктивного (т + 1)-го поставщика, потребности которого .

Модель такой задачи будет иметь вид

при ограничениях:

При введении фиктивного поставщика или потребителя открытая транспортная задача становится закрытой и решается по ранее рассмотренному алгоритму для закрытых транспортных задач, причём тарифы, соответствующие фиктивному поставщику или потребителю, больше или равны наибольшему из всех транспортных тарифов, иногда их считают равными нулю. В целевой функции фиктивный поставщик или потребитель не учитываются.