Метод указ по МО

- 32 -

Составим функцию Лагранжа

L(x,u) (x1 3)2 (x2 3)2

u1(x2 2) u2 (4x1 3x2 10) u3(3x1 x2 14)

u4 ( x1 4x2 30) u5( 5x1 4x2 38) u6 ( 4x1 3x2 18) .

Находим частные производные функции Лагранжа и приравниваем нулю:

2(x1 3) 4u2 3u3 u4 5u5 4u6 0,

2(x2 3) u1 3u2 u3 4u4 4u5 3u6 0,

x2 2 0,	4x1 3x2 10 0,	3x1 x2 14 0 ,
x1 4x2 30 0 ,	5x1 4x2 38 0,	4x1 3x2 18 0 .
Положим u1 u3 u4 u5 u6 0. Тогда имеем:
x1 2u2 3, 2x2 3u2 6 , 4x1 3x2 10.
Отсюда
x* (31/ 25;	42 / 25) , u* (0; 22 / 25; 0; 0; 0; 0).

Легко проверить, что пара (x*,u*) является седловой точкой функции

Лагранжа. Следовательно, x* (31/ 25; 42 / 25) - точка минимума и

			fmin f (x*)			121		.
					25
			Задание № 4
	Найти расстояние от заданной точки				A до четырехугольника A1A2 A3A4
с вершинами в заданных точках A1,				A2 ,	A3 ,		A4 , составляя и решая задачу
выпуклого программирования.
			Варианты
1)	A( 1; 2),	A1(0; 4),	A2 (1; 1),	A3(3; 3) ,			A4 (4; 5) .
2)	A( 2; 2),	A1(1; 4),	A2 (0; 1),	A3(3; 3) , A4 (4; 3) .

- 33 -

3)

A( 3; 2) ,

A1(1; 4),

A2 (1; 2),

A3(3; 2) ,

A4 (4; 4) .

4)

A( 1; 0),

A1(1; 4),

A2 (2; 1),

A3(3; 3) ,

A4 (5; 2) .

5)

A(1; 2) ,

A1(0; 4),

A2 ( 1; 1) ,

A3( 3; 3), A4 ( 4; 5) .

6)

A(2; 2) ,

A1( 1; 4) ,

A2 (0; 1),

A3( 3; 3) , A4 ( 4; 3).

7)

A(3; 2),

A1( 1; 4) ,

A2 ( 1; 2) ,

A3( 3; 2),

A4 ( 4; 4).

8)

A(1; 0),

A1( 1; 4) ,

A2 ( 2; 1),

A3( 3; 3) ,

A4 ( 5; 2).

9)

A(2; 1),

A1(4; 0),

A2 ( 1;1),

A3(3; 3) , A4 (5; 4) .

10)

A(2; 2),

A1(4;1),

A2 ( 1; 0) ,

A3( 3; 3),

A4 (3; 4) .

11)

A( 2; 3),

A1(4;1),

A2 ( 2;1),

A3(2; 3) ,

A4 (4; 4) .

12)

A(0; 1),

A1(4;1),

A2 ( 1; 2),

A3( 3; 3),

A4 (2; 5) .

13)

A(2;1) ,

A1(4; 0),

A2 ( 1; 1) ,

A3(3; 3) ,

A4 (5; 4) .

14)

A(2; 2) ,

A1(4; 1),

A2 ( 1; 0) ,

A3( 3; 3) ,

A4 (3; 4).

15)

A( 2; 3),

A1(4; 3),

A2 ( 2; 1), A3(2; 3) , A4 (4; 4).

16)

A(1;1) ,

A1(4; 1),

A2 ( 1; 2) ,

A3( 3; 3) ,

A4 (2; 5) .

17)

A(1; 2) ,

A1(2; 4),

A2 (3; 6), A3(4; 2) , A4 (3; 1).

18)

A(3; 2),

A1( 1; 4) ,

A2 (1; 1),

A3(3; 3) ,

A4 (4; 5) .

19)

A( 2; 3),

A1(0; 4),

A2 (2; 1),

A3(3; 2) , A4 (4; 5) .

20)

A(2;1) ,

A1( 1; 4) ,

A2 ( 2; 6),

A3( 3; 5),

A4 ( 2; 5).

21)

A( 3; 4) ,

A1(0; 4),

A2 (1; 1),

A3(3; 3) ,

A4 (4; 5) .

22)

A(4; 3) ,

A1(1; 1),

A2 (2; 4),

A3(3; 3) ,

A4 (2; 5) .

23)

A( 1; 2),

A1(1; 4),

A2 (2; 1),

A3(3; 2) ,

A4 (4; 5) .

24)

A(2; 1),

A1( 1; 4) ,

A2 ( 1; 1) ,

A3( 3; 3),

A4 ( 1; 5).

25)

A( 3; 2),

A1(0; 4),

A2 (1; 1),

A3(3; 3) , A4 (4; 5) .

- 34 -

§5. Метод динамического программирования

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

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

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

f f1(x0, x1) f2 (x1, x2 ) ... fm (xm 1, xm ) min,
x1 D1,		x2 D2 , . . . , xm Dm ,
где элемент x0, множества D1,		D2 , ..., Dm , функции f1, f2 , ..., fm задаются,
а элементы x1, x2 , ...,	xm неизвестны. Данную задачу можно свести к
следующей последовательности оптимизационных задач:
Gm 1	(xm 1) min		fm (xm 1, xm ),
		xm Dm
Gm 2 (xm 2 )	min	Gm 1(xm 1) fm 1(xm 2, xm 1) ,
xm 1 Dm 1
		. . . . . . . .
G0 (x0 ) min G1(x1) f1(x0, x1) .
	x1 D1

Процесс построения функций Gm 1, Gm 2 , ..., G0 называют обратным ходом.

По функциям G0, ..., Gm 1 выполняют прямой ход, состоящий в последовательном нахождении элементов

x10 : G0 (x0 ) G1(x10 ) f1(x0, x10 ) ,

- 35 -

x20 : G1(x10 ) G2 (x20 ) f2 (x10, x20 ),

. . . . . . . . .

xm0 1 : Gm 1(xm0 2 ) Gm 1(xm0 1) fm 1(xm0 2, xm0 1) ,

xm0 : Gm 1(xm0 1) fm (xm0 1, xm0 ).

Тогда набор элементов (x10, ..., xm0 ) будет решением исходной оптимизационной задачи.

Метод динамического программирования также применим для решения оптимизационных задач вида

f f1(x1) f2 (x1, x2 ) f3(x1, x2, x3) ... fm (x1, ..., xm ) min ,

x1 D1, x2 D2 , . . . , xm Dm .

Пример 5.1. В заданном ациклическом ориентированном графе с весами найти маршрут минимальной длины, соединяющий начальную и конечную вершины.

				10	8
			6		1
		6	4		13
					5
	2		6	9	3	1
3	3	5	1
	3	5	2		12	14
1			4			5
		4	4	8	2
2	2	3
		7	5		2	4
		4	3		11
			6		3
				7	8
Вершины	графа	разобьем	на следующие слои: D0 {1}, D1				{2, 3},
D2 {4, 5, 6},		D3 {7, 8, 9,10},		D4 {11,12,13}, D5		{14}.	Любой

маршрут, соединяющий начальную вершину с конечной, можно представить как набор элементов (x1, x2, x3, x4, x5) , где xi - вершина i –го слоя графа,

- 36 -

куда осуществляется переход от вершины xi 1 (i 1)-го слоя. Длину участка

перехода от			xi 1		в	xi обозначим через									fi (xi 1, xi ) . Тогда длина маршрута
равна		f1(x0, x1) f2 (x1, x2 ) f3(x2, x3) f4 (x3, x4 ) f5(x4, x5) .																					Таким
образом, получаем следующую оптимизационную задачу
f	f1(x0, x1) f2 (x1, x2 ) f3(x2, x3) f4 (x3, x4 ) f5(x4, x5) min ,
							x0 1,				xi Di , i 1, 2, 3, 4, 5.
где D0 {1}, D1 {2, 3},								D2 {4, 5, 6}, D3								{7, 8, 9,10}, D4					{11,12,13},
D5 {14},			функции				f1,		f2 ,		f3,	f4 ,		f5		по	условию задачи определены
следующими таблицами:
x0 x1		f1		x1 x2			f2			x2 x3			f3			x3 x4		f4		x4 x5		f5
1	2	2		2	4		7			4	7		6			7	11	8		11	14		4
1	3	3		2	5		3			4	8		3			7	12	3		12	14		5
				2	6		4			4	9		5			7	13			13 14		1
				3	4		1			4	10					8	11	2
				3	5		5			5	7		4			8	12	2
				3	6		2			5	8		4			8	13	4
										5	9		2			9	11	1
										5	10		1			9	12	3
										6	7					9	13	5
										6	8		6			10	11
										6	9		4			10	12	1
										6	10		6			10	13	8

В соответствии с методом динамического программирования выполним обратный и прямой ход.

Обратный ход. Находим функции G4 , G3 , G2 , G1, G0:

- 37 -

		x4	G4
G4	(11) f5(11,14) 4,	11	4
G4	(12) f5(12,14) 5,
		12	5
G4	(13) f5(13,14) 1,
		13	1

G3(7) min{G4 (11) f4 (7,11), G4 (12) f4 (7,12), G4 (13) f4 (7,13) }

min{ 4 8, 5 3,1 } 5 3 G4 (12) f4 (7,12) 8,

				x3		G3
G3	(7) G4(12) f4(7,12) 8,			7	8
G3	(8) G4(13) f4(8,13) 5,
				8	5
G3	(9) G4(11) f4(9,11) 5,
				9	5
G3	(10) G4(12) f4(10,12) 6,
				10	6
				x2		G2
G2(4) G3(8) f3(4,8) 8,
			4			8
G2(5) G3(10) f3(5,10) 7,
			5			7
G2(6) G3(9) f3(6, 9) 9,
			6			9
				x1		G1
G1(2) G2(5) f2(2, 5) 10,
			2		10
G1(3) G2(4) f2(3, 4) 9,
			3		9
				x0		G0
G0(1) G1(2) f1(1, 2) 12,
			1		12
Прямой ход. По функциям G0, G1, G2 ,		G3 , G4 находим оптимальный

маршрут:

- 38 -

G (1) G (x0) f (1, x0),					x	0	2,
0	1	1	1	1	1
G1(2) G2(x20) f2				(2, x20),	x20 5,
G2	(5) G3(x30) f3			(5, x30),	x	0	10,
	(10) G4(x40) f4(10, x40),				3
G3					x40 12,
G4	(12) f5(12, x50),				x	0	14.
					5

Следовательно, 1 2 5 10 12 14 - оптимальный маршрут с длиной,

равной

fmin f1(1, 2) f2 (2, 5) f3(5,10) f4 (10,12) f5(12,14) 12.

Задание № 5

В заданном ациклическом ориентированном графе с весами G (V , E),

где V {1, ..., n} - множество вершин графа и E - множество дуг (ki , k j , wij )

с весами wij , найти маршрут минимальной длины, соединяющий начальную и конечную вершины.

Варианты

1)

n 12,	E {(1,2,3),(1,3,2),(1,4,1),(2,5,5),(3,5,5),(3,6,4),(4,6,3),
	(5,7,3),(5,8,4),(5,9,6),(6,7,2),(6,8,5),(6,9,4), (7,10,2),
	(7,11,2),(8,10,1),(8,11,4),(9,11,3),(10,12,4),(11,12,3)}
2)
n 11,	E {(1,2,4),(1,3,3),(2,4,3),(2,5,4),(3,4,2),(3,5,6),(4,6,3),
	(4,7,2),(4,8,3),(5,6,1),(5,7,4),(5,8,1),(6,9,2), (6,10,3),
	(7,9,1),(7,10,1),(8,9,4),(8,10,5),(9,11,5),(10,11,7)}

- 39 -

3)

n 12,	E {(1,2,2),(1,3,3),(2,4,5),(2,5,7),(3,5,4),(3,6,2),(4,9,1),
	(4,7,4),(4,8,2),(5,7,3),(5,8,2),(6,7,1),(6,8,3), (6,9,2),
	(7,10,2),(8,10,3),(8,11,9),(9,10,5),(9,11,4),(10,12,9),(11,12,8)}
4)
n 12,	E {(1,2,3),(1,3,4),(2,4,1),(2,5,4),(3,4,3),(3,5,2),(4,6,6),
	(4,7,4),(4,8,6),(5,6,8),(5,7,5),(5,8,4),(6,9,5), (6,10,3),
(7,9,2),(7,10,2),(7,11,5),(8,10,7),(8,11,3),(9,12,3),(10,12,4),(11,12,2)}
5)
n 13,	E {(1,2,4),(1,3,3),(1,4,5),(2,5,4),(2,6,1),(2,7,3),(3,5,4), (3,6,2),

(3,7,1),(4,6,2),(4,7,2),(5,8,2),(5,9,4), (6,8,5), (6,9,2),(7,8,3),(7,9,4), (8,11,4),(8,10,2),(9,11,1),(9,10,3),(9,12,6),(10,13,6),(11,13,7),(12,13,5)}

6)

n 12, E {(1,2,3),(1,3,4),(2,4,3),(2,5,2),(2,6,1),(3,4,1),(3,5,2), (3,6,4),(4,7,2),(4,8,7),(4,9,2),(5,7,6),(5,8,1), (5,9,1), (6,8,2),(6,9,1),

(7,10,4),(7,11,3),(8,10,3),(8,11,4),(9,10,2),(9,11,7),(10,12,3),(11,12,5)}

7)

n 11,	E {(1,2,8),(1,3,7),(2,4,6),(2,5,4),(2,6,8),(3,4,5),(3,5,3),
	(3,6,9),(4,7,4),(5,7,1),(5,8,7),(6,7,2),(6,8,3), (7,9,3),
	(7,10,2),(8,9,3),(8,10,2),(9,11,5),(10,11,4)}
8)
n 12,	E {(1,2,5),(1,3,7),(1,4,6),(2,5,4),(2,6,4),(3,5,6),(3,6,5),
	(4,5,7),(4,6,6),(5,7,2),(5,8,6),(5,9,3),(6,7,4), (6,8,3),

(6,9,4),(7,10,4),(8,10,2),(8,11,4),(9,10,3),(9,11,2),(10,12,4),(11,12,6)}

- 40 -

9)

n 12, E {(1,2,5),(1,3,4),(2,4,2),(2,5,1),(3,4,1),(3,5,3),(4,6,7), (4,7,1),

(4,8,2),(5,6,3),(5,7,4),(5,8,3),(6,9,5), (7,9,4), (7,10,2),(7,11,5),(8,9,3), (8,11,6),(9,12,5),(10,12,6),(11,12,7)}

10)

n 12, E {(1,2,3),(1,3,4),(2,4,5),(2,5,2),(2,6,1),(3,4,4),(3,5,3), (3,6,2), (4,7,3),(4,8,5),(5,7,4),(5,8,7),(5,9,4), (6,7,4), (6,8,2),(6,9,3),(7,10,5),

(7,11,7),(8,10,4),(8,11,3),(9,10,3),(9,11,4),(10,12,9),(11,12,7)}

11)

n 12, E {(1,2,5),(1,3,3),(2,4,4),(2,5,2),(2,6,2),(3,4,3),(3,5,1), (3,6,3), (4,7,4),(4,8,3),(5,7,4),(5,8,2),(5,9,4), (6,8,3), (6,9,6),(7,10,7),(7,11,5),

(8,10,5),(8,11,6),(9,10,8),(9,11,7),(10,12,4),(11,12,3)}

12)

n 11, E {(1,2,7),(1,3,5),(2,4,5),(2,5,5),(3,4,4),(3,5,4),(4,6,3), (4,7,4),

(4,8,2),(5,6,3),	(5,7,3),(5,8,7),(6,9,2), (6,10,2), (7,9,4),
(8,9,3),	(8,10,1), (9,11,6),(10,11,7)}

13)

n 12, E {(1,2,5),(1,3,2),(2,4,5),(2,6,5),(3,4,1),(3,5,7), (3,6,4), (4,7,3),(4,8,2),(5,7,6),(5,8,7),(5,9,10), (6,8,4), (6,9,3),(7,10,6),(7,11,3),

(8,10,4),(8,11,1),(9,10,5),(9,11,6),(10,12,3),(11,12,2)}

14)

n 12, E {(1,2,3),(1,3,5),(2,4,2),(2,5,1),(3,4,7),(3,5,3),(3,6,4), (4,7,4), (4,8,5),(5,7,6),(5,8,2),(6,7,10),(6,8,7), (7,9,4), (7,10,5),(7,11,7),(8,9,6),

(8,10,3),(8,11,1),(9,12,5),(10,12,4),(11,12,3)}

15)

n 12, E {(1,2,3),(1,3,2),(2,4,4),(2,5,2),(2,6,3),(3,4,5),(3,5,4), (3,6,1), (4,7,6),(4,8,5),(5,7,7),(5,8,6),(5,9,10), (6,8,2), (6,9,3),(7,10,4),(8,10,2),

(8,11,5),(9,11,4),(10,12,1),(11,12,3)}

- 41 -

16)

n 12,	E {(1,2,2),(1,3,3)(2,4,6),(2,5,4),(3,4,8),(3,5,5), (3,6,7),
	(4,7,3),(4,8,2),(5,7,5),(5,8,6), (6,7,1), (6,8,3),(7,9,5),(7,10,6),
	(7,11,3),(8,9,4),(8,10,2),(8,11,4),(9,12,6),(10,12,3),(11,12,5)}
17)
n 13,	E {(1,2,6),(1,3,5),(2,4,3),(2,5,1),(2,6,2),(3,5,2),(3,6,1), (3,7,4),
(4,8,3),(5,8,7),(5,9,8),(5,10,2),(6,8,8), (6,9,2), (6,10,1),(7,10,3),(8,11,7),
(8,12,5),(9,11,4),(9,12,6),(10,11,9),(10,12,5),(11,13,3),(12,13,4)}
18)
n 12,	E {(1,2,5),(1,3,4),(2,4,2),(2,5,1),(2,6,3),(3,4,9),(3,5,2), (3,6,7),

(4,7,3),(4,8,5),(5,7,6),(5,8,2),(5,9,5), (6,8,4), (6,9,3),(7,10,7),(7,11,2), (8,10,1),(8,11,1),(9,10,6),(9,11,4),(10,12,2),(11,12,3)}

19)

n 12, E {(1,2,4),(1,3,3),(2,4,4),(2,5,3),(2,6,6),(3,4,2),(3,5,1), (3,6,5), (4,7,7),(4,8,6),(5,7,4),(5,8,5),(5,9,3), (6,8,4), (6,9,4),(7,10,5),(8,10,2),

(8,11,1),(9,10,2),(9,11,3),(10,12,1),(11,12,3)}

20)

n 12, E {(1,2,1),(1,3,2),(2,4,2),(2,5,4),(2,6,3),(3,4,5),(3,5,3), (3,6,5), (4,7,3),(4,8,5),(5,7,4),(5,8,1),(5,9,2), (6,8,6), (6,9,3),(7,10,4),(7,11,3),

(8,10,2), (8,11,2),(9,10,7),(9,11,5),(10,12,3),(11,12,4)}

21)

n 12, E {(1,2,3),(1,3,4),(1,4,5),(2,5,5),(2,6,2),(3,5,4),(3,6,3),(4,5,7), (4,6,4),(5,7,2),(5,8,4),(6,7,2),(6,8,6), (6,9,5), (7,10,1),(8,10,4),

(8,11,3),(9,11,2),(10,12,6),(11,12,4)}

22)

n 12, E {(1,2,5),(1,3,4),(2,4,4),(2,5,1),(2,6,2),(3,4,4),(3,5,3), (3,6,7), (4,7,6),(4,8,4),(5,7,5),(5,8,3),(5,9,4), (6,8,5), (6,9,6),(7,10,2),(7,11,4),

(8,10,1), (8,11,6),(9,10,5),(9,11,2),(10,12,4),(11,12,3)}