Variatsionnoe_ischislenia

Второй вариант: минимум квадратного трехчлена достигается на концах отрезка , а именно при ˆ

[−1, 1] ψ(t) 6

−2, uˆ(t) = −1. Итак,

uˆ(t) =

xˆ(t) =

если

=

если

(	ˆ	1,		если
	2
	ψ(t)		,	если
t	−			t

ZZ

dτ uˆ(τ ) =		dτ
0	0
	то	t
t 6 2,		R

ψ−ˆ(t)	6	ˆ	1	) = max (−1, 2					) ;
1 <		ψ(t)						ˆ
		2						ψ(t)
2		−
τ	1			если		6
	2			если τ − 4		> −2
−−4					τ − 4		−2		=

dτ (−1) = −t,

	0
	2	t
t > 2, то	R dτ (−1) + R dτ τ2 − 2 = t42 − 2 t + 1,
	0	2

J = inf J (x) = −143

Задача 24. Доказать что минимум inf J (x) достигается.

x

Пример 25 (Задача о лифте.). Надо возможно быстрее спуститься на лифте, естественно, при ограничении на

ускорение.

|x¨(t)| 6 1, x(0) = 1, x˙ (0) = 0, x(T ) = 0, x˙ (T ) = 0, T → min .

Запишем задачу как оптимизационную на быстродействие.

	x¨(t) = u(t), t : |u(t)| 6 1,
	x(0) = 1, x˙ (0) = 0,	x(T ) = 0,			x˙ (T ) = 0,
T
Z0	f0(t, x(t), u(t)) dt → min c			f0(t, x, u) ≡ 1.
Перепишем в виде системы уравнений
x ≡ x1, x˙ ≡ x2, x˙ 1 = x2, x˙ 2 = u, |u| 6 1, n = 2, k = 1,
	x1(0) = 1, x2(0) = 0, x1(T ) = 0, x2(T ) = 0,
	H = ψ0 + ψ1x2 + ψ2u, ψ0 6 0,
	ψ02 + ψ12(t) + ψ22(t) 6= 0			t [0, T ]
	u =?
	ˆ			ˆ
max H(ˆx(t), ψ(t), u, t) = H(ˆx(t), ψ(t), uˆ(t), t),
	u
	ˆ	˙	= 0,	˙	= −ψ1,
	uˆ(t) = sgn ψ2(t),	ψ1		ψ2
ψ1 = c1, ψ2 = −c1t + c2,			uˆ(t) = sgn (−c1t + c2).

Разберем возникающие варианты. Пусть при . Тогда ˆ Из граничных

−c1t + c2 =6 0 t (0, T ) x2(t) = sgn((x) · (t)

условий следует x2(T ) = 0, что невозможно. Значит, есть t1 (0, T ) при котором −c1t1 + c2 = 0. Если c1 > 0, то

				+1	для	t < t1
		u(t) = −1			для	t > t1
					t	при	t < t1
		x2(t) = t1 + (t1 − t)				при	t > t1
Граничное условие x2(T ) = 0	дает 0 = x2(t) = 2t1 − T , т.е. t1 = T2 , Тогда
x1(t) =	(	1 + (T /2)2	+ T (t	T ) + (	t2 ) = (T /2)2			при	t > T /2
				1 + t2				при	t < T /2
				2
		2		− 2	− 2		2

Опять получаем противоречие с граничным условием x1(T ) = 0: 0 = 1 + 14 · T 2 > 0. – Пусть c1 < 0. Тогда

u(t) =

−1

для

t < t1

при

+1

для

t > t1

T

x2

(t) =

−t

t < t1

, 0 = x2(T ) = T

−

2t1

t1 =

.

при

t > t1

2

t − 2 t1

t21 + −

t2

, (T /2)2

t < T /2

x1(t) =

(T /2)2

2

−

T 2

,

1 −

2

+

2

T

·

t −

2

2

t > T /2

T

2

t

2

−2

T

2

T

2

2

T

это возможно при T = 2

0 = x1(T ) = 1 −

+

− T

−

+

= 1 −

8

2

8

2

4

Ответ: T = 2, uˆ(t) = sgn (t − 1).

Задача 25. Насколько обоснован этот ответ?

VII.2	Обоснование принципа максимума
VII.2.1	Частный случай общей теоремы с одним закрепленным, другим свободным
	концами и без фазовых ограничений
Теорема 39.
	x˙ = f (t, x, u), x Rn, u V R2,	(VII.8)

{u(t)} ≡ U множество всех допустимых управлений, в частности, функции u(t) кусочно-непрерывны.

		t [t0, T ], f C, D2f C,		(VII.9)
		xˆ(t0) S0(t0), xˆ(T ) S1(T ), xˆ(t) G(t).
У нас S0(t0) = x0, S1(T ) = Rn, G(t) = Rn.
		T		(VII.10)
	J (x, u) ≡ tZ0 dt f0(t, x, u) + Φ(x(T )) → u
			min J (u) = J (ˆu) + ψ(x(t))
Пусть (ˆx, uˆ) оптимальный процесс на [0, T ]. Задача для сопряженной системы имеет вид
˙		∂
ψ = Dxf0	− hψ, Dxf i ≡ Dxf0 −	∂ x	hψ, f i,
			ψ(T ) ≡ −DΦ(ˆx(T )).	(VII.11)

При сформулированных условиях решение задачи (VII.8),(VII.9),(VII.11) существует и единственно и выполняется необходимое условие оптимальности

− f0(t, xˆ(t), uˆ(t)) + hψ(t), f (t, xˆ(t), uˆ(t))i >

> −f (t, xˆ(t), u) + hψ(t), f (t, xˆ(t), u)i (VII.12)

для всех t [t0, T ] и всех u V .

Заметим, что здесь вместо H взято −f0 + hψ, f i. То есть мы покажем, что можно положить ψ0 = −1.

Доказательство. Cуществование и единственность решения системы для ψ следует из теоремы существования

и единственности решения линейных систем дифференциальных уравнений. Bведем вариацию управления. А именно, пусть τ – точка непрерывности uˆ(t). Возьмем α таким, чтобы на отрезке [τ − α, τ ] управление uˆ(t) оставалось непрерывным, и заменим uˆ(t) на этом отрезке [τ −α, τ ] на const v V . Пара (ˆuα(t), xˆα(t)) называется игольчатой вариацией процесса, (τ, v) – иголкой.

Лемма 2.	Пусть (τ, v) фиксированная иголка. Тогда		существует α					> 0 такое, что для любого α		[0, α ]
					n		0			0
функция xˆα(t) определена на [t0, T ] и xˆα → xˆ в метрике			C([t0, T ], R			) при α → 0. Причем
	xˆα(t) − xˆ(t) = α · y(t) + o(α),								(VII.13)
где y непрерывная, кусочно дифференцируемая функция на [τ, T ] и удовлетворяет условиям
	y˙ = Dxf (t, xˆ(t), uˆ(t)) y(t)
	для t [τ, T ]	{множество непрерывности uˆ(t)}							(VII.14)
	y(τ ) =	T	−	f (τ, xˆ(τ ), uˆ(τ ))
	f (τ, xˆ(τ ), v)

Доказательство леммы 2. xˆα(t) ≡ xˆ(t) для t0 6 t 6 τ − α. На отрезке [τ − α, τ ] xˆα(t) есть решение задачи

˙

xˆα(τ − α) = xˆ(τ − α), xˆα(t) = f (t, xˆα(t), v),

если это решение определено на [τ − α, τ ]. На отрезке [τ, T ] xˆα(t) есть решение задачи

˙

xˆα(t) = xˆα(τ − 0), xˆα(t) = f (t, xˆα(t), uˆ(t)),

(VII.15)

(VII.16)

для тех t 6 T , для которых это решение определено.

Решение задачи (VII.8),(VII.9) единственно и существует, во всяком случае, до значения (τ − α) + ε (α) 6 τ (направо от точки τ − α). На этой области определения

t

Z

xˆα(t) − xˆ(t) = dη [f (η, xˆα(η), v) − f (η, xˆ(η), uˆ(η))] =

τ −α

t	t
Z	Z

=dη[f (η, xˆα(η), v) − f (η, xˆ(η), v)] + dη[f (η, xˆ(η), v) − f (η, xˆ(η), uˆ(η))]. (VII.17)

τ −α

τ −α

Первое слагаемое есть

t1

τ −Zα dη Z0	d
	ds ds f (η, sxˆα(η) + (1 − s)ˆx(η), v) =

1t

ZZ

= ds	dη D2f (η, sxˆα(η) + (1 − s)ˆx(η), v) · [ˆxα(η) − xˆ(η)]. (VII.18)

0τ −α

Второе слагаемое имеет оценку

t
kτ −Zα dη [f (η, xˆ(η), v)	−	f (η, xˆ(η), uˆ(η))]kC	6	ε(α)	·	C1. (VII.19)

Решение может перестать существовать только за счет ухода в бесконечность kxˆα(t)kC (или, что то же, kxˆα − xˆkC ). Из формулы (VII.17) получаем оценку

kxˆα(t) − xˆ(t)kC[τ −α,τ −α+ε] 6
6 ε(α)				·	max
					06s61 kD2f (η, sxˆα(η) + (1 − s)ˆx(η), v)kC · kxˆα − xˆkC[τ −α,τ −α+ε] + ε(α) · C1 ≡
							≡ ε(α) · C2 · kxˆα − xˆkC[τ −α,τ −α+ε(α)] + ε(α) · C1. (VII.20)
Возьмем εmin <	1		и получим равномерную по α оценку сверху нормы разности это дает α0 = ε и существо-
	2C2
вание и единственность решения на всем отрезке [τ − α, τ ] для любого α [0, α0].
Теперь мы пришли к задаче (VII.16). Здесь xˆ удовлетворяет уравнению (VII.8) на отрезке t [τ, T ] и
						t	xˆα(t) − xˆ(t) = xˆα(τ − 0) − xˆ(τ )+	(VII.21)
						R	dη [f (η, xˆα(η), uˆ(η)) − f (η, xˆ(η), uˆ(η))].
					+
						τ
Оценка решения имеет вид
						kxˆα − xˆkC[τ,ε]	6 |xˆα(τ − 0) − xˆ(τ )| + ε · kD2f kC · kxˆα − xˆkC[τ,ε].
1	1
Берем ε = 2	·					и получаем kxˆα − xˆkC[τ,ε] 6 2 |xˆα(τ − 0) − xˆ(τ )| . В частности, |xˆα(τ + ε) − xˆ(τ + ε)| 6
		kD2 f kc

2 |xˆα(τ − 0) − xˆ(τ )| , то есть решение существует до этого ε равномерно по α. Разбив весь отрезок [τ, T ] на конечное число отрезков с длинами не больше ε и повторяя для каждого отрезка приведенные выше расчеты "шагами"можно довести существование до отрезка [τ, T ]. Конечно, решение единственно. Это решение xˆα → xˆ в C на [τ, T ] при

|xˆα(τ − 0) − xˆ(τ )| → 0,

а последнее выражение стремится к 0 при α → 0. Причем и kxˆα − xˆkC[τ −α,τ ] → 0.

T

τ

T

Z

На [τ, T ] вычисляем y как lim		xˆα (t)−xˆ(t)			, пользуясь формулой (VII.21)
	α→+0	α
	xˆα(t) − xˆ(t)					xˆα(τ − 0) − xˆ(τ )		Zτ	t
y(t) = lim			=		lim		+		dη D	f (η, xˆ(η), uˆ(η))y(η).
α→+0	α			x→+0		α			2

После дифференцирования по t это дает дифференциальное уравнение условий (VII.14). Остается вычислить y(τ )

α→+0		− α −	= α→+0 α [ˆxα(τ − α) + Z				−
	xˆα(τ	0) xˆ(τ )		1		τ −0
y(τ ) = lim			lim				dηf (η, xˆ(η), v)]
						τ −α
						τ −0	dηf (η, xˆ(η), uˆ(η))]
				− [ˆx(τ − α) +		Z		= f (τ, xˆ(τ ), v) − f (τ, xˆ(τ ), uˆ(τ )).
						τ −α

Лемма 3. Пусть (τ, v) фиксированная иголка, z(α) = J (ˆxα, uˆα), α > 0. Эта функция дифференцируема справа в нуле и

Dz(+0) = f0(τ, xˆ(τ ), v) − f0(τ, xˆ(τ ), uˆ(τ )) − hψ(τ ), y(τ )i,

где ψ есть решение леммы (VII.11).

Доказательство леммы 3.

Dz(+0)

≡

lim

z(α) − z(0)

=

lim

1

[J (ˆx , uˆ

)

−

J (ˆx, uˆ)] =

α→+0

α

α→+0

α

α

α

1

T

[f0(t, xˆα(t), uˆα(t)) − f0(t, xˆ(t), uˆ(t))]dt+

= α→+0 α tZ0

1

lim

разобьем интеграл на три

+

lim

[Φ(ˆx (T ))

−

Φ(ˆx(T ))] =

|

|

=

α→+0

α

α

τ −α τ

T

1

τ

= tZ0

+τ −Zα + Zτ

+ < DΦ(ˆx(τ )), y(τ ) >= α→+0

0

α

−

0

ατ −Zα

lim

dt [f

(t, xˆ

(t), v)

f

(t, xˆ(t), uˆ(t))]+

+dt hD2f0(t, xˆ(t), uˆ(t)), y(t)i + hD Φ(ˆx(T )), y(T )i =

= f0(τ, xˆ(τ ), v) − f0(τ, xˆ(τ ), uˆ(τ )) + Zτ							dt [hψ˙ (t), y(t)i + h	∂	hψ, f i, y(t)i]+
								∂ x
+ hD Φ(ˆx(T )), y(T )i = f0(τ, xˆ(τ ), v) − f0(τ, xˆ(τ ), uˆ(τ ))+
					T
+ hψ(T ), y(T )i − hψ(τ ), y(τ )i − Zτ						dt hψ(t), [D2f (t, xˆ(t), uˆ(t)) · y(t)]i+
T			∂
+ Zτ	dt h				hψ, f i, y(t)i + h−ψ(T ), y(T )i =
		∂ x
							= f0(τ, xˆ(τ ), v) − f0(τ, xˆ(τ ), uˆ(τ )) − ψ(τ )y(τ ). (VII.22)
	˙		∂
Мы здесь использовали то, что Dxf0 = ψ +				hψ, f i, и интегрирование по частям.
			∂ x

Продолжение доказательства теоремы. J (ˆxα, uˆα) − J (ˆx, uˆ) > 0. Поэтому Dz(+0) > 0, то есть из начального условия для y(τ ) получаем

	ˆ
f0(τ, xˆ(τ ), v) − ψ(τ )f (τ, xˆ(τ ), v) > f0(τ, xˆ(τ ), uˆ(τ )) − ψ(τ )f (τ, (τ ), uˆ(τ )).
Или для функции Гамильтона H ≡ −f0 + hϕ, f i имеем
ˆ	ˆ

max H(ˆx(t), ψ(t), v, t) = H(ˆx(t), ψ(t), uˆ(t), t),

v V

то есть принцип максимума.

VII.2.2

Задача о синтезе управления

Пример 26 (Простейшая задача о быстродействии). Oбобщение задачи о лифте.

T → min,

0 6 t 6 T,

|x¨| 6 1,

x(0) = ξ1,

x˙ (0) = ξ2,

x(T ) = x˙ (T ) = 0, x = x1, x˙ = x2, x¨ = u,

T

J (x) = Z0

dt · 1 → min,

f0 = 1,

u

,

Dt x2

= u

, f (t, x, u) =

x1

x2

,

x2

x2

x2

(0) =

ξ2

(T ) = 0,

x1

ξ1

x1

H(x, ψ, ψ0, u, t) = H(x, ψ, −1, u, t) = −1 + ψ1 · x2 + ψ2 · u.

Применим теорему 38:

−

−

−

1 2 − 2

ψ1

|v|61

1 2

2

˙

0

= 0,

max (

1 + ψ xˆ

+ ψ v) =

1 + ψ xˆ

ψ u,ˆ

ψ =

граничных условий на ψ нет.

ˆ

ψ

1

1

2

− 1

2

|v|61

−

2

− 2

2

при

2

6

= c

, ψ =

c

t + c

,

min ( ψ (t)v) =

ψ (t)ˆu(t), (t) = sgn ψ (t)

ψ (t) = 0.

Если u = 1, то x2(t) = t − T , x1

t

(t−T )2

T 2

(t) = T dτ (τ − T ) =

2

. Получается такая связь между

ξ1 и ξ2 ξ1 = 2 ,

ξ2 = −T , ξ1 =

ξ22

(ξ2 < 0).

R

2

Если u = −1, то x2(t) = T −t, x1

t

(t−T )2

,опять ξ1 и ξ2 взаимозависимы: ξ1 = −

T 2

, ξ2 = T ,

(t) = T dτ (T −τ ) = −

2

2

ξ1 = −

ξ22

.

R

2

Если же не выполняются условия uˆ(t) ≡ 1 или u′ˆ(t) ≡ −1, то uˆ(t) = sgn(−c1t + c2) один раз меняет знак на

интервале (0, T ) пусть это происходит в точке t .

2

(x −a′)2

x2

′2

Если uˆ(t) = 1, то x2 = t + a′, x1 = t2

+ a′t + a′′

=

2

+ a′(x2 − a′) + a′′

=

2

+ c1 c c1 = −a2 + a′′.

2

2

Если uˆ(t) = −1, то

x

=

−

t + b′,

x

=

−

t2

+ b′t

+ b′′ =

−

(b′

− x2)2

+ b′(b′

−

x ) + b′′ =

−

x22

+ c′′ (VII.23)

2

2

2

1

2

2

c c′′ =

b′2

+ b′′.

2

Рис. VII.1:

Итак, оптимальные траектории состоят из кусков парабол x1 = ±x22 + c. См. рис.(VII.1).

Из любой точки ξ′ заштрихованной области можно попасть в начало координат, только начав двигаться по

	x22			uˆ =		−	1. Аналогично в незаштрихованной области uˆ = +1. На
параболе x1 = − 2 + c. Значит, в этой области 1
границе uˆ = +1 на и uˆ = −1 на 2 = {x1 = −				x2	, x2 > 0}. Таким образом, если зададим фукции
				2
+1			на Г1 незаштрихованной области,
		U (ξ) = −1	на Г2 заштрихованной области,					,

то мы можем задать оптимальное управление формулой u(t) = U (x1(t), x2 (t)). Задача нахождения функции U (x) называется задачей "синтеза управления".

Смысл введения функции U (x) в том, что с ее помощью удобнее управлять реальными процессами. Функция

синтезированного управления указывает, в какой точке фазового пространства следует переключать управление при этом не требуется знания "предыдущей истории"траектории движения.

Глава VIII

Элементы теории динамического программирования принцип Беллмана

VIII.1 Основные понятия динамического программирования

VIII.1.1 Вывод уравнения Беллмана

Мы рассмотрим задачу об оптимальном быстродействии. Объект, описываемый системой дифференциальных уравнений, x˙ = ϕ(x, u), надо перевести из состояния x(0) = ξ в состояние x(T ) = 0 (для определенности) за кратчайшее время T . u(t) U для любого t. Это множество U часто является замкнутым множеством в Rk. Управления могут быть кусочно непрерывными и, скажем, непрерывными справа, то есть для любого t u(t) = u(t + 0) и функция непрерывна на концах отрезка, на котором задана.

Гипотеза 1. Для любого ξ существует uopt, переводящее x(t) из ξ = x(0) в 0 = x(T ) за кратчайшее время T . Таким образом, определена функция T = T (ξ), обозначим −T (ξ) ≡ ω(ξ).

Гипотеза 2. ω(ξ) C(Rn) T C1(Rn\0).

Возьмем произвольное ξ0 и произвольное u0 U , пусть x(t0) = ξ0 и движение начинается под действием управления u(t) = u0. Соответствующая интегральная кривая имеет в фазовой плоскости проекцию траекто-

рию y(t). То есть y˙ = ϕ(y, u0), y(t0) = ξ0. Движение из точки ξ0 до точки y(t) займет время t − t0. В точке y(t) включим оптимальное управление и приведем траекторию в начало координат: На движение от точки y(t)Z до

точки 0 будет затрачено время T (y(t)). На весь путь потрачено время t −t0 + T (y(t)). См. рис.VIII.1.1. Очевидно,

td− t0 + T (y(t)) > T (ξ0). Заменим здесь T на ω, разделим на t − t0, перейдем к пределу при t → t0 + 0 и получим

ω(y(t)) |t=t0 6 1 . Эта производная в силу системы есть h ω(y(t)), ϕ(y(t0 ), u)i 6 1 или h ω(ξ0), ϕ(ξ0, u)i 6 1. А

dt

для

оптимального процесса имеем равенство

h

ω(ξ ), ϕ(ξ , u)

i

= 1. Назовем

h

ω(x), ϕ(x, u)

B(x, u), функцией

1)

.

0

0

i ≡

Беллмана

Теорема 40. В предположении гипотез 1, 2

B(x, u) 6 1

для всех x =6 0 и всех u, B(x, u) = 1 для любого оптимального процесса (ˆx(t), uˆ(t)).

Формулируем по-другому: B(x, u) 6 1 причем для оптимального процесса max B(x, u) = B(x, uˆ) достигается

u U

для любого x =6 0. Уравнение Беллмана сразу дает решение задачи синтеза управления (при выполнении гипотез

1, 2).

1) Bellman R(Белман Ричард) американский математик, создатель теории динамического программирования

Рис. VIII.1:

67

VIII.1.2 Об эквивалентности принципов Беллмана и Понтрягина

Сравним методы динамического программирования и принцип максимума.

Гипотеза 3. ω C2(Rn\0), ϕ и Dxϕ C.

Для оптимального процесса B(x, uˆ(t)) по x при x = xˆ(t) имеется max, то есть 0 = DxB(ˆx(t), uˆ(t)) ≡ D2ωϕ + DxϕDω. Но заметим

dtd Dω = D2ωϕ.

Поэтому 0 = dtd Dω + DxϕDω. Удобно обозначить

	p ≡ Dω,	(VIII.1)
тогда получаем
B = hp, ϕi 6 1,	при всех u и оптимальном x,	(VIII.2)
hp, ϕi = 1,	при оптимальном u,	(VIII.3)
p˙ + Dxϕp = 0.		(VIII.4)

Итак, если (ˆx(t), uˆ(t)) оптимальный процесс, то существуют функции p(t) такие, что выполняются (VIII.1) –

(VIII.4).

Введем обозначение
H(p, x, u) ≡ hp, ϕ(x, u)i					(VIII.5)
H называется функцией Гамильтона. Тогда имеем
max H(p, xˆ(t), v) = H(p, xˆ(t), uˆ(t))					(VIII.6)
v U
p˙ = −		∂H			(VIII.7)
		∂x
x˙ =	∂H		.		(VIII.8)
	∂p

Если (ˆx(t), uˆ(t)) оптимальный процесс для x = ∂H∂p c H, определенным (VIII.5), то выполняется (VIII.6) – (VIII.8), то есть существует такое нетривиальное решение p системы (VIII.7), что система (VIII.8) имеет оптимальное управление со свойством (VIII.6). Мы получили принцип max, но при жестких гипотезах 2, 3. Причем см.

пример 17 именно они могут не выполняются в реальной задаче.

Задача 26. Показать, что в примере 26 ω / C1.

Задача 27. Показать, что в примере 26 не выполняется гипотеза 1.

VIII.1.3 Принцип оптимальности

В основу метода динамического программирования Беллман положил сформулированный им принцип оптимальности:

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

Пркажем, что не всегда выполняется принцип оптимальности Беллмана.

			2π
Пример 27. Рассмотрим функционал, который "не поддается"принципу Беллмана J (y) = α2			(y(t)−sin t)2dt+
	2π	2	R
			0
	0	y(t)dt , y C[R1]. Ясно, что при y = sin t, J (sin t) = 0 = min J (y). Разобьем промежуток измерения t
	R

[0, 2π] ≡ [A, C]

на два промежутка точкой B = π: [A, B] = [0, π] и [B, C] = [π, 2π]. По принципу Беллмана траектория, оптимальная на BC, должна была бы составлять часть траектории, оптимальной на всем AC. То есть функция y(t) = sin tдолжно бы быть оптимальным и на отрезке [π, 2π]. Однако для

JBC (y) = α2	2π(y		sin t)2dt +	2πydt 2		,
	Z	−		Z
	π			π

имеем JBC (sin t) = 4, JBC (0) = α2 π2 . Следовательно, при достаточно малом α будет JBC (0) < JBC (sin t), то есть

принцип оптимальности в данном случае несправедлив.

VIII.2 Дискретная задача оптимального управления

В дискретных задачах гладкость функций не обязательна. Поэтому открывается больше возможностей применения принципа оптимальности Беллмана. Продемонстрируем это на примере задачи о рюкзаке.

Пример 28. Имеются в достаточном количестве предметы m типов. Каждый i-ый предмет имеет стоимость ci и вес ai, i = 1, m. В рюкзак кладется xi штук предметов i-го типа. Таким образом определен целочисленный вектор x = (x1, . . . , xm). Задан максимальный возможный вес рюкзака b. Возникает задача, которая называ-

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

m

суммарной стоимости µ(x) ≡ j=1 cixi.

Выработаем алгоритм ее

решения.

P

m

.

Рассмотрим семейство задач, в которых вместо b стоит переменная z [0, b] и F (z) = max µ(x)

i=1 aixi 6 z

Если z0 = min(a1, . . . , am) > 0, то, очевидно, для z

[0, z0), F (z) = 0. Для z

[z0, b) имеем

P

F (z) =

max[c

+ F (z

−

a

)] (1 6 i 6 m,

a

6 z).

(VIII.9)

i

i

i

i

Процесс решения задачи состоит из двух этапов.

Прямой ход: по формуле (VIII.9) для всех целых z = z0, b вычисляем последовательно величины F (z) и фиксируем индексы iz , при которых достигается максимум в (VIII.9), при этом заполняется таблица VIII. 1.

						Таблица VIII. 1:
z		z0	z0 + 1	z0 + 2	. . .	b
F (z)		F (z0)	F (z0 + 1)	F (z0 + 2)	. . .	F (b)
iz		iz0	iz0+1	iz0+2	. . .	ib

Обратный ход:

Для получения (x1, . . . , xm) c F (b), во-первых, включаем предмет с номером iz1 c z1 = b и подсчитываем z2 =

z1 − aiz1				. Если z2 > z0, то берем предмет с номером iz2 и вычисляем z3 = z2 − aiz2 и т.д. Очевидно, для любого
k zk+1 6 zk − z0, поэтому через конечное число шагов будет zk+1 < z0.
	Проиллюстрируем это на выбранных конкретных значениях.
Пример 29. Пусть m = 5, b = 25.
	ai	= 7, 10, 12, 15, 17, соответственно ci = 11, 18, 22, 29, 34. Cм. рис.VIII. 2.
																			Таблица VIII. 2:
7	8		9		10	11	12	13	14	15	16	17	18		19	20	21		22	23	24		25
11	11		11		18	18	22	22	22	29	29	34	34		34	36	36		40	40	45		47
1	1		1		2	2	3	3	1,3	4	4	5		5	5	2	2	1,2,3,4		1,2,3,4	1		2,4
	Итак, получили 2 варианта оптимальной последовательности заполнения рюкзака
															10	,	15			и		15		,	10	.
															2	,	4					4		,	2

Они дают одинаковый итоговый результат оптимиального содержимого рюкзака µopt = 47, xopt = (0, 1, 0, 1, 0).

Изменим в приведеннои примере одно условие, положив b = 23. Тогда получаем 4 варианта оптимальной последовательности укладывания {1, 4}, {2, 3}, {3, 2}, {4, 1}, дающих две различные возможности оптимальной укладки рюкзака xopt,1 = (1, 0, 0, 1, 0), xopt,2 = (0, 1, 1, 0, 0), µopt = 40.

Глава IX

Прямые методы вариационного исчисления

IX.1 Метод Ритца

IX.1.1 Схема метода

Задачи вариационнного исчисления сводятся к краевым задачам для дифференциальных уравнений выписыванием необходимого условия минимума уравнения Эйлера функционала. Для рассмотренного на гильбертовом пространстве H квадратичного функционала

J (u) = hAu, ui − hu, f i − hf, ui

(IX.1)

с положительным оператором A решение операторного уравнения (чаще всего дифференциального) Au = f

является необходимым и достаточным условием решения задачи о минимуме этого функционала.

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

Однако широко распространены методы непосредственнoго вычисления значения минимума функционала и доставляющего этот минимум элемента без применения уравнения Эйлера. Такие методы называются прямыми методами вариационного исчисления. На примере квадратичного функционала (IX.1) опишем наиболее употребительный метод Ритца.

Теорема 41. Пусть A положительный оператор на гильбертовом пространстве H с областью определе-

p

ния DA H. На DA можно задать новую норму энергетическую, положив kuk = hAu, uiH . Пополнение DA по этой норме будет новым гильбертовым пространством энергетическим пространством оператора A. Будем обозначать его HA.

Доказательство. Очевидно, нуждается в обосновании только выполнение неравенства треугольника и возможность введения нового скалярного произведения. Это скалярное произведение определим на DA равенством [u, v] ≡ hAu, viH . Выполнение свойств скалярного произведения легко проверяется.

Покажем, что |[u, v]| 6 kuk·kvk. Возьмем t = λ·eiϕ с произвольными вещественными числами λ, ϕ и запишем

неравенство

[u + t v, u + t v] ≡ hA(u + t v), (u + t v)iH > 0

Раскрыв скобки, приведем это неравенство к виду

kuk2 + 2λ Re (e−iϕ[u, v]) + λ2kvk2 > 0

Левая часть по λ есть квадратный трехчлен, все значения которого неотрицательны. Значит, его дискриминант

неположителен, то есть

			(Re (e−iϕ[u, v]))2 − kuk2 · kvk2 6 0
Взяв eiϕ =	[u, v]		, приходим к оценке
	|[u, v]|
			|[u, v]|2 6 kuk2 · kvk2	(IX.2)

или |[u, v]| 6 kuk · kvk, выполняющейся для любых u и v DA. Теперь установим неравенство треугольника. В

равенстве

ku + vk2 = [u + v, u + v]

70