Экономико-математические методы и модели в логистики

 

Табл. 7

	0	1	2	3	4	5
х1	0*
х2	0	15	13	13	13*
х3	0	3*
х4	0	27	18	18	18
х5	0	9	9*
х6	0	11	11	11*

 

 

 

 

Шаг 5

а) Определим множество вершин графа, смежных с вершиной Х₂, не имеющих еще постоянных меток (рис. 1, табл. 2):

S(x₂) = {x₄}.

        в)Для вершины Х₂, принадлежащей множеству S(х₂), вычислим новую временную метку L(x₂), равную min{X^CT(x₂), L*(x₂) + R₂₄}, где L^CT(x₂) - старая временная метка вершины x₂, L*(х₂) = 13 - постоянная метка вершины x₂,

 

Табл. 7-а

L(x₂) = 13

(xj)	L*(x2)+R24		min{(xj),(L*(x2)+R24}
L(x4)=18	L*(x2)+R24=	13+12=25	min {18,25}=18

 

Вершине x₄ присвоим новую временную метку, т.е. L(x₄) = 18. Занесем ее в четвертый столбец (табл. 8).

 

Табл.8

	0	1	2	3	4	5
х1	0*
х2	0	15	13	13	13*
х3	0	3*
х4	0	27	18	18	18	18*
х5	0	9	9*
х6	0	11	11	11*

 

Процесс расстановки меток  закончен. Значения их дают кратчайшие расстояния от исходной вершины Х₁ до всех остальных:

L(x₂) = 13, L(x₃) = 3, L(х₄) = 18, L(x₅) = 9, L(x₆)=11.

На рисунке 2 в квадратных скобках укажем найденные кратчайшие расстояния от вершины X₁ до всех остальных, т.е. взвесим вершины исходного графа.

 

 

 

 

 

 

 

 

                   [13]                                                           [3]                                       

 10

12 18 15

15  

 3 21 14                                              [18]

 27                                                                                                                    

 14 

[0] 9 20

11 24

 

 26                                  [9]

                 [11]

                                                                                

Рис.2

 

 

              Определение кратчайших путей

Чтобы найти кратчайшие пути от вершины х₁ до всех остальных вершин, используем соотношение:

L*(xj) = L*(xi) + R_ij

где вершина X_i предшествует вершине X_j.

а) Найдем кратчайший путь от вершины  х₁ до вершины х₄. Для этого определим, из каких вершин можно попасть в вершину х₄ (то есть какие вершины связаны с вершиной х₄ ребром).

Вершина х₄ имеет пять смежных вершин х₁,х₂ х₃, х_5, х₆: S(х₁,х₂,х₃,х_5,х₆) . Определим, какая из этих вершин удовлетворяет соотношению (1)

 

L*(x₄) = 18

 

L*(x₁) = 0        R₁₄ = 27 L*(x₄) ≠ L*(x₁) + R₁₄ = 0+27=27

L*(x₂) = 13      R₂₄ = 12 L*(x₄) ≠ L*(x₂) + R₂₄ = 13+12=25

L*(x₃) = 3        R₃₄ = 15 L*(x₄) = L*(x₃) + R₃₄ = 3+15=18

L*(x₅) = 18      R₅₄ = 24 L*(x₄) ≠ L*(x₅) + R₅₄=18+24=42

L*(x₆) = 11      R₆₄ = 20 L*(x₄) ≠ L*(x₆) + R₆₄=11+20=31

Как видно, только вершина  х₃ удовлетворяет соотношению (1). Следовательно, в кратчайшем пути вершине х₄ предшествует вершина х₃ (Рис. 2). Выделим на графе ребро (х₃, х₄)

 

 

 

 

                   [13]                                                           [3]                                       

 10

12 18 15

15  

 3 21 14                                              [18]

 27                                                                                                                    

 14 

[0] 9 20

11 24

 

 26                                  [9]

                 [11]                               

                                                          Рис.3

 

b) Определим, какая вершина  предшествует вершине х₃ в кратчайшем пути. Вершина х₃ имеет четыре смежные вершины:х₁, х₂, х_5, х₆ (вершина х₄ уже вошла в искомый путь и поэтому не рассматривается): S(х₁, х_2, х₅, х₆). Определим, какая из этих вершин удовлетворяет соотношению (2).

L*(x₃) = 3

L*(x₁) = 0        R₁₃ = 3 L*(x₃) = L*(x₁) + R₁₃ = 0+3=3

L*(x₂) = 13      R₂₃ = 10 L*(x₃) ≠ L*(x₃) + R₂₃ = 13+10=23

L*(x₅) = 18      R₅₃ = 18 L*(x₃) ≠ L*(x₅) + R₅₃= 18+18=36

L*(x₆) = 11      R₆₃ = 14 L*(x₃)  ≠L*(x₆) + R₆₃ =11+14=25

 

Как видно, соотношению (2) удовлетворяет  вершина х₁. Следовательно, в кратчайшем пути вершине х₃ предшествует вершина х₁ (рис 4.) Выделяем на графе ребро х₁, х_3.

 

 

                   [13]                                                            [3]                                       

 10

12 18 15

15  

 3 21 14                                              [18]

 27                                                                                                                    

 14 

[0] 9 20

11 24

 

 26                                  [9]

                 [11]                               

                                                          Рис.4

Таким образом, минимальный  путь от вершины х₁ до вершины х₄ проходит по вершинам (х₁, х₃, х₄) и длина этого пути равна 18. Очевидно, что каждый из путей из вершины х₁ до любой вершины, входящей в построенный кратчайший путь (от вершины х₁ в вершину х₄), тоже будет оптимальным.

 

Найдем кратчайший путь от вершины х₁ до х₅

а) Вершина х₅ имеет пять смежных вершин х₁,х₂ х₃, х_4, х₆: S(х₁,х₂,х₃,х_4,х₆) . Определим какая из пяти вершин удовлетворяет отношению (3)

 

 L*(x₅) = 9

 

L*(x₁) = 0        R₁₅ = 9 L*(x₅) = L*(x₁) + R₁₅ = 0+9=9

L*(x₂) = 13      R₂₅ = 21 L*(x₅) ≠ L*(x₂) + R₂₅ = 13+21=34

L*(x₃) = 3        R₃₅ = 18 L*(x₅) ≠ L*(x₄) + R₃₅ = 3+18=21

L*(x₄) = 18      R₄₅ = 24 L*(x₅) ≠ L*(x₅) + R₄₅ = 18+24=42

L*(x₆) = 11      R₆₅ = 26 L*(x₅) ≠ L*(x₆) + R₆₅ = 11+26=37

Как видно, соотношению (3) удовлетворяет  вершина х₁ Следовательно в кратчайшем пути от вершины х₁ до х₅ будет само ребро( х₁х₅). Выделяем его на рис.5

 

                   [13]                                                           [3]                                       

 10

12 18 15

15  

 3 21 14                                              [18]

 27                                                                                                                    

 14 

[0] 9 20

11 24

 

 26                                  [9]

                 [11]                               

                                                          Рис.5

Таким образом, минимальный  путь от вершины х₁ до вершины х₅ проходит по самому ребру (х₁х₅) и длина этого пути равна 9(весу ребра).

 

Найдем кратчайший путь от вершины х₁ до х₂

а) Вершина х₂ имеет пять смежных вершин х₁, х₃, х_4,х_5, х₆: S(х₂,х₃,х₄,х_5,х₆) . Определим, какая из пяти вершин удовлетворяет отношению (4)

 

L*(x₂) = 13

 

L*(x₁) = 0       R₁₂ = 15 L*(x₂) ≠ L*(x₁) + R₁₂ = 0+15=15

L*(x₃) = 3       R₃₂ = 10 L*(x₂) = L*(x₃) + R₃₂ = 3+10=13

L*(x₄) = 18     R₄₂ = 12 L*(x₂) ≠ L*(x₄) + R₄₂ = 18+12=30

L*(x₅) = 9       R₅₂ = 21 L*(x₂) ≠ L*(x₅) + R₅₂ = 9+21=30

L*(x₆) = 11     R₆₂ = 14 L*(x₂) ≠ L*(x₆) + R₆₂ = 11+14=25

Как видно, только вершина  х₃ удовлетворяет соотношению (4). Следовательно, в кратчайшем пути вершине х₂ предшествует вершина х₃ (Рис. 6). Выделим на графе ребро (х₃, х₂).

 

                   [13]                                                           [3]                                       

 10

12 18 15

15  

 3 21 14                                              [18]

 27                                                                                                                    

 14 

[0] 9 20

11 24

 

 26                                  [9]

                 [11]                               

                                                          Рис.6

b) Определим, какая вершина  предшествует вершине х₃ в кратчайшем пути. Вершина х₃ имеет четыре смежные вершины:х₁, х₄, х_5, х₆ (вершина х₂ уже вошла в искомый путь и поэтому не рассматривается): S(х₁, х_4, х₅, х₆). Определим, какая из этих вершин удовлетворяет соотношению (5).

 

L*(x₃) = 3

L*(x₁) = 0        R₁₃ = 3 L*(x₃) = L*(x₁) + R₁₂ = 0+3=3

L*(x₄) = 18      R₄₃ = 15 L*(x₃) ≠ L*(x₃) + R₃₂ = 18+15=33

L*(x₅) = 9        R₅₃ = 18 L*(x₃) ≠ L*(x₅) + R₅₂= 9+18=37

L*(x₆) = 11      R₆₃ = 14 L*(x₃)  ≠L*(x₆) + R₆₂ =11+14=25

 

Как видно, соотношению (5) удовлетворяет  вершина х_{1 .} Следовательно, в кратчайшем пути вершине х₃ предшествует вершина х₁ (рис 6.) Выделяем на графе ребро х₁, х_3.

Таким образом, минимальный  путь от вершины х₁ до вершины х₂ проходит по вершинам (х₁, х₃, х₂₎ и длина этого пути равна 13. Очевидно, что каждый из путей из вершины х₁ до любой вершины, входящей в построенный кратчайший путь (от вершины х₁ в вершину х₂), тоже будет оптимальным.

 

Найдем кратчайший путь от вершины х₁ до х₆

 

а) Вершина х₆ имеет смежные вершины S(х₁, х₂, х₃, х₄, х₅). Определим, какая из этих вершин удовлетворяет соотношению (6).

 

L*(x₆) = 11

L*(x₁) = 0        R₁₆ = 11 L*(x₆) =L*(x₁) + R₁₆ = 0+11=11

L*(x₂) = 13      R₂₆ = 14 L*(x₆) ≠ L*(x₂) + R₂₆ = 13+14=27

L*(x₃) = 3        R₃₆ = 14 L*(x₆) ≠L*(x₃) + R₃₆= 3+14=17

L*(x₄) = 18      R₄₆ = 20 L*(x₆)  ≠L*(x₄) + R₄₆ =18+20=38

L*(x₅) = 9        R₅₆ = 26 L*(x₆) ≠ L*(x₅) + R₅₆ =9+26=35

Как видно соотношению (6) удовлетворяет вершина х_{1 .} Следовательно в кратчайшем пути вершине х₆ предшествует вершина х₁ (рис 7.)

Таким образом, минимальный  путь от вершины х₁ до вершины х₆ проходит по ребру (х₁, х₆) и длина его равна 11 (весу ребра).

 

 

                   [13]                                                           [3]                                       

 10

12 18 15

15  

 3 21 14                                              [18]

 27                                                                                                                    

 14 

[0] 9 20

11 24

 

 26                                  [9]

                 [11]                               

                                                          Рис.7

 

 

РЕШЕНЕИЕ В Maple

 

1) Войдем в пакет функций теории графов networks. Для этого используем команду:

 

>

 

2) Создадим пустой граф (без ребер и узлов) G и затем добавим в него нужное количество вершин (6  ):