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

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

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

∑d_i + ∑d_j = 1

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

H(7,6) = 46 + 1 = 47 ≤ 48

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

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

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

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

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

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

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

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


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

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

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

H(3*,4*) = 47 + 1 = 48

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

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

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

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

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

∑d_i + ∑d_j = 0

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

H(3,4) = 47 + 0 = 47 ≤ 48
Поскольку нижняя граница этого подмножества (3,4) меньше, чем подмножества (3*,4*), то ребро (3,4) включаем в маршрут с новой границей H = 47

В соответствии с этой матрицей включаем в гамильтонов маршрут ребра (4,7) и (6,1).

Вывод:

В результате по дереву ветвлений гамильтонов цикл образуют ребра:

(5,3), (3,4), (4,7), (7,6), (6,1), (1,2), (2,5),

Cуммарное время переналадок

F = 47