Эксперт по сдаче вступительных испытаний в ВУЗах
Составить математическую модель и найти оптимальный план назначений в задаче о назначениях, заданной таблицей.
Прибыль от назначения i-кандидата на j-должность:
| |
Должности |
| j=1 |
j=2 |
j=3 |
| кандидаты |
i=1 |
3 |
7 |
5 |
| i=2 |
2 |
4 |
4 |
| i=3 |
4 |
7 |
2 |
Решение
1) Составим математическую модель задачи.
По исходным данным задачи имеются три кандидата и три должности. Следовательно, модель исходной задачи является закрытой.
Обозначим через х
ij – назначение i-го кандидата на j-ю должность. Переменные x
ij могут принимать лишь одно из двух значений 0 или 1:
Занесем данные в таблицу:
| Должности
Кандидаты |
1 |
2 |
3 |
Количество должностей, на которые назначен кандидат |
| 1 |
3 |
7 |
5 |
1 |
| 2 |
2 |
4 |
4 |
1 |
| 3 |
4 |
7 |
2 |
1 |
| Количество кандидатов, назначенных на должность |
1 |
1 |
1 |
|
Тогда суммарная прибыль от назначения кандидатов на должности F(x) составят:
Составим систему ограничений:
а) каждый кандидат может быть назначен на одну должность:
б) на каждую должность может быть назначен только один кандидат:
в) Переменные х
ij являются булевыми значениями.
Математическая модель представленной задачи составлена.
2) Для решения задачи используем венгерский метод.
Шаг 1. Модифицируем исходную матрицу: из каждого значения матрицы вычитаем максимальное значение матрицы (max = 7). Полученное значение берем по модулю:
| |
Должности |
| j=1 |
j=2 |
j=3 |
| кандидаты |
i=1 |
4 |
0 |
2 |
| i=2 |
5 |
3 |
3 |
| i=3 |
3 |
0 |
5 |
Шаг 2. Проводим редукцию матрицы по строкам. В результате в полученной матрице в каждой строке будет как минимум один ноль:
| |
Должности |
min |
| j=1 |
j=2 |
j=3 |
| кандидаты |
i=1 |
4 |
0 |
2 |
0 |
| i=2 |
5 |
3 |
3 |
3 |
| i=3 |
3 |
0 |
5 |
0 |
Проводим редукцию матрицы по столбцам. В результате в полученной матрице в каждом столбце будет как минимум один ноль:
| |
Должности |
| j=1 |
j=2 |
j=3 |
| кандидаты |
i=1 |
4 |
0 |
2 |
| i=2 |
2 |
0 |
0 |
| i=3 |
3 |
0 |
5 |
| min |
2 |
0 |
0 |
После вычитания минимальных элементов получаем полностью редуцированную матрицу:
| |
Должности |
| j=1 |
j=2 |
j=3 |
| кандидаты |
i=1 |
2 |
0 |
2 |
| i=2 |
0 |
0 |
0 |
| i=3 |
1 |
0 |
5 |
Шаг 3. Проводим поиск допустимого решения, для которого все назначения имеют нулевую стоимость.
Фиксируем нулевое значение в клетках (1, 2), (2, 1). Другие нули в данных столбцах и строках вычеркиваем. В итоге получаем следующую матрицу:
| |
Должности |
| j=1 |
j=2 |
j=3 |
| кандидаты |
i=1 |
2 |
0 |
2 |
| i=2 |
0 |
0 |
0 |
| i=3 |
1 |
0 |
5 |
Поскольку расположение нулевых элементов в матрице не позволяет образовать систему из 3-х независимых нулей (в матрице их только 2), то решение недопустимое.
Проводим модификацию матрицы. Вычеркиваем строки и столбцы с возможно большим количеством нулевых элементов: строку 2, столбец 2. Получаем сокращенную матрицу (элементы выделены):
| |
Должности |
| j=1 |
j=2 |
j=3 |
| кандидаты |
i=1 |
2 |
0 |
2 |
| i=2 |
0 |
0 |
0 |
| i=3 |
1 |
0 |
5 |
Минимальный элемент сокращенной матрицы (min = 1) вычитаем из всех ее элементов. Затем складываем минимальный элемент с элементами, расположенными на пересечениях вычеркнутых строк и столбцов:
| |
Должности |
| j=1 |
j=2 |
j=3 |
| кандидаты |
i=1 |
1 |
0 |
1 |
| i=2 |
0 |
1 |
0 |
| i=3 |
0 |
0 |
4 |
Возвращаемся к шагу 2.
Шаг 2. Методом проб и ошибок проводим поиск допустимого решения, для которого все назначения имеют нулевую стоимость. В итоге получаем следующую матрицу:
| |
Должности |
| j=1 |
j=2 |
j=3 |
| кандидаты |
i=1 |
1 |
0 |
1 |
| i=2 |
0 |
1 |
0 |
| i=3 |
0 |
0 |
4 |
Количество найденных нулей равно k = 3. Полученное распределение является оптимальным, поскольку в каждом столбце и в каждой строке находится ровно один отмеченный ноль.
Определим максимальную прибыль:
C
max = 4 + 7 + 4 = 15.
Ответ. Оптимальный план назначений:
Согласно оптимальному плану необходимо:
— кандидата №1 назначить на должность №2;
— кандидата №2 назначить на должность №3;
— кандидата №3 назначить на должность №1.
При использовании данного плана назначений кандидатов на должности суммарная прибыль будет максимальной и составит 15 единиц.
Ссылка на первоисточник:
https://umney.ru/
