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

80 чел.

Лабораторная работа 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

  •  В ячейках B4:F10 введены результаты тестирования претендентов, а в ячейках G4:H10 введены нули, что соответствует фиктивным вакансиям.
  •  Ячейки B14:H20 являются изменяемыми ячейками для нашей процедуры.
  •  В ячейках 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: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. Решить задачи о назначениях, представленные следующими матрицами стоимостей, исследуя функцию цели на максимум. Проверить решение, сведя исходную задачу к транспортной.

Варианты:

  1.      2.

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

Университет заинтересован создать наименьшую по составу комиссию, гарантирующую представительство каждой их указанных категорий. Найти оптимальное решение задачи.


 

А также другие работы, которые могут Вас заинтересовать

38472. Менеджмент организации. Методические рекомендации к производственной практике 235 KB
  Производственная практика студентов проводится на предприятиях производственной и финансово-банковской сфер, в научно-исследовательских учреждениях, государственных организациях и структурах, а также в компаниях и фирмах различных форм собственности.
38473. Составление сметы затрат и определение себестоимости оборудования «Rademaker» по производству хлебобулочных изделий 208.85 KB
  Современное состояние технологического оборудования хлебозаводов и пекарен вызывает тревогу. Лишь 30 предприятий находится в удовлетворительном состоянии значительная часть технологического оборудования эксплуатируется более 20 лет Хлебопечение одна из ведущих отраслей пищевой промышленности. Составить сметы затрат и определение себестоимости оборудования Rdemker по производству хлебобулочных изделий. Для достижения цели в курсовой работе необходимо решить следующие задачи: рассмотрим характеристику планово ...
38474. Проектирование хлебопекарного предприятия «Rademaker» 43.59 KB
  Самостоятельное выполнение работ старшим техником Контроль качества продукции проверка соответствия качества продукции или процесса от которого оно зависит установленным требованиям. Контроль качества продукции включает государственный надзор за качеством продукции ведомственный контроль качества продукции и технический контроль качества в объединениях предприятиях и организациях. За контроль качества продукции на предприятии отвечает старший техник. Технический контроль качества продукции осуществляется на всех стадиях производственного...
38475. Фінанси і кредит усіх форм навчання Всі цитати цифровий та фактичний матеріал бібліо 345 KB
  Для досягнення вказаної мети студенти повинні вирішити такі завдання: з урахуванням бази практики вибрати тему випускової роботи та обґрунтувати її актуальність; опрацювати та узагальнити законодавчу базу України нормативноправові та інструктивні матеріали літературні та інші з досліджуваної проблеми; зібрати практичні матеріали з обраної теми досліджень в умовах реального підприємства установи організації; розглянути теоретичні аспекти за темою досліджень; виконати аналіз стану обраної проблеми та запропонувати шляхи їх...
38476. Насосная станция в условиях системы водоснабжения с. Драынивка Новосанжарского району 3.97 MB
  Кроме того система водоснабжения должна обладать определенной степенью надежности то есть обеспечивать снабжение потребителей водой без недопустимого снижения установленных показателей своей работы в отношении количества или качества подаваемой воды перерывы или снижение подачи воды или ухудшение ее качества в недопустимых пределах. Система водоснабжения населенного места или промышленного предприятия должна обеспечивать получение воды из природных источников ее очистку если это вызывается требованиями потребителей и подачу к местам...
38477. РАЗРАБОТКА СИСТЕМЫ АВТОМАТИЗИРОВАННОГО ЭЛЕКТРОПРИВОДА НАСОСА ВОДОСНАБЖЕНИЯ 7.66 MB
  1 Функциональная схема автоматизированного электропривода насоса На рис.1 представлена функциональная схема автоматизированного электропривода насосной станции. Схема показывает принцип работы буровой насосной станции после установки станции управления насосами.1 Функциональная схема автоматизированного ЭП насоса 3.
38478. Досягнення та перспективи розвитку електроенергетики України 144.44 KB
  Завдання Стратегії розвитку атомної енергетики України як частини паливно-енергетичного комплексу є визначення місця і ролі атомної енергетики у вирішенні проблеми сталого розвитку держави, формування напрямів і шляхів розвитку атомно-енергетичного комплексу