Лабораторная работа3. Лабораторная работа 3 Оптимизация последовательности переналадок технологической линии Постановка задачи

• Название: Лабораторная работа 3 Оптимизация последовательности переналадок технологической линии Постановка задачи
• Дата: 21.02.2019
• Размер: 78.34 Kb.
• Имя файла: Лабораторная работа3.docx
• Тип: Лабораторная работа; #68534
• страница: 3 из 4

Включение ребра (2,5) проводится путем исключения всех элементов 2-ой строки и 5-го столбца, в которой элемент d₅₂ заменяем на М, для исключения образования негамильтонова цикла.

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

После операции приведения сокращенная матрица будет иметь вид:

i j	1	2	4	6	7	di
1	M	0	10	2	3	0
3	2	0	0	0	1	0
4	0	0	M	3	1	0
6	0	3	1	M	0	0
7	3	1	2	0	M	0
dj	0	0	0	0	0	0

Сумма констант приведения сокращенной матрицы:

∑d_i + ∑d_j = 0

Нижняя граница подмножества (2,5) равна:

H(2,5) = 46 + 0 = 46 ≤ 47

Чтобы исключить подциклы, запретим следующие переходы: (3,2).

Поскольку нижняя граница этого подмножества (2,5) меньше, чем подмножества (2*,5*), то ребро (2,5) включаем в маршрут с новой границей H = 46

Шаг №3.

Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).

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

i j	1	2	4	6	7	di
1	M	0(2)	10	2	3	2
3	2	M	0(1)	0(0)	1	0
4	0(0)	0(0)	M	3	1	0
6	0(0)	3	1	M	0(1)	0
7	3	1	2	0(1)	M	1
dj	0	0	1	0	1	0

d(1,2) = 2 + 0 = 2; d(3,4) = 0 + 1 = 1; d(3,6) = 0 + 0 = 0; d(4,1) = 0 + 0 = 0;

d(4,2) = 0 + 0 = 0; d(6,1) = 0 + 0 = 0; d(6,7) = 0 + 1 = 1; d(7,6) = 1 + 0 = 1;

Наибольшая сумма констант приведения равна (2 + 0) = 2 для ребра (1,2), следовательно, множество разбивается на два подмножества (1,2) и (1*,2*).

Исключение ребра (1,2) проводим путем замены элемента d₁₂ = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (1*,2*), в результате получим редуцированную матрицу.

i j	1	2	4	6	7	di
1	M	M	10	2	3	2
3	2	M	0	0	1	0
4	0	0	M	3	1	0
6	0	3	1	M	0	0
7	3	1	2	0	M	0
dj	0	0	0	0	0	2

Нижняя граница гамильтоновых циклов этого подмножества:

H(1*,2*) = 46 + 2 = 48

Включение ребра (1,2) проводится путем исключения всех элементов 1-ой строки и 2-го столбца, в которой элемент d₂₁ заменяем на М, для исключения образования негамильтонова цикла.

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

После операции приведения сокращенная матрица будет иметь вид:

i j	1	4	6	7	di
3	2	0	0	1	0
4	0	M	3	1	0
6	0	1	M	0	0
7	3	2	0	M	0
dj	0	0	0	0	0

Сумма констант приведения сокращенной матрицы:

∑d_i + ∑d_j = 0

Нижняя граница подмножества (1,2) равна:

H(1,2) = 46 + 0 = 46 ≤ 48

Чтобы исключить подциклы, запретим переходы: (3,2), (3,1).

Поскольку нижняя граница этого подмножества (1,2) меньше, чем подмножества (1*,2*), то ребро (1,2) включаем в маршрут с новой границей H = 46
Шаг №4.

Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).

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

i j	1	4	6	7	di
3	M	0(1)	0(0)	1	0
4	0(1)	M	3	1	1
6	0(0)	1	M	0(1)	0
7	3	2	0(2)	M	2
dj	0	1	0	1	0

d(3,4) = 0 + 1 = 1; d(3,6) = 0 + 0 = 0; d(4,1) = 1 + 0 = 1; d(6,1) = 0 + 0 = 0;

d(6,7) = 0 + 1 = 1; d(7,6) = 2 + 0 = 2;

Наибольшая сумма констант приведения равна (2 + 0) = 2 для ребра (7,6), следовательно, множество разбивается на два подмножества (7,6) и (7*,6*).

Исключение ребра (7,6) проводим путем замены элемента d₇₆ = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (7*,6*), в результате получим редуцированную матрицу.

i j	1	4	6	7	di
3	M	0	0	1	0
4	0	M	3	1	0
6	0	1	M	0	0
7	3	2	M	M	2
dj	0	0	0	0	2

Нижняя граница гамильтоновых циклов этого подмножества:

H(7*,6*) = 46 + 2 = 48

Включение ребра (7,6) проводится путем исключения всех элементов 7-ой строки и 6-го столбца, в которой элемент d₆₇ заменяем на М, для исключения образования негамильтонова цикла.

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

После операции приведения сокращенная матрица будет иметь вид:

i j	1	4	7	di
3	M	0	1	0
4	0	M	1	0
6	0	1	M	0
dj	0	0	1	1