Решение задачи в процедуре EXCEL

Задача о назначениях

Пример 3:

В конкурсе на занятие пяти вакансий (V1, V2, V3, V4, V5) участвуют семь претендентов (P1, P2, P3, P4, P5, P6, P7). Результаты тестирования каждого претендента, на соответствующие вакансии, даны в виде матрицы - С (тестирование производилось по десятибалльной системе).

Определить, какого претендента и на какую вакансию следует принять, причем так, чтобы сумма баллов всех претендентов оказалась максимальной.

С =

  V1 V2 V3 V4 V5
P1
P2
P3
P4
P5
P6
P7

Рис.22

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

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

Ведем переменные xij принимающие два значения:

xij=0, если i-й претендент (Pi) не принимается на j-ю вакансию (Vj).

xij=1, если i-й претендент (Pi) принимается на вакансию (Vj).

i=1,2,...7; j=1,2,...5.

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

Очевидно, что все переменные задачи неотрицательные и целые числа: xij Решение задачи в процедуре EXCEL - student2.ru 0 и xij - целые.

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

Решение задачи в процедуре EXCEL - student2.ru , j=1,2,...7 ,

Решение задачи в процедуре EXCEL - student2.ru , i=1,2,...5 ,

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

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

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

Решение задачи в процедуре EXCEL - student2.ru ;

Z=c11x11+c12x12+...+c75x75=7x11+5x12+...+4x75;

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

найти max Решение задачи в процедуре EXCEL - student2.ru ;

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

xij Решение задачи в процедуре EXCEL - student2.ru 0 и xij - целые числа, i=1,2,...7; j=1,2,...5;

Решение задачи в процедуре EXCEL - student2.ru , j=1,2,...7 ;

Решение задачи в процедуре EXCEL - student2.ru , i=1,2,...5 .

Таким образом, задача о назначениях есть частный случай транспортной задачи (Пример 2).

Решение задачи в процедуре EXCEL

«Поиск решения»

1) Ввод данных. Переносим данные задачи в EXCEL, при этом нужно ввести 2 столбца (6-ой и 7-ой) с нулевыми значениями для сбалансирования задачи. Результаты заполнения таблицы EXCEL можно увидеть на рис.24 :

Решение задачи в процедуре EXCEL - student2.ru

Рис.24

В ячейках B4 : F10 введены результаты тестирования претендентов, а в ячейках G4 : H10 введены нули, что соответствует фиктивным вакансиям.

Ячейки B14 : F20 являются изменяемыми ячейками для нашей процедуры.

В ячейках B21 : H21 находятся суммы значений соответствующих столбцов изменяемых ячеек. Так в ячейке B21 находится сумма ячеек B14 : B20. Аналогично в ячейках :

в С21 находится сумма ячеек С14 : С20;

в D21 находится сумма ячеек D14 : D20;

в E21 находится сумма ячеек E14 : E20;

в F21 находится сумма ячеек F14 : F20.

в G21 находится сумма ячеек G14 : G20;

в H21 находится сумма ячеек H14 : H20.

В ячейках I14 : I20 находятся суммы значений соответствующих строк изменяемых ячеек. Так в ячейке I14 находится сумма ячеек B14 : H14. Аналогично в ячейках :

в I15 находится сумма ячеек B15 : H15;

в I16 находится сумма ячеек B16 : H16;

в I17 находится сумма ячеек B17 : H17;

в I18 находится сумма ячеек B18 : H18;

в I19 находится сумма ячеек B19 : H19;

в I20 находится сумма ячеек B20 : H20.

Целевая функция заносится в ячейку J3 и вычисляется по формуле «СУММПРОИЗВ(B4:H10;B14:H20)».

2) Заполнение окна процедуры «Поиск решения»:

целевая функция : J3;

значение целевой функции : max;

изменяемые ячейки : B14 : H20;

ограничения задачи :

B21 : H21 =1 и I14 : I20 = 1(все свободные рабочие места должны быть заняты);

B14 : F20 Решение задачи в процедуре EXCEL - student2.ru 0 (изменяемые ячейки должны иметь положительные значения).

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

Решение задачи в процедуре EXCEL - student2.ru Рис.25

3) Выполнив процедуру «Поиск решения» мы получили в первоначальной таблице следующие результаты (таблица 26):

Решение задачи в процедуре EXCEL - student2.ru

Рис.26

Эти результаты совпадают с решением задачи, полученным преобразованием матрицы (С).

Наши рекомендации