Оптимизация построения кольцевых маршрутов в почтовой связи

Московский Технический Университет  Связи и Информатики

 

Кафедра Организации Производства Аудита и Бухгалтерского Учета

 

 

 

 

 

 

 

 

 

 

 

Индивидуальная  работа

 

по дисциплине «Организация производства на предприятии почтовой связи»

 

на тему:

 

Оптимизация построения кольцевых маршрутов  в почтовой связи

 

(Вариант  №48)

 

 

 

 

 

 

 

Выполнил: студент 3 курса

 группы  ЭП0901 Хакимов С.Р.

Проверил: доцент Смирнов Ю.Д.

 

 

 

 

 

 

Москва 2011

 

Задача оптимизации построения кольцевых маршрутов почтовой связи.

 

Цель задачи:

 

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

 

 

 

 

Исходная информация для решения  задачи:

 

Матрица кратчайших расстояний

 

j i	1	2	3	4	5	6
1	∞	11	6	7	10	8
2	10	∞	5	8	9	12
3	5	10	∞	6	14	9
4	7	8	6	∞	13	11
5	9	8	14	12	∞	10
6	7	12	8	11	8	∞

 

 

Где i-начальные пункты возможных вариантов кольцевых маршрутов.

j-конечные пункты возможных вариантов кольцевых маршрутов.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Решение задачи.

 

Приведение матрицы.

а) по строкам:

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

 

Исходная матрица.

 

j i	1	2	3	4	5	6	min
1	∞	11	6	7	10	8	6
2	10	∞	5	8	9	12	5
3	5	10	∞	6	14	9	5
4	7	8	6	∞	13	11	6
5	9	8	14	12	∞	10	8
6	7	12	8	11	8	∞	7

 

 

Полученная матрица.

 

j i	1	2	3	4	5	6
1	∞	5	0	1	4	2
2	5	∞	0	3	4	7
3	0	5	∞	1	9	4
4	1	2	0	∞	7	5
5	1	0	6	4	∞	2
6	0	5	1	4	1	∞

 

 

Полученная матрица не считается приведенной, так как  в 3-ем и 5-ом столбцах нет нуля.

 

б) приведение матрицы по столбцам.

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

 

 

 

 

 

 

 

 

Матрица, приведенная по строкам.

 

j i	1	2	3	4	5	6
1	∞	5	0	1	4	2
2	5	∞	0	3	4	7
3	0	5	∞	1	9	4
4	1	2	0	∞	7	5
5	1	0	6	4	∞	2
6	0	5	1	4	1	∞
min	0	0	0	1	1	2

 

 

Приведенная матрица.

 

j i	1	2	3	4	5	6
1	∞	5	0	0	3	0
2	5	∞	0	2	3	5
3	0	5	∞	0	8	2
4	1	2	0	∞	6	3
5	1	0	6	3	∞	0
6	0	5	1	3	0	∞

 

 

Данная матрица считается  приведенной, так как в каждой строке и в каждом столбце есть хотя бы один ноль.

 

Сумма констант приведения (Н) исходной матрицы определяет нижнюю границу вершины дерева- «все циклы».

Н=16+17+18+17+19+16+2+2=107

 

2.Решение  задачи предусматривает исследование  клеток с нулями для каждой  приведенной матрицы. Для каждой  клетки с нулем находится значение Θ(i,j).

Найдем Θ(i,j) и выберем максимальную.

 

 

 

 

 

 

 

j i	1	2	3	4	5	6
1	∞	5	0	0	3	0
2	5	∞	0	2	3	5
3	0	5	∞	0	8	2
4	1	2	0	∞	6	3
5	1	0	6	3	∞	0
6	0	5	1	3	0	∞

 

Ɵ(1.3)=0+0=0

Ɵ(1.4)=0+0=0

Ɵ(1.6)=0+0=0

Ɵ(2.3)=2+0=2

Ɵ(3.1)=0+0=0

Ɵ(3.4)=0+0=0

Ɵ(4.3)=0+1=1

Ɵ(5.2)=0+2=2

Ɵ(6.1)=0+0=0

Ɵ(6.5)=0+3=3

 

 

 

 

В результате имеем следующий фрагмент дерева. Для определения нижней границы  вершины (i,j) берется сумма нижней границы предыдущей вершины и максимального значения Θ(i,j), по которому были выбраны две вершины. А i-тую строку и j-тый столбец вычеркиваем, и значение для клетки (j,i)=∞.

 

 

Полученная таблица.

 

j i	1	2	3	4	6
1	∞	5	0	0	0
2	5	∞	0	2	5
3	0	5	∞	0	2
4	1	2	0	∞	3
5	1	0	6	3	∞

H1=0

Полученную  таблицу не требуется приводить по строкам и столбцам.  Найдем Θ(i,j) и выберем максимальную.

 

j i	1	2	3	4	6
1	∞	5	0	0	0
2	5	∞	0	2	5
3	0	5	∞	0	2
4	1	2	0	∞	3
5	1	0	6	3	∞

Ɵ(1,3)=0+0=0

Ɵ(1,4)=0+0=0

Ɵ(1,6)=0+2=2

Ɵ(2,3)=0+2=2

Ɵ(3,1)=0+1=1

Ɵ(3,4)=0+0=0

Ɵ(4,3)=0+1=1

Ɵ(5,2)=0+3=3

 

 

МаксимальнаяΘ(5,2), соответственно вычеркиваем 5-ю строку и 2-ой столбец. Так как в новой таблице отсутствует клетка (j,i), соответствующая обратному переезду, то в виде графика изображаем часть кольцевого маршрута.

 

j i	1	3	4	6
1	∞	0	0	0
2	5	0	2	5
3	0	∞	0	2
4	1	0	∞	3

 

 

5               2

              ∞

6

 

 

По вершинам уже включенным в маршрут видно: если в клетку (2,6) не поставить бесконечность, то не исключено получение подцикла.

 

j i	1	3	4	6
1	∞	0	0	0
2	5	0	2	∞
3	0	∞	0	2
4	1	0	∞	3