Практическая работа №9 Вариант 17 / Практика_№9
.docМИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ
ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
ЛИПЕЦКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
КАФЕДРА АВТОМАТИЗИРОВАННЫХ СИСТЕМ УПРАВЛЕНИЯ
Практическая работа №9
«Задача о назначениях»
по дисциплине
«Теория принятия решений»
|
|
Студент |
|
|
|
Филатов А.А. |
|
||||||||
|
|
|
|
подпись, дата |
|
фамилия, инициалы |
|
||||||||
|
|
Группа |
|
АС-09 |
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
||||||||
|
|
Принял |
|
|
|
|
|
||||||||
|
|
|
|
|
|
Корнеев А.М. |
|
||||||||
|
|
ученая степень, звание |
|
подпись, дата |
|
фамилия, инициалы |
|
||||||||
Липецк 2012
1. Задание
Найти оптимальное распределение работников по заданным работам.
Из приложения 3 выбрать свой вариант.
Решить задачу о назначениях:
1) Венгерским методом;
2) методом Мака.
2. Решение
|
Вариант 17 |
Работы |
|||||
|
|
|
|
|
|
||
|
Работники |
|
4 |
9 |
7 |
10 |
6 |
|
|
11 |
8 |
12 |
9 |
5 |
|
|
|
6 |
9 |
13 |
5 |
9 |
|
|
|
7 |
4 |
6 |
11 |
6 |
|
|
|
13 |
8 |
6 |
4 |
7 |
|
1) Решим задачу о назначениях Венгерским методом.
Найдем в каждой строке минимальную стоимость:
|
4 |
9 |
7 |
10 |
6 |
|
11 |
8 |
12 |
9 |
5 |
|
6 |
9 |
13 |
5 |
9 |
|
7 |
4 |
6 |
11 |
6 |
|
13 |
8 |
6 |
4 |
7 |
Вычтем из каждого элемента строки минимальную стоимость:
|
0 |
5 |
3 |
6 |
2 |
|
6 |
3 |
7 |
4 |
0 |
|
1 |
4 |
8 |
0 |
4 |
|
3 |
0 |
2 |
7 |
2 |
|
9 |
4 |
2 |
0 |
3 |
Найдем в каждом столбце минимальную стоимость:
|
0 |
5 |
3 |
6 |
2 |
|
6 |
3 |
7 |
4 |
0 |
|
1 |
4 |
8 |
0 |
4 |
|
3 |
0 |
2 |
7 |
2 |
|
9 |
4 |
2 |
0 |
3 |
Вычтем из каждого элемента столбца минимальную стоимость:
|
0 |
5 |
1 |
6 |
2 |
|
6 |
3 |
5 |
4 |
0 |
|
1 |
4 |
6 |
0 |
4 |
|
3 |
0 |
0 |
7 |
2 |
|
9 |
4 |
0 |
0 |
3 |
Данное решение является допустимым, оптимальные назначения соответствуют нулевым элементам:
|
0 |
5 |
1 |
6 |
2 |
|
6 |
3 |
5 |
4 |
0 |
|
1 |
4 |
6 |
0 |
4 |
|
3 |
0 |
0 |
7 |
2 |
|
9 |
4 |
0 |
0 |
3 |
Значит, оптимальные назначения имеют вид:
|
4 |
9 |
7 |
10 |
6 |
|
11 |
8 |
12 |
9 |
5 |
|
6 |
9 |
13 |
5 |
9 |
|
7 |
4 |
6 |
11 |
6 |
|
13 |
8 |
6 |
4 |
7 |
Таким образом,
значение функции:
.
2) Решим задачу о назначениях методом Мака.
|
4 |
9 |
7 |
10 |
6 |
|
|
11 |
8 |
12 |
9 |
5 |
|
|
6 |
9 |
13 |
5 |
9 |
|
|
7 |
4 |
6 |
11 |
6 |
|
|
13 |
8 |
6 |
4 |
7 |
|
|
4 |
9 |
7 |
10 |
6 |
|
|
11 |
8 |
12 |
9 |
5 |
|
|
*6* |
9 |
13 |
5 |
9 |
1 |
|
7 |
4 |
6 |
11 |
6 |
|
|
13 |
8 |
6 |
4 |
7 |
2 |
|
C |
|
|
A |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
4 |
9 |
7 |
10 |
*6* |
2 |
|
11 |
8 |
12 |
9 |
5 |
|
|
*6* |
9 |
13 |
5 |
9 |
4 |
|
7 |
4 |
6 |
11 |
6 |
|
|
13 |
8 |
6 |
4 |
7 |
2 |
|
A |
|
|
A |
C |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
4 |
9 |
7 |
10 |
*6* |
3 |
|
11 |
8 |
12 |
9 |
5 |
3 |
|
*6* |
9 |
13 |
5 |
9 |
4 |
|
7 |
4 |
6 |
11 |
6 |
|
|
13 |
8 |
*6* |
4 |
7 |
2 |
|
A |
|
C |
A |
A |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
6 |
9 |
7 |
12 |
*8* |
3 |
|
13 |
8 |
12 |
11 |
7 |
3 |
|
*8* |
9 |
13 |
7 |
11 |
4 |
|
9 |
4 |
6 |
13 |
8 |
|
|
15 |
8 |
6 |
6 |
9 |
2 |
|
A |
|
C |
A |
A |
|
|
|
|
|
D |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
6 |
9 |
7 |
12 |
*8* |
|
|
13 |
8 |
12 |
11 |
7 |
|
|
*8* |
9 |
13 |
7 |
11 |
|
|
9 |
4 |
6 |
13 |
8 |
|
|
15 |
8 |
6 |
6 |
9 |
|
|
A |
|
C |
A |
A |
|
|
|
|
|
D |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
6 |
9 |
7 |
12 |
8 |
|
|
13 |
8 |
12 |
11 |
7 |
|
|
8 |
9 |
13 |
7 |
11 |
|
|
9 |
4 |
6 |
13 |
8 |
|
|
15 |
8 |
6 |
6 |
9 |
|
Таким образом, значение функции: f = 30.