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

 

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

 

 

ПОСТРОЕНИЕ МАТЕМАТИЧЕСКОЙ МОДЕЛИ

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

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

 10

12 18 15

15  

 3 21 14

 27

 14 

9 20

11 24

 

 26

 

Рис.1

 

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

 

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

    Табл. 3

	0	1	2	3	4	5
Х1	0*
Х2	∞
Х3	∞
Х4	∞
Х5	∞
Х6	∞

 

Предварительно всем вершинам графа, кроме вершины х1, присвоим временные метки, равные бесконечности: L(х₂) = L(х_з) = L(х₄) = L(х₅) =L(x₆) =∞, а вершине х₁ присвоим постоянную метку L*(х₁) = О. Занесем метки в нулевой столбец табл. З.

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

Шаг 1

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

S(x₁) = {x₂, x₃, x₄, x₅, x₆}

в) Для каждой вершины, принадлежащей  множеству S (х₁), вычислим новые временные метки L(х_j), равные min{ L^сТ(х_j), L*(х₁) + R_1j,}, где L^сТ(х_j) — старая временная метка вершины х_j, L *(х₁) = 0 — постоянная метка вершины x₁, R_1j- вес ребра(x₁, x_j).

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

 

             Табл. 3-а

L*(x₁)= 0

(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

 

Вершинам х₂, х₃ х₄ , х_5, х₆ присвоим новые временные метки, вычисленные в табл.3а

 L(x₂) ⁼ 15, L(x₃) =3, L(x₄)=27; L(x₅)=9, L(x₆)=11.

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

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

Табл. 4

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

 

 

Шаг 2

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

S(х₃) = {х₂, х₄, х_5, x₆ } .

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

 

   Табл. 4-а

L*(x₃)= 3

(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(x₅) = 9, L(x₆) =11. Занесем их во второй столбец (табл. 5).

с) Из всех имеющихся временных меток в столбце 2 табл. 5 выберем наименьшую и сделаем ее постоянной для своей вершины: min{13, 18,9,11} = 9. Эта метка соответствует вершине L(х₅) = 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

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

S(х₅) = {х_2, х_4, х₆}.

в) Для вершины х₅, принадлежащей множеству S(х₅), вычислим новую временную метку L(x₅), равную min{L^ст(х_j), L*(x₅) + R_5j } где L^cт(х₅) - старая временная метка вершины х₅, L*(х₅) = 9 - постоянная метка вершины х₂, R_5j - вес ребра (х₅, х_j) (см. табл. 5-а).

          Табл. 5-а

L(x₅)= 9

(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

 

Метки вершин х₂,х_4, х₆ остаются без изменения, т.е. L(x₂) = 13, L(x₄) = 18, L(x₆)=11. Занесем их во второй столбец (табл. 6).

с) Из всех имеющихся временных меток в третьем столбце табл. 5 выберем наименьшую и сделаем ее постоянной для своей вершины: min{13,18, 11} = 11. Эта метка соответствует вершине х₆: L* (х₆) = 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

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

S(x₆) = {x_2, x₄}

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

 

Табл. 6-а

L(x₆) = 11

(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

 

Метки вершин х₂,х_4, остаются без изменения, т.е. L(x₂) = 13, L(x₄) = 18. Занесем их во второй столбец (табл. 7).

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