Автор: Пользователь скрыл имя, 04 Марта 2013 в 07:53, контрольная работа
Менеджеру транспортного отдела поручено составить план перевозок продукции со склада фирмы в четыре торговые точки области, обеспечивающий минимальные издержки на перевозки (известно, что издержки на перевозки пропорциональны длине пути).
Расстояния от базы до каждого магазина и между магазинами приводятся в таблице 1:
Табл. 1
база Т2 Т3 Т4 Т5 Т6
база ∞ 15 26 31 16 6
Т2 15 ∞ 16 14 24 33
Т3 26 16 ∞ 17 19 25
Т4 31 14 17 ∞ 26 28
Т5 16 24 19 26 ∞ 14
Т6 6 33 25 28 14 ∞
Пустые клетки означают, что дороги или ремонтируются или плохого качества.
Табл. 7
0 |
1 |
2 |
3 |
4 |
5 | |
х1 |
0* |
|||||
х2 |
∞ |
15 |
15* |
|||
х3 |
∞ |
26 |
26 |
26 |
26* |
|
х4 |
∞ |
31 |
31 |
29 |
29 |
|
х5 |
∞ |
16 |
16 |
16* |
||
х6 |
∞ |
6* |
Шаг 5
а) Определим множество вершин графа, смежных с вершиной Х3, не имеющих еще постоянных меток (рис. 1, табл. 2):
S(X3) = {Х4}.
в)Для вершины Х4, принадлежащей множеству S(х3), вычислим новую временную метку L(x3), равную min{XCT(x4), L*(x3) + R34}, где LCT(x4) - старая временная метка вершины Х4, L*(х3) = 26 - постоянная метка вершины Х3, R34 - вес ребра (Х3, Х4) Табл. 7-а
Табл. 7-а
LCT(Xi) |
L*(x3)+R3j |
min{LCT(xj), ( L*(x1) +R1j} | |
L(x4) = 29 |
L*(x3) + R34 = |
26 + 17 = |
min{29, 43} = 29 |
Вершине Х4 присвоим новую временную метку, т.е. L(x4) = 31. Занесем ее в пятый столбец (табл. 8).
0 |
1 |
2 |
3 |
4 |
5 | |
х1 |
0* |
|||||
х2 |
∞ |
15 |
15* |
|||
х3 |
∞ |
26 |
26 |
26 |
26* |
|
х4 |
∞ |
31 |
31 |
29 |
29 |
29* |
х5 |
∞ |
16 |
16 |
16* |
||
х6 |
∞ |
6* |
Процесс расстановки меток закончен. Значения их дают кратчайшие расстояния от исходной вершины Х] до всех остальных:
L(x2) =15 , L(x3) =26 , L(х4) =29 , L(x5) =16 , L(x6)=6.
На рисунке 2 в квадратных скобках укажем найденные кратчайшие расстояния от вершины X1 до всех остальных, т.е. взвесим вершины исходного графа.
Рис. 2
Чтобы найти кратчайшие пути от вершины х\ до всех остальных вершин, используем соотношение:
L*(xj) = L*(xi) + Rij
где вершина Xi предшествует вершине Xj.
а). Найдем кратчайший путь от вершины х1 до вершины х4. Для этого определим, из каких вершин можно попасть в вершину х4 (то есть какие вершины связаны с вершиной х4 ребром).
Вершина Х4 имеет пять смежных вершин: х1,х2,х3,х5,х6: S(х1,х2,х3,х5,х6). Определим, какая из этих вершин удовлетворяет соотношению (4).
L*(x4) = L*(Xi) + Ri4.
L*(x4) = 29
L*(x1)=0 |
R14=31 |
L*(x4)=L*(x1)+R14=0+31=31 |
L*(x2)=15 |
R24=14 |
L*(x4)≠L*(x2)+R24=15+14=29 |
L*(x3)=26 |
R34=17 |
L*(x4)≠L*(x3)+R34=26+17=43 |
L*(x5)=16 |
R54=26 |
L*(x4)≠L*(x5)+R54=16+26=42 |
L*(x6)=6 |
R64=28 |
L*(x4)≠L*(x6)+R64=6+28=34 |
Как видно, только вершина Х2 удовлетворяет соотношению (4). Следовательно, в кратчайшем пути вершине Х4 предшествует X2. Выделем на графе ребро Х2,Х4
б). Определим, какая вершина предшествует вершине Х2 в кратчайшем пути. Вершина X2 имеет смежные вершины: Х1, Х3,X5,X6 (вершина Х4 уже вошла в искомый путь и поэтому не рассматривается).Определим, какая из этих вершин удовлетворяет соотношению (4).
L*(x2) =15,
L*(x1)=0 |
R12=15 |
L*(x2)=L*(x1)+R12=0+15=15 |
L*(x3)=26 |
R32=16 |
L*(x2)≠L*(x3)+R32=26+16=42 |
L*(x5)=16 |
R52=24 |
L*(x2)≠L*(x5)+R52=16+24=40 |
L*(x6)=6 |
R62=33 |
L*(x2)≠L*(x6)+R62=6+33=39 |
Как видно, соотношению (4) удовлетворяет вершина Х1. Следовательно, в кратчайшем пути вершине Х2 предшествует вершина Х1 (рис. 3). Выделим на графе ребро Х1, Х2.
Рис. 3
Таким образом, минимальный путь от вершины Х1 до вершины Х4 проходит по вершинам x1, x2,x4 и длина этого пути равна 29.
Очевидно, что каждый из путей из вершины X1 до любой вершины, входящей в построенный кратчайший путь (от вершины X1 в вершину Х4), тоже будет оптимальным.
Найдем кратчайший путь от вершины x1 до вершины х3.
а). Вершина х3 имеет смежные вершины: S(x1,x2,x4,x5,x6 ). Определим, какая из этих вершин удовлетворяет соотношению (4).
L*(x3) = 26,
L*(x1)=0 |
R13=26 |
L*(x3)=L*(x1)+R13=0+26=26 |
L*(x2)=15 |
R23=16 |
L*(x3)≠L*(x2)+R23=15+16=31 |
L*(x4)=29 |
R43=17 |
L*(x3)≠L*(x4)+R43=29+17=46 |
L*(x5)=16 |
R53=19 |
L*(x3)≠L*(x5)+R53=16+19=35 |
L*(x6)=6 |
R63=25 |
L*(x3)≠L*(x6)+R63=6+25=31 |
Как видно, соотношению (4) удовлетворяет только вершина х1 . Следовательно, в кратчайшем пути вершине х3 предшествует вершина x1.
Таким образом, минимальный путь от вершины х1 до вершины х3 проходит по ребру (х1х3) и длина его равна 26 (весу ребра).
Рис. 4
Найдем кратчайший путь от вершины x1 до вершины х3.
б). Вершина х5 имеет смежные вершины: S(x1,x2,x4,x6 ). Определим, какая из этих вершин удовлетворяет соотношению (4).
L*(x5) = 16,
L*(x1)=0 |
R15=16 |
L*(x5)=L*(x1)+R15=0+16=16 |
L*(x2)=15 |
R25=24 |
L*(x5)≠L*(x2)+R25=15+24=39 |
L*(x4)=29 |
R45=26 |
L*(x5)≠L*(x4)+R45=29+26=55 |
L*(x6)=6 |
R65=14 |
L*(x5)≠L*(x6)+R65=6+14=20 |
Как видно, соотношению (4) удовлетворяет только вершина х1 . Следовательно, в кратчайшем пути вершине х5 предшествует вершина x1.
Таким образом, минимальный путь от вершины х1 до вершины х5 проходит по ребру (х1х5) и длина его равна 16 (весу ребра).
Рис. 5
Найдем кратчайший путь от вершины x1 до вершины х3.
в). Вершина х6 имеет смежные вершины: S(x1,x2,x4 ). Определим, какая из этих вершин удовлетворяет соотношению (4).
L*(x6) = 6,
L*(x1)=0 |
R16=6 |
L*(x6)=L*(x1)+R16=0+6=6 |
L*(x2)=15 |
R26=33 |
L*(x6)≠L*(x2)+R26=15+33=48 |
L*(x4)=29 |
R46=28 |
L*(x6)≠L*(x4)+R46=29+28=57 |
Как видно, соотношению (4) удовлетворяет только вершина х1 . Следовательно, в кратчайшем пути вершине х6 предшествует вершина x1.
Таким образом, минимальный путь от вершины х1 до вершины х6 проходит по ребру (х1х6) и длина его равна 6 (весу ребра).
Рис. 6