Расчет перевозки порожних вагонов между станциями

Задача №3

На трех станциях отделения железной дороги имеется избыток порожних вагонов, запасы которых составляют соответственно 45, 50, и 35, а на четырех станциях вагонов не хватает. Требуется так распределить порожние вагоны на станции недостатка, спрос которых равен соответственно 25, 30, 20, 50, чтобы пробеги были минимальными. Расстояния  от станции избытка до станции недостатка указаны в таблице.

Решение

Расстояние от станции избытка до станции недостатка изобразим в виде таблицы.

Так как суммарный избыток вагонов не равен суммарному недостатку, что составляет 130 и 125 вагонов:

то условие общего баланса невыполняется, и задача является открытого типа, значит требуется ввести (n+1)-го фективного потребителя, потребности которого равны излишку запаса, т.е.

Стоимость перевозки еденицы груза от i-го поставщика к (n+1)-му потребителю c_in+1 принимается равным нулю ( поставщики x_in+1 в оптимальном плане покажут остатки продукции на складах поставщиков).

                 Построим начальный базисный план методом северо-западного угла.

Базисный план предполагает, что количество перевозок m+n-1=7, где m, n – соответственно количество строк и столбцов.

Стоимость перевозки:

Z(X⁰)=15*25+3*20+10*10+5*20+12*20+6*30+0*5=1055 ден. ед.

Построим оптимальный план методом потенциалов, воспользуясь условием оптимальности Канторовича:

                  ∆ij = Vj-Uj-Cij

∆₁₃ = -2-0-8 = -10

∆₁₄ = 5-0-4 = 1>0

∆₁₅ = -1-0-0 = -1

∆₂₁ = 15+7-7 = 15>0

∆₂₅ = -1+7-0 = 6>0

∆₃₁ = 15+1-20 = -4

∆₃₂ = 3+1-9 = -5

∆₃₃ = -2+1-4 = -5

∆₃₅ = -1+1-0 = 0

План  не является оптимальным, т.к. есть ∆ij>0.    Θ = min{25;10}=10;