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

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

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

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

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

при ограничениях:

;

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

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

при ограничениях:

.

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

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

.

Решение. Запасы груза у поставщиков: 240 + 40 + 110 = 390 т. Потребности потребителей: 90 + 190 +40 + 130 = 450 т. Так как запасов груза меньше, чем потребности потребителей, то задача открытая. Следовательно, вводим фиктивного поставщика с грузом а_4ф = 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
4ф		-		-	-	-13
	vj

 

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

D ₁₁ = – 2, D ₁₃ = 3, D ₂₁ = – 14, D ₂₄ = – 7, D ₃₂ = – 4, D ₃₃ = – 10, D _4ф1 = – 8, D _4ф3 = – 1, D _4ф4 = – 5.

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

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

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

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

D ₁₁ = – 2, D ₂₁ = – 14, D ₂₃ = – 3, D ₂₄ = – 7, D ₃₂ = – 4, D ₃₃ = – 13, D _4ф1 = – 8, D _4ф3 = – 4, D _4ф4 = – 5.

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

.

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

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