ДВУХЭТАПНАЯ ТРАНСПОРТНАЯ ЗАДАЧА

Сформулируем следующую задачу. Три свеклосеящих хозяйства К₁, К₂, К₃ поставляют сахарную свеклу на два сахарных завода З₁, З₂, которые имеют в трех местах приемные пункты П₁, П₂, П₃, расположенные на некотором расстоянии от хозяйств и заводов. Объемы поставок свеклы хозяйствами, возможности приемных пунктов, мощности сахарных заводов и расстояния между хозяйствами, пунктами и заводами приведены в табл. 2.10 и 2.11. Требуется составить план перевозок свеклы из хозяйств на приемные пункты, а затем с пунктов на заводы, который имел бы минимальную тонно-километровую работу.

Таблица 2.10 Таблица 2.11

Для решения из таблиц 2.10-2.11 составим таблицу 2.12, в которой приемные пункты показаны как промежуточные, буквой М блокируются клетки, означающие поставку свеклы из хозяйств на заводы и между приемными пунктами. Клетки, отражающие поставку приемного пункта самому себе, имеют расстояние 0, и записанные в них поставки будут означать неиспользованные возможности приемных пунктов.

Решение. Исходное распределение (табл. 2.12) выполнено способом наименьшего элемента матрицы, при этом клетки с нулевыми элементами, как в задачах открытой модели, заполняются в последнюю очередь. Для проверки плана на оптимальность рассчитаем потенциалы строк и столбцов. Все свободные клетки имеют положительные характеристики, значит, получен оптимальный план.

Таблица 2.12

Согласно этому плану хозяйство К₁ поставляет 4 т свеклы приемному пункту П₂,

К₂ – 5 т пункту П₁ и 2 т - П₃,

К₃ – 1 т пункту П₂ и 2 т - П₃.

При этом недоиспользованные возможности 1 т будет иметь пункт П₃.

Из пункта П₁ на сахарный завод З₂ будет поставлено 5 т, из П₂ 5 т на З₁, из П₃ 2 т на З₁ и 2 т на З₂, недоиспользованные возможности составят 1 т.

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

Как единая двухэтапная задача решается не только тогда, когда возможности промежуточных пунктов превышают сбалансированные объемы вывоза поставщиками и завоза потребителями, но и тогда, когда такого баланса нет.

Если возможности пунктов соответствуют объему поставок и мощности заводов, то задача решается по частям: вначале рассчитывается план перевозок свеклы от хозяйств до приемных пунктов, а затем от приемных пунктов до сахарных заводов.