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

  •  В ячейках 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

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


 

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

5675. Теорія алгоритмів і основи представлення знань 339 KB
  Вступ. Інтуїтивне поняття алгоритму. Поняття алгоритму інтуїтивно зрозуміло і часто використовується в математиці. Додавання і множення чисел стовпчиком, що відомо ще зі школи, формула обчислення коренів квадратного рівняння,...
5676. Економіка підприємств. Курс лекцій 1.59 MB
  Підприємство як суб'єкт господарювання Введення, предмет та завдання дисципліни. Галузева структура народного господарства України. Загальна характеристика підприємств. Структура управління підприємством. Зовнішнє середовищ...
5677. Економічна теорія (Економіка). Конспект лекцій 1.06 MB
  Загальні основи економічної теорії Тема 1.1 Економічна теорія: предмет і методи пізнання 1. Поняття економіки як системи економічних знань. Обмеженість ресурсів та безмежність потреб. Предмет курсу економічної теорії. Мета і функції економі...
5678. Історія економіки та економічної думки. Предмет і метод історії економіки та економічної думки 1.3 MB
  Предмет і метод історії економіки та економічної думки Поява історії економіки та економічної думки як самостійної учбової дисципліни в учбових планах і програмах провідних вузів України та країн Західної Європи було обумовлено необхідністю...
5679. Психологія. Конспект лекцій. Предмет і методи психології 273.5 KB
  Передмова Курс Психологія являє собою складову частину загальногуманітарної підготовки студентів. Психологія - одна з найцікавіших у світі наук. Саме психологія дає змогу відшукати відповіді на життєво важливі питання: як і чому люди думають,...
5680. Релігієзнавство. Курс лекцій. Релігія та суспільство 85.25 KB
  Лекція 1. Релігія та суспільство Поняття та сутність релігії: а) богословсько-теологічне дослідження релігії б) філософський аналіз релігії в) наукові теорії дослідження релігії. Виникнення релігії: а) формування релігійних уявле...
5681. Охорона праці в галузі. Конспект лекцій 636.5 KB
  Основні поняття організації охорони праці в галузі Виробниче середовище - частина техносферы, що володіє підвищеною концентрацією негативних чинників. Основними носіями травмуючих і шкідливих чинників у виробничому середовищі є машини і т...
5682. Основи замлевпорядкування та кадастру. Курс лекцій 2.09 MB
  Нормативно-правові основи землевпорядкування та кадастру Нормативно-правове підгрунтя в системі землевпорядкування та кадастру за нормами міжнародного права Національна система законодавства в галузі землевпорядкування та ...
5683. Інформаційно-аналітична діяльність. Наукова обробка документів 677.5 KB
  Обсяг і зміст матеріалу, що увійшов до конспекту лекцій відповідають вимогам робочої програми з дисципліни Інформаційнно - аналітична діяльність. Конспект лекцій містить мету і завдання дисципліни, програму курсу. У кінці конспекту лекцій пода...