Открытая транспортная задача
Открытую транспортную задачу можно преобразовать в закрытую путем введения фиктивного пункта производства или потребления. В случае если суммарный запас груза превышает суммарные потребности на 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 т бензина с хранилищ к заправочным станциям задаются матрицей
.
Составить план поставок бензина заправочным станциям с минимальной стоимостью.