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

87 чел.

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

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


 

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

8311. Основи теорії держави 124.5 KB
  Основи теорії держави Мета заняття.Ознайомити студентів із поняттям держави, її ознаками, закономірностями виникнення, основними теоріями походження та функціями держави. Охарактеризувати форми держави,поняття та ознаки громадянського су...
8312. Генетика. Конспект лекций 3.82 MB
  Введение. История развития генетики Цель лекции: ознакомить учащихся с основными этапами развития генетики как науки, познакомить с зарубежными и отечественными ведущими учеными-генетиками и селекционерами, изучить особенности темы Основы генетики ...
8313. Вища фізика. Конспект лекцій 7.33 MB
  Частина 1. Механіка. Тема 1. Вступ. Кінематика поступального руху. Вступ. Кінематика поступального руху (2 год.) Мета: Ввести основні поняття механіки. План Елементи кінематики. Поступальний рух. Радіус-вектор, траєкторія, шлях, переміще...
8314. Экономическая оценка обновления парка подвижного состава АТП 391 KB
  Экономическая оценка обновления парка подвижного состава АТП Методические указания содержат определение потребности предприятия в материальных и трудовых ресурсах, расчет экономических показателей деятельности предприятия (затраты, доходы, прибыль),...
8315. Сложение элементов столбцов матрицы и нормирование вектора 215.5 KB
  Сложение элементов столбцов матрицы и нормирование вектора Часть 1. Сложение элементов в столбцах матрицы. Задача 1: Просуммировать элементы столбцов заданной матрицы размером mхn. Результат получить в одномерном массиве размером n Задача была выпол...
8316. Численные методы на Mathcad’е 594.01 KB
  Численные методы на Mathcad’е Введение Сегодня не часто вспоминают о том, что компьютеры были созданы в первую очередь для проведения научных расчетов. До сих пор научные и инженерные расчеты остаются одной из важнейших, хотя, пожалуй, и не сам...
8317. Развитие агентской сети страховой компании. Методическое пособие 438.45 KB
  Развитие агентской сети страховой компании. Методическое пособие. Книга 1 Оглавление Глава. Характеристика профессии страхового агента Психологические основы страхования Представления и стереотипы, связанные с профессией страхового агента Влияние ...
8318. Прикладная информатика в экономике. Организация производственных практик 367.87 KB
  Прикладная информатика в экономике. Организация производственных практик В работе, рекомендованной учебно-методическим советом института менеджмента и бизнеса Дальневосточного государственного университета, представлены организационно-методические п...
8319. Личность в системе профессиональной подготовки 520 KB
  Профессиональная подготовка - одна из важнейших сфер жизни общества Прогрессивное движение выражается в развитии, совершенствовании и усложнении профессий, а, следовательно, в требований профессиональной подготовки. Современная тенденция формировать...