42067
Решение задачи о назначениях
Лабораторная работа
Информатика, кибернетика и программирование
В ячейках 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 находятся суммы значений соответствующих строк изменяемых ячеек.
Русский
2013-10-27
3.01 MB
85 чел.
Лабораторная работа 3_1. Решение задачи о назначениях
Цель работы - изучить возможности информационных технологий для нахождения решения комбинаторных задач
Задача о назначениях.
В конкурсе на занятие пяти вакансий (V1,V2,V3,V4,V5) участвуют семь претендентов (P1,P2,P3,P4,P5,P6,P7). Результаты тестирования каждого претендента на соответствующие вакансии (по десятибалльной системе) заданы в виде матрицы (рис.1).
Определить, какого претендента и на какую вакансию следует принять, причем так, чтобы сумма баллов всех претендентов оказалась максимальной.
V1 |
V2 |
V3 |
V4 |
V5 |
|
P1 |
7 |
5 |
7 |
6 |
7 |
P2 |
6 |
4 |
8 |
4 |
9 |
P3 |
8 |
6 |
4 |
3 |
8 |
P4 |
7 |
7 |
8 |
5 |
7 |
P5 |
5 |
9 |
7 |
9 |
5 |
P6 |
6 |
8 |
6 |
4 |
7 |
P7 |
7 |
7 |
8 |
6 |
4 |
Рис.1
Математическая модель задачи.
1) Переменные задачи.
Введем переменные , принимающие два значения:
=0, если i-й претендент (Pi) не принимается на j-ю вакансию (Vj).
=1, если i-й претендент (Pi) принимается на вакансию (Vj).
i=1,2,...7; j=1,2,...5.
2) Ограничения на переменные задачи.
Очевидно, что все переменные задачи неотрицательные и целые числа. Кроме того, так как каждый претендент может занять только одну вакансию, и все вакансии должны быть заняты, удовлетворяются следующие ограничения:
, j=1,2,...5 ,
, i=1,2,...7 ,
Другими словами, в матрице X={}суммы элементов по каждой строке и по каждому столбцу должны быть равны единицам. Это условие означает, что выбор претендентов должен быть таким, чтобы в матрице X, представляющей решение задачи, было бы по одной единице в каждой строке и по одной единице в каждом столбце, при остальных элементах матрицы равных нулю.
3) Целевая функция в задаче о назначениях.
Необходимо выбрать претендентов так, чтобы суммарное число баллов, набранное ими, было бы максимальным:
;
4) Окончательная математическая модель задачи записывается так: найти
;
при ограничениях:
0; - целые числа, i=1,2,...7; j=1,2,...5;
, j=1,2,...5;
, i=1,2,...7 .
Решение задачи в процедуре EXCEL «Поиск решения»
1) Ввод данных. Переносим данные задачи в EXCEL, при этом нужно ввести 2 столбца (6-ой и 7-ой) с нулевыми значениями для сбалансирования задачи. Результаты заполнения таблицы EXCEL представлены на рис.2:
Рис.2
в B21 находится сумма ячеек B14:B20;
в С21 находится сумма ячеек С14:С20;
в D21 находится сумма ячеек D14:D20;
в E21 находится сумма ячеек E14:E20;
в F21 находится сумма ячеек F14:F20.
в G21 находится сумма ячеек G14:G20;
в H21 находится сумма ячеек H14:H20.
в 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:H20 0 (изменяемые ячейки должны иметь положительные значения);
B14:H20 = целое
В окне «Параметры» установить «Линейная модель», что соответствует решению задачи симплекс-методом. Результаты заполнения окна показаны на рис.3:
Рис.3
3) Выполнив процедуру «Поиск решения» получим в первоначальной таблице следующие результаты (рис.4):
Рис. 4
Результат решения: претенденты Р1 и Р7 попадают на фиктивные вакансии и не принимаются на работу. Р2 принимается на пятую вакансию, Р3 - на первую, Р4 - на третью, Р5 - на четвертую, Р6 - на вторую. Сумма баллов, полученная при данном решении равна: 9+8+8+9+8=42.
Замечание. Отметим, что при умножении ЦФ на -1, задача о назначениях может быть приведена к транспортной задаче, в которой объем запасов каждого поставщика и объем потребностей каждого потребителя равны 1.
Контрольные упражнения
I. Решить задачи о назначениях, представленные следующими матрицами стоимостей, исследуя функцию цели на максимум. Проверить решение, сведя исходную задачу к транспортной.
Варианты:
3. 4.
5. 6.
7. 8.
9. 10.
11. 12.
13.
II. Составить и реализовать математическую модель следующей комбинаторной задачи с булевыми переменными.
Частным случаем задач с целочисленными переменными являются задачи, в результате решения которых искомые переменные могут принимать только одно из двух значений: 0 или 1. Такие переменные называют булевыми. Помимо задания требования целочисленности, при вводе условия задач с булевыми переменными необходимо в окне "Поиск решения" добавить условие «двоичные».
Задача. Университет формирует комиссию по рассмотрению жалоб студентов. В соответствии с указаниями, полученными из администрации, в эту комиссию необходимо включить по крайней мере одну женщину, одного мужчину, одного студента, одного администратора и одного преподавателя. Выдвинуты 10 кандидатур (обозначены буквами от a до j). Принадлежность этих кандидатур к различным категориям отражена в таблице
Категория |
Кандидатуры |
Женщины |
a, b, c, d, e |
Мужчины |
f, g, h, i, j |
Студенты |
a, b, c, j |
Администраторы |
e, f |
Преподаватели |
d, g, h, i |
Университет заинтересован создать наименьшую по составу комиссию, гарантирующую представительство каждой их указанных категорий. Найти оптимальное решение задачи.
А также другие работы, которые могут Вас заинтересовать | |||
57597. | КИЇВСЬКА РУСЬ НАПРИКІНЦІ Х – У ПЕРШІЙ ПОЛОВИНІ ХІ СТОЛІТТЯ | 88 KB | |
МЕТА - узагальнити і систематизувати знання учнів з історії Київської Русі, а також про видатних історичних осіб - київських князів і державців; закріпити в ігровій формі уміння учнів працювати з поняттями, хронологією | |||
57598. | Культура Украины в XVI веке | 67 KB | |
Цель: определить условия и состояние развития культуры в Украине в XVI веке охарактеризовать влияние данных условий на развитие образования книгопечатания и искусства; развивать у учащихся умение самостоятельно работать с разными источниками информации... | |||
57599. | Окупаційний режим. Рух Опору в Україні | 1.78 MB | |
Головна увага викладача історії зосереджується на використанні нових педагогічних технологій, які б стимулювали пізнавальний інтерес до історії свого народу, його минулого та сучасного буття; відроджувати традиції свого народу; шанувати обряди та звичаї; аргументовано, на основі історичних фактів та свідчень очевидців відстоювати власні погляди на будь-яку проблему... | |||
57600. | Радянізація західних областей України у повоєнний період | 88.5 KB | |
Мета уроку: розкрити суперечливі складові та наслідки радянізації; розібрати особливості процесу відбудови в Західній Україні; формувати самостійне ставлення до складних історичних процесів, розуміння суперечності суспільного життя... | |||
57601. | ДЕРЖАВА З ЦЕНТРОМ У КИЄВІ. ПЕРШІ КНЯЗІ | 94.5 KB | |
І хоч Рюрик уже помер а його син Ігор поскандінавському Інґвар був ще замолодим щоб стати на чолі дружини Олег що був регентом опікуном доки Ігор не досягне повноліття зібрав дружину з варягів словян та фіннів узяв із собою Ігоря й поплив до Києва. | |||
57602. | Сталінська індустріалізація України. Друга і третя п’ятирічки | 1.09 MB | |
Мета уроку: Освітня: Визначити протиречиві тенденції 30х років Уяснити що друга і третя пятирічки були важливим етапом індустріалізації визначити дати другої та третьої пятирічок Визначити хронологічну послідовність головних подій... | |||
57603. | Україна – наш спільний дім | 42 KB | |
Обладнання: відеоматеріали: уривок з реклами Я їду додому адміністративна карта України фізична карта України; фотографії видатних людей вихідців з України; аудіозаписи пісен: С чего начинается Родина Україна у виконанні... | |||
57604. | Другий зимовий похід армії УНР. Припинення боротьби регулярних українських військ за незалежність України | 59 KB | |
Мета: проаналізувати мету та причини поразки Другого зимового походу армії УНР; пояснити значення Другого зимового походу як останньої збройної спроби відвоювати самостійність України та наслідки невдачі акції. | |||
57605. | Київська держава наприкінці Х – у першій половині ХІ ст | 196.5 KB | |
Відповідає та команда у якої швидше буде готова відповідь. За кожний правильний термін команда отримує 1 бал. Перша команда літера К. Друга команда літера С. | |||