Тема 10. Алгоритмы комбинаторной оптимизации

комбинаторной оптимизации
Шевченко А. В.

комбинаторной оптимизации
Пример 1. Производство краски
В производстве краски при смене цвета

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

комбинаторной оптимизации
Пример 2. Координатно-пробивной пресс со сменным инструментом
При изготовлении деталей

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

коммивояжёра
Требуется объехать все города, побывав в каждом только один раз,

и затратив минимальное время на весь путь.

В.
Задача коммивояжёра. Структура данных
Cij = расстояние от i до j
1
3
2
5
4
6
1
2
3
4
5
6
1
6
4
8
7
14
2
6
7
11
7
10
3
4
7
4
3
10
4
8
11
4
5
11
5
7
7
3
5
7
6
14
10
10
11
7
Cij

= Cji

Cij  Cji

Симметричная задача

Несимметричная задача

10. Алгоритмы и структуры данных (окончание)
6
Шевченко А. В.
Задача коммивояжёра. Точное

решение

1

3

2

5

4

6

1

2

3

4

5

6

1

6

4

8

7

14

2

6

7

11

7

10

3

4

7

4

3

10

4

8

11

4

5

11

5

7

7

3

5

7

6

14

10

10

11

7

Число вариантов в несимметричной задаче (n-1)!

5!

~102

10!

~106

15!

~1012

20!

~1018

25!

~1025

30!

~1032

35!

~1040

40!

~1047

45!

~1056

50!

~1064

Решение 1-2-6-5-4-3-1, расстояние 36

комбинаторной оптимизации
7
Шевченко А. В.
Задача коммивояжёра. Быстрое решение
1
3
2
5
4
6
1
2
3
4
5
6
1
6
4
8
7
14
2
6
7
11
7
10
3
4
7
4
3
10
4
8
11
4
5
11
5
7
7
3
5
7
6
14
10
10
11
7
Решение 1-3-5-4-2-6-1, расстояние 47
На

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

коммивояжёра. Метод ветвей и границ
Приведение по строкам
Cij
1
2
3
4
5
6
1
6
4
8
7
14
2
6
7
11
7
10
3
4
7
4
3
10
4
8
11
4
5
11
5
7
7
3
5
7
6
14
10
10
11
7
Cij
1
2
3
4
5
6
1
0
1
4
4
7
2
2
4
7
4
3
3
0
1
0
0
3
4
4
5
1
2
4
5
3
1
0
1
0
6
10
4
7
7
4
4
6
3
4
3
7
Cij
1
2
3
4
5
6
1
0
1
4
4
7
2
0
2
5
2
1
3
0
1
0
0
3
4
3
4
0
1
3
5
3
1
0
1
0
6
6
0
3
3
0
4
6
3
4
3
7
0
2
0
1
0
4
Приведение

по столбцам

27

7

34

коммивояжёра. Метод ветвей и границ
Оценка нулей
Cij
1
2
3
4
5
6
1
0
1
4
4
7
2
0
2
5
2
1
3
0
1
0
0
3
4
3
4
0
1
3
5
3
1
0
1
0
6
6
0
3
3
0
Отказ от пути 1-2

увеличит расстояние на 1 (1+0)

Cij

1

2

3

4

5

6

1

01

1

4

4

7

2

01

2

5

2

1

3

0

1

01

0

3

4

3

4

01

1

3

5

3

1

0

1

01

6

6

0

3

3

0

Выбирается первая из максимальных оценок

Все множество путей делится на два класса - включающие путь 1-2 и остальные

коммивояжёра. Метод ветвей и границ
Cij
1
2
3
4
5
6
1
01
1
4
4
7
2
01
2
5
2
1
3
0
1
01
0
3
4
3
4
01
1
3
5
3
1
0
1
01
6
6
0
3
3
0
Cij
2
3
4
5
6
1
01
0
3
3
6
3
1
0
0
3
4
4
0
1
3
5
1
0
1
0
6
0
3
3
0
1
все
1, 2
___
1, 2
34
35
35
Ветвление

коммивояжёра. Метод ветвей и границ
Cij
2
3
4
5
6
1
03
3
3
6
3
1
01
0
3
4
4
01
1
3
5
1
0
1
03
6
01
3
3
0
все
1, 2
___
1, 2
34
35
35
3, 1
36
___
3, 1
38
Cij

2

4

5

6

3

1

0

0

3

4

3

0

2

5

1

1

0

6

0

3

0

1

коммивояжёра. Метод ветвей и границ
все
1, 2
___
1, 2
34
35
35
3, 1
36
___
3, 1
38
Cij
2
4
5
6
3
01
0
3
4
3
02
2
5
1
1
03
6
01
3
0
Cij

2

4

5

3

03

0

4

3

03

6

06

3

6, 5

36

___
6, 5

39

Cij

4

5

3

0

4

0

2, 6

36

___
2, 6

39

5, 4

36

4, 3

36

Конец ветви

коммивояжёра. Метод ветвей и границ
Cij
1
2
3
4
5
6
1
01
1
4
4
7
2
01
2
5
2
1
3
03
1
01
0
3
4
3
4
01
1
3
5
3
1
0
1
01
6
6
0
3
3
0
Cij
2
3
4
5
6
1
0
1
4
4
7
2
1
4
1
0
4
4
0
1
3
5
1
0
1
0
6
0
3
3
0
1
все
___
1, 2
34
35
___
1, 3
38
1, 3
36
Проверка

альтернативных вариантов

коммивояжёра. Метод ветвей и границ
Cij
1
2
3
4
5
6
1
6
4
8
7
14
2
6
7
11
7
10
3
4
7
4
3
10
4
8
11
4
5
11
5
7
7
3
5
7
6
14
10
10
11
7
1
3
2
5
4
6
Решение 1-2-6-5-4-3-1, расстояние 36

программирование
Метод динамического программирования состоит в том, что оптимальное управление строится

постепенно. На каждом шаге оптимизируется управление только этого шага. Вместе с тем на каждом шаге управление выбирается с учетом последствий, так как управление, оптимизирующее целевую функцию только для данного шага, может привести к неоптимальному эффекту всего процесса. Управление на каждом шаге должно быть оптимальным с точки зрения процесса в целом.
Каково бы ни было начальное состояние системы перед очередным шагом, управление на этом этапе выбирается так, чтобы выигрыш на данном шаге плюс оптимальный выигрыш на всех последующих шагах был максимальным.
Ричард Эрнст Беллман (1920 - 1984)

задачи динамического программирования
Оптимизация последовательности работ штамповочной машины Strippit-1250

работы машины
Лазер
Поворотная турель
Лист
Дополнительные столы
Зажимы
Стол
Лист размещается на движущемся столе и крепится

зажимами. Для больших листов могут устанавливаться дополнительные столы

Рабочая позиция

инструмент
Для пробивки отверстий используется пара инструментов - пуансон и матрица.

Для одного пуансона могут применяться разные матрицы. Выбор матрицы зависит от толщины листа. Чем толще лист, тем больше должен быть зазор между пуансоном и матрицей.

Лист

Пуансон

Матрица

Зазор

турель
Пробивной инструмент (пуансоны и матрицы) устанавливается в поворотную турель, имеющую

20 станций (16 нормальных и 4 большие)

оптимизации последовательности заданий
В малосерийном производстве через штамповочную машину за день

проходит до 50 партий изделий (заданий). Для каждого задания требуется установка в турель от 1 до 19 инструментов. Для минимизации общего времени производ-ства требуется подобрать такую последовательность выполнения заданий, при которой время смены инструмента было бы минимальным.

Задание

Общее время производства

Выполнение программы

Смена инструмента

инструмента
Специальные условия
Инструмент
Угол установки
Блокирование
станций
Размер
Специальный
инструмент
Большие
зажимы
Лазер
Лазер
Смена
захвата
Пуансон
Матрицы

алгоритм
Задание
Задание
Лучшее задание
Предыдущее
состояние турели
Последующее
состояние турели
1. Последовательно выполняются N шагов, где N

- число заданий.
2. На каждом шаге из списка оставшихся заданий выбирается лучшее задание.
3. Выбор на основе стоимостной функции для всех комбинаций инструмент - станция.
4. При вычислении стоимостной функции учитывается влияние выбора на оставшиеся задания.
5. Ограничения применяются как можно раньше для снижения размерности задачи.

ограничений
1
2
3
4
5
6
7
8
3 и 5 - срочные задания
6 перед 2
7 перед

6

Станции

Большой инструмент

Малый инструмент

Угол 0°

Угол 45°

Угол 90°

Специальный инструмент

стоимостной функции смены инструмента
Задание
Задание
Инструмент
Бонус
Бонус
Штраф
Стоимостная функция поощряет установку инструмента, который может

быть использован другими заданиями, и наказывает снятие инструмента, для которого еще есть задания.

стоимостной функции для 8 инструментов
Ищется вариант размещения инструментов, который даст

минимальное значение стоимостной функции

Станции

-60

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

И 1

44

-40

36

И 2

40

42

42

40

42

44

44

42

40

42

42

42

40

48

42

И 3

40

42

42

42

40

42

42

42

40

44

-20

44

42

40

40

44

И 4

46

44

28

42

36

42

40

40

И 5

32

28

42

И 6

44

42

48

44

-60

46

42

42

40

42

40

44

И 7

42

42

42

44

42

44

44

42

46

42

42

44

42

44

44

44

И 8

стоимостная функция
Станции
/число инструментов

Дополнительные
столы
Смена зажимов
Защита зажимов
Лазер

Стоимость

решения
Шаг 3
1
2
3
4
5
6
7
8
Шаг 4
1
2
3
4
5
6
7
8
Минимальная стоимость

оптимизации
INIT STATE--------------------------------------------------------------------------------
Punch [ 0 287 292 281 35

302 316 302 44 81 17 316 45 249 14 133 169 323 281 275 ] 0: 0
Matrix [ 0 459 476 442 28 507 535 495 37 78 15 535 43 364 8 134 206 550 442 423 ] 0: 0
Angle [ 0 90 0 0 90 0 0 0 0 0 90 0 90 0 0 0 0 45 0 0 ]


RETOOLING---------------------------------------------------------------------------------
Punch [ 287 91 40 281 138 316 323 302 44 289 17 316 45 249 14 133 169 281 281 275 ] 2: 6
Matrix [ 458 85 35 442 142 531 548 495 37 463 15 535 43 364 8 134 206 440 442 423 ] 2: 6
Angle [ 0 0 0 0 0 90 0 0 0 90 90 0 90 0 0 0 0 45 0 0 ]

Job 15 * * *
Job 14 * * *
Job 16 * * *
Job 17 * * *
Job 18 * * *
Job 19 * * *
Job 20 * * *
Job 4 * * * * *
Job 3 * * *

RETOOLING---------------------------------------------------------------------------------
Punch [ 287 91 40 281 138 316 323 302 44 60 316 139 6 17 14 133 54 297 302 275 ] 1: 7
Matrix [ 458 85 35 440 142 531 548 495 37 53 531 143 2 10 8 134 47 484 495 423 ] 1: 8
Angle [ 0 0 0 0 0 90 0 0 0 0 0 0 0 0 0 0 0 0 90 0 ]

Job 1 * * * * * * * *
Job 2 * * * * *

оптимизации
RETOOLING---------------------------------------------------------------------------------
Punch [ 287 91 40 281 138 316 323

302 44 60 316 139 6 110 14 133 54 297 302 275 ] 0: 1
Matrix [ 458 85 35 440 142 535 550 495 37 53 535 143 2 111 8 134 47 484 495 423 ] 2: 2
Angle [ 0 0 0 0 0 90 0 0 0 0 0 0 0 0 0 0 0 0 90 0 ]

Job 13 * * * *

RETOOLING---------------------------------------------------------------------------------
Punch [ 287 91 40 281 138 316 323 302 44 60 316 139 1 110 14 169 155 35 302 275 ] 1: 3
Matrix [ 458 85 33 440 142 531 550 495 37 53 531 143 2 111 8 206 172 28 495 423 ] 3: 3
Angle [ 0 0 0 0 0 90 0 0 0 0 0 0 0 0 0 0 0 0 90 0 ]

Job 5 *
Job 6 *
Job 7 *
Job 21 * * * *
Job 28 * * * * *
Job 27 * * * * *

RETOOLING---------------------------------------------------------------------------------
Punch [ 287 91 40 281 249 163 323 302 70 60 316 139 1 25 14 169 155 35 302 133 ] 1: 4
Matrix [ 459 85 33 440 364 191 549 495 66 53 531 143 1 21 8 206 173 28 495 134 ] 2: 7
Angle [ 0 0 0 0 90 0 0 0 0 0 0 0 0 0 0 0 0 0 90 0 ]

Job 8 *
Job 9 *
Job 10 * *
Job 11 *
Job 12 *
Job 25 *
Job 24 * * * *
Job 23 * * * * *

оптимизации
RETOOLING---------------------------------------------------------------------------------
Punch [ 287 91 40 281 249 163 323

302 70 60 316 139 1 25 14 169 155 35 302 133 ] 0: 0
Matrix [ 459 85 33 440 364 191 548 495 66 53 531 143 1 21 8 206 173 28 495 134 ] 0: 1
Angle [ 0 0 0 0 90 0 0 0 0 0 0 0 0 0 0 0 0 0 90 0 ]

Job 22 * *

RETOOLING---------------------------------------------------------------------------------
Punch [ 287 64 40 36 26 163 323 264 70 60 284 139 1 45 114 169 155 35 102 107 ] 1: 8
Matrix [ 459 63 33 36 26 191 551 406 66 59 453 143 1 45 115 206 174 28 104 108 ] 1:11
Angle [ 0 0 0 0 0 0 0 90 0 0 0 0 0 0 0 0 0 0 0 0 ]

Job 33 * * *
Job 30 * * * * * * * * * * * * *

RETOOLING---------------------------------------------------------------------------------
Punch [ 287 120 40 36 26 164 323 264 91 144 284 139 1 45 114 169 51 35 102 107 ] 1: 4
Matrix [ 459 120 33 36 26 195 551 406 88 153 453 143 1 45 115 206 50 35 104 108 ] 1: 5
Angle [ 0 0 0 0 0 0 0 90 0 0 0 0 0 0 0 0 0 0 0 0 ]

Job 31 * * * * * * * * * *
Job 34 * * * * * *
Job 32 * * * * * * *

RETOOLING---------------------------------------------------------------------------------
Punch [ 287 120 40 36 105 311 323 127 91 144 284 139 1 45 97 311 51 157 321 112 ] 2: 6
Matrix [ 459 120 39 36 106 523 551 127 88 153 453 145 1 45 98 523 50 177 546 114 ] 2: 8
Angle [ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 90 0 0 0 0 ]

Job 29 * * * * * * * * * * * * * *
Job 26 *