Определение кратчайшего расстояния между го и гп
Метод потенциалов.
Метод основан на приписывании вершинам временных пометок, которые дают верхнюю границу длины от начальной вершины до этой вершины.
Алгоритм определения кратчайших расстояний методом потенциалов:
1. Начальной точке сети, за которую может быть принята любая из вершин, присваивают потенциал, равный нулю (vi = 0).
2. Определяют потенциалы соседних с начальной точкой вершин сети по формуле
vj = vi + lij,
где:
vi - потенциал предшествующей (соседней) вершины;
lij - длина звена, соединяющего вершины i и j.
Из них выбирают наименьший потенциал и присваивают его соответствующей вершине. Выбранный потенциал определяет кратчайшее расстояние от начальной точки до данной, на сети эту связь отмечают стрелкой.
3. Определяют потенциалы вершин, соседних с выбранной вершиной, и из всей совокупности потенциалов выбирают наименьший, который проставляют у соответствующей вершины и т.д.
Полное решение задачи включает столько этапов, сколько вершин включает транспортная сеть, поскольку каждый раз определяют кратчайшие расстояния от начальной точки до остальных.
Кратчайшие расстояния от точки А1.
А1 - А1 = 0
А1 - A2 = 7
А1 - А3 = 11
А1 - А4 = 8
А1 - Б1 = 7
А1 - Б2 = 14
А1 - Б3 = 5
А1 - Б4 = 9
А1 - Б5 = 5
А1 - Б6 = 9
А1 - Б7 = 4
Полученная таблица кратчайших расстояний.
Таблица № 2
|
|
А1 |
А2 |
А3 |
А4 |
Б1 |
Б2 |
Б3 |
Б4 |
Б5 |
Б6 |
Б7 |
|
А1 |
- |
7 |
11 |
8 |
7 |
14 |
5 |
9 |
5 |
9 |
4 |
|
А2 |
7 |
- |
4 |
7 |
5 |
7 |
4 |
2 |
7 |
2 |
3 |
|
А3 |
11 |
4 |
- |
8 |
7 |
4 |
8 |
2 |
9 |
4 |
7 |
|
А4 |
15 |
11 |
8 |
- |
15 |
8 |
7 |
10 |
17 |
12 |
14 |
|
Б1 |
7 |
5 |
7 |
12 |
- |
11 |
9 |
5 |
2 |
3 |
9 |
|
Б2 |
14 |
6 |
2 |
8 |
12 |
- |
9 |
4 |
11 |
6 |
10 |
|
Б3 |
8 |
4 |
8 |
3 |
9 |
9 |
- |
6 |
11 |
6 |
7 |
|
Б4 |
9 |
2 |
2 |
9 |
5 |
6 |
6 |
- |
7 |
2 |
5 |
|
Б5 |
5 |
7 |
9 |
13 |
2 |
13 |
10 |
7 |
- |
5 |
8 |
|
Б6 |
9 |
2 |
4 |
9 |
3 |
8 |
6 |
2 |
5 |
- |
5 |
|
Б7 |
4 |
3 |
7 |
10 |
8 |
10 |
7 |
5 |
8 |
5 |
- |
Построение опорного плана методом двойного предпочтения.
Сначала просматривают все строки матрицы и в каждой из них отмечают элемент с минимальной стоимостью (*). Затем просматривают столбцы и также отмечают в них элемент с минимальной стоимостью (*). В клетки с двумя знаками (**) помещают максимально возможные перевозки.
L(x)= 60*5+4*0+60*5+10*4+20*2+60*2+60*3+40*4+70*2+40*7=1560 т*км
Таблица № 3
|
ГО |
ГП |
вывоз, т | |||||||||||||
|
Б1 |
Б2 |
Б3 |
Б4 |
Б5 |
Б6 |
Б7 | |||||||||
|
А1 |
|
7 |
|
14 |
|
5 |
|
9 |
|
5 |
|
9 |
|
4 |
60 |
|
|
|
|
|
|
60 |
|
|
0 |
| ||||||
|
А2 |
|
5 |
|
7 |
|
4 |
|
2 |
|
7 |
|
2 |
|
3 |
210 |
|
60 |
|
|
|
10 |
|
20 |
|
|
60 |
|
60 |
| |||
|
А3 |
|
7 |
40 |
4 |
|
8 |
|
2 |
|
9 |
|
4 |
|
7 |
110 |
|
|
|
|
|
|
|
70 |
|
|
|
| |||||
|
А4 |
|
15 |
|
8 |
|
7 |
|
10 |
|
17 |
|
12 |
|
14 |
40 |
|
|
|
|
|
40 |
|
|
|
|
|
|
| ||||
|
ввоз, т |
60 |
40 |
50 |
90 |
60 |
60 |
60 |
| |||||||