Создан заказ №2362715
27 октября 2017
Тема «Решение задачи о назначениях венгерским методом» Отдел кадров предприятия устроил конкурсный набор специалистов на две вакантные должности
Как заказчик описал требования к работе:
Предмет: Математическое моделирование в экономике. Необходимо решить 2 задачи.
Фрагмент выполненной работы:
Тема «Решение задачи о назначениях венгерским методом»
Отдел кадров предприятия устроил конкурсный набор специалистов на две вакантные должности. На эти новые места (НМ) претендуют 3 прежних сотрудника (ПС), уже работающие в других отделах, и 4 новых сотрудника (НС). Номера новых сотрудников, новых и прежних мест представлены в таблице 1. Номера прежних мест являются номерами прежних сотрудников. (работа была выполнена специалистами Автор 24)
Таблица 1. Номера сотрудников и мест их работы
Новые сотрудники
(НС) Места работы прежних сотрудников (ПМ) Новые места (НМ)
1, 2, 3, 4 1, 2, 3 1, 2
Отдел кадров оценил по десятибалльной шкале компетентность новых сотрудников (таблица 2) и прежних сотрудников (таблица 3) для работы и на новых местах, и на прежних местах (ПМ), то есть занимаемых прежними сотрудниками.
Таблица 2. Компетентность новых сотрудников
НМ1 НМ2 ПМ1 ПМ2 ПМ3
НС1 6 7 4 5 4
НС2 7 8 5 7 6
НС3 9 8 8 7 8
НС4 7 7 7 8 9
Таблица 3. Компетентность прежних сотрудников
НМ1 НМ2 Занимаемое место
ПС1 7 6 7
ПС2 8 9 8
ПС3 6 5 6
Руководство предприятия предпочитает, чтобы прежние сотрудники не претендовали на места друг друга. Необходимо:
1. Построить модель задачи, включая транспортную таблицу.
2. Венгерским методом распределить сотрудников по должностям наилучшим образом.
Решение:
На основании таблиц 1-3 составим сводную таблицу назначений
НМ1
НМ2
ПМ1
ПМ2
ПМ3
НС1 6 7 4 5 4
НС2 7 8 5 7 6
НС3 9 8 8 7 8
НС4 7 7 7 8 9
ПС1 7 6 7 0 0
ПС2 8 9 0 8 0
ПС3 6 5 0 0 9
Математическая модель задачи.
1) Переменные задачи.
Ведем переменные xij принимающие два значения:
xij=0, если i-й претендент (Pi) не принимается на j-ю вакансию (Vj),
xij=1, если i-й претендент (Pi) принимается на вакансию (Vj),
где i=1,2,...7; j=1,2,...5.
2) Ограничения на переменные задачи.
Очевидно, что все переменные задачи неотрицательные и целые числа: xij > 0 и xij – целые.
Кроме того, так как каждый претендент может занять только одну вакансию и все вакансии должны быть заняты, должны удовлетворяться следующие ограничения:
другими словами в матрице (xij) суммы элементов по каждой строке и суммы элементов по каждому столбцу должны быть равны единицам. Это условие означает, что выбор претендентов должен быть таким, чтобы в матрице (xij), представляющей решение задачи, было бы по одной единице в каждой строке и по одной единице в каждом столбце, остальные элементы матрицы должны равняться нулю.
3) Целевая функция в задаче о назначениях.
Необходимо выбрать претендентов так, чтобы суммарное число очков, набранное ими было бы максимальным. Суммарное число набранных очков вычисляется по формуле:
L(X)=c11x11+c12x12+...+c75x75=6x11+7x12+...+9x75;
Окончательная математическая модель задачи записывается так:
Составим транспортную модель задачи о назначении, в которой требуется найти максимум целевой функции. Предварительно задачу о назначениях нужно сбалансировать. В рассматриваемом примере эта процедура выполняется добавлением двух столбцов (две фиктивные вакансии) с нулевыми результатами компетентности
Претендент Рi
Вакансии Vj
Количество претендентов
V1
(НМ1) V2
(НМ2) V3
(ПМ1) V4
(ПМ2) V5
(ПМ3) V6
(МФ1) V7
(МФ2)
P1 (НС1) 6 7 4 5 4 0 0 1
P2 (НС2) 7 8 5 7 6 0 0 1
P3 (НС3) 9 8 8 7 8 0 0 1
P4 (НС4) 7 7 7 8 9 0 0 1
P5 (ПС1) 7 6 7 0 0 0 0 1
P6 (ПС2) 8 9 0 8 0 0 0 1
P7 (ПС3) 6 5 0 0 9 0 0 1
Количество вакансий 1 1 1 1 1 1 1 ai=bj
Решим задачу венгерским методом
Используем венгерский алгоритм.
Значения максимальных элементов строк равны
max{6,7,4,5,4,0,0}=7
max{7,8,5,7,6,0,0}=8
max{9,8,8,7,8,0,0}=9
max{7,7,7,8,9,0,0}=9
max{7,6,7,0,0,0,0}=7
max{8,9,0,8,0,0,0}=9
max{6,5,0,0,9,0,0}=9
Заменив каждый элемент матрицы разностью максимального элемента этой строки и самого элемента.
1 0 3 2 3 7 7
1 0 3 1 2 8 8
0 1 1 2 1 9 9
2 2 2 1 0 9 9
0 1 0 7 7 7 7
1 0 9 1 9 9 9
3 4 9 9 0 9 9
Значения минимальных элементов столбцов равны
min{1,1,0,2,0,1,3}=0
min{0,0,1,2,1,0,4}=0
min{3,3,1,2,0,9,9}=0
min{2,1,2,1,7,1,9}=1
min{3,2,1,0,7,9,0}=0
min{7,8,9,9,7,9,9}=7
min{7,8,9,9,7,9,9}=7
Значит из третьего столбца вычитаем 1, из шестого и седьмого вычитаем 7
1 0 3 1 3 0 0
1 0 3 0 2 1 1
0 1 1 1 1 2 2
2 2 2 0 0 2 2
0 1 0 6 7 0 0
1 0 9 0 9 2 2
3 4 9 8 0 2 2
В полученной матрице пытаемся выбрать ровно по одному нулевому элементу в каждом столбце и каждой строке
В строке №7 один нулевой элемент, вычеркиваем ее, Р7 назначен на V5, столбец 5 так же вычеркиваем
В строке №3 один нулевой элемент, вычеркиваем ее...Посмотреть предложения по расчету стоимости
Заказчик
заплатил
заплатил
20 ₽
Заказчик не использовал рассрочку
Гарантия сервиса
Автор24
Автор24
20 дней
Заказчик принял работу без использования гарантии
28 октября 2017
Заказ завершен, заказчик получил финальный файл с работой
5
Тема «Решение задачи о назначениях венгерским методом»
Отдел кадров предприятия устроил конкурсный набор специалистов на две вакантные должности.jpg
2017-10-31 09:16
Последний отзыв студента о бирже Автор24
Общая оценка
5
Положительно
благодарю за качественное и оперативное выполнение заказа! Буду рад еще поработать с Вами!
Хочешь такую же работу?
300 ₽
