Прикладные программы

     ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

     ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ  УЧРЕЖДЕНИЕ ВЫСШЕГО  ПРОФЕССИОНАЛЬНОГО  ОБРАЗОВАНИЯ

       МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ  УНИВЕРСИТЕТ ПРИБОРОСТРОЕНИЯ  И ИНФОРМАТИКИ

     _____________________________________________________________Кафедра  УП -1 
 
 
 
 
 
 
 
 
 
 

     Домашняя  работа по дисциплине «Теория и методы принятия решений» 
 

     ВАРИАНТ №3 (задача о назначениях) 
 
 
 
 
 
 
 
 

     Студентка Бороздина Ирина  Евгеньевна

     Специальность 080505, курс 4, группа 0802 

     Проверил: Серегин Алексей  Николаевич 
 
 
 
 
 

М – 2011 
 

Введение:

Целью домашней работы является расширение и углубление практических знаний в области применения стандартных прикладных программ при постановке и решении задач линейного программирования. 

Задачи  данной работы:

1. Сформулировать задачу о назначениях.

2. Решить Венгерским методом.

3. Решить  задачу с помощью MS Excel. 

Задача  о назначениях - частный случай транспортной задачи, в которой количество пунктов производства и потребления равны, т.е транспортная таблица имеет форму квадрата, а объем потребления и производства в каждом пункте равен 1. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

     Задача:

     В конкурсе на занятие пяти вакансий (V1, V2, V3, V4, V5) участвуют семь претендентов (P1, P2, P3, P4, P5, P6, P7). Результаты тестирования каждого претендента, на соответствующие вакансии, даны в виде матрицы (тестирование производилось по десятибалльной системе). 

	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

     Определить, какого претендента и на какую  вакансию следует принять, причем так, чтобы сумма баллов всех претендентов оказалась максимальной. 

     Решение:

     I. Формулировка задачи о назначениях .

     1) Переменные задачи:

     Ведем переменные x_ij принимающие два значения:

     x_ij=0, если i-й претендент (P_i) не принимается на j-ю    вакансию (V_j).

     x_ij=1, если i-й претендент (P_i) принимается на вакансию (V_j).

     i=1,2,...7; j=1,2,...5.

     2) Ограничения:

     Очевидно, что все переменные задачи неотрицательные  и целые числа: x_ij 0  и x_ij - целые.

     Кроме того, так как каждый претендент может занять только одну вакансию и все вакансии должны быть заняты, должны удовлетворяться следующие  ограничения:

      , j=1,2,...7 ,

      , i=1,2,...5 ,

     другими словами в матрице (x_ij) суммы элементов по каждой строке и суммы элементов по каждому столбцу должны быть равны единицам. Это условие означает, что выбор претендентов должен быть таким, чтобы в матрице (x_ij), представляющей решение задачи, было бы по одной единице в каждой строке и по одной единице в каждом столбце, остальные элементы матрицы должны равняться нулю.

     3) Целевая функция:

     Необходимо  выбрать претендентов так, чтобы  суммарное число очков, набранное ими было бы максимальным. Суммарное число набранных очков вычисляется по формуле:

      ;

     Z=c₁₁x₁₁+c₁₂x₁₂+...+c₇₅x₇₅=7x₁₁+5x₁₂+...+4x₇₅;

     Окончательная математическая модель задачи записывается так:

     найти max ;

     при ограничениях:

     x_ij 0  и x_ij - целые числа, i=1,2,...7; j=1,2,...5;

      , j=1,2,...7 ;

      , i=1,2,...5 .

     II. Решение задачи Венгерским методом:

     Рассмотрим  решение задачи о назначениях, в  которой нужно найти min функции Z. Предварительно задачу о назначениях нужно сбалансировать. В рассматриваемом примере эта процедура выполняется добавлением двух столбцов (две фиктивные вакансии) с нулевыми результатами тестирования:

     

     Задача  нахождения минимального значения функции  Z эквивалентна задаче нахождения минимума для функции , матрица имеет вид:

     -

     нетрудно  показать, что при вычитании из всех элементов столбца или строки матрицы одного и того же числа, решения  x_ij при которых функция имеет минимум не меняется. Поэтому матрицу преобразуем по следующему правилу. В каждой строке и в каждом столбце образуют нули, вычитая минимальные элементы из соответствующих строк или столбцов. Если среди нулевых элементов матрицы можно получить допустимое решение задачи, то оно является оптимальным. Напомним, что допустимым решением является такой выбор из нулей, при котором выбирается по одному нулю в каждой строке и по одному нулю в каждом столбце.

     В рассматриваемом примере в каждой строке матрицы нули есть (они появились  в результате добавления фиктивных  вакансий). Чтобы образовать нули в  первых пяти столбцах матрицы, определяем минимальные элементы в этих столбцах: -8, -9, -8, -9, -9 и вычитаем эти элементы из соответствующих столбцов матрицы.

       В результате получим следующую матрицу:

1	4	1	3	2	0	0
2	5	0	5	0	0	0
0	3	4	6	1	0	0
1	2	0	4	2	0	0
3	0	1	0	4	0	0
1	1	2	5	2	0	0
2	2	0	3	5	0	0

 

     Так как из нулевых элементов нельзя получить допустимое решение (в первой и шестой строках, а также в  четвертой и седьмой строках  нули стоят на одном и том же месте), то алгоритм продолжается следующим  образом:

     a) минимальным количеством горизонтальных и вертикальных прямых вычеркиваем все нули.

     b) среди не вычеркнутых элементов находим минимальный элемент;

     c) вычитаем минимальный элемент из всех вычеркнутых элементов;

4. к элементам, стоящим на пересечении вертикальных и горизонтальных прямых, прибавляем минимальный элемент.

     Среди множества получаемых нулевых элементов  определяем допустимое решение. Если допустимое решение найти нельзя, повторяем  шаги a, b, c, d снова.

     Процедура вычеркивания элементов и ее результат  показаны на рисунке. Минимальный среди не вычеркнутых элементов равен единице.

      Допустимое решение соответствует  отмеченным элементам.

1	4	1	3	2	0	0
2	5	0	5	0	0	0
0	3	4	6	1	0	0
1	2	0	4	2	0	0
3	0	1	0	4	0	0
1	1	2	5	2	0	0
2	2	0	3	5	0	0

                          

     Далее показан результат после вычитания единицы из не вычеркнутых элементов и прибавления единицы к элементам, стоящим на пересечении прямых.  

1	3	1	2	1	0	0
3	5	1	5	0	1	1
0	2	4	5	0	0	0
1	1	0	3	1	0	0
4	0	2	0	4	1	1
1	0	2	4	1	0	0
2	1	0	2	4	0	0

 

     Перенеся  полученное решение на исходную матрицу:

7	5	7	6	7	0	0
6	4	8	4	9	0	0
8	6	4	3	8	0	0
7	7	8	5	7	0	0
5	9	7	9	5	0	0
6	8	6	4	7	0	0
7	7	8	6	4	0	0