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

81 чел.

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

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


 

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

81989. А вже весна, а вже красна… 80 KB
  Показати, як поети і письменники засобами художнього слова розкривають багатство і красу навколишнього світу; розвивати навички виразного читання, формувати уміння робити посильні висновки з прочитаного, побаченого, почутого; збагачувати лексичний словник учнів...
81990. Бринить струною гілочка весни. (Весна у природі) 61.5 KB
  Закріплення елементарних уявлень про найхарактерніші ознаки весни в живій і неживій природі, які можна виявити в процесі спостережень, а саме: з пробудженням рослин, з поведінкою перелітних птахів; показати, як зміни в неживій природі впливають на живу природу; поповнювати знання учнів...
81991. Зігріємо землю своєю любов’ю, для наших нащадків її збережемо 231 KB
  Мета. Поглиблювати знання учнів про природу, її красу та багатства, сприяти розумінню необхідності захищати і берегти навколишнє середовище, виховувати любов і повагу до рідної землі, трепетне ставлення до всього живого на ній.
81992. РАЗРАБОТКА СИСТЕМЫ БЮДЖЕТИРОВАНИЯ НА БАЗЕ 1С:ПРЕДПРИЯТИЕ 8.0: ОБМЕН ИНФОРМАЦИЕЙ С БУХГАЛТЕРСКОЙ КОНФИГУРАЦИЕЙ, РАЗРАБОТКА БИЗНЕС-ПРОЦЕССОВ 888 KB
  Созданы обработки для обмена данными между разрабатываемой конфигураций и стандартной конфигурацией 1С:Бухгалтерия, разработаны бизнес-процессы, необходимые для формирования бюджета.
81993. Стежинами рідного міста 155 KB
  Познайомити учнів з головними історичними подіями в процесі розвитку рідного міста. Розвивати зв’язне мовлення, пізнавальний інтерес, уміння робити висновки. Виховувати патріотичні почуття, бажання набувати нові знання.
81994. Дзеркало людської душі 46.51 KB
  На початку виховної години для розвитку креативного мислення проводиться мозковий штурм Вихователь пропонує дітям відгадати що в неї в подарунковому пакеті пропонуючи підказки з історії виникнення дзеркала його форми і де воно зустрічається в літературі.
81995. ЛЮБОВ – ЦЕ ДАР. І БОГ САМ ВИБИРА, ХТО ЗАСЛУЖИВ ОЦЕ ПІЗНАТИ ДИВО 42.5 KB
  Мета: поспілкуватися з учнями про кохання, про те, що вважається природним і що є небажаним у взаєминах молоді; зорієнтувати учнів на толерантне ставлення до вираження почуттів протилежними статями; допомогти учням розібратися у собі, підготувати до майбутнього сімейного життя.
81996. Виховна година «Злочин і покарання» 35.5 KB
  Мета: запобігати шкідливим звичкам, які негативно впливають на здоров’я підлітків; формувати вміння і навички учнів щодо власної безпеки, розуміння відповідальності за власні вчинки та їх наслідки; виховувати в учнів бажання зберегти власне здоров’я.
81997. Прийди до серця, Україно, благослови добром мене… 45.5 KB
  Мета: виховувати почуття патріотизму, національної гордості, любові до рідного краю, розуміння своєї причетності до всіх подій, які відбувалися в Україні; формувати переконаність у нетлінності духовних скарбів народу.