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

При открытой транспортной задаче сумма запасов не совпадает с суммой потребностей:

открытая транспортная задача - student2.ru

При этом возможны два варианта:

а) если открытая транспортная задача - student2.ru , то объем запасов превышает объем потребления, все потребители будут удовлетворены полностью и часть запасов останется не вывезенной. Для решения задачи вводят фиктивного (n + 1) потребителя, потребности которого открытая транспортная задача - student2.ru .

Модель такой задачи будет иметь вид

открытая транспортная задача - student2.ru

при ограничениях: открытая транспортная задача - student2.ru

открытая транспортная задача - student2.ru ;

б) если открытая транспортная задача - student2.ru , то объем потребления превышает объем запасов, часть потребностей останется неудовлетворенной. Для решения такой задачи вводят фиктивного (m+ 1) поставщика, запас которого открытая транспортная задача - student2.ru .

Модель такой задачи имеет вид

открытая транспортная задача - student2.ru

при ограничениях: открытая транспортная задача - student2.ru

открытая транспортная задача - student2.ru .

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

Пример. Составить оптимальный план перевозки грузов от трех поставщиков с грузами 240, 40, 110 т к четырем потребителям с потребностями 90, 190, 40 и 130 т. Стоимости перевозок единицы груза от каждого поставщика к каждому потребителю заданы матрицей

открытая транспортная задача - student2.ru .

Решение. Запасы груза у поставщиков: 240 + 40 + 110 = 390 т. Потребности потребителей: 90 + 190 +40 + 130 = 450 т. Так как запасов груза меньше, чем потребности потребителей, то задача открытая. Следовательно, вводим фиктивного поставщика с грузом а = 450 – 390 = 60 т.

Тариф фиктивного поставщика примем равным нулю. Распределительная таблица:

bj ai ui
90/0 190/60 40/0 130/110/0
240/130/0 - -
40/0 - - -5
110/20/0 - - -2
- - - -13
  vj  

Так как m + n – 1 = 7, а число занятых клеток равно 6, то для исключения вырожденности введем в клетку (2, 2) нулевую поставку. Расчет потенциалов проведен в распределительной таблице. Оценки свободных клеток:

D11 = – 2, D13 = 3, D21 = – 14, D24 = – 7, D32 = – 4, D33 = – 10, D4ф1 = – 8, D4ф3 = – 1, D4ф4 = – 5.

Оценка свободной клетки (1, 3) больше нуля, от нее строим цикл и перераспределяем грузы:

открытая транспортная задача - student2.ru открытая транспортная задача - student2.ru

Полученное перераспределение грузов вносим в распределительную таблицу и проверяем на оптимальность:

bj ai ui
-
- - - -5
- - -2
- - - -13
  vj  

Оценки свободных клеток:

D11 = – 2, D21 = – 14, D23 = – 3, D24 = – 7, D32 = – 4, D33 = – 13, D4ф1 = – 8, D4ф3 = – 4, D4ф4 = – 5.

Следовательно, получено оптимальное решение:

открытая транспортная задача - student2.ru .

Стоимость транспортных расходов составит:

L(X)min = 90×13 + 40×9 + 110×8 + 40×8 + 90×3 + 20×6 = 3120 ден. ед.

Применение транспортных задач в экономике

Транспортная задача является важным частным случаем задачи линейного программирования.

Алгоритм и методы решения транспортной задачи могут быть использованы при решении некоторых экономических задач, не относящихся к транспортировке груза. В этом случае величины тарифов имеют различный смысл в зависимости от конкретной экономической задачи. К таким задачам относятся:

1) оптимальное закрепление за станками операций по обработке деталей. В них сij является таким экономическим показателем, как производительность. Задача позволяет определить, сколько времени и на какой операции должен использоваться каждый из станков, чтобы обработать максимальное количество деталей. Так как транспортная задача требует нахождения минимума, то значения сij берутся с отрицательным знаком;

2) оптимальные назначения или проблема выбора. Имеется m механизмов, которые могут выполнять n различных работ с производительностью сij. Задача позволяет определить, какой механизм и на какую работу надо назначить, чтобы добиться максимальной производительности;

3) задача о сокращении производства с учетом суммарных расходов на изготовление и транспортировку продукции;

4) увеличение производительности автомобильного транспорта за счет минимизации порожнего пробега. Уменьшение порожнего пробега сократит количество автомобилей для перевозок, увеличив их производительность;

5) решение задач с помощью метода запрещения перевозок. Используется в том случае, если груз от некоторого поставщика по каким-то причинам не может быть направлен одному из потребителей. Данное ограничение можно учесть, присвоив соответствующей клетке достаточно большое значение стоимости, тем самым в эту клетку не будут производиться перевозки.

Наши рекомендации