Лабораторная работа №3 - Задачи дискретного программирования и методы их решения
Подождите немного. Документ загружается.
МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ
УФИМСКИЙ ГОСУДАРСТВЕННЫЙ АВИАЦИОНЫЙ ТЕХНИЧЕСКИЙ
УНИВЕРСИТЕТ
Кафедра АСУ
Задачи дискретного программирования и методы
их решения
«Системный анализ и ИСО»
Выполнил: студент гр. АСОИ-335
Проверил: Бабак С. Ф.
УФА 2010
Задача коммивояжера
Задание:
Решить задачу коммивояжера по следующим данным:
1 2 3 4 5 6
1 - 41 27 54 46 5
2 42 - 11 32 58 21
3 36 5 - 33 22 33
4 46 24 59 - 49 59
5 48 58 11 44 - 47
6 26 50 35 19 27 -
Решение:
Приведем данную матрицу по строкам и по столбцам, получим:
1 2 3 4 5 6 75
1 - 36 22 49 41 0 5
2 31 - 0 21 47 10 11
3 31 0 - 28 17 28 5
4 22 0 35 - 25 35 24
5 37 47 0 33 - 36 11
6 7 31 16 0 8 - 19
1 2 3 4 5 6
1 - 36 22 49 33 0
2 24 - 0 21 39 10
3 24 0 - 28 9 28
4 15 0 35 - 17 35
5 30 47 0 33 - 36
6 0 31 16 0 0 -
15 7 0 0 0 8 0
Сложив приведение по строкам и по столбцам, получим: 75 + 15= 90.
Следовательно, Min оценка = 90.
Оценим нули в полученной матрице:
1 2 3 4 5 6 1 2 3 4 5
1 - 36 22 49 33
0/32
2 24 - 0 21 39
2 24 -
0/10
21 39 10 3 24
0
- 28 9
3 24
0/9
- 28 9 28 4 15 0 35 - 17
4 15
0/15
35 - 17 35 5 30 47 0 33 -
5 30 47
0/30
33 - 36 6 0 31 16 0 0/9
6
0/15
31 16
0/21 0/9
-
Max оценка = 32.
Разбиваем на 1,6 и not 1,6. not 1,6 = 122
Минор по 1,6.
Вводим запрет на 6,1.
Оценим нули в полученной матрице:
1 2 3 4 5 1 2 4 5
2 9 -
0/9
21 39 2 9 - 21 39
3 9
0/9
- 28 9 3 9 0/9 28 9
4 0
0
35 - 17 4 0 0 - 17
5 30 47
0/30
33 - 6 0 31 0/21 0/9
6
0
31 16
0/21 0/9
15 15
Max оценка = 30.
Разбиваем на 5,3 и not 5,3. 1,6 = 90+15=105
Минор по 5,3. not 5,3 = 105+30=135
Вводим запрет на 3,5.
Приводим матрицу по 1 столбцу.
Оценим нули в полученной матрице:
1 2 4 5 9
2 0/12 - 12 30 9
3 9 0/9 28 9
4 0 0 - 17
6 0 31 0/12 0/17
1 2 4
2 0 - 12
3 9 0 28
4 0 0 -
Max оценка = 17.
Разбиваем на 6,5 и not 6,5. 5,3 = 105+9=114
Минор по 6,5. not 6,5 = 114+17=131
Вводим запрет на 3,1.
Приводим матрицу по 2 строке.
Оценим нули в полученной матрице:
1 2 4
2 0 - 0/16
3 9 0/16 16
4 0 0 -
12 0 0 12
Max оценка = 16.
Разбиваем на 2,4 и not 2,4. 6,5 = 114+12=126
Минор по 2,4. not 2,4 = 126+12=138
Вводим запрет на 4,2
Приводим матрицу по 4 столбцу.
Получим: (not 1,6 = 122) < (6,5 = 126)
Переходим к задаче:
1 2 3 4 5 6
1 - 41 27 54 46 -
2 42 - 11 32 58 21
3 36 5 - 33 22 33
4 46 24 59 - 49 59
5 48 58 11 44 - 47
6 26 50 35 19 27 -
Приведем данную матрицу по строкам и по столбцам, получим:
1 2 3 4 5 6 97 1 2 3 4 5 6
1 - 14 0 27 19 - 27 1 - 14 0 27 11 -
2 31 - 0 21 47 10 11 2 24 - 0 21 39 0
3 31 0 - 28 17 28 5 3 24 0 - 28 9 18
4 22 0 35 - 25 35 24 4 15 0 35 - 17 25
5 37 47 0 33 - 36 11 5 30 47 0 33 - 26
6 7 31 16 0 8 - 19 6 0 31 16 0 0 -
25 7 0 0 0 8 10
Сложив приведение по строкам и по столбцам, получим: 97 + 25= 122.
Оценим нули в полученной матрице:
1 2 3 4 5 6 1 2 4 5 6 11
1 - 14
0/11
27 11
-
1 - 3 16 0 - 11
2 24 -
0
21 39
0/18
2 24 - 21 39 0 0
3 24
0/9
- 28 9 18 3 24 0 28 9 18 0
4 15
0/15
35 - 17 25 4 15 0 - 17 25 0
5 30 47
0/30
33 - 26 6 0 31 0 0 - 0
6
0/15
31 16
0/21 0/9
-
Max оценка = 30.
Разбиваем на 5,3 и not 5,3. not 5,3 = 152
Минор по 5,3. 5,3 = 122+11=133
Вводим запрет на 3,5.
(5,3 = 133)>(6,5=126)
Переходим к предыдущей задаче, где мы прервались:
1 2 4 1 2
2 0 - 0/16 3 9 0
3 9 0/16 16 4 0 0
4 0 0 -
12 12
В итоге получим дерево ветвлений и длин путей:
По этому дереву можно определить, что оптимальным маршрутом является
последовательность:
1 6 5 3 2 4 1 и его длина равна 126.
Вывод:
Задача решена по методу «ветвей и границ». Путь является оптимальным и
наикротчайшим.
Задача о назначениях
Задание:
Решить задачу по следующим данным:
1 2 3 4 5 6 7
1 6 5 9 10 7 12 8
2 9 7 11 6 8 11 10
3 8 10 7 8 10 7 4
4 5 6 10 5 6 11 12
5 4 9 8 9 4 1 2
6 5 6 10 11 10 12 5
7 4 11 5 4 5 12 13
Необходимо найти наиболее высокую производительность работников, выполняющих
ту или иную работу.
i – работник; j – работа; C
ij
– производительность
Все
1,6 1,6
4,1
5,3
5,3
6,5
6,5
2,4 2,4
3,2
90
122105
114
135
126131
138
126
126
126
5,3
5,3
152
133
Решение:
Приведем задачу максимизации к задаче минимизации:
1 2 3 4 5 6 7
1 -6 -5 -9 -10 -7 -12 -8
2 -9 -7 -11 -6 -8 -11 -10
3 -8 -10 -7 -8 -10 -7 -4
4 -5 -6 -10 -5 -6 -11 -12
5 -4 -9 -8 -9 -4 -1 -2
6 -5 -6 -10 -11 -10 -12 -5
7 -4 -11 -5 -4 -5 -12 -13
Приведем данную матрицу по строкам и по столбцам, получим:
1 2 3 4 5 6 7 -79
1 6 7 3 2 5 0 4 -12
2 2 4 0 5 3 0 1 -11
3 2 0 3 2 0 3 6 -10
4 7 6 2 7 6 1 0 -12
5 5 0 1 0 5 8 7 -9
6 7 6 2 1 2 0 7 -12
7 9 2 8 9 8 1 0 -13
1 2 3 4 5 6 7
1 4 7 3 2 5 0 4
2 0 4 0 5 3 0 1
3 0 0 3 2 0 3 6
4 5 6 2 7 6 1 0
5 3 0 1 0 5 8 7
6 5 6 2 1 2 0 7
7 7 2 8 9 8 1 0
2 2 0 0 0 0 0 0
Сложив приведение по строкам и по столбцам, получим: -79 + 2 = -77.
Следовательно, Min оценка = -77.
Оценим нули в полученной матрице: