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

Страницы работы

Содержание работы

Задача №3

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

Решение

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

j

i

Потребители

Мощности поставщиков(вагоны)

В1

В2

В3

В4

Поставщики

А1

15

3

8

4

45

А2

7

10

5

12

50

А3

20

9

4

6

35

Спросы потребителей (вагоны)

25

30

20

50

            130

  125

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

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

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

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

В1

В2

В3

В4

B5

Ai

А1

25                             15

20                               3

                                    8            

                                    4

                   0

45

А2

                                    7

10                            10

20                               5

20                             12                                     

                   0

50

А3

                                 20

9

                                    4

30                               6                                     

5                             0

35

Bj

25

30

20

50

5

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

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

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

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


V1=15

V2=3

V3=-2

V4=5

V5=-1

 

U1=0

25                         15

20                           3

                                    8           

                               4

0

 

U2=-7

                                7

10                        10

20                               5

20                        12                                 

0

 

U3=-1

                              20

9

                                    4

30                           6                                 

5                         0

 
 

                  ∆ij = Vj-Uj-Cij

13 = -2-0-8 = -10

14 = 5-0-4 = 1>0

15 = -1-0-0 = -1

21 = 15+7-7 = 15>0

25 = -1+7-0 = 6>0

31 = 15+1-20 = -4

32 = 3+1-9 = -5

33 = -2+1-4 = -5

35 = -1+1-0 = 0

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

Похожие материалы

Информация о работе