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

 

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

                                          (5)

где hi, hj – константы приведения соответственно по строкам и столбцам.

Следовательно = 3+6+6+3+3 = 21

 

По формуле (6) для нулевых элементов матрицы, приведенной в таблице 8, определим оценки Qij, которые проставим в правом нижнем углу соответствующей ячейки.

 при условии: k ¹ j; s ¹ i; k, s = 1, 2, …, n,

где  l'ik – наименьшее значение элемента в строке i;

l''sj – наименьшее значение  элемента в столбце j.

• определяются пары (ks) с максимальной оценкой, то есть:

                                (6)

Так для нулевого элемента, находящегося на пересечении строки А и столбца 8, оценка Q_А8 = 1 + 0 = 1 (минимальное значение по строке – 1, а по столбцу – 0). При этом необходимо помнить, что элемент, для которого производиться расчет, не учитывается и необходимо искать следующее наименьшее значение.

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

Таблица 9

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

	А	3	4	5	8
А	∞	5	4	1	0 1
3	2	∞	0 6	6	4
4	1	0 6	∞	4	1
5	1	9	7	∞	0 1
8	0 1	7	4	0 1	∞

  В таблице 9 получили две максимальные оценки равные 6. Для дальнейшего решения выберем одну из них, какую не имеет принципиального значения. Пусть ветвь маршрута будет 3-4. Таким образом, исключает из дальнейшего рассмотрения строку k = 3 и столбец s = 4. На пересечении строки 4 и столбца 3 ставим знак « ».

 

 

 

Таблица 10

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

	А	3	5	8
А	∞	5	1	0
4	1	∞	4	1
5	1	9	∞	0
8	0	7	0	∞

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

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

Графическое изображение  полученного решения приведено на рис. 2.

Таблица 11

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

	А	3	5	8	hi
А	∞	0	1	0	0
4	0	∞	3	0	1
5	1	4	∞	0	0
8	0	3	0	∞	0
hj	0	5	0	0

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

Далее производится расчет оценок для нулевых значений усеченной  матрицы, выбирается максимальное значение, которое покажет новое ветвление «дерева решений» (табл. 12).

 

 

Таблица 12

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

	А	3	5	8
А	∞	0 4	1	0 1
4	0 4	∞	3	0 3
5	1	4	∞	0 1
8	0 4	3	0 4	∞

Полученное ветвление  отмечаем на «дереве решений» (рис. 3).

В таблице 11 получили четыре максимальных оценки равные 4. Для дальнейшего решения выберем одну из них, какую не имеет принципиального значения. Выберем 4-А. Получаем две «ветки дерева решений» 4 – А и . Исключаем из дальнейшего рассмотрения указанные строку и столбец. Знак не проставляется, так как столбец четыре уже был исключен при первой усечении матрицы кратчайших расстояний (табл. 13).

Рис. 3. Второе ветвление «дерева решений»

 

Таблица 13

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

	3	5	8
А	0	1	0
5	4	∞	0
8	3	0	∞

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

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

Таблица 14

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

	3	5	8
А	0 4	1	0 1
5	4	∞	0 4
8	3	0 4	∞

 

 

Наибольшее искомое значение получаем 4, выбираем на пересечении столбца 5 и строки 8. Исключаем из дальнейшего рассмотрения указанные строку и столбце (табл. 15).

Таблица 15

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

	3	8
А	0	0
5	4	∞

 

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

Таблица 16

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

	3	8	hi
А	0	0	0
5	0	∞	4
hj	0	0

 

И получаем матрицу 2 х 2, в  которой однозначно представлены две  последние «ветки» маршрута (табл. 17).

 

Таблица 17

Матрица 2 х 2 для метода «ветвей  и границ»

	3	8
А	0	0
5	0	∞

 

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

Анализируя полученные участки (ветви), имеем следующий маршрут: A 8 5 3 4 A, длина которого составляет 31 км.

 

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

Проверим, правильно ли была определена нижняя граница, для чего просуммируем соответствующие расстояния между пунктами маршрута: 3 + 3 + 12 + 6 + 7 = 31 км.

 

Теперь проводим аналогичные  вычисления для двух маршрутов грузоотправителя Б.

Для первого маршрута (1,6,7) грузоотправителя Б построим матрицу кратчайших расстояний (Табл. 18).

 

 

Таблица 18

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

	Б	1	6	7
Б	∞	10	11	9
1	10	∞	4	8
6	11	4	∞	12
7	9	8	12	∞

 

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

Таблица 19

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

	Б	1	6	7	hi
Б	∞	1	2	0	9
1	6	∞	0	4	4
6	7	0	∞	8	4
7	1	0	4	∞	8

 

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

Таблица 20

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

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