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

77 чел.

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

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


 

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

52748. Біоадекватна технологія як умова розвитку творчого мислення школярів 59 KB
  Проект Концепції літературної освіти в 11річній загальноосвітній школі визначає головною метою літературної освіти виховання читацької особистості з розвиненим естетичним смаком самостійним критичним мисленням гуманістичним світоглядом. Об’єкт літературної освіти – особистість учня його духовноемоційний світ моральні цінності та орієнтації творче мислення уява читацькі компетенції мовлення. Вивчення літератури за біологічно адекватною технологією БАТ якраз і сприяє розв’язанню таких завдань як формування в...
52749. Формування у молодших школярів мотивації до навчання 48.5 KB
  Проблема розвитку мотивації навчання в останній час стає все більш актуальною. свідчать що основи мотивації навчання закладаються у початковій школі тому саме молодший шкільний вік має великі резерви формування мотиваційної сфери учнів. Зусилля практиків та науковців сьогодні спрямовані на дослідження певних організаційних форм та змістових компонентів навчальної діяльності за яких відбувається посилення мотивації навчання що оптимізує весь навчальновиховний процес.
52750. Організація дитчого самоврядування 119 KB
  З цією метою у школі сформована певна діюча структура органів самоврядування. Провідна ідея: всебічне виховання учнів через участь в органах самоврядування. Пріоритетні напрями діяльності: навчальна робота; виховна робота; інформаційно методична робота; розвиток учнівського самоврядування. Організація самоврядування побудована на інноваційних підходах: задоволення учнівської природної потреби у...
52751. Розвиток критичного мислення учнів на уроках математики як важливого елементу продуктивної технології навчання 147.5 KB
  Кривий Ріг Україна Розвиток критичного мислення учнів на уроках математики як важливого елементу продуктивної технології навчання У статті розкрито розвиток критичного мислення учнів на уроках математики як важливого елементу продуктивної технології навчання. Як відомо у шкільній освіті існує безліч методів навчання різні типи уроків які переслідують одну єдину мету засвоєння знань учнями. Учень і вчитель є рівноправними суб’єктами навчання. Організація інтерактивного навчання припускає моделювання життєвих ситуацій використання...
52753. Розробка і виготовлення композицій за творами О.Довженка на уроках трудового навчання з теми «Художня обробка деревини» 2.71 MB
  Із творчістю одного з таких митців – письменника, художника, кінемотографіста, дуже талановитої людини - Олександра Петровича Довженка, діти продовжують знайомство на уроках праці, розробляючи і виготовляючи композиції за його творами. Батьківщина Олександра Петровича – це золотаві соняшники, жовтогарячі колоски пшениці, синє волошкове поле, мальовничі луки, Біла круча на Десні, пісня солов’я...Саме про це й говоримо на уроках. Зачитуємо епізоди з творів письменника, а потім виконуємо завдання: створити композицію за уривками
52754. ХОЧЕШЬ СТАТЬ МИЛЛИОНЕРОМ? DO YOU WANT TO BE A MILLIONAIRE? 142.81 KB
  Начало викторины. Организационный момент. Игра дает шанс поиграть каждому из 7 участников по очереди. Они сидят на стульях перед сценой, спиной к зрительному залу. Ведущий задает вопросы в порядке увеличения трудности вопроса и его стоимости. У участников есть 1 подсказка - помощь друга. В случае ошибки ему выдается стоимость предыдущего вопроса (в евромонетах), а затем принимается следующий игрок. Правильные ответы приветствуются аплодисментами. В конце игры объявляются победители. Great Britain is divided into ... (10 «евро») a) three parts; b) five parts; c) four parts; d) two parts. 2. What is a Picadilly Circus? (20 «евро») a) a circus; b) a square; c) a street; d) a house. 3. What is the Tower of London now? (50 «евро») a) a prison; b) a museum; c) a house; d) a fortress.
52755. Інтегрований урок. Українська література + фізична культура. 5 клас 195.5 KB
  Завдання: прочитати речення з певними інтонаціями: Спочатку із захопленням потім з осудом Ну і богатир Із захватом із розчаруванням Оце так козак Зачудовано із зневагою Яка красуня Домашнє завдання 3хв. Перевірка домашнього завдання Що ви знаєте про речення Як ви розумієте епіграф до нашого уроку Мотивація навчання школярів 45хв. Завдання: створити словесний образ слова здоров’я або 2. Завдання: Скласти 5 речень з ключовими словами: Діти Небезпека Правила Здоров’я Оголошення теми і мети уроку 1хв.
52756. Drama Techniques for Teaching English 37 KB
  Using drama to teach English results in real communication involving ideas, emotions, feelings appropriateness and adaptability; in short an opportunity to use language in operation which is absent in a conventional language class. Such activities add to the teachers repertoire of pedagogic strategies giving them a wider option of learner-centered activities to chose from for classroom teaching, thereby augmenting their efficiency in teaching English