 |
|
Определение назначения и модифицирование редукцируемой матрицы
Преобразование строк и столбцов матрицы (редукция строк и столбцов)
Ежемесячная зарплата претендента
| Должности | ||||||
| Претенденты | ||||||
F(x) -> min
| Должности | min | ||||||
| Претенденты | |||||||
| Должности | ||||||
| Претенденты | ||||||
Значения минимальных элементов по строкам 1-4 соответственно равны
Значения минимальных элементов по столбцам 1-4 соответственно равны
Проводим модификацию редукцируемой матрицы
Определение назначения и модифицирование редукцируемой матрицы
Модифицируем редукцируемую матрицу. Для этого:
А) Вычёркиваем все строки и столбцы, содержащие максимальное количество нулей. Затем, двигаясь по строкам сверху вниз и по столбцам слева направо вычёркиваем строки и столбцы, содержащие нулевые элементы.
| Должности | ||||||
| Претенденты | ||||||
| Должности | |||||
| Претенденты | |||||
В полученной сокращённой матрице выбираем минимальный элемент и вычитаем его из всех не вычеркнутых элементов
Min = 50
| Должности | |||||
| Претенденты | |||||
Прибавляем минимальный элемент к значениям, расположенным на пересечении строк и столбцов.
| Должности | ||||||
| Претенденты | ||||||
Количество зачёркнутых строк и столбцов = n (5=5), следовательно получено полное назначение
Проверяем решение на оптимальность:
| Должности | ||||||
| Претенденты | ||||||
| | ||||||
| | ||||||
| | ||||||
| |
Получили пять независимых нулей, следовательно получили назначение
| Должности | ||||||
| Претенденты | ||||||
F(x) = 700 + 950 + 550 + 900 + 600 = 3700
Таким образом яопределил назначение претендентов на работу на основе «зарплаты» F(x) = 3700
Задача на нахождение назначения претендента по «Оценке»
Оценка претендента за месяц
| Должности | ||||||
| Претенденты | ||||||
F(x) -> max
Поскольку F(x) ->max, умножаем на -1 все элементы матрицы стоимостей и складываем их с достаточно большим числом – 25
Получаем новую матрицу стоимостей:
| Должности | ||||||
| Претенденты | ||||||
Далее решаем, как задачу на min.
Преобразование строк и столбцов матрицы (редукция строк и столбцов)
| Должности | min | ||||||
| Претенденты | |||||||
| Должности | ||||||
| Претенденты | ||||||
| Должности | ||||||
| Претенденты | ||||||
| min |
| Должности | ||||||
| Претенденты | ||||||
Определение назначения и модифицирование редукцируемой матрицы
| Должности | ||||||
| Претенденты | ||||||
Так как в каждом столбце и в каждой строке редукцируемой матрице можно выбрать по одному нулевому элементу, то полученное решение будет оптимальным назначением.
Модифицируем редукцируемую матрицу. Для этого:
А) Вычёркиваем все строки и столбцы, содержащие максимальное количество нулей. Затем, двигаясь по строкам сверху вниз и по столбцам слева направо вычёркиваем строки и столбцы, содержащие нулевые элементы.
| Должности | ||||||
| Претенденты | ||||||
| Должности | ||||||
| Претенденты | ||||||
В полученной сокращённой матрице выбираем минимальный элемент и вычитаем его из всех не вычеркнутых элементов
Min = 1
| Должности | ||||||
| Претенденты | ||||||
Прибавляем минимальный элемент к значениям, расположенным на пересечении строк и столбцов.
| Должности | ||||||
| Претенденты | ||||||
Количество зачёркнутых строк и столбцов ≠n (4≠5), следовательнополное назначение не получено. Повторяем операцию
| Должности | ||||
| Претенденты | ||||
Min = 3
| Должности | ||||
| Претенденты | ||||
Прибавляем минимальный элемент к значениям, расположенным на пересечении строк и столбцов.
| Должности | ||||||
| Претенденты | ||||||
Количество зачёркнутых строк и столбцов = n (5=5), следовательно получено полное назначение
Проверяем решение на оптимальность:
| Должности | ||||||
| Претенденты | ||||||
В данном случае, мы получили одно очевидное назначение, далее в каждой строке и каждом столбце есть хотя бы два нулевых значения, следовательно, задачу можно решать несколькими способами.
Способ №1
| Должности | ||||||
| Претенденты | | |||||
| | | | ||||
| | ||||||
| |
F(x) = 7+7+0+0+1 = 15
Способ №2
| Должности | ||||||
| Претенденты | | |||||
| | | | ||||
| | ||||||
| |
F (x) = 4+11+0+0+0 = 15
Способ №3
| Должности | ||||||
| Претенденты | | |||||
| | | |||||
| | ||||||
| |
F(x) = 4+10+0+0+1 = 15
Дальнейшие пути решения задачи будут идентичны предыдущим
Ответ F(x) = 15
Вывод: Таким образом, я определила назначение на работу на основе «оценки». F(x) = 15