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

Может оказаться, что сумма поставок не равна сумме потребностей, в этом случае имеем открытую модель транспортной задачи. Рассмотрим решение открытой транспортной задачи на примере.

Пример 2. Минимизировать транспортные расходы по доставке грузов от поставщиков А₁, А₂, А₃ к потребителям В₁, В₂, В₃, если заданы объем поставок и потребностей, а также тарифы по доставке единицы груза от каждого поставщика до каждого потребителя (в д.е.).

Сумма поставок 8+20+24=52, сумма потребностей 7+17+23=47. Сумма поставок не равна сумме потребностей, поэтому мы имеем открытую модель транспортной задачи. Введем фиктивного потребителя с потребностью, равной 52-47=5 (ед. товара).

7 9 5 0

Дочертим еще один столбец в таблице. Основные тарифы в этом столбце возьмем равные нулю. Далее решаем задачу как закрытую модель.

Составим опорный план по методу северо-западного угла.

Число загруженных клеток должно равно m+n-1=3+4-

-1=6 – невырожденный план. Улучшаем план по методу потенциалов.

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

По циклу перемещаем наименьшую отрицательную поставку 7.

5 11 7 2

По циклу перемещаем поставку 9.

3 6 5 0

По циклу перемещаем поставку 5.

5 8 7 0

Последний план перевозок оптимален, так как все косвенные тарифы £ основных тарифов.

Посчитаем минимальную стоимость перевозок товаров (д.е.).