Контрольная работа по Экономико-математическим методам и модели в отрасли связи (стр. 3 из 5)

А	Б	В	Г	Д	Е
А	-	8	3	0	5	5
Б	11	-	3	0	6	1
В	0	7	-	5	8	7
Г	0	4	4	-	13	0
Д	3	7	8	10	-	0
Е	8	4	8	1	0	-

Наконец вычитаем наименьший элемент в столбце из элементов своего столбца - получается приведенная матрица:

А	Б	В	Г	Д	Е
А	-	4	0	0	5	5
Б	11	-	0	0	6	1
В	0	3	-	5	8	7
Г	0	0	1	-	13	0
Д	3	3	5	10	-	0
Е	8	0	5	1	0	-

Таблица 11 – Приведенная матрица.

Параллельно с расчетами в матрицах рисуется "дерево маршрута". Исходной вершиной дерева является вершина "все циклы", определяющая все множество возможных вариантов построения кольцевого маршрута по объезду (обходу) заданных пунктов. Для вершин дерева считаются "нижние границы". Нижняя граница вершины "все циклы" равна сумме наименьших элементов строк и столбцов, в результате вычитания которых получена приведенная матрица. Сумма констант приведения равна:

5+10+7+6+6+6+4+3=47

"Нижняя граница" обозначает: необходимое время на обслуживание маршрута при условии включения заданных пунктов в маршрут в любой произвольной последовательности будет не менее значения "нижней границы" вершины.

Выбор конкретной связи между пунктами производится с помощью характеристик, рассчитываемых для всех нулей приведенной матрицы. Характеристика считается как сумма наименьших элементов строки и столбца приведенной матрицы, в которых находится ноль. Сам ноль, для которого в данный момент считается характеристика, во внимание не берется.

Например, характеристика для нуля в строке А и столбце В складывается из минимума по строке А, равного 0 (Р_А,Г=0), и минимума по столбцу В, равного 0 (Р_Б,В=1), без учета самого Р_АВ

Итак, запишем приведенную матрицу, указывая рядом с каждым нулем его характеристики:

А	Б	В	Г	Д	Е
А	-	4	0(0)	0(0)	5	5
Б	11	-	0(0)	0(0)	6	1
В	0(3)	3	-	5	8	7
Г	0(0)	0(0)	1	-	13	0(0)
Д	3	3	5	10	-	0(3)
Е	8	0(0)	5	1	0(5)	-

Ноль с наибольшим значением характеристики находится в ячейке Е-Д, он указывает на связь между пунктами, которую следует оценить - включать ее в маршрут (Р_ЕР_Д) или от нее следует отказаться

.

От исходной вершины рисуется две ветви: одна к вершине Р_ЕР_Д, другая к вершине

. Чтобы оценить, что выгоднее, нужно для обеих вершин рассчитать "нижние границы". "Нижняя граница" с обязательным исключением связи считается как сумма "нижней границы" исходной вершины, откуда выходит ветвь, идущая к вершине , и характеристики нуля, указавшего на эту связь.

Чтобы рассчитать "нижнюю границу" вершины с обязательным включением связи Р_ЕР_Д нужно прежде вычеркнуть Е строку и Д столбец и одновременно элемент, соответствующий обратной связи этих пунктов Р_ЕР_Д.

А	Б	В	Г	Е
А	-	4	0	0	5
Б	11	-	0	0	1
В	0	3	-	5	7
Г	0	0	1	-	0
Д	3	3	5	10	0

Теперь проанализируем оставшуюся матрицу. Это матрица приведенная, т.к. в каждой строке и каждом столбце ее содержит не менее одного нуля. Тогда сумму констант приведения для этой таблицы равна 0.

Сумма констант приведения и нижней границы вершины "все циклы" определяет значение "нижней границы" вершины Р_ЕР_Д.

Та вершина, которой соответствует наименьшая по величине "нижняя граница", определяет включить связь в маршрут или нет. Наименьшее значение нижней границы будет соответствовать вершине с обязательным включением в маршрут связи Р_ЕР_Д, поэтому ветвление дерева продолжается от вершины Р_ЕР_Д.

Очередная связь определяется аналогично - путем расчета характеристик для нулей последней матрицы. Итак, запишем приведенную матрицу, указывая рядом с каждым нулем его характеристики:

А	Б	В	Г	Е
А	-	4	0(0)	0(0)	5
Б	11	-	0(0)	0(0)	1
В	0(3)	3	-	5	7
Г	0(0)	0(0)	1	-	0(0)
Д	3	3	5	10	0(3)

Ноль с наибольшим значением характеристики находится в ячейке строки Д и столбца Е. Продолжаем рисовать «дерево маршрута»: