Характеристика расположения пунктов транспортной сети на оси координат OXY

 

Нижняя граница, то есть минимально возможная длина маршрута, определяется по формуле (7)

                                         (7)

и равна:

= 10+4+4+8+1= 26;

Для нулевых элементов матрицы, приведенной в табл. 20, определим оценки Q_ij. Так для нулевого элемента, находящегося на пересечении строки Б и столбца 1, оценка QБ-7 = 1 + 4 = 5 (минимальное значение по строке – 1, а по столбцу – 4). При этом необходимо помнить, что элемент, для которого производиться расчет, не учитывается и необходимо искать следующее наименьшее значение.

Результаты расчета оценок представлены в табл. 21.

Таблица 21

Расчет оценок для нулевых  элементов

	Б	1	6	7
Б	∞	1	2	0 5
1	5	∞	0 6	4
6	6	0 6	∞	8
7	0 5	0 0	4	∞

 

В табл. 21 получили две максимальные оценки равные 6. Для дальнейшего решения выберем одну из них, какую не имеет принципиального значения. Пусть ветвь маршрута будет 1-6. На пересечении строки 6 и столбца 1 ставим знак “∞“.

Таблица 22

Матрица кратчайших расстояний, после исключения строки 6, столбца 1

	Б	1	7
Б	∞	1	0
6	6	∞	8
7	0	0	∞

Проверяем условие, что бы в каждой строке и столбце усеченной  матрицы были нулевые значения, оно не выполняется, поэтому операция приведения  проводится заново (Табл. 23).

Таблица 23

Приведение матрицы усеченной  на строку Б и столбец 10

	Б	1	7	hi
Б	∞	1	0	0
6	0	∞	2	6
7	0	0	∞	0
hj	0	0	0

 

От начальной вершины "все решения" проводят ответвление  вершин ks и с нижними границами:

Рис. 5. Первое ветвление «дерева решений» для метода «ветвей и границ»

Следующее усечение матрицы представлено в табл. 24

Таблица 24

Расчет оценок для нулевых  элементов

	Б	1	7
Б	∞	1	0 3
6	0 2	∞	2
7	0 0	0 1	∞

 

Наибольшее искомое значение получаем 3, выбираем на пересечении столбца Б и строки 7. Исключаем из дальнейшего рассмотрения указанные строку и столбец. Получаем матрицу 2 х 2, в которой однозначно представлены две последние «ветки» маршрута (табл. 25).

Таблица 25

Приведение матрицы усеченной на строку Б и столбец 7

	Б	1
6	0	∞
7	0	0

 

При этом «дерево решений» примет окончательный вид, который  проиллюстрирован на рис. 6.

Анализируя полученные участки (ветви), имеем следующий маршрут: Б 7 1 6 Б, длина которого составляет 32 км.

 

Рис. 6. «Дерево решений» для маршрута грузоотправителя Б

Проверим, правильно ли была определена нижняя граница, для чего просуммируем соответствующие расстояния между пунктами маршрута: 4 + 9 + 8 + 11 = 32 км.

Для второго маршрута (2,9,10) грузоотправителя Б построим матрицу кратчайших расстояний (Табл. 26).

 

 

 

Таблица 26

Матрица кратчайших расстояний для второго маршрута от Б

	Б	2	9	10
Б	∞	9	10	8
2	9	∞	5	9
9	10	5	∞	6
10	8	9	6	∞

 

В каждой строке находим  минимальный элемент hi и выполним приведение матрицы по строкам (Табл. 27).

Таблица 27

Матрица кратчайших расстояний, приведенная по строкам

	Б	2	9	10	hi
Б	∞	1	2	0	8
2	4	∞	0	4	5
9	5	0	∞	1	5
10	2	3	0	∞	6

 

Далее, полученную в табл. 27 матрицу необходимо привести по столбцам. Результат приведения представлен в табл. 28.

Таблица 28

Матрица кратчайших расстояний, приведенная по столбцам

	Б	2	9	10
Б	∞	1	2	0
2	2	∞	0	4
9	3	0	∞	1
10	0	3	0	∞
hj	2	0	0	0

 

Нижняя граница, то есть минимально возможная длина маршрута, определяется по формуле (8):

                                         (8)

и равна:

= 8+5+5+6+2= 26;

Для нулевых элементов матрицы, приведенной в табл. 28, определим оценки Q_ij. Так для нулевого элемента, находящегося на пересечении строки Б и столбца 10, оценка Q_Б-10 = 1 + 1 = 2 (минимальное значение по строке – 1, а по столбцу – 1). При этом необходимо помнить, что элемент, для которого производиться расчет, не учитывается и необходимо искать следующее наименьшее значение.

Результаты расчета оценок представлены в табл. 29.

Таблица 29

Расчет оценок для нулевых  элементов

	Б	2	9	10
Б	∞	1	2	0 2
2	2	∞	0 2	4
9	3	0 2	∞	1
10	0 2	3	0 0	∞

 

В табл. 29 получили четыри максимальные оценки равные 2. Для дальнейшего решения выберем одну из них, какую не имеет принципиального значения. Пусть ветвь маршрута будет Б-10. На пересечении строки 10 и столбца Б ставим знак “∞“.

Таблица 30

Матрица кратчайших расстояний, после исключения строки Б столбца 10

	Б	2	9
2	2	∞	0
9	3	0	∞
10	∞	3	0

Проверяем условие, что бы в каждой строке и столбце усеченной  матрицы были нулевые значения, оно не выполняется, поэтому операция приведения  проводится заново (Табл. 31).

Таблица 31

Приведение матрицы усеченной  на строку Б и столбец 10

	Б	2	9	hi
2	0	∞	0	0
9	1	0	∞	0
10	∞	3	0	0
hj	2	0	0

От начальной вершины "все решения" проводят ответвление  вершин ks и с нижними границами:

Рис. 7. Первое ветвление «дерева решений» для метода «ветвей и границ»

Следующее усечение матрицы представлено в табл. 32

Таблица 32

Расчет оценок для нулевых  элементов

	Б	2	9
2	0 1	∞	0 0
9	1	0 4	∞
10	∞	3	0 3

 

Наибольшее искомое значение получаем 4, выбираем на пересечении столбца 2 и строки 9. Исключаем из дальнейшего рассмотрения указанные строку и столбец. Получаем матрицу 2 х 2, в которой однозначно представлены две последние «ветки» маршрута (табл. 33).

 

Таблица 33

Приведение матрицы усеченной на строку Б и столбец 7

	Б	9
2	0	∞
10	∞	0

 

При этом «дерево решений» примет окончательный вид, который  проиллюстрирован на рис. 8.

Анализируя полученные участки (ветви), имеем следующий маршрут: Б 10 9 2 Б, длина которого составляет 28 км.