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

- 42 -

23)

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

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

(10,11,4), (10,12,4),(11,13,2),(12,13,3)}

§6. Максимальный поток в транспортной сети

Транспортной сетью называют ориентированный граф с n вершинами v1,

. . ., vn , обладающий следующими свойствами:

1)нет дуг, входящих в вершину v1 называемой источником;

2)нет дуг, выходящих из вершины vn называемой стоком;

3)есть хотя бы один путь от v1 до vn ;

4)каждой дуге (vi ,v j ) сопоставлено положительное число cij

называемое пропускной способностью дуги.

Транспортную сеть можно задавать матрицей пропускных способностей

C {cij }i, j 1,n , где cij 0 и в случае cij 0 считаем, что дуга (vi ,v j )

отсутствует.

- 43 -

Потоком в транспортной сети называют матрицу F { fij }i, j 1,n ,

удовлетворяющую следующим условиям:

1) при любых i, j 1, n выполняется неравенство 0 fij cij , число fij

называют потоком по дуге (vi ,v j ), оно не должно быть больше

пропускной способности дуги cij ;

2)для каждой внутренней вершины vk , где k 2, n 1, сумма входящих

внее потоков равна сумме выходящих из нее потоков

f1k f2k fnk fk1 fk 2 fkn .

Число W (F) f11 f12 f1n называют объемом потока F . Объем потока равен сумме потоков, выходящих из источника, и сумме потоков,

входящих в сток. Поток с наибольшим объемом называют максимальным.

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

W (F) f11 f12 f1n max,

0 fij cij , i, j 1, n ,

f1k f2k fnk fk1 fk 2 fkn , k 2, n 1.

Пример 6.1. Рассмотрим следующую транспортную сеть

	v2	2	v4
				10
9	6
v1		8	9	v6
	5	3
7	v3		v5	5
		9

- 44 -

Составим задачу линейного программирования:

W (F) f12 f13 f14 max,

f11 0, 0 f12 9, 0 f13 7, 0 f14 5, f15 0, f16 0,

f21 0,	f22 0, 0 f23 6, 0 f24 2,						f25 0, f26 0,
f31 0,	f32 0,	f33 0 ,		f34 0, 0 f35 9 , 0 f36 3,
f41 0,	f42 0,	f43 0,		f44 0, 0 f45 8, 0 f46 10,
f51 0,	f52 0,	f53 0 ,		0 f54 9,		f55 0 , 0 f56 5,
f61 0, f62 0, f63 0 , f64 0,						f65 0, f66 0,
	f12 f23		f24 ,	f13 f23	f35		f36 ,
f14 f24 f54			f45 f46 , f35		f45		f54 f56 .

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

f13, f14 , f23 , f24 ,	f35,	f36 , f45 ,			f46 , f54 , f56 , находим
0		6	7	5	0	0
		0	4	2	0	0
0
	0	0	0	0	8	3
F*		0	0 0		0	10	- максимальный поток,
0
	0	0	0 3		0	5
	0	0	0 0		0	0
W (F*) 6 7 5 18 - объем максимального потока,
			v2			2		v4
									10
	6			4
v1							0	3	v6
			5			3
	7			v3				v5	5
						8

- 45 -

Задание № 6

Построить транспортную сеть, заданную матрицей пропускных

способностей C {cij }i, j 1,6 , и найти максимальный поток в транспортной

сети.

				Варианты
1)				2)
0 4 5 6 0		0		0 5 6 3 0			0
0 0 5 6 4		0		0 0 7 9 8			0
	0 6 0 0 8	2			0 6 0 0 1		3
C				C
0 0 6 0 0		9		0 0 5 0 0			4
	0 0 2 3 0	5			0 0 3 3 0		8
	0 0 0 0 0	0			0 0 0 0	0	0
3)				4)
0 9 6 4 0		0		0 4 6 9 0			0
0 0 8 7 9		0		0 0 6 8 7			0
	0 5 0 0 3	5			0 6 0 0	3	4
C				C
0 0 4 0 0		5		0 0 5 0 0			5
	0 0 3 5 0	9			0 0 4 3	0	8
	0 0 0 0 0	0			0 0 0 0	0	0
5)				6)
0 6 9 3 0		0		0 3 6 5 0			0
0 0 5 7 8		0		0 0 9 7 8			0
	0 6 0 0 4	3			0 6 0 0	5	3
C				C
0 0 5 0 0		5		0 0 5 0 0			7
	0 0 4 3 0	7			0 0 3 4	0	8
	0 0 0 0 0	0			0 0 0 0	0	0

- 46 -

7)								8)
0 5				6 7	0	0		0 6			7 5 0 0
				7 6	5
0 0						0		0 0			5 7 4 0
		0	0	0 0	4	8				0 0	0 0 8 3
C				4 0	3			C
0 0						9		0 0			3 0 0 8
		0	0	0 4	0	6				0 0	0 5 0 7
		0	0	0 0	0	0				0 0	0 0 0 0
9)								10)
0 8				7 4	0	0		0 9			7 6	0	0
				4 3	0						4 4	0
0 0						0		0 0					0
		0	5	0 0	8	4			0 5		0 0	8	5
C								C			3 0	5
0 0				3 0 0 9				0 0					10
		0	0	0 5 0 6					0 0		0 4	0	6
		0	0	0 0 0 0					0 0		0 0	0	0
11)								12)
0 5				7 8 0 0				0 7			7 6 0 0
0 0				4 3 0 0				0 0			4 3 0 0
	0 3			0 2 8 5						0 2	0 0 8 3
C								C
0 0				4 0 1 10				0 0			6 0 4 9
	0 0			0 3 0 5						0 0	0 1 0 5
	0 0			0 0 0 0						0 0	0 0 0 0
13)								14)
0 8				7 9	0	0		0 5			8 5	0	0
				4 2 0							4 3	0
0 0						0		0 0					0
		0	4	0 0	8	5			0 0		0 2	8	6
C				0 0	4			C			2 0	4
0 0						6		0 0					10
		0	0	2 3	0	7			0 0		0 3	0	5
		0	0	0 0	0	0			0 0		0 0	0	0

- 47 -

15)						16)
0 9			7 6 0 0			0 6				7 8 0 0
0 0			4 2 0 0			0 0				4 3 0 0
		0 3	0 0 8 7					0 1		0 0 8 3
C						C
0 4			0 0 5 8			0 0				0 0 0 9
		0 0	0 4 0 4					0 0		2 3 0 5
		0 0	0 0 0 0					0 0		0 0 0 0
17)						18)
0 8			6 7 0 0			0 9				7 8	0	0
										4 2 0
0 0			4 2 0 0			0 0						0
		0 0	0 0 8 5				0		2	0 0	8	3
C						C				0 0 2
0 0			0 0 6 9			0 0						10
		0 0	0 3 0 5				0		0	6 3	0	5
		0 0	0 0 0 0				0		0	0 0 0		0
19)						20)
0 7			7 5 0	0		0 8				6 5	0	0
			4 2 0							4 3	0
0 0				0		0 0						0
	0 2		0 0 8	3			0		2	0 0	8	3
C			0 0 2			C				0 0	1
0 0				10		0 0						10
	0 0		4 3 0	5			0		0	4 3	0	6
	0 0		0 0 0	0			0		0	0 0	0	0
21)						22)
0 5			7 5 0	0		0 6				7 5	0	0
			4 2 0							4 2	0
0 0				0		0 0						0
	0 0		0 0 8	6			0		0	0 0	8	3
C			0 0 4			C				0 0 0
0 0				10		0 0						10
	0 0		0 3 0	3			0		0	0 3	0	5
	0 0		0 0 0	0			0		0	0 0 0		0

- 48 -

23)								24)
0 6			7 5		0	0		0 8		9 6 0	0
			4 2		0					4 2 0
0 0						0		0 0			0
	0 1		0 0		8	3			0 3	0 0 8	9
C			0 0		0			C		0 0 4
0 0						10		0 0			8
	0 0		0 3		0	5			0 0	0 3 0	5
	0 0		0 0		0	0			0 0	0 0 0	0
25)
0		4	9	5	0	0
		0	4	2	0
0						0
	0	3	0	0	8	6
C		0	0 0		4
0						10
	0	0	0 3		0	9
	0	0	0 0		0	0

§7.	Численные методы оптимизации
Пусть функция	f (x), определенная при	всех n –мерных векторов
x Rn , имеет минимум
f (x*) min{ f (x) : x (x ,..., x		n	) Rn }.
	1

Последовательность векторов x(0) , x(1) ,..., x(k) , ... называют минимизирующей последовательностью, если f (x(k) ) f (x*) при k .

Методы построения минимизирующей последовательности называют численными методами оптимизации. Рассмотрим два из них – метод спуска и метод Ньютона.

- 49 -

Метод спуска. Если целевая функция f (x) в некоторой окрестности точки минимума x * дифференцируема и ее градиент удовлетворяет условию Липшица

f

где L называют константой критических точек функции можно построить следующей

(x) f (y) L x y ,

Липшица, и если в этой окрестности нет других f (x), то минимизирующую последовательность формулой

x(k) x(k 1) t f (x(k 1) ), k 1, 2, ,

где t 1/(2L), x(0) - начальная точка из рассматриваемой окрестности.

Алгоритм метода спуска для приближенного нахождения точки минимума:

1.Задать точность приближения 0 и выбрать начальную точку x(0) .

2.Последовательно находить точки

x(k) x(k 1) t f (x(k 1) ), k 1, 2, ,

до тех пор, пока при некотором k0 не будет выполнено неравенство

f (x(k0 ) ) .

3. x x(k0 ) – приближенная точка минимума.

Метод Ньютона. Пусть целевая функция f (x) дважды непрерывна

дифференцируема в некоторой окрестности точки минимума x * и в каждой

точке x этой окрестности существует матрица H 1(x) , обратная матрице

вторых производных H (x) функции f (x). И пусть в данной окрестности нет других критических точек функции f (x). Тогда минимизирующую последовательность можно построить следующей формулой

x(k) x(k 1) H 1(x(k 1) ) f (x(k 1) ) , k 1, 2, ,

- 50 -

где x(0) - начальная точка из окрестности x *.

Алгоритм метода Ньютона для приближенного нахождения точки

минимума:

1.Задать точность приближения 0 и выбрать начальную точку x(0) .

2.Последовательно находить точки

x(k) x(k 1) H 1(x(k 1) ) f (x(k 1) ) , k 1, 2, ,

до тех пор, пока при некотором k0 не будет выполнено неравенство

f (x(k0 ) ) .

3. x x(k0 ) – приближенная точка минимума.

Если целевая функция f (x) трижды непрерывно дифференцируема в

некоторой окрестности точки минимума x * и ее матрица вторых производных

H (x) удовлетворяет условию сильной выпуклости H (x) l I , где I -

единичная матрица и l 0 не зависит от x , то последовательности, которые

строятся методами спуска и Ньютона, действительно будут минимизурующими

последовательностями.

Пример 7.1. Рассмотрим функцию

f (x) x4	ax4 (bx cx )2				px qx ,			x (x , x		2	)	,
1		2	1	2	1	2			1
где a 0 , bc 0,	|	p | | q | 0. Заметим, что
f (x)			при	| x |2 x2		x2	.
					1	2
Отсюда вытекает существование минимума функции.
Найдем градиент и матрицу вторых производных функции:
f (x) 4x3		2b(bx cx ) p , 4ax3
						2c(bx cx ) q							,
	1	1	2		2			1	2
		12x2 2b2			2bc
	H (x)		1		12ax	2 2c		.
			2bc					2
					2

- 51 -

Заметим, что в любой точке отличной			от	нуля, в	силу a 0 , bc 0,
определитель матрицы H (x) положительный:
det H (x) 24 6ax2x2 c			2x2 ab2x2		0.
	1	2	1	2
Любая критическая точка функции		f (x),	в силу | p | | q | 0,			отлична от
нуля. Следовательно, в любой критической точке det H (x) 0.
В любой точке x матрица H (x) удовлетворяет условию сильной
выпуклости H (x) l I , где	l min (2b2			, 2c2 ).	Поэтому	сходимость

методов спуска и Ньютона обеспечена.

Находим константу Липшица:

f (x) f (y) 2 4(x13 y13) 2b2 (x1 y1) 2bc(x2 y2 ) 2

		4a(x3		y	3) 2c				2 (x			2		y			2		) 2bc(x y ) 2
			2		2																	1				1
	3 4(x3 y			3) 2	3 2b2 (x y ) 2 3 2bc(x																				2	y		2	) 2
	1		1						1					1
	3 4a(x3		y3) 2 3 2c2 (x										2	y				2		) 2	3 2bc(x y ) 2
	2			2																						1		1
	48 | x y |2 (x2						x y y2 ) a2														(x2 x		2	y		2	y		2 )
					1			1	1					1								2						2
				24 max(| b |4,| c |4 ) | x y |2
	96 max(1, a2 )(| x |2							| y |2 ) 24 max(| b |4,| c |4 )																					| x y |2
Полагая |	x | r , | y | r и				L2			192 max(1, a2 )r2 24 max(| b |4,| c |4 ),
имеем:
		f (x) f (y)					L				x y						при				|	x | r ,			| y | r .
Теперь найдем матрицу							H 1(x) :
H 1(x) 36ax2x2 6c2x2									6ab2x								2			1		2	c				2		bc
																						6ax2									.
			1 2					1									2					bc						6x2		b	2
																													1

Таким образом, формула метода спуска принимает следующий вид: