Методичка Зайцева

x + 2x

≤ 8

y −

x − 4

≤ 3

x ≥ 3

1

2

≤ 6

3x1 + x2 ≤15

2 ≤ x

3x + 5y ≤ 24

≥1

27.

28.

29.

x1 + x2

y ≥ 0

y ≥ 0

x ≥ 0;x

2

≥ 0

f = y −

x − 4

f = x2 + y2

1

f = (x − 6)2 + (x − 2)2

1

2

x + 2x

≥ 2

x + x

≤ 7

1

2

1

2

x1 + x2 ≤ 6

2x1 − x2 ≤ 8

30. 2x1 + x2 ≤11

31. x1

≥ 0

x ≥ 0;x

2

≥ 0

x ≥ 0

1

2

f = 2(x − 7)2

+ 4(x

2

− 3)2

f = 4(x − 2)2 + 2(x − 2)2

1

1

2

3.7. Задача нелинейного программирования

Дана кривая второго порядка вида:

f= a11x2 + a12xy + a22y2 + a13x + a23y + a33.

1.Определить вид кривой второго порядка и аналитически найти точку минимума.

2.Методом градиентного спуска с точностью до тысячных найти минимальное значение функции:

в качестве начальной точки взять (x0, y0). Делать до пяти итераций. Исходные данные представлены в табл. 3.2

								Таблица 3.2
Вариант	a11	a12	a22	a13	a23	a33	x0		y0
1	1	2	1	–60	–60	300	2		1
2	1	2	1	–66	–36	273	12		8
3	1	2	1	–48	–78	387	3		2
4	1	2	1	–86	–88	631	18		8
5	1	2	1	–106	–104	919	2		1
6	1	2	1	–38	–40	127	13		6
7	1	2	1	–84	–54	453	4		17
8	1	2	1	–22	–38	91	12		3
9	1	2	1	–88	–68	532	13		1
10	1	2	1	–38	–70	307	15		9
11	1	2	1	–14	–10	13	16		17
12	1	2	1	–78	–96	651	13		0
13	1	2	1	–46	–44	169	1		1
14	1	2	1	–48	–54	219	15		17

43

Окончание табл. 3.2

Вариант	a11	a12	a22	a13	a23	a33	x0	y0
15	1	2	1	–84	–96	684	18	15
16	1	2	1	–104	–88	784	13	10
17	1	2	1	–62	–34	241	3	5
18	1	2	1	–100	–80	700	15	7
19	1	2	1	–64	–68	364	2	5
20	1	2	1	–32	–46	139	17	4
21	1	2	1	–64	–86	499	7	18
22	1	2	1	–84	–72	516	20	19
23	1	2	1	–46	–44	169	2	2
24	1	2	1	–72	–66	399	14	18
25	1	2	1	–60	–60	300	1	2
26	1	2	1	–112	–104	976	17	17
27	1	2	1	–64	–68	364	5	6
28	1	2	1	–64	–86	499	1	18
29	1	2	1	–46	–32	139	9	11
30	1	2	1	–62	–88	511	4	13
31	1	2	1	–40	–56	208	6	9
32	1	2	1	–40	–32	112	17	12
33	1	2	1	–84	–84	588	15	17
34	1	2	1	–32	–22	67	14	13
35	1	2	1	–86	–82	589	2	14
36	1	2	1	–86	–52	469	20	15
37	1	2	1	–30	–36	93	12	7
38	1	2	1	–68	–88	532	9	8
39	1	2	1	–10	–14	13	19	4
40	1	2	1	–54	–60	273	4	20
41	1	2	1	–60	–60	300	9	12
42	1	2	1	–84	–54	453	6	0
43	1	2	1	–56	–82	439	12	9
44	1	2	1	–66	–42	279	6	3
45	1	2	1	–52	–56	244	7	7
46	1	2	1	–22	–38	91	2	19
47	1	2	1	–80	–70	475	13	14
48	1	2	1	–16	–32	64	9	7
49	1	2	1	–66	–36	273	5	20
50	1	2	1	–36	–60	228	1	14
51	1	2	1	–62	–46	259	11	5
52	1	2	1	–96	–84	684	3	2
53	1	2	1	–50	–46	193	18	4
54	1	2	1	–30	–18	57	2	6
55	1	2	1	–56	–40	208	20	11

44

ЗАДАНИЕ № 4

ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ. МАТРИЧНЫЕ ИГРЫ

4.1.Задание для предложенного варианта

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

Таблица 4.1

	№	Матрица			№	Матрица			№	Матрица			№	Матрица
	вар.				вар.				вар.				вар.
		4	6	7		4	8	12		2	4	5		3	5	4
	1	8	9	8	2	4	5	10	3	6	2	4	4	7	1	12
		3	5	4		6	7	8		4	6	8		9	10	2
		4	5	4		5	6	12		4	3	5		6	3	5
	5	8	7	12	6	6	10	8	7	7	6	2	8	5	2	4
		3	8	4		5	2	7		6	5	1		4	3	3
		3	4	6		5	6	7		4	3	5		3	10	4
	9	5	8	7	10	4	5	6	11	6	7	8	12	11	2	5
		9	9	2		6	7	8		6	5	6		1	6	7
		6	7	8		6	4	1		12	8	7		4	3	10
	13	10	5	6	14	7	10	2	15	8	9	16	16	3	8	12
		4	6	10		8	5	6		2	1	4		5	9	4
		8	6	6		8	7	10		8	10	12		9	10	12
	17	12	7	8	18	12	4	5	19	12	4	5	20	4	1	2
		4	8	9		3	8	7		10	12	6		6	7	8
		10	7	3		5	6	7		4	8	12		2	4	5
	21	11	12	5	22	3	5	4	23	4	5	4	24	3	4	6
		5	2	4		6	7	8		6	4	1		8	7	10

4.1.2.Свести игру в матричной постановке к задаче линейного программирования. Показать, что прямая задача линейного программирования и двойственная задача линейного программирования соответствуют смешанным стратегиям (соответственно для первого и второго игроков).

4.1.3.С помощью симплекс-метода найти решение матричной игры в смешанных стратегиях, т.е. найти:

–смешанную стратегию первого игрока как решение прямой задачи линейного программирования;

–смешанную стратегию второго игрока как решение двойственной задачи линейного программирования;

–цену игры как значение целевой функции указанных задач линейного программирования.

45

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

																									Таблица 4.2
	№	Исходные данные												№	Исходные данные
	вар.													вар.
				7				8			9						7				6			8
		6				9			7		4				7				9			7		5
					8			6			7							8			6			7
	1	9							8		5			2	8							7		6
						7													6
					9			5			6							8			5			7
											4													5
		8				6			5						7				6			7
								6			4
		7													7				7					4
				7				6			4						7				7			4
		9				7			8		5				8				6			7		6
											7													7
					8			6										8			6
	3	6							7		4			4	7							7		5
						9													9
					7			8			9							7			6			8
											4													5
		8				6			5						7				6			7
								8			9										7			8
		7													5
				3				4			6						5				6			7
		9				8			7		5				8				6			7		6
											6													6
					8			7										7			5
	5	5							7		9			6	5							8		8
						7													7
					7			6			5							5			6			5
											6													6
		9				8			7						8				7			7
								6			8										4			4
		4													4
				8				6			8						7				6			8
		9				8			7		6				7				7			6		8
											5													7
					7			6										5			6
	7	5							7		9			8	8							8		8
						7													7
					4			5			6							7			8			9
											9													9
		4				5			7						4				6			8
								7			8										6			7
		6													5
				6				7			8						5				6			7
		5				7			7		9				8				7			8		8
											6													9
					4			5										7			8
	9	9							7		6			10	8							7		5
						8													6
					4			6			8							4			6			8
											5													7
		9				7			8						8				6			7
								6			8										6			8
		4													4

46

Продолжение табл. 4.2

	№	Исходные данные												№	Исходные данные
	вар.													вар.
				3				4			5						5				6			7
		9				8			7		5				8				6			7		6
					8			7			6							7			5			6
	11	5							7		9			12	5							8		9
						7													7
					7			6			5							5			6			5
											6													6
		9				8			7						8				7			7
								6			8										4			8
		4													4
				8				7			6						7				6			7
		9				7			8		5				4				6			8		9
											8													5
					4			6										5			6
	13	4							7		9			14	4							8		9
						5													6
					4			5			6							7			8			9
											9													8
		9				7			8						7				9			9
								6			8										6			7
		4													5
				5				6			7						3				4			5
		8				6			7		6				9				8			7		5
											6													6
					7			5										8			7
	15	5							8		9			16	5							7		9
						7													7
					5			6			5							7			6			5
											6													9
		8				7			7						9				7			8
								4			8										6			8
		4													4
				3				4			6						5				6			7
		9				8			7		5				8				6			7		6
											6													6
					8			7										7			5
	17	5							7		9			18	5							8		9
						7													7
					7			6			5							5			6			5
											6													6
		8				6			7						8				7			7
								6			8										4			8
		4													4
				8				6			8						7				6			7
		9				8			7		6				4				6			8		9
											5													6
					7			6										4			5
	19	5							7		9			20	4							8		9
						7													6
					4			5			6							7			8			9
											9													5
		4				5			7						9				8			7
								7			8										6			7
		6													5

47

Окончание табл. 4.2

	№	Исходные данные												№	Исходные данные
	вар.													вар.
				6				7			8						3				4			5
		5				7			7		9				9				8			7		5
					4			5			6							8			7			6
	21	9							7		6			22	5							7		9
						8													7
					4			6			8							7			6			5
											5													4
		7				6			7						8				6			5
								6			8										6			8
		4													4
				7				6			4						7				7			4
		9				7			8		5				8				6			7		6
											7													7
					8			6										8			6
	23	6							7		4			24	9							8		5
						9													7
					7			8			9							7			6			8
											4													5
		8				6			5						7				6			7
								8			9										7			8
		7													5
				6				9			8						5				6			7
		5				7			7		9				8				7			8		7
											6													9
					4			9										7			8
	25	9							7		6			26	8							7		5
						8													6
					4			9			8							4			7			8
											5													7
		9				7			8						8				6			7
								9			8										6			8
		4													4
				6				7			8						5				6			7
		5				7			7		9				8				7			8		8
											6													9
					4			5										7			8
	27	3							7		6			28	8							7		5
						3													6
					4			6			8							2			6			8
											5													7
		9				3			8						8				2			7
								6			8										6			8
		4													4
				6				7			8						5				6			7
		5				7			7		9				8				7			8		8
											6													9
					4			5										7			8
	29	5							7		6			30	8							7		5
						8													6
					5			6			8							4			6			8
											5													7
		9				5			8						8				6			7
								5			8										6			8
		4													4

48

Рис. 4.1

4.2. Методические указания к выполнению задания № 4

Теория матричных игр достаточно полно изложена в работах [1–5]. Там же рассматривается приложение линейного программирования к решению матричных игр. При выполнении пп. 4.1.1–4.1.3 необходимо привести математическую постановку задачи решения матричной игры в смешанных стратегиях, сформулировать основную теорему матричных игр.

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

п.4.1.1 сделать вывод о существовании седловой точки. Сопоставить полученные результаты с результатами выполнения п. 4.1.3.

Содержательную постановку задачи о выборе траектории для

п.4.1.4 можно рассмотреть, например, следующим образом.

Пусть самолет, находящийся на высоте H и имеющий скорость V , должен подняться на высоту Hk и достичь скорости Vk .

Известен расход горючего при подъеме самолета с любой высоты H1 на высоту H2 >H1. Также известен расход горючего при увеличении скорости от любого значения V1 до любого значения V2 > V1.

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

Такая постановка задачи подробно рассмотрена в работе [2]. Там же приводится метод ее решения, который предлагает дискретизацию задачи, т.е. разбиение интервалов [V0,Vk ] и [H0,Hk ] на конечное число подинтервалов. Оптимальная

траектория аппроксимируется кусочно-постоянной траекторией. Поясняет ситуацию рис. 4.1.

Цифры, стоящие над горизонтальными линиями в клетках, показывают закон изменения расхода горючего при изменении скорости, а цифры, стоящие слева от вертикальных линий клетки, показывают закон изменения расхода горючего при изменении высоты.

49

Стрелками указана оптимальная траектория. Варианты данных для выполнения п. 4.1.4 приведены в табл. 4.2.

4.3. Варианты задания

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

4.4. План оптимального распределения ресурсов

Составить план оптимального распределения ресурсов отрасли по годам. Исходные данные смотри в табл. 4.3.

							Таблица 4.3
Отрасль	Доход				Остаток		Количество лет
I	ay2				cy		N = 3
II	b(x – y)2				d(x – y)
№	a		b	c		d	x
1	1		2	0,6		0,1	1000
2	2		3	0,7		0,2	2000
3	3		4	0,8		0,3	3000
4	4		5	0,9		0,4	4000
5	2		1	0,6		0,7	5000
6	3		2	0,7		0,8	6000
7	4		3	0,6		0,8	7000
8	5		4	0,5		0,8	8000
9	1		2	0,5		0,3	9000
10	2		3	0,8		0,5	1000
11	3		4	0,6		0,4	2000
12	4		5	0,4		0,3	3000
13	2		1	0,1		0,6	4000
14	3		2	0,2		0,7	5000
15	4		3	0,3		0,8	6000
16	5		4	0,4		0,9	7000
17	1		3	0,5		0,1	8000
18	2		4	0,6		0,2	9000
19	3		5	0,7		0,3	1000
20	4		6	0,8		0,4	2000
21	2		3	0,5		0,4	3000
22	3		4	0,6		0,3	4000
23	4		5	0,7		0,2	5000
24	5		6	0,8		0,7	6000
25	3		1	0,1		0,5	7000
26	4		2	0,2		0,6	8000
27	5		3	0,3		0,7	9000
28	6		4	0,4		0,8	1000
29	3		2	0,5		0,8	2000
30	4		3	0,6		0,7	3000

50

							Окончание табл. 4.3
Отрасль	Доход				Остаток			Количество лет
I	ay2				cy			N = 3
II	b(x – y)2				d(x – y)
№	a		b	c		d		x
31	5		4	0,7		0,8		4000
32	6		5	0,8		0,9		5000
33	3		4	0,6		0,4		6000
34	5		6	0,7		0,5		7000
35	7		8	0,6		0,5		8000
36	9		8	0,6		0,7		9000
37	3		2	0,2		0,5		1000
38	4		3	0,3		0,6		2000
39	5		4	0,4		0,7		3000
40	6		5	0,5		0,6		4000
41	3		6	0,6		0,3		5000
42	5		7	0,7		0,4		6000
43	7		8	0,5		0,3		7000
44	9		9	0,3		0,6		8000
45	2		3	0,7		0,4		9000
46	2		4	0,7		0,5		1000
47	3		4	0,7		0,6		2000
48	2		6	0,7		0,2		3000
49	2		7	0,7		0,1		4000
50	2		8	0,7		0,1		5000

4.5. Графическое решение для матричной игры

Найти графическое решение для матричной игры. Исходные данные смотри в табл. 4.4.

Таблица 4.4

№	Матрица стоимостей				№		Матрица стоимостей				№	Матрица стоимостей
вар.					вар.						вар.
1	–12	3	9	5	11		–7	–5	–8	5	21	1	3	6	–3
	0	–5	0	–1			8	–4	–1	–10		–2	0	2	0
2	–8	2	1	1	12		–3	3	9	5	22	–6	–12	–7	2
	4	–6	0	0			7	–2	10	4		–3	–7	3	–3
3	15	9	15	–6	13		–8	–9	4	–5	23	–2	–4	4	–4
	6	1	6	6			7	–11	–11	–5		7	–5	–5	–3
4	–6	9	15	15	14		–4	–2	5	–3	24	–3	–1	2	5
	6	1	6	6			0	0	–2	3		–4	2	–4	–4
5	5	6	2	7	15		9	–1	5	8	25	9	–5	–6	3
	6	–6	6	9			9		0	6		1	1	6	2
6	1	3	6	–3	16		–7	–3	6	–8	26	–7	–5	–8	5
	–2	0	2	0			–4	2	–4	–4		8	–4	–1	–10
7	–6	–12	–7	2	17		–3	–5	5	1	27	–3	3	9	5
	–3	–7	3	–3			–1	–3	1	5		7	–2	10	4

51

Окончание табл. 4.4

	№	Матрица стоимостей				№	Матрица стоимостей				№	Матрица стоимостей
	вар.					вар.					вар.
	8	–2	–4	4	–4	18	–4	3	–7	–1	28	–8	–9	4	–5
		7	–5	–5	–3		0	0	–2	2		7	–11	–11	–5
	9	–3	–1	2	5	19	–8	4	–11	–11	29	–4	–2	5	–3
		–4	2	–4	–4		4	–8	–8	–8		0	0	–2	3
	10	9	–5	–6	3	20	4	–6	–11	–10	30	9	–1	5	8
		1	1	6	2		–6	–4	4	–6		9		0	6

ЗАДАНИЕ № 5

ПРЕДСТАВИТЬ ПРОГРАММНЫЙ КОД ОДНОГО ИЗ МЕТОДОВ

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

I. Методы безусловной оптимизации

1)Методы одномерной оптимизации а) Методы исключения интервалов:

– метод половинного деления;

– метод «золотого» сечения;

– метод Фибоначчи.

б) Методы полиномиальной аппроксимации. в) Методы с использованием производных:

– метод хорд;

– метод касательных;

– метод средней точки.

2)Методы многомерной оптимизации

а) Методы нулевого порядка:

–покоординатного спуска;

–Хука – Дживса;

–симплексный метод Нелдера – Мида. б) Методы первого порядка:

–градиентный;

–наискорейшего спуска;

–сопряженных градиентов;

–метод Давидона – Флетчера – Пауэлла;

–метод Флетчера – Ривса.

II. Методы условной оптимизации

52