Главная страница

транспортная задача. Решение Рассмотрим неравенство 1 системы ограничений. 3 x 1 2 x 2 6 Построим прямую 3 x 1 2 x 2 6


Скачать 71.47 Kb.
НазваниеРешение Рассмотрим неравенство 1 системы ограничений. 3 x 1 2 x 2 6 Построим прямую 3 x 1 2 x 2 6
Анкортранспортная задача
Дата29.11.2022
Размер71.47 Kb.
Формат файлаdocx
Имя файла8966807 jn 181122.docx
ТипРешение
#819193
страница3 из 5
1   2   3   4   5

19 = min { 32, 19 }

Поставщик

Потребитель

  Запас  

1

2

3

4

5

1

13

23

8

12

9

10

  23   нет  

2

12

3

13

13

11

29

2

  41   12   нет  

3

15

7

13

28

6

7

  28   нет  

4

18

6

10

19

10

14

6

  37   19   нет  

5

7

22

9

12

?

10

4

  41   19  

  Потребность  

30
18
нет

45
22
нет

32
13

34
6

29
нет




6 = min { 6, 19 }

Поставщик

Потребитель

  Запас  

1

2

3

4

5

1

13

23

8

12

9

10

  23   нет  

2

12

3

13

13

11

29

2

  41   12   нет  

3

15

7

13

28

6

7

  28   нет  

4

18

6

10

19

10

14

6

  37   19   нет  

5

7

22

9

?

12

6

10

4

  41   19   13  

  Потребность  

30
18
нет

45
22
нет

32
13

34
6
нет

29
нет




13 = min { 13, 13 }

Поставщик

Потребитель

  Запас  

1

2

3

4

5

1

13

23

8

12

9

10

  23   нет  

2

12

3

13

13

11

29

2

  41   12   нет  

3

15

7

13

28

6

7

  28   нет  

4

18

6

10

19

10

14

6

  37   19   нет  

5

7

22

9

13

12

6

10

4

  41   19   13   нет  

  Потребность  

30
18
нет

45
22
нет

32
13
нет

34
6
нет

29
нет




Стоимость доставки продукции, для начального решения:

23*8+12*3+29*2+2/*6+18*6+19*10+22*9+13*12+6*10=1158 ден. ед
Проверим на оптимальность
потенциал поставщика + потенциал потребителя = тариф задействованного маршрута.
Последовательно найдем значения потенциалов.
Значение одного потенциала необходимо задать. Пусть u5= 0.

A5B2:

v2+u5= 9

v2= 9-0 = 9

A5B3:

v3+u5=12

v3=12-0=12

A5B4:

v4+u5=10

v4= 10-0=10

A1B2 :  

v2+u1=8

u1=8 - 9 = -1

A3B4 :  

v4+ u3= 6

u3=6-10= -4

A4B3 :  

v3+u4=10

u4=10-12=-2

A4B1 :  

v1+u4= 6

v1=6-(-2) =8

A2B1:  

v1+ u2=3

u2=3- 8 = -5

A2B5:  

v5+ u2= 2

v5=2-(-5)= 7




Поставщик

Потребитель

U

B1

B2

B3

B4

B5

A1

13

23

8

12

9

10

u1=-1

A2

12

3

13

13

11

29

2

u2=-5

A3

15

7

13

28

6

7

u3=-4

A4

18

6

10

19

10

14

6

u4=-2

A5

7

22

9

13

12

6

10

4

u5=0

V

v1=8

v2=9

v3=12

v4=10

v5= 7







Найдем оценки незадействованных маршрутов (cij - стоимость доставки). ?

A1B1 :  

Δ11 = c11 - ( u1 + v1 ) = 13 - ( -1 + 8 ) =6

A1B3 :  

Δ13 = c13 - ( u1 + v3 ) = 12 - ( -1 + 12 ) =1

A1B4 :  

Δ14 = c14 - ( u1+ v4 ) = 9 - ( -1 + 10 ) =0

A1B5 :  

Δ15 = c15 - ( u1+ v5 ) = 10 - ( -1 + 7 ) =4

A2B2 :  

Δ22 = c22 - ( u2+ v2 ) = 13 - ( -5 + 9 ) =9

A2B3 :  

Δ23 = c23 - ( u2+ v3 ) = 13 - ( -5 + 12 ) =6

A2B4 :  

Δ24 = c24 - ( u2+ v4 ) = 11 - ( -5 + 10 ) =6

A3B1 :  

Δ31 = c31 - ( u3 + v1 ) = 15 - ( -4 + 8 ) =11

A3B2 :  

Δ32 = c32 - ( u3 + v2 ) = 7 - ( -4 + 9 ) =2

A3B3 :  

Δ33 = c33 - ( u3 + v3 ) = 13 - ( -4 + 12 ) =5

A3B5 :  

Δ35 = c35 - ( u3 + v5 ) = 7 - ( -4 + 7 ) =4

A4B2 :  

Δ42 = c42 - ( u4 + v2 ) = 10 - ( -2 + 9 ) =3

A4B4 :  

Δ44 = c44 - ( u4 + v4 ) = 14 - ( -2 + 10 ) =6

A4B5 :  

Δ45 = c45 - ( u4 + v5 ) = 6 - ( -2 + 7 ) =1

A5B1 :  

Δ51 = c51 - ( u5 + v1 ) = 7 - ( 0 + 8 ) =-1

A5B5 :  

Δ55 = c55 - ( u5 + v5 ) = 4 - ( 0 + 7 ) =-3




Есть отрицательные оценки.
1   2   3   4   5


написать администратору сайта