Практическое занятие №9.

«Задача о назначениях»

1. Цель работы.

Найти оптимальное распределение работников по заданным работам.

2. Порядок выполнения работы

1. Из приложения 3 выбрать свой вариант.

2. Решить задачу о назначениях:

• Венгерским методом;

• методом Мака.

3. Краткая теория

Венгерский метод.

1) В исходной матрице стоимостей определим в каждой строке минимальную стоимость и отнимем ее от других элементов строки, затем в каждом столбце минимальную стоимость и отнимем ее от других элементов столбца.

2) Если допустимое решение получено, то оптимальные назначения соответствуют нулевым элементам. Завершить работу.

3) Иначе: В последней матрице провести минимальное число горизонтальных и вертикальных прямых, чтобы вычеркнуть все нулевые элементы.

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

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

Метод Мака.

1. Увеличить все элементы матрицы А на выбранную на 2-м шаге минимальную разность.

2. В строке с минимальной разностью отметить пунктиром минимальный неподчеркнутый элемент

3. Столбец, содержащий отмеченный пунктиром элемент , перенести в множество С. Если в С более 2-х неподчеркнутых элементов, то перенести С из A' в А и перейти ко 2-му шагу. Иначе, перейти к 6-му шагу.

4. Отмеченный пунктиром элемент подчеркнуть.

5. Найти исходный подчеркнутый элемент в строке с минимальной разностью и убрать подчеркивание. Обозначить столбец с элементом D.

6. Если D не содержит других подчеркнутых элементов, он должен содержать элементы, отмеченные пунктиром. Обозначить этот элемент и перейти к 6-му шагу. ЕслиD содержит еще 1 подчеркнутый элемент, то полностью подчеркнутые элементы образуют новый базис. В этом случае перейти к 1-му шагу.

Практическое занятие №10. «Теория игр»

1. Цель работы

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

1. Порядок выполнения работы

1. Исходные данные взять из приложения 3. Четные числа оставить положительными, а нечетные – сделать отрицательными.

2) При решении матричной игры нужно выделить следующие этапы:

1. Проверить, имеет ли игра решение в чистых стратегиях.

2. Упростить платежную матрицу.

3. Если среди элементов платежной матрицы есть отрицательные, то ко всем элементам матрицы необходимо прибавить такое число L > 0, чтобы все элементы стали неотрицательными. При этом цена игры увеличится на L, а оптимальные смешанные стратегии не изменятся.

4. Составить пару взаимно двойственных задач ЛП, эквивалентных данной матричной игре.

5. Определить оптимальные планы двойственных задач.

6. Найти решение игры.

Список литературы.

1. Львовский Е.Н. Статистические методы построения эмпирических формул: Учебное пособие для ВТУЗов. —М.: Высшая школа, 1988.—239 с.

2. Львовский Е.Н. Статистические методы построения эмпирических формул: Учебное пособие для ВТУЗов. —М.: Высшая школа, 1988.—239 с.

3. Орлов А.И. Теория приянтия решений. [текст]: учебное пособие / А.И. Орлов. – М.: Март, 2004. – 60 с.

4. Пакет прикладных программ ОТЭКС (для анализа данных)\Н.Г.Загоруйко, В.Н. Елкина, С.В. Емельянов. —М.: Финансы и статистика, 1986. —160 с.

5. Штойер Р. Многокритериальная оптимизация. Теория, вычисления, приложения. – М.: Радио и связь, 1992, - 683 с.

Приложение 1

Приложение 1

Приложение 2

№В	потребители (B)						1	142	140	141	140	138		2	142	139	142	140	135
произв-ли(А)	Стоимости						137	7	10	8	5	11		138	6	5	9	13	7
							141	5	7	13	8	13		141	5	10	13	8	7
							139	10	7	6	5	9		143	9	7	10	7	9
							284	7	10	7	9	6		276	6	12	7	10	7
3	141	139	143	137	140		4	140	138	137	139	138		5	103	100	97	95	98
141	5	11	8	12	7		140	13	11	8	12	5		104	16	14	17	3	6
136	13	6	8	7	5		143	13	8	12	10	13		103	10	15	14	16	18
138	11	9	6	13	7		138	8	12	5	11	6		101	4	7	5	3	10
285	5	8	6	11	5		271	10	7	12	9	7		185	18	15	13	16	17
6	125	120	123	119	121		7	87	85	80	78	83		8	65	70	73	71	66
124	3	10	4	7	8		81	12	13	8	9	15		68	9	15	11	7	11
126	3	9	11	7	10		79	10	13	8	13	15		70	15	10	14	11	9
122	3	6	8	4	9		82	16	14	11	14	12		74	12	11	15	10	7
236	7	11	6	3	10		171	9	15	13	8	14		133	8	10	15	13	11
9	59	55	54	60	56		10	111	120	118	115	121		11	75	70	67	65	63
58	12	14	6	8	9		113	8	4	6	3	10		66	7	12	14	11	15
61	12	14	8	6	13		117	4	5	3	7	10		69	12	9	7	12	15
63	9	11	10	12	6		120	6	9	5	3	7		73	12	7	10	13	15
102	9	7	12	14	7		235	9	11	6	4	9		132	11	7	10	12	8
12	110	117	120	115	113		13	67	63	61	68	70		14	153	157	163	160	158
112	6	8	5	11	3		71	8	13	7	12	9		154	11	13	9	12	14
118	7	2	3	6	10		74	7	13	15	8	13		162	7	10	13	9	11
111	5	11	3	6	3		72	9	10	13	7	15		163	10	7	13	9	11
234	5	3	9	8	11		112	8	12	9	11	9		312	10	14	9	13	9
15	135	137	145	143	136		16	167	169	173	164	168		17	130	135	133	136	132
139	10	7	11	13	8		166	15	13	11	8	15		137	9	5	6	9	13
143	11	10	10	9	5		170	14	11	15	12	8		134	5	9	7	4	6
140	10	7	8	6	11		174	14	11	15	9	14		138	11	6	13	8	6
274	9	13	10	8	5		331	10	15	13	11	8		257	4	7	10	13	6
18	159	157	155	148	153		19	77	73	66	69	72		20	95	97	100	101	96
157	15	9	13	6	8		75	12	14	7	10	12		103	17	6	18	15	10
149	14	8	13	6	13		77	14	9	7	8	15		97	3	17	2	18	14
156	9	11	15	8	6		69	14	12	7	13	15		104	4	6	5	16	14
310	13	9	12	15	13		136	10	14	12	13	15		185	17	10	4	10	6

Приложение 2

21	145	143	140	144	139		22	177	170	168	169	167		23	121	123	128	125	129
142	10	5	8	6	10		173	10	8	14	16	10		131	4	11	5	12	8
135	11	9	12	5	13		175	12	14	13	15	9		124	4	6	10	5	8
139	9	6	10	13	10		177	16	15	11	14	16		126	6	4	10	5	12
295	12	9	11	13	8		326	10	8	13	15	10		245	6	8	11	4	10
24	117	110	112	115	113		25	120	123	128	124	121		26	110	113	118	114	111
111	8	3	8	6	7		125	9	11	7	4	8		115	4	10	7	2	5
110	5	9	4	2	6		127	6	10	5	12	10		117	3	7	9	8	10
109	9	4	2	5	8		130	7	11	8	6	11		119	4	11	7	3	6
237	9	7	2	8	9		234	5	3	8	12	10		215	2	5	8	11	4
27	100	104	109	111	108		28	90	92	96	93	95		29	80	84	87	82	80
106	6	10	3	7	9		97	12	16	18	13	9		83	14	17	10	15	12
103	5	2	4	9	2		94	12	16	18	2	17		85	16	13	10	8	11
101	8	6	4	10	5		91	14	10	12	16	11		88	13	16	12	14	17
222	10	3	2	6	4		184	9	17	10	16	11		157	11	9	10	8	12
30	70	73	75	72	76		31	60	65	62	67	69		32	50	53	58	54	50
81	8	11	14	16	11		71	6	11	14	7	13		53	13	8	5	7	11
79	7	10	15	9	16		66	8	7	10	12	15		59	14	7	12	9	5
75	11	8	12	16	10		63	13	9	6	11	8		55	8	11	14	7	11
131	7	13	9	8	14		123	10	13	15	8	13		98	6	8	12	14	7
33	75	79	76	70	74		34	92	97	101	96	94		35	115	113	117	112	110
80	12	16	9	14	16		90	13	16	14	18	15		114	11	4	9	6	3
76	11	9	7	10	15		93	10	13	12	9	14		116	5	10	3	9	4
72	9	14	12	10	16		98	16	18	12	10	14		120	7	4	10	3	8
146	9	15	13	9	7		199	16	13	15	10	16		217	3	6	10	4	9
36	60	63	68	69	64		37	81	87	84	90	85
62	15	10	8	13	15		82	10	15	12	10	8
65	8	12	10	6	9		86	13	11	15	17	10
71	13	7	14	10	8		88	14	11	9	13	10
126	12	15	8	13	7		171	8	14	12	15	10

Приложение 3

1	7	5	6	5	12		2	7	13	7	5	9		3	6	13	8	11	5
	11	6	13	7	10			12	6	8	6	5			6	10	12	5	11
	8	5	11	5	7			9	13	7	5	10			8	12	7	13	6
	13	8	13	10	7			13	8	7	9	7			8	7	5	11	9
	6	5	9	7	10			10	7	9	6	12			6	13	7	5	8

Приложение 3

4	5	12	11	13	12		5	4	10	16	14	17		6	8	3	6	11	4
	5	8	12	13	11			5	4	2	16	14			7	9	5	3	10
	8	12	5	13	8			17	3	6	10	15			4	7	8	3	9
	12	10	13	8	12			14	16	18	4	7			11	7	10	3	6
	5	11	6	10	7			5	3	10	18	15			8	4	9	7	11
7	15	13	8	15	11		8	11	7	10	8	12		9	14	10	9	6	11
	9	16	10	12	13			14	7	11	9	15			13	7	9	12	14
	8	9	15	10	13			11	7	11	15	10			6	8	9	12	14
	8	13	15	16	14			14	11	9	12	11			8	6	13	9	11
	11	14	12	9	15			15	10	7	8	10			10	12	6	9	7
10	3	3	10	7	4		11	12	7	13	11	9		12	2	9	3	7	5
	5	9	3	8	4			12	15	10	7	12			4	10	3	6	8
	6	3	10	4	5			14	11	15	12	9			5	11	3	7	2
	3	7	10	6	9			7	12	15	12	7			3	6	10	5	11
	5	3	7	9	11			10	13	15	11	7			3	6	3	5	3
13	13	9	7	14	7		14	9	13	10	7	14		15	9	11	10	8	10
	8	11	9	8	13			10	9	10	11	13			13	8	5	10	7
	7	12	9	7	13			9	12	14	7	10			11	13	8	11	10
	15	8	13	9	10			13	9	11	10	7			10	9	5	10	7
	13	7	15	8	12			13	9	11	10	14			8	6	11	9	13
16	14	16	11	11	15		17	4	9	7	10	6		18	15	13	11	13	9
	13	8	12	15	13			11	8	12	9	5			13	14	12	15	9
	11	8	15	14	11			6	9	13	5	9			13	6	8	14	8
	15	12	8	14	11			7	4	6	11	6			13	6	13	9	11
	15	9	14	10	15			13	8	6	4	7			15	8	6	13	9
19	14	10	12	15	9		20	14	16	10	2	15		21	10	8	5	9	13
	12	14	15	12	14			4	16	5	17	6			7	9	13	10	5
	7	10	12	14	9			18	15	10	3	17			8	6	10	11	9
	7	8	15	14	12			2	18	14	4	6			12	5	13	9	6
	7	13	15	10	14			5	16	14	17	10			10	13	10	12	9
22	15	8	15	16	14		23	4	6	11	8	12		24	9	2	4	7	5
	11	13	15	10	8			5	7	9	4	11			3	2	10	8	3
	14	16	10	12	14			5	12	8	4	6			8	6	7	5	9
	13	15	9	16	15			10	5	8	6	4			4	2	6	9	4
	11	14	16	10	8			10	5	12	6	8			2	5	8	9	7

Приложение 3

25	3	6	11	7	4		26	2	5	10	6	3		27	10	5	10	3	9
	8	10	4	9	11			7	9	11	4	10			7	4	2	6	10
	7	4	8	6	10			7	2	5	3	7			3	7	9	5	2
	5	12	10	7	11			9	8	10	4	11			4	9	2	8	6
	8	6	11	5	3			7	3	6	2	5			4	10	5	10	3
28	9	11	15	12	14		29	8	12	15	10	8		30	7	10	12	9	13
	16	13	10	12	16			11	13	16	14	17			9	16	12	8	11
	18	13	9	12	16			10	15	12	16	13			14	16	11	7	10
	18	2	17	14	10			10	8	11	13	16			15	9	16	11	8
	12	16	11	9	17			12	14	17	11	9			12	16	10	7	13
31	6	11	8	13	15		32	5	8	13	9	5		33	12	16	13	7	11
	8	12	9	6	11			8	14	10	13	8			8	13	9	12	16
	14	7	13	8	7			5	7	11	14	7			9	14	16	11	9
	10	12	15	13	9			12	9	5	8	11			7	10	15	9	14
	6	11	8	10	13			14	7	11	6	8			12	10	16	9	15
34	11	16	2	15	13		35	7	5	9	4	2		36	6	9	14	15	10
	9	12	17	13	16			6	8	3	11	4			8	11	8	15	10
	14	18	15	10	13			9	6	3	5	10			8	13	15	8	12
	12	9	14	16	18			3	9	4	7	4			10	6	9	13	7
	12	10	14	16	13			10	3	8	3	6			14	10	8	12	15
37	9	15	12	9	13
	10	14	16	10	15
	12	10	8	13	11
	15	17	10	14	11
	9	13	10	8	14

17