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

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

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

В А	7	17	23
8	2	4	10
20	5	11	7
24	3	6	5

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

В А	7	17	23	5
8	2 7----	4 ----1	10 0	0 -5	-5
20	5 + ----- 9 4	11 --- 16	7 4	0 2 2	2
24	3 7 4	6 9	5 19	0 5	0

7 9 5 0

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

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

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

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

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

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

В А	7	17	23	5
8	2 -2	4 8	10 0	0 -5	-7
20	5 7	11 9-----	7 ---- 4	0 2 2	0
24	3 3	6 + ----- 9 3	5 -----19	0 5	-2

5 11 7 2

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

В А	7	17	23	5
8	2 1	4 8	10 3	0 -4	-2
20	5 7	11 8	7 13---	-- +0 2 2	2
24	3 3	6 9	5 10---	0 ----5	0

3 6 5 0

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

В А	7	17	23	5
8	2 1	4 8	10 3	0 -4	-4
20	5 7	11 8	7 8	0 5	0
24	3 3	6 9	5 15	0 -2	2

5 8 7 0

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

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