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

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

Сумма констант приведения определяет нижнюю границу H:

H = ∑d_i + ∑d_j

H = 6+7+4+5+6+6+5+1+5+0+1+0+0+0 = 46

Элементы матрицы d_ij соответствуют премени от пункта i до пункта j.
Шаг №1.

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

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

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

d(1,2) = 0 + 0 = 0; d(1,5) = 0 + 0 = 0; d(2,5) = 1 + 0 = 1; d(3,2) = 0 + 0 = 0;

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(4,5) = 0 + 0 = 0; d(5,3) = 1 + 1 = 2; d(6,1) = 0 + 0 = 0; d(6,7) = 0 + 1 = 1;

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

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

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

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

H(5*,3*) = 46 + 2 = 48

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

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

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

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

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

∑d_i + ∑d_j = 0

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

H(5,3) = 46 + 0 = 46 ≤ 48

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

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

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

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

d(1,2) = 0 + 0 = 0; d(1,5) = 0 + 0 = 0; d(2,5) = 1 + 0 = 1; d(3,2) = 0 + 0 = 0;

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

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

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

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

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

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

H(2*,5*) = 46 + 1 = 47