Открытая транспортная задача. Как решить?

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

Будем считать, что мы уже знаем, что такое транспортная задача, как решить закрытую транспортную задачу, как составить первоначальный опорный план и как бороться с вырожденностью плана. Если что - то из этого Вам незнакомо, то при желании можно изучить тут:

Как решить транспортную задачу?

Вырожденность опорного плана транспортной задачи. Как избавиться?

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

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

Все очень просто. Если не хватает товара, чтобы удовлетворить потребности магазинов, нужно добавить мнимого (фиктивного) поставщика.  Если предложение превышает над спросом, добавим мнимого (фиктивного) потребителя.

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

Чтобы привести открытую транспортную задачу к закрытому (замкнутому) виду, добавляем столбец (строку) с нулевыми стоимостями.

  • Если превышают запасы - добавляем фиктивного потребителя (столбец)

  • Если превышает спрос - добавляем фиктивного поставщика (строку)

Рассмотрим подробно на примере.

Открытая транспортная задача - пример 1:

Решить транспортную задачу с исходными данными:

условие открытой транспортной задачи

Общие потребности (спрос) = 40 + 180 + 80 + 60 = 360

Общие запасы (предложение) = 120 + 100 = 220

Видим, что спрос превышает над предложением.

Следовательно добавляем фиктивного поставщика Ас объем запасов 360 - 220 = 140.

добавили фиктивного поставщика с нулевыми стоимостями 

Получили закрытую транспортную задачу: спрос = предложению.

Построим первоначальный план методом северо-западного угла:

первоначальный план методом северо-западного угла

Шаг 1:

Проверим первоначальный план на оптимальность: 

проверка оптимальности первоначального плана 

Подробно о том, как были заполнены таблицы можно посмотреть тут: Как решить транспортную задачу? 

Среди оценочных значений правой таблице есть отрицательные, следовательно план не оптимален.

Построили замкнутую цепочку знаков " + " и " — ".

Среди ячеек, помеченных " — " выберем ячейку с минимальным значением: 

К = min{80;100}=80

Это значение 80 перенесем в пустую ячейку, помеченную " + ", далее, к значениям в ячейках с " + " прибавим К, из значений в ячейках с " — " вычтем К.

Определим стоимость перевозки на первом шаге:

S1 = 40 · 4 + 80 · 9 + 100 · 11 + 0 · 0 + 80 · 0 + 60 · 0 = 1980

Шаг 2:

проверка на оптимальность опорного плана транспортной задачи

К = min{20;60}=20

Среди оценочных значений правой таблице есть отрицательные, следовательно план не оптимален.

В ячейках с " + " прибавим данное значение, в ячейках с " — " вычтем.

Общая стоимость перевозки на данном шаге:

S2 = 40 · 4 + 80 · 9 + 20 · 11 + 80 · 3 + 80 · 0 + 60 · 0 = 1340 < S1

Видим, что стоимость перевозки на текущем шаге меньше чем на предыдущем.

Шаг 3:

открытая транспортная задача решение 

К = min{80;40}=40

Среди оценочных значений правой таблице есть отрицательные, следовательно план не оптимален.

Общая стоимость перевозки на данном шаге:

S3 = 40 · 4 + 80 · 9 + 80 · 3 + 20 · 4 + 100 · 0 + 40 · 0 = 1200 < S2

Видим, что стоимость перевозки на текущем шаге меньше чем на предыдущем. 

Шаг 4:

решение транспортной задачи пример открытой задачи

Среди оценочных значений нет отрицательных, следовательно решение оптимально. 

S4 = 40 · 4 + 40 · 9 + 40 · 2 + 40 · 3 + 60 · 4 + 140 · 0 = 960 < S3 

Задача решена, получен оптимальный план перевозок. 

решение открытой транспортной задачи пример 

 

Открытая транспортная задача - пример 2:

Решить открытую транспортную задачу с исходными данными:

открытая транспортная задача пример решения

Общие потребности (спрос) = 40 + 40 + 20 = 100

Общие запасы (предложение) = 20 + 30 + 40 + 20 = 110

Видим, что предложение превышает над спросом.

Следовательно добавляем фиктивного потребителя Вс потребностями 110 - 100 = 10.

открытая транспортная задача пример решения 

Получили закрытую транспортную задачу: спрос = предложению. 

Статистика

Эконометрика

Английский язык

Матметоды в экономике