Задача о назначениях. Нахождение максимальной прибыли
Типичное задание:Компании нужно направить коммивояжеров в новые рынки сбыта. Имеется три вакансии и четыре кандидата. Результат назначения кандидата на определенное место определяется ожидаемым увеличением прибыли. Прибыль, которую может дать кандидат, работая на той или иной территории, показана в таблице.
Исходная матрица имеет вид:
| 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
Перейти к онлайн решению своей задачи
Решение задачи о назначении на максимум
Распределить производство трех видов товара Т1, Т2, Т3 среди пяти предприятий П1, П2, П3, П4, П5 с целью получения максимальной прибыли от продажи товаров по следующим данным:Издержки производства cij единицы товара
|
|
П1 |
П2 |
П3 |
П4 |
П5 |
|
Т1 |
20 |
25 |
40 |
15 |
35 |
|
Т2 |
10 |
30 |
5 |
35 |
35 |
|
Т3 |
5 |
10 |
2 |
5 |
10 |
Затраты по сбыту dij единицы товара
|
|
П1 |
П2 |
П3 |
П4 |
П5 |
|
Т1 |
20 |
50 |
20 |
10 |
15 |
|
Т2 |
10 |
80 |
10 |
35 |
50 |
|
Т3 |
5 |
5 |
5 |
15 |
5 |
Годовой спрос и цена товара
|
|
Спрос, Qi |
Цена, Pi |
|
Т1 |
40000 |
60 |
|
Т2 |
200000 |
55 |
|
Т3 |
60000 |
40 |
Решение:
Экономико-математическая постановки задачи. Расчет прибыли для каждой пары товара-производитель Ti, Пi определяем по следующей модели:
|
|
П1 |
П2 |
П3 |
П4 |
П5 |
|
Т1 |
20 |
-15 |
0 |
35 |
10 |
|
Т2 |
35 |
-55 |
40 |
-15 |
-30 |
|
Т3 |
30 |
25 |
33 |
20 |
25 |
Формируем матрицу годовой прибыли с учетом спроса Qi.
|
|
П1 |
П2 |
П3 |
П4 |
П5 |
|
Т1 |
800 |
-600 |
0 |
1400 |
400 |
|
Т2 |
7000 |
-11000 |
8000 |
-3000 |
-6000 |
|
Т3 |
1800 |
1500 |
1980 |
1200 |
1500 |
Полученные данные обрабатываем с помощью сервиса Задача о назначениях. Выбираем количество столбцов равное 5, количество строк - 3. Заполняем матрицу Hij. В качестве целевой функции выбираем Максимальная прибыль.