Математическая модель задачи.

Примерпостроения модели ТЗ

Отдел кадров предприятия устроил конкурсный набор специалистов на две вакантные должности. На эти новые места (НМ) претендуют 3 прежних сотрудника (ПС), уже работающие в других отделах, и 4 новых сотрудника (НС). Номера новых сотрудников, новых и прежних мест выбираются из табл. 2.2. Номера прежних мест являются номерами прежних сотрудников.

Отдел кадров оценил по десятибалльной шкале компетентность новых сотрудников (табл. 2.3) и прежних сотрудников (табл. 2.4) для работы и на новых местах, и на прежних местах (ПМ), то есть занимаемых прежними сотрудниками. Необходимо учесть, что руководство предприятия, во-первых, предпочитает, чтобы прежние сотрудники не претендовали на места друг друга, и, во-вторых, не намерено увольнять прежних сотрудников. Необходимо распределить сотрудников по должностям наилучшим образом.

Таблица 2.2

Таблица 2.3

Таблица 2.4

Решение.

На основе данных таблицы 2.3 выбираем необходимые данные из таблиц 2.3 и 2.4. Исходя из выбранных данных, составляем матрицу:

Математическая модель задачи.

1. Переменные задачи.

Ведем переменные x_ij принимающие два значения:
x_ij = 0, если i -й претендент (P_i) не принимается на j -ю вакансию (V_j),
x_ij = 1, если i -й претендент (P_i) принимается на вакансию (V_j),

где i = 1,2,...7; j = 1,2,...5.

2. Ограничения на переменные задачи.

Очевидно, что все переменные задачи неотрицательные и целые числа: x_ij ≥ 0 и x_ij – целые.

Кроме того, так как каждый претендент может занять только одну вакансию и все вакансии должны быть заняты, должны удовлетворяться следующие ограничения:

, j =1,2,...7,

, i =1,2,...5,

другими словами в матрице (x_ij) суммы элементов по каждой строке и суммы элементов по каждому столбцу должны быть равны единицам. Это условие означает, что выбор претендентов должен быть таким, чтобы в матрице (x_ij), представляющей решение задачи, было бы по одной единице в каждой строке и по одной единице в каждом столбце, остальные элементы матрицы должны равняться нулю.

3. Целевая функция в задаче о назначениях.

Необходимо выбрать претендентов так, чтобы суммарное число очков, набранное ими было бы максимальным. Суммарное число набранных очков вычисляется по формуле:

L (X)= c ₁₁ x ₁₁+ c ₁₂ x ₁₂+...+ c ₇₅ x ₇₅=6 x ₁₁+7 x ₁₂+...+5 x ₇₅;

Окончательная математическая модель задачи записывается так:

при ограничениях:

Составим транспортную модель задачи о назначении, в которой требуется найти максимум целевой функции. Предварительно задачу о назначениях нужно сбалансировать. В рассматриваемом примере эта процедура выполняется добавлением двух столбцов (две фиктивные вакансии) с нулевыми результатами компетентности.

Претендент, P 1	Вакансии, V 1	Количество претендентов
V 1 (НМ1)	V 2 (НМ3)	V 3 (ПМ2)	V 4 (ПМ4)	V 5 (ПМ6)	V 6 (МФ1)	V 7 (МФ2)
P 1 (НС1)
P 2 (НС2)
P 3 (НС7)
P 4 (НС8)
P 5 (ПС2)
P 6 (ПС4)
P 7 (ПС6)
Количество вакансий

Решение задачи в Excel.

Экранные формы, задание переменных, целевой функции,ограничений и граничных условий задачи представлены на рис.2.1, 2.2, и в табл.2.5.

Рис.2.1. Экранная форма задачи

Таблица 2.5

Рис.2.2. Ограничения и граничные условия задачи

В окне «Параметры» установить«Линейная модель», что соответствует решению задачи симплекс-методом.

Результаты решения задачи представлены на рис. 2.3.

Рис.2.3. Результаты решения задачи