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

В случае вырожденной транспортной задачи число занятых клеток меньше, чем /п + п - 1. Здесь целесообразно поменять местами поставщиков и потребите пей или ввести в свободную клетку с наименьшим тарифом нулевую поставку.

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

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

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

Решение.

Запишем исходные данные в распределительную таичнцу, найдем исходное опорное решение по метолу минимального тарифа. Число заполненных клеток равно 5, т +■ п — 1 = 6, следовательно, задача является вы ре косиной.

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

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

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

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