Составить экономико-математическую модель задачи. Найдите оптимальное решение задачи в Excel.
Постановка задачи о назначениях
Отдел кадров предприятия устроил конкурсный набор специалистов на две вакантные должности. На эти новые места (НМ) претендуют 3 прежних сотрудника (ПС), уже работающие в других отделах, и 4 новых сотрудника (НС). Номера новых сотрудников, новых и прежних мест выбираются по вариантам из табл. 1. Номера прежних мест являются номерами прежних сотрудников.
Отдел кадров оценил по десятибалльной шкале компетентность новых сотрудников (табл. 2) и прежних сотрудников (табл. 3) для работы и на новых местах, и на прежних местах (ПМ), то есть занимаемых прежними сотрудниками. Необходимо учесть, что руководство предприятия, во-первых, предпочитает, чтобы прежние сотрудники не претендовали на места друг друга, и, во-вторых, не намерено увольнять прежних сотрудников.
Необходимо распределить сотрудников по должностям наилучшим образом.
Таблица 1
Номера сотрудников и мест их работы для конкретного варианта
№ варианта | Новые сотрудники (НС) | Места работы прежних сотрудников (ПМ) | Новые места (НМ) |
5 | 1,2,3,4 | 2,3,4 | 2,4 |
Таблица 2
Компетентность новых сотрудников
НМ1 | НМ2 | НМ3 | НМ4 | ПМ1 | ПМ2 | ПМ3 | ПМ4 | ПМ5 | ПМ6 | |
НС1 | 6 | 5 | 7 | 6 | 5 | 6 | 7 | 6 | 7 | 5 |
НС2 | 5 | 5 | 8 | 8 | 7 | 6 | 4 | 5 | 8 | 8 |
НС3 | 6 | 7 | 5 | 6 | 4 | 5 | 4 | 5 | 6 | 6 |
НС4 | 7 | 8 | 7 | 6 | 5 | 7 | 6 | 8 | 5 | 5 |
НС5 | 7 | 6 | 6 | 5 | 5 | 4 | 5 | 5 | 4 | 6 |
НС6 | 8 | 8 | 9 | 7 | 6 | 7 | 8 | 7 | 9 | 8 |
НС7 | 9 | 8 | 9 | 9 | 8 | 7 | 8 | 9 | 8 | 7 |
НС8 | 7 | 7 | 8 | 9 | 7 | 9 | 9 | 6 | 7 | 8 |
Таблица 3
Компетентность прежних сотрудников
НМ1 | НМ2 | НМ3 | НМ4 | Занимаемое место | |
ПС1 | 7 | 6 | 6 | 7 | 7 |
ПС2 | 8 | 9 | 7 | 7 | 8 |
ПС3 | 6 | 5 | 6 | 6 | 6 |
ПС4 | 7 | 9 | 6 | 8 | 8 |
ПС5 | 8 | 7 | 8 | 8 | 7 |
ПС6 | 4 | 5 | 6 | 4 | 5 |
Решение:
1. На основе данных индивидуального варианта (таблица 1) и исходных данных (таблицы 2 и 3) выбираем данные и составляем матрицу.
Таблица 1
Номера сотрудников и мест их работы для конкретного варианта
№ варианта | Новые сотрудники (НС) | Места работы прежних сотрудников (ПМ) | Новые места (НМ) |
5 | 1,2,3,4 | 2,3,4 | 2,4 |
Таблица 2
Компетентность новых сотрудников
НМ1 | НМ2 | НМ3 | НМ4 | ПМ1 | ПМ2 | ПМ3 | ПМ4 | ПМ5 | ПМ6 | |
НС1 | 6 | 5 | 7 | 6 | 5 | 6 | 7 | 6 | 7 | 5 |
НС2 | 5 | 5 | 8 | 8 | 7 | 6 | 4 | 5 | 8 | 8 |
НС3 | 6 | 7 | 5 | 6 | 4 | 5 | 4 | 5 | 6 | 6 |
НС4 | 7 | 8 | 7 | 6 | 5 | 7 | 6 | 8 | 5 | 5 |
НС5 | 7 | 6 | 6 | 5 | 5 | 4 | 5 | 5 | 4 | 6 |
НС6 | 8 | 8 | 9 | 7 | 6 | 7 | 8 | 7 | 9 | 8 |
НС7 | 9 | 8 | 9 | 9 | 8 | 7 | 8 | 9 | 8 | 7 |
НС8 | 7 | 7 | 8 | 9 | 7 | 9 | 9 | 6 | 7 | 8 |
Таблица 3
Компетентность прежних сотрудников
НМ1 | НМ2 | НМ3 | НМ4 | Занимаемое место | |
ПС1 | 7 | 6 | 6 | 7 | 7 |
ПС2 | 8 | 9 | 7 | 7 | 8 |
ПС3 | 6 | 5 | 6 | 6 | 6 |
ПС4 | 7 | 9 | 6 | 8 | 8 |
ПС5 | 8 | 7 | 8 | 8 | 7 |
ПС6 | 4 | 5 | 6 | 4 | 5 |
Претендент | Вакансии | ||||
НМ2 | НМ4 | ПМ2 | ПМ3 | ПМ4 | |
НС1 | 5 | 6 | 6 | 7 | 6 |
НС2 | 5 | 8 | 6 | 4 | 5 |
НС3 | 7 | 6 | 5 | 4 | 5 |
НС4 | 8 | 6 | 7 | 6 | 8 |
ПС2 | 9 | 7 | 8 | 0 | 0 |
ПС3 | 5 | 6 | 0 | 6 | 0 |
ПС4 | 9 | 8 | 0 | 0 | 8 |
2. Составим математическую модель задачи.
2.1. Переменные задачи:
Введем переменные 
, принимающие два значения:
, если 
претендент 
не принимается на 
вакансию 
,
, если 
претендент 
принимается на 
вакансию 
,
где 
; 
.
2.2. Ограничения на переменные задачи:
Все переменные задачи неотрицательные и целые числа:
и 
- целые.
Поскольку каждый претендент может занять только одну вакансию и при этом все вакансии должны быть заняты, должны удовлетворяться следующие ограничения:
, 
; 
.
Иначе говоря, в матрице 
суммы элементов по каждой строке и суммы элементов по каждому столбцу должны быть равны единицам. Это условие означает, что выбор претендентов должен быть таким, чтобы в матрице 
, представляющей решение задачи, было по одной единице в каждой строке и по одной единице в каждом столбце, остальные элементы матрицы должны равняться нулю.
2.3. Целевая функция:
Необходимо выбрать претендентов так, чтобы суммарное число очков, набранное ими, было максимальным. Суммарное число набранных очков вычисляется по формуле:
.
Окончательная математическая модель задачи:
,
при ограничениях:
.
3. Составим транспортную модель задачи о назначении, в которой требуется найти максимум целевой функции. Для этого нужно предварительно сбалансировать задачу посредством добавления двух столбцов (две фиктивные вакансии) с нулевыми результатами компетентности.
Претендент,
| Вакансии, | Количество претендентов | |||||||
|
|
|
|
|
|
| |||
НМ2 | НМ4 | ПМ2 | ПМ3 | ПМ4 | МФ1 | МФ2 | 1 | ||
| НС1 | 5 | 6 | 6 | 7 | 6 | 0 | 0 | 1 |
| НС2 | 5 | 8 | 6 | 4 | 5 | 0 | 0 | 1 |
| НС3 | 7 | 6 | 5 | 4 | 5 | 0 | 0 | 1 |
| НС4 | 8 | 6 | 7 | 6 | 8 | 0 | 0 | 1 |
| ПС2 | 9 | 7 | 8 | 0 | 0 | 0 | 0 | 1 |
| ПС3 | 5 | 6 | 0 | 6 | 0 | 0 | 0 | 1 |
| ПС4 | 9 | 8 | 0 | 0 | 8 | 0 | 0 | 1 |
Количество вакансий | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
|
4. Решение задачи в Excel.
4.1. Экранные формы, задание переменных, целевой функцмм, ограничений и граничных условий задачи представим на рисунках 1, 2 и 3.
Рисунок 1. Экранная форма задачи о назначениях
Объект математической модели | Выражение в Excel |
Переменные задачи | B5:H11 |
Формула в целевой ячейке K5 | =СУММПРОИЗВ(B5:H11;B16:H22) |
Ограничения по строкам в ячейках I16:I22 | =СУММ(B16:H16) Копируем в диапазон I16:I22 |
Ограничения по столбцам в ячейках B23:H23 | =СУММ(B16:B22) Копируем в диапазон B23:H23 |
Рисунок 2. Формулы экранной формы задачи о назначениях
Рисунок 3. Ограничения и граничные условия задачи о назначениях
4.2. Результаты решения представим на рисунке 4.
Рисунок 4. Результаты решения задачи о назначениях
5. Получено следующее оптимальное распределение сотрудников по местам работы (возможно, оно не является единственным):
- НС3 и ПС3 – не берут на работу;
- НС1 принимают на место ПМ3;
- НС2 – на НМ4;
- НС4 – на ПМ4;
- ПС2 остается на ПМ2;
- ПС4 – НМ2.
