Файл: Иоффе, А. Д. Теория экстремальных задач [учеб. пособие].pdf

Скачать файл (14,79Мб)

Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 15.10.2024

Просмотров: 192

Скачиваний: 0

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

§ 6.4. ДИСКРЕТНЫЕ ЗАДАЧИ

295

во-первых, условия локального минимума функции Лагранжа по х:

д З

дх„ Х = Х т

\ f o x ( X *Q’ U*b)

% х ( Х *0>

U*0

и=и*

дЗ

1го

(х*) 1о=

°>

дх\ х=х+ =

h f ' l x ( X*V U* l ) - V ' l x ( X*l>

U*l)P-2

Pi +

xl**!’ Utl)

(6)

дхN—1 X—X*

U—U*

T t f - l . x {X * N - P U* N - i) P n ~ ^

+ Р н - i " b P n - \ S ' n - i (x * n - i ) ~

д З

Pn "b hN (x*N) lN

дхN

x —x„

u —u.

по

во-вторых, условия минимума

функции Лагранжа

и:

| T'i( Х * Р

W*0) =

K f

1 ( Х * Р U * i ) ~

( P i

min

( У ; ( у ,

и) -

{р. |ф. (х,.,

и)), (7)

ui ^ ui

i — 0,

1, . . . »

iV — 1,

и,

в-третьих, условия дополняющей нежесткости

Положим

i== l .........N — l.

(8)

А0) =

(Pi |

— A0/t- (xh щ).

Ht (х, и, р,

(Х[, щ))

Тогда из

(6)

следует,

что

векторы р „

pN удовлет

воряют следующей рекуррентной системе соотношений:

	dHt(xi. «г> Pi+и А0)			(9)
	Pi ~ '	дх	■Pig'i{x*i)>	(9)
которая	называется	сопряженной системой. Положим,
далее,	р0 = Н'0х{х*о’	и*о’ Р р \ ).	Тогда в силу	первого

296 ГЛ. 6. СПЕЦИАЛЬНЫЕ ЗАДАЧИ

равенства в (6)

Ро	hо (-^„о) ^0’	( Ю )

а согласно последнему равенству в (6)
P n	^ n {x *n)^n -	( 11)

Наконец, равенство (7) можно переписать следующим образом:

Итак, мы доказали следующий результат.

Т е о р е м а	1	(дискретный	принцип	максимума).
Пусть пара	x* =	(xo, . . . , хдг),	и, = (ы*о,	. . . . и*jv—i)

является точкой локального минимума в задаче (1) — (5).

Тогда	существуют	числа	А0^ 0 ,	р1^ 0 , . . . .		p ^ - i	^ O
и векторы р0<= Rra,		. . . , рдг <= R",		l0е Rs“,	lxе	Rs',	не
равные одновременно нулю и такие, что					До)	является
а)	последовательность		(pN, pN-\, .. .,

решением сопряженной системы (9), удовлетворяющим конечным условиям (10), (11);

б) при всех i = 0, 1.........JV— 1 выполнено условие максимума (12);

в) числа рь .. ., рл?_1 удовлетворяют условию до


полняющей нежесткости					(8).
Подчеркнем аналогию приведенной теоремы 1 и тео
ремы	1	из	§ 5.2, где был получен принцип максимума
для задач с фазовыми ограничениями.
Дискретный принцип максимума вместе с условиями
(2),	(4),		(5) содержит полную систему соотношений
для определения искомых переменных х0, . .. ,								xN, ы0, ...
. .. , «,v-i			и	множителей			Лагранжа рь	. .. , p.v_b
Ро, ■■■> P		n ,	/о, In- В самом деле, х{ и Pi суть п-мерные
векторы,		/0	есть 50-мерный			и	есть Sjv-мерный векторы,
т. е. полный				набор	искомых величин			содержит
2 (Л/ -j- 1)л + Nr + п -f s0 +						Sjv параметров. С другой сто

роны, каждое из равенств (2) содержит п соотношений, условия ( 4 ) — s0+ sN соотношений, условия (5) — п со отношений; каждое уравнение сопряженной системы (9) содержит п соотношений, условия (10), (11) и (8) со держат тоже по п соотношений каждое и, наконец, каж-

'	§ 6 . 4 . Д И С К Р Е Т Н Ы Е З А Д А Ч И			2 9 7
дое из равенств (12) определяет, по существу,				г соот
ношений, характеризующих точку, в которой				функция
Hi достигает	максимума по	и. В итоге	получается
2 ( i V + l ) « + jV/'-j-«-\|-So-f-sJv		соотношений,	столько же,
сколько и неизвестных.

6.4.3. Метод динамического программирования. Для иллюстрации основной идеи этого метода рассмотрим

упрощенный вариант задачи		(1) — (5):
N- 1
2	fi (Xi,	ut)-> inf;	(13)
i= 0
Xi+l=q>i(Xi, щ),	i = 0 ,1 .........iV — 1,		(14)
ui <=Ui cz'Rr,	/ =	0, 1.........N — 1,	(15)
Xq— заданная		точка из Rn,	(16)

т. e. задачу без фазовых ограничений с закрепленным левым и свободным правым концом.

Наряду с задачей (13)— (16) рассмотрим семейство «возмущенных» задач, каждая из которых определяется

номером	k — 0, 1, . .. ,		N — 1		и вектором			^ e		R";
		JV- I
		2	fi (xh U[)			>infj					(13')
		i—k			k +	1, .				1,	(14')
Xi + i = < P i ( X i ,		Ui),	i =	k,			. . ,	N —
«i e (/; c		R',	i =	k,	k +	1..........N — 1,					(15')
			xk =		x.						(16')
Нетрудно видеть, что задача						(13)— (16)				получается
из задачи (13') — (16'),			если положить k =					0, х =			х0.
Обозначим через Fh(x) значение задачи									(13') — (16'),
Тогда /^(^о) — значение задачи (13) — (16).									решениями
Т е о р е м а 2.		Функции		Fh{x)		являются
системы функциональных уравнений Веллмана
Fi (х) =	inf (ft (х,	и) +	Ft+l (фt (х, и))),				i =	N.........			(17)
u е Ui

с конечными условиями

F n (х ) = 0 .

(1 8 )


298	ГЛ. 6. СПЕЦИАЛЬНЫЕ ЗАДАЧИ
Если	последовательности х =		(хо,	. .. . Xn) и	и =
— ( « о ,	•••, иjv—1) допустимы в задаче			(13)— (16)	и
	Fi (xi) = ft (xh ид +		Fi+i (x,+I)		(19)
для всех i ~ О, 1, .		N — 1, то пара		(х, и) является ре

шением этой задачи.

Доказательство теоремы очень просто. Соотношения (17), (18) следуют прямо из определения функций Fui

ГДГ-1
Fk (*) = ini { 2	U (xh Ui)I *г+1=Ф< (xi> «<), Ui<=Ut, xk= x
l i=k
= inf lfk (x, Uk) +		inf (	2	ft (xlt ut) \|xi+{ —
l		1	ft+i
= <Ti{xi,ui),	Ui£=Ui,	xk+l=<p(x, M)J\|«e Uk} =
	= inf {fk (x, u) +			Fk+l (cpft (x, a ))\| « s Uk) .

Второе утверждение тоже проверяется непосредственно:

F0 (х0) = / о (*о> «о) +		Л (*i) = fo (х0, « о )		+ ft {Xu Ml) +
- j - /•'г ( * 2) = •••	—	М * о > н о ) +	••• +	/ л ' - i ( % - i >	un-\) +
				N -1
			~\~Fn (xn) = 1		ft (xh ui),
				i-0
откуда следует,	что x — {xo,		.. ., x.v), м = (м 0,		uN-\)
— решение задачи		(13)— (16). Теорема доказана.

Комментарий к гл. 6. К § 6.1. Более подробно о линейном про граммировании см. Гасс [1], Рокафеллар [14], Юдин и Гольштейн [1].

К §§ 6.2 и 6.3. В этих параграфах мы во многом следовали работе Хестенса [3]. К этой тематике естественно примыкает извест ная теорема Морса: индекс квадратичной формы классического ва риационного исчисления равен числу сопряженных точек на отрезке

цо, 6].

К § 6.4. Доказательство теоремы 1, близкое к приведенному, со держится в книге Пшеничного [4]. Подробное изложение теории опти мального управления дискретными объектами можно найти в книгах Болтянского [5] и Пропоя [2]. О методе динамического программиро вания см. книги Ариса [1], Веллмана [1], Веллмана и Калабы [1].

Г л а в а 7

ДОСТАТОЧНЫЕ УСЛОВИЯ ЭКСТРЕМУМА

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

восновном традиционными методами.

§7.1. Метод возмущений


0	7.1.1. Возмущения		экстремальных		задач. Пусть	X
и Z — некоторые		множества, /0: X —»R — функция на X,
С0— подмножество X. Рассмотрим экстремальную						за
дачу:		h (х) ~> inf;		J te C 0.		(1)

Включим задачу		(1)	в семейство экстремальных задач
	f (х, z) -> inf;			х<=С {г),		(2)
где	f: X X . Z - + R ,	C(z) — многозначное			отображение	из

Z в X. Предполагается, что для некоторого z0е Z вы полнены равенства

/ (х, z0) = /о (х), С (z0) = С0.

При выполнении этих равенств задача (2) назы вается возмущением задачи (1), а множество Z, фигури рующее в постановке задачи (2), называется классом возмущений.

Нижняя грань в задаче (2) является функцией от z. Она обозначается далее S(e) и называется S-функцией

Смотрите также файлы

Картирование шельфов сборник статей..pdf

Квитко, М. П. Кислородно-конвертерный процесс.pdf

КМА набирает высоту сборник статей, очерков об освоении Курской магнитной аномалии..pdf

Коган, З. А. Консервация и упаковка машиностроительной продукции.pdf

Козырев, А. П. Теория тепловых и гидродинамических процессов в атомных энергетических установках учеб. пособие.pdf

Файл: Иоффе, А. Д. Теория экстремальных задач [учеб. пособие].pdf

Смотрите также файлы

Информация

Списки файлов

Дополнительно