Лабораторная работа №3 - Задачи дискретного программирования и методы их решения
Подождите немного. Документ загружается.
1 2 3 4 5 6 7
1 4 7 3 2 5 0/2 4
2 0 4 0 /1 5 3 0 1
3 0 0 3 2 0/2 3 6
4 5 6 2 7 6 1 0/1
5 3 0 1 0/1 5 8 7
6 5 6 2 1 2 0/1 7
7 7 2 8 9 8 1 0/1
1 2 3 4 5 7 1
2 0 4 0 5 3 1 0
3 0 0 3 2 0 6 0
4 5 6 2 7 6 0 0
5 3 0 1 0 5 7 0
6 4 5 1 0 1 6 1
7 7 2 8 9 8 0 0
Max оценка = 2.
Разбиваем на 1,6 и not 1,6. not 1,6 = -77+2=-75
Минор по 1,6. 1,6=-77+1=-76
Приводим матрицу по 6 строке.
Оценим нули в полученной матрице:
1 2 3 4 5 7 1 2 3 4 5 2
2 0 4 0/1 5 3 1 2 0 4 0 5 3 0
3 0 0 3 2 0/1 6 3 0 0 3 2 0 0
4 5 6 2 7 6 0/2 5 3 0 1 0 5 0
5 3 0 1 0 5 7 6 4 5 1 0 1 0
6 4 5 1 0/1 1 6 7 5 0 6 7 6 2
7 7 2 8 9 8 0/2
Max оценка = 2.
Разбиваем на 4,7 и not 4,7. not 4,7 = -76+2=-74
Минор по 4,7. 4,7 = -76+2=-74
Приводим матрицу по 7 строке.
Получим: (not 1,6 = -75)<(4,7 = -74)
Переходим к задаче:
1 2 3 4 5 6 7
1 -6 -5 -9 -10 -7 - -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 -77 1 2 3 4 5 6 7
1 4 5 1 0 3 - 2 -10 1 4 5 1 0 3 - 2
2 2 4 0 5 3 0 1 -11 2 2 4 0 5 3 0 1
3 2 0 3 2 0 3 6 -10 3 2 0 3 2 0 3 6
4 7 6 2 7 6 1 0 -12 4 7 6 2 7 6 1 0
5 5 0 1 0 5 8 7 -9 5 5 0 1 0 5 8 7
6 7 6 2 1 2 0 7 -12 6 7 6 2 1 2 0 7
7 9 2 8 9 8 1 0 -13 7 9 2 8 9 8 1 0
2 2 0 0 0 0 0 0
Сложив приведение по строкам и по столбцам, получим: -77 + 2 = -75.
Оценим нули в полученной матрице:
1 2 3 4 5 6 7 1 2 3 4 6 7
1 4 5 1 0/2 3 - 2 1 2 5 1 0 - 2
2 2 4 0/1 5 3 0 /1 1 2 0 4 0 5 0 1
3 2 0 3 2 0/2 3 6 4 5 6 2 7 1 0
4 7 6 2 7 6 1 0/1 5 3 0 1 0 8 7
5 5 0 1 0 5 8 7 6 5 6 2 1 0 7
6 7 6 2 1 2 0/1 7 7 7 2 8 9 1 0
7 9 2 8 9 8 1 0/1 2 2 0 0 0 0 0
Max оценка = 2.
Разбиваем на 3,5 и not 3,5. not 3,5 = -75+2=-73
Минор по 3,5. 3,5= -75+2=-73
Приводим матрицу по 6 строке.
(3,5 = -73)>(4,7=-74)
Переходим к предыдущей задаче, где мы прервались:
Оценим нули в полученной матрице:
1 2 3 4 5 1 3 4 5
2 0 4 0 /1 5 3 2 0 0 5 3
3 0 0 3 2 0/1 3 0 3 2 0
5 3 0 1 0 5 5 3 1 0 5
6 4 5 1 0/1 1 6 4 1 0 1
7 5 0/5 6 7 6
Max оценка = 5.
Разбиваем на 7,2 и not 7,2. not 7,2 = -69
Минор по 7,2. 7,2 = -74
Оценим нули в полученной матрице:
1 3 4 5 1 4 5
2 0 0/1 5 3 3 0/3 2 0/1
3 0 3 2 0/1 5 3 0/3 5
5 3 1 0 /1 5 6 4 0/1 1
6 4 1 0 /1 1
Max оценка = 1.
Разбиваем на 2,3 и not 2,3. not 2,3 = - 73
Минор по 2,3. 2,3 = -74
Оценим нули в полученной матрице:
1 4 5 4 5
3 0/3 2 0/1 5 0 4
5 3 0/3 5 6 0 0
6 4 0/1 1 1 0 1
Max оценка = 3.
Разбиваем на 3,1 и not 3,1. not 3,1 = -71
Минор по 3,1. 3,1 = -73
Приводим матрицу по 5 столбцу.
Получим: (not 4,7 = -74)<(3,1 = -73)
Переходим к задаче:
1 2 3 4 5 7
2 0 4 0 5 3 1
3 0 0 3 2 0 6
4 5 6 2 7 6 -
5 3 0 1 0 5 7
6 4 5 1 0 1 6
7 7 2 8 9 8 0
Приведем данную матрицу по 4 строке и оценим нули:
1 2 3 4 5 7 2
2 0 4 0 5 3 1 0
3 0 0 3 2 0/1 6 0
4 3 4 0/3 5 4 - 2
5 3 0 1 0 5 7 0
6 4 5 1 0/1 1 6 0
7 7 2 8 9 8 0/3 0
Max оценка = 3.
Разбиваем на 4,3 и not 4,3. not 4,3 = -71
Минор по 4,3. 4,3 = -72
(4,3 = -72)>(3,1=-73)
Переходим к предыдущей задаче, где мы прервались:
Оценим нули в полученной матрице:
4 5 5
5 0/4 4 6 0
6 0 0/4
В итоге получим дерево ветвлений:
1 – 6
4 – 7
7 – 2
2 – 3
3 – 1
5 – 4
6 – 5
Итоговая производительность:
C
ij
= 73 (при переходе к задаче максимизации домножаем на -1)
Вывод:
Задача решена по методу «ветвей и границ». Наиболее высокая производительность
работников, выполняющих ту или иную работу, равна 73.
-77
4,7
-74
4,7
4,7
-72
1,6
1,6
5,4
4,7
7,2
7,2
2,3 2,3
3,1
-75
-76
-74
-74
-69
-73
-74
-73
-73
3,1
-71
5,4
-69
6,5
-73
3,5
3,5
-73 -73
Все
-71