Задача №2 (Вариант 12) - Экономико-математические методы и модели в логистике

Условие задачи

Менеджеру транспортного отдела поручено составить план перевозок продукции со склада фирмы в четыре торговые точки области, обеспечивающий минимальные издержки на перевозки (известно, что издержки на перевозки пропорциональны длине пути).

Расстояния от базы до каждого магазина и между магазинами приводятся в таб. 1:

Табл. 1

База

Т2

Т3

Т4

Т5

Т6

База

-

15

3

27

9

11

Т2

15

-

10

12

21

14

Т3

3

10

-

15

18

14

Т4

27

12

15

-

24

20

Т5

9

21

18

21

-

26

Т6

11

14

14

20

26

-

Пустые клетки означают, что дороги или ремонтируются или плохого качества.

Построение математической модели

Сеть дорог, связывающих базу с магазинами области можно представить в виде неориентированного графа, вершинам которого поставлены в соответствие название базы и магазинов, ребрам - связывающие их дороги, и каждому ребру поставлен в соответствие вес - длина дороги. Для удобства обозначим название базы через х1, а торговые точки через х2, х3, х3, х5. Расстояния от вершины Х1 до всех остальных и между вершинами представим в виде матрицы весов неориентированного графа (табл. 2). Для наглядности в матрице весов знаки оо (показывающие отсутствие дороги) опустим. Тогда задача сводится к нахождению кратчайших путей от вершины X1 до всех остальных. Для ее решения используем метод Дейкстры.

Табл. 2

Х1

Х2

Х3

Х4

Х5

Х6

Х1

-

15

3

27

9

11

Х2

15

-

10

12

21

14

Х3

3

10

-

15

18

14

Х4

27

12

15

-

24

20

Х5

9

21

18

24

-

26

Х6

11

14

14

20

26

-

Решение задачи

Построение графа

Построим граф (рис. 1), соответствующий матрице смежности (табл. 2).

Рис.1

Определение кратчайших расстояний от вершины х1 до всех остальных

Результаты вычислений будем представлять в таблице (табл. 3), в которой имена столбцов соответствуют номерам шагов алгоритма.

Табл. 3

0

1

2

3

4

5

Х1

0*

Х2

?

Х3

?

Х4

?

Х5

?

Х6

?

Предварительно всем вершинам графа, кроме вершины х1, присвоим временные метки, равные бесконечности: L(х2) = L(хЗ) = L(х4) = L(х5) =L(x6) =?, а вершине х1 присвоим постоянную метку L*(х1) = О. Занесем метки в нулевой столбец табл. З.

Выполним последовательность следующих шагов:

Шаг 1

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

S(x1) = {x2, x3, x4, x5, x6}

В) Для каждой вершины, принадлежащей множеству S (х1), вычислим новые временные метки L(хJ), равные min{ LСТ(хJ), L*(х1) + R1j,}, где LСТ(хJ) -- старая временная метка вершины хJ, L *(х1) = 0 -- постоянная метка вершины x1, R1j- вес ребра(x1, xJ).

Вычисления выполним в табл. 3-а.

Табл. 3-а

(xJ)

L*(x1)+R1j

Min{(xJ),(L*(x1)+R1j}

L(x2)=?

L*(x1)+R12=

0+15=15

Min {,15}=15

L(x3)=?

L*(x1)+R13=

0+3=3

Min {,3}=3

L(x4)=?

L*(x1)+R14=

0+27=27

Min {,27}=27

L(x5)=?

L*(x1)+R15=

0+9=9

Min {,9}=9

L(x6)=?

L*(x1)+R16=

0+11=11

Min {,11}=11

Прим: L*(x1)= 0

Вершинам х2, х3 х4 , х5, х6 присвоим новые временные метки, вычисленные в табл.3а

L(x2) = 15, L(x3) =3, L(x4)=27; L(x5)=9, L(x6)=11.

Занесем новые метки в первый столбец табл. 4.

С) Из всех имеющихся временных меток в столбце 1 (табл. 4) выберем наименьшую и сделаем ее постоянной для своей вершины: min{15,3,27,9,11}=3. Эта метка соответствует вершине Х3. Отметим ее звездочкой в столбце 1 L*(x3)= 3.

Табл. 4

0

1

2

3

4

5

Х1

0*

Х2

?

15

Х3

?

3*

Х4

?

27

Х5

?

9

Х6

?

11

Шаг 2

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

S(х3) = {х2, х4, х5, X6 } .

В) Для каждой вершины, принадлежащей множеству S(х3), вычислим новые временные метки L(х,), равные min{( (хJ),L *(Х2) + R2J}, где( (хJ) - старая временная метка вершины хJ, L *(х3) = 3 - постоянная метка вершины х3 , R3j - вес ребра (х3, хJ) (см. табл. 4-а)

Табл. 4-а

(xJ)

L*(x3)+R3j

Min{(xJ),(L*(x3)+R3j}

L(x2)=15

L*(x3)+R32=

3+10=13

Min {15,13}=13

L(x4)=27

L*(x3)+R34=

3+15=18

Min {27,18}=18

L(x5)=9

L*(x3)+R35=

3+18=21

Min {9,21}=9

L(x6)=11

L*(x3)+R36=

3+14=17

Min {11,17}=11

Прим: L*(x3)= 3

Метки вершин х5, х6 остаются без изменения, т. е. L(x5) = 9, L(x6) =11. Занесем их во второй столбец (табл. 5).

С) Из всех имеющихся временных меток в столбце 2 табл. 5 выберем наименьшую и сделаем ее постоянной для своей вершины: min{13, 18,9,11} = 9. Эта метка соответствует вершине L(х5) = 9. Отметим ее звездочкой.

Табл. 5

0

1

2

3

4

5

Х1

0*

Х2

0

15

13

Х3

0

3*

Х4

0

27

18

Х5

0

9

9*

Х6

0

11

11

Шаг 3

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

S(х5) = {х2, х4, х6}.

В) Для вершины х5, принадлежащей множеству S(х5), вычислим новую временную метку L(x5), равную min{LСт(хJ), L*(x5) + R5j } где LCт(х5) - старая временная метка вершины х5, L*(х5) = 9 - постоянная метка вершины х2, R5j - вес ребра (х5, хJ) (см. табл. 5-а).

Табл. 5-а

(xJ)

L*(x5)+R5j

Min{(xJ),(L*(x5)+R5j}

L(x2)=13

L*(x5)+R52=

9+21=30

Min {13,30}=13

L(x4)=18

L*(x5)+R54=

9+24=33

Min {18,33}=18

L(x6)=11

L*(x5)+R56=

9+26=35

Min {11,35}=11

Прим: L(x5)= 9

Метки вершин х2,х4, х6 остаются без изменения, т. е. L(x2) = 13, L(x4) = 18, L(x6)=11. Занесем их во второй столбец (табл. 6).

С) Из всех имеющихся временных меток в третьем столбце табл. 5 выберем наименьшую и сделаем ее постоянной для своей вершины: min{13,18, 11} = 11. Эта метка соответствует вершине х6: L* (х6) = 11. Отметим ее звездочкой.

Табл. 6

0

1

2

3

4

5

Х1

0*

Х2

0

15

13

13

Х3

0

3*

Х4

0

27

18

18

Х5

0

9

9*

Х6

0

11

11

11*

Шаг 4

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

S(x6) = {x2, x4}

В)Для вершины Х6, принадлежащей множеству S(х6), вычислим новую временную метку L(x6), равную min{XCT(xJ), L*(x6) + R6j}, где LCT(x6) - старая временная метка вершины x6, L*(х6) = 11 - постоянная метка вершины Х6, R6j - вес ребра (х6, хJ)

Табл. 6-а

(xJ)

L*(x6)+R6j

Min{(xJ),(L*(x6)+R6j}

L(x2)=13

L*(x6)+R62=

11+14=25

Min {13,25}=13

L(x4)=18

L*(x6)+R64=

11+20=31

Min {18,31}=18

Прим: L(x6) = 11

Метки вершин х2,х4, остаются без изменения, т. е. L(x2) = 13, L(x4) = 18. Занесем их во второй столбец (табл. 7).

С) Из всех имеющихся временных меток в четвертом столбце табл. 7 выберем наименьшую и сделаем ее постоянной для своей вершины: min{13,18} = 13. Эта метка соответствует вершине х2: L* (х2) = 13. Отметим ее звездочкой.

Табл. 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

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

S(x2) = {x4}.

В)Для вершины Х2, принадлежащей множеству S(х2), вычислим новую временную метку L(x2), равную min{XCT(x2), L*(x2) + R24}, где LCT(x2) - старая временная метка вершины x2, L*(х2) = 13 - постоянная метка вершины x2,

Табл. 7-а

(xJ)

L*(x2)+R24

Min{(xJ),(L*(x2)+R24}

L(x4)=18

L*(x2)+R24=

13+12=25

Min {18,25}=18

Прим: L(x2) = 13

Вершине x4 присвоим новую временную метку, т. е. L(x4) = 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*

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

L(x2) = 13, L(x3) = 3, L(х4) = 18, L(x5) = 9, L(x6)=11.

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

Рис.2

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

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

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

Где вершина XI предшествует вершине XJ.

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

Вершина х4 имеет пять смежных вершин х1,х2 х3, х5, Х6: S(х1,х2,х3,х5,Х6) . Определим, какая из этих вершин удовлетворяет соотношению (1)

L*(x4) = 18

L*(x1) = 0 R14 = 27L*(x4) ? L*(x1) + R14 = 0+27=27

L*(x2) = 13 R24 = 12L*(x4) ? L*(x2) + R24 = 13+12=25

L*(x3) = 3 R34 = 15L*(x4) = L*(x3) + R34 = 3+15=18

L*(x5) = 18 R54 = 24L*(x4) ? L*(x5) + R54=18+24=42

L*(x6) = 11 R64 = 20L*(x4) ? L*(x6) + R64=11+20=31

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

Рис.3

B) Определим, какая вершина предшествует вершине х3 в кратчайшем пути. Вершина х3 Имеет четыре смежные вершины:х1, х2, х5, Х6 (вершина х4 уже вошла в искомый путь и поэтому не рассматривается): S(х1, х2, Х5, х6). Определим, какая из этих вершин удовлетворяет соотношению (2).

L*(x3) = 3

L*(x1) = 0 R13 = 3L*(x3) = L*(x1) + R13 = 0+3=3

L*(x2) = 13 R23 = 10L*(x3) ? L*(x3) + R23 = 13+10=23

L*(x5) = 18 R53 = 18L*(x3) ? L*(x5) + R53= 18+18=36

L*(x6) = 11 R63 = 14L*(x3) ?L*(x6) + R63 =11+14=25

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

Рис.4

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

Найдем кратчайший путь от вершины Х1 до Х5

А) Вершина х5 имеет пять смежных вершин х1,х2 х3, х4, Х6: S(х1,х2,х3,х4,Х6) . Определим какая из пяти вершин удовлетворяет отношению (3)

L*(x5) = 9

L*(x1) = 0 R15 = 9L*(x5) = L*(x1) + R15 = 0+9=9

L*(x2) = 13 R25 = 21L*(x5) ? L*(x2) + R25 = 13+21=34

L*(x3) = 3 R35 = 18L*(x5) ? L*(x4) + R35 = 3+18=21

L*(x4) = 18 R45 = 24L*(x5) ? L*(x5) + R45 = 18+24=42

L*(x6) = 11 R65 = 26L*(x5) ? L*(x6) + R65 = 11+26=37

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

Рис.5

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

Найдем кратчайший путь от вершины Х1 до Х2

А) Вершина х2 имеет пять смежных вершин х1, х3, х4,Х5, Х6: S(х2,х3,х4,х5,Х6) . Определим, какая из пяти вершин удовлетворяет отношению (4)

L*(x2) = 13

L*(x1) = 0 R12 = 15L*(x2) ? L*(x1) + R12 = 0+15=15

L*(x3) = 3 R32 = 10L*(x2) = L*(x3) + R32 = 3+10=13

L*(x4) = 18 R42 = 12L*(x2) ? L*(x4) + R42 = 18+12=30

L*(x5) = 9 R52 = 21L*(x2) ? L*(x5) + R52 = 9+21=30

L*(x6) = 11 R62 = 14L*(x2) ? L*(x6) + R62 = 11+14=25

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

Рис.6

B) Определим, какая вершина предшествует вершине х3 в кратчайшем пути. Вершина х3 Имеет четыре смежные вершины:х1, х4, х5, Х6 (вершина х2 уже вошла в искомый путь и поэтому не рассматривается): S(х1, х4, Х5, х6). Определим, какая из этих вершин удовлетворяет соотношению (5).

L*(x3) = 3

L*(x1) = 0 R13 = 3L*(x3) = L*(x1) + R12 = 0+3=3

L*(x4) = 18 R43 = 15L*(x3) ? L*(x3) + R32 = 18+15=33

L*(x5) = 9 R53 = 18L*(x3) ? L*(x5) + R52= 9+18=37

L*(x6) = 11 R63 = 14L*(x3) ?L*(x6) + R62 =11+14=25

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

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

Найдем кратчайший путь от вершины Х1 до Х6

А) Вершина х6 имеет смежные вершины S(х1, х2, х3, х4, х5). Определим, какая из этих вершин удовлетворяет соотношению (6).

L*(x6) = 11

L*(x1) = 0 R16 = 11L*(x6) =L*(x1) + R16 = 0+11=11

L*(x2) = 13 R26 = 14L*(x6) ? L*(x2) + R26 = 13+14=27

L*(x3) = 3 R36 = 14L*(x6) ?L*(x3) + R36= 3+14=17

L*(x4) = 18 R46 = 20L*(x6) ?L*(x4) + R46 =18+20=38

L*(x5) = 9 R56 = 26L*(x6) ? L*(x5) + R56 =9+26=35

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

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

Рис.7

Похожие статьи




Задача №2 (Вариант 12) - Экономико-математические методы и модели в логистике

Предыдущая | Следующая