Задача о назначениях. Нахождение максимальной прибыли
Типичное задание:Компании нужно направить коммивояжеров в новые рынки сбыта. Имеется три вакансии и четыре кандидата. Результат назначения кандидата на определенное место определяется ожидаемым увеличением прибыли. Прибыль, которую может дать кандидат, работая на той или иной территории, показана в таблице.
Исходная матрица имеет вид:
| 5 | 5 | M | 2 | 2 |
| 7 | 4 | 2 | 3 | 1 |
| 9 | 3 | 5 | M | 2 |
| 7 | 2 | 6 | 7 | 8 |
Решение получаем через калькулятор.
Модифицируем матрицу умножением всех элементов на (-1) и затем сложением их с максимальным элементом матрицы (9) так, чтобы матрица не содержала бы отрицательных элементов:
| 4 | 4 | M | 7 | 7 |
| 2 | 5 | 7 | 6 | 8 |
| 0 | 6 | 4 | M | 7 |
| 2 | 7 | 3 | 2 | 1 |
Для устранения дисбаланса добавляем дополнительные строки.
1. Проводим редукцию матрицы по строкам. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.
| 0 | 0 | M | 3 | 3 | 4 |
| 0 | 3 | 5 | 4 | 6 | 2 |
| 0 | 6 | 4 | M | 7 | 0 |
| 1 | 6 | 2 | 1 | 0 | 1 |
| 0 | 0 | 0 | 0 | 0 | 0 |
Затем такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент:
| 0 | 0 | M | 3 | 3 |
| 0 | 3 | 5 | 4 | 6 |
| 0 | 6 | 4 | M | 7 |
| 1 | 6 | 2 | 1 | 0 |
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 0 |
После вычитания минимальных элементов получаем полностью редуцированную матрицу.
2. Методом проб и ошибок проводим поиск допустимого решения, для которого все назначения имеют нулевую стоимость.
[0] |
[-0-] |
M |
3 |
3 |
[-0-] |
3 |
5 |
4 |
6 |
[-0-] |
6 |
4 |
M |
7 |
1 |
6 |
2 |
1 |
[-0-] |
[-0-] |
[-0-] |
[-0-] |
[-0-] |
[0] |
Поскольку расположение нулевых элементов в матрице не позволяет образовать систему из 5-х независимых нулей (в матрице их только 2), то решение недопустимое .
3. Проводим модификацию матрицы. Вычеркиваем строки и столбцы с возможно большим количеством нулевых элементов: строку 5, столбец 1, строку 1, столбец 5.
Получаем сокращенную матрицу (элементы выделены):
0 |
0 |
M |
3 |
3 |
0 |
3 |
5 |
4 |
6 |
0 |
6 |
4 |
M |
7 |
1 |
6 |
2 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
Минимальный элемент сокращенной матрицы (1) вычитаем из всех ее элементов:
0 |
0 |
M |
3 |
3 |
0 |
2 |
4 |
3 |
6 |
0 |
5 |
3 |
M |
7 |
1 |
5 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
Затем складываем минимальный элемент с элементами, расположенными на пересечениях вычеркнутых строк и столбцов:
1 |
0 |
M |
3 |
4 |
0 |
2 |
4 |
3 |
6 |
0 |
5 |
3 |
M |
7 |
1 |
5 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
1. Проводим редукцию матрицы по строкам. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.
1 |
0 |
M |
3 |
4 |
0 |
0 |
2 |
4 |
3 |
6 |
0 |
0 |
5 |
3 |
M |
7 |
0 |
1 |
5 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
Затем такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент:
1 |
0 |
M |
3 |
4 |
0 |
2 |
4 |
3 |
6 |
0 |
5 |
3 |
M |
7 |
1 |
5 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
После вычитания минимальных элементов получаем полностью редуцированную матрицу.
2. Методом проб и ошибок проводим поиск допустимого решения, для которого все назначения имеют нулевую стоимость.
1 |
[0] |
M |
3 |
4 |
[0] |
2 |
4 |
3 |
6 |
[-0-] |
5 |
3 |
M |
7 |
1 |
5 |
1 |
[-0-] |
[0] |
1 |
[-0-] |
[-0-] |
[0] |
1 |
Поскольку расположение нулевых элементов в матрице не позволяет образовать систему из 5-х независимых нулей (в матрице их только 4), то решение недопустимое .
3. Проводим модификацию матрицы. Вычеркиваем строки и столбцы с возможно большим количеством нулевых элементов: строку 5, столбец 1, строку 4, столбец 2.
Получаем сокращенную матрицу (элементы выделены):
1 |
0 |
M |
3 |
4 |
0 |
2 |
4 |
3 |
6 |
0 |
5 |
3 |
M |
7 |
1 |
5 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
Минимальный элемент сокращенной матрицы (3) вычитаем из всех ее элементов:
1 |
0 |
M |
0 |
1 |
0 |
2 |
1 |
0 |
3 |
0 |
5 |
0 |
M |
4 |
1 |
5 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
Затем складываем минимальный элемент с элементами, расположенными на пересечениях вычеркнутых строк и столбцов:
1 |
0 |
M |
0 |
1 |
0 |
2 |
1 |
0 |
3 |
0 |
5 |
0 |
M |
4 |
4 |
8 |
1 |
0 |
0 |
4 |
3 |
0 |
0 |
1 |
1. Проводим редукцию матрицы по строкам. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.
1 |
0 |
M |
0 |
1 |
0 |
0 |
2 |
1 |
0 |
3 |
0 |
0 |
5 |
0 |
M |
4 |
0 |
4 |
8 |
1 |
0 |
0 |
0 |
4 |
3 |
0 |
0 |
1 |
0 |
Затем такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент:
1 |
0 |
M |
0 |
1 |
0 |
2 |
1 |
0 |
3 |
0 |
5 |
0 |
M |
4 |
4 |
8 |
1 |
0 |
0 |
4 |
3 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
После вычитания минимальных элементов получаем полностью редуцированную матрицу.
2. Методом проб и ошибок проводим поиск допустимого решения, для которого все назначения имеют нулевую стоимость.
1 |
[0] |
M |
[-0-] |
1 |
[-0-] |
2 |
1 |
[0] |
3 |
[0] |
5 |
[-0-] |
M |
4 |
4 |
8 |
1 |
[-0-] |
[0] |
4 |
3 |
[0] |
[-0-] |
1 |
В результате получаем эквивалентную матрицу Сэ:
1 |
0 |
M |
0 |
1 |
0 |
2 |
1 |
0 |
3 |
0 |
5 |
0 |
M |
4 |
4 |
8 |
1 |
0 |
0 |
4 |
3 |
0 |
0 |
1 |
4. Методом проб и ошибок определяем матрицу назначения Х, которая позволяет по аналогично расположенным элементам исходной матрицы (в квадратах) вычислить максимальное значение прибыли.
1 |
[0] |
M |
[-0-] |
1 |
[-0-] |
2 |
1 |
[0] |
3 |
[0] |
5 |
[-0-] |
M |
4 |
4 |
8 |
1 |
[-0-] |
[0] |
4 |
3 |
[0] |
[-0-] |
1 |
Cmax = 3 + 5 + 9 + 8 + 0 = 25
Альтернативный вариант №2.
1 |
[0] |
M |
[-0-] |
1 |
[0] |
2 |
1 |
[-0-] |
3 |
[-0-] |
5 |
[0] |
M |
4 |
4 |
8 |
1 |
[-0-] |
[0] |
4 |
3 |
[-0-] |
[0] |
1 |
Cmax = 8 + 5 + 7 + 5 + 0 = 25