<<
>>

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

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

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

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

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

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

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

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

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

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

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

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

Таким образом, со склада 1 целесообразно поставить 3000 бутылок второму и четвертому заводам, со склада 2 — 2000 бутылок второму заводу и 1000 бутылок третьему, со склада 3 — 4000 бутылок первому заводу, при этом стоимость транспортных расходов будет минимальной и составит 28 000 усл. ед.

<< | >>
Источник: Архаров Евгений Валерьевич. Учебно–методический комплекс по дисциплине Математика Нижний Новгород, 2011. 2011

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

  1. 2.3.2 ВЫРОЖДЕННОСТЬ
  2. 2.3.2П ВЫРОЖДЕННОСТЬ
  3. 8.2. Алгоритм метода потенциалов
  4. 8.5. Транспортная задача в сетевой постановке
  5. Критерии оптимальности.
  6. § 67, Транспортная задача
  7. Формула изобретения (полезной модели)
  8. Рабочий день.
  9. § 4.7. Проект «электронного государства» и проблема тотального контроля над человеком
  10. Вырожденность в транспортных задачах
  11. Определение оптимального варианта перевозки грузов с учетом трансформации спроса и предложений
  12. Транспортная задача.