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

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

Пример 1.22. Для задачи оптимального планирования перевозок груза тарифы перевозок, запасы груза и потребности в грузе такие же, как в примере 1.20, за исключением потребности третьего магазина, которая составляет 9 ед. Найти оптимальный план перевозок. Решение. Балансное равенство (1.39) не выполняется, поэтому задача открытая, так как суммарная потребность в грузе превышает суммарный запас на 2 ед. Для решения этой задачи вводим фиктивного поставщика с запасом груза 2 ед. (табл. 1.82).

Таблица 1.82

 

Модель задачи запишется следующим образом:

– количество груза, перевозимого с i склада в j магазин

; .

;

 

 

;

;

;

;

;

;

;

;

.

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

.

 

Чтобы получить оптимальный план исходной задачи, нужно отбросить последнюю строку, соответствующую фиктивному поставщику:

.

Отброшенная строка плана означает, сколько единиц груза недополучат потребители, а именно третий магазин недополучит 2 ед. груза.

 

1.111. Для строительства четырех объектов используется кирпич, изготовляемый на трех заводах. Ежедневно каждый завод может изготовлять 100, 150 и 50 ед. кирпича. Ежедневные потребности в кирпиче на каждом строящемся объекте соответственно равны 75, 80, 60 и 85 ед. Известны также тарифы перевозок 1 ед. кирпича с каждого завода к каждому строящемуся объекту:

.

Составить такой план перевозок кирпича к строящимся объектам, при котором общая стоимость перевозок является минимальной.

1.112. На трех хлебокомбинатах ежедневно производится 110,190 и 90 т муки. Эта мука потребляется четырьмя хлебозаводами, ежедневные потребности которых равна соответственно 80,60, 170 и 80 т. Тарифы перевозок 1 т муки с хлебокомбинатов к каждому из хлебозаводов задаются матрицей

.

Составить такой план доставки муки, при котором общая стоимость перевозок является минимальной.

1.113. В трех хранилищах горючего ежедневно хранится 175,125 и 140 т бензина. Этот бензин ежедневно получают четыре заправочные станции в количествах, равных соответственно 180,110, 60 и 40 т. Стоимость перевозок 1 т бензина с хранилищ к заправочным станциям задаются матрицей

.

Составить план поставок бензина заправочным станциям с минимальной стоимостью.