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

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

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

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

Модель Такой задачи будет иметь вид F(x) = min при ограничениях:

,

X_ij≥ 0, j=1,n+1, j=1,n;

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

A_m+1= -

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

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

,

X_ij≥ 0, i = 1,m+1, j =1,n.

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

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

Решение. Запасы грузов у поставщик: = 390т. Запросы

потребителей: = 450т, так как < , то вводим фиктивного поставщика с грузом а4ф= 450 – 390 = 60т.

Тариф фиктивного поставщика 4ф примем равным 0 ден.ед.

Составим опорный план методом минимальной стоимости.

Так как m+n–1=7, а число занятых клеток равно 6, то для исключения вырожденности введем в клетку (2,2) нулевую поставку. Оценки ∆1,1= –2, ∆1,3 = 3, ∆2,1= –14, ∆2,4 = –7, ∆3,3 = –10, ∆4ф1= –8, ∆4ф3= –1,∆4ф4= –5. Для клетки (1,3), имеющую положительную оценку строим контур и перераспределяем грузы.

Получаем новый план.

∆11= -2, ∆21= -14, ∆23=-3, ∆24=-7, ∆32=-4, ∆33=-13, ∆41=-8, ∆43=-4, ∆44=-5.

Таким образом, мы получили оптимальное решение.

.

Стоимость транспортных расходов составляет: (Xопт) = 3120 ден.ед.

Варианты контрольной работы.