Ф.П. Васильев - Методы оптимизации (2002) (1158201), страница 27
Текст из файла (страница 27)
о Пользуясь неравенством Коши — Буняковского, с учетом условия (6) получим [у'(х) — у(у) — (ут(у), х — у) [ < ! ! г~ !2 < 1 ~7'(у+ Ф(х — у)) — У'(у)[[х — у[!(1 < (5[х — у]аЫ( = ~ ~~ . П о о 3. Приведем несколько лемм о числовых последовательностях, которые нам пригодятся при доказательстве сходимости методов минимизации, при оценке скорости их сходимости.
Л е м м а 2. Пусть числовая последовательность (аз) такова, что о,„,<а„+6„, 6ь>0, 6=0,1,..., 2 6„<оо. (8) !',н Гп 2. КЛАССИЧЕСКАЯ ТЕОРИЯ ЭКСТРЕМУМА Тогда существует 1пп ай < со. Если (ай) ограничена гще и снизу, то !пп ай конечен. Заметим, что если 6, = О, й = О, 1,..., то,последовательность (ай) не возрастает, и лемма 1 превращается в хорошо известное утверждение о пределе монотонной последовательности. Д о к а з а т е л ь с т в о. Суммируя первое из неравенств (8), имеем а <а, + 2 61 <ай+ 2" 6 (9) (12) гО В.
ВСПОМОГАТЕЛЬНЫЕ ПРЕДЛОЖЕНИЯ 89 Л е м м а 5. Пусть числовая последовательность (ай) удовлетворяет условиям -Хг" ай > О, й Е А! = ( 1, 2, ...); (13) (14) ай й1 < ай + Сй-'О, й Е Т„й + 1 Е То (15) при всех йи > й > О. Пусть !!ш а.= 1пп ай, й„< й„~ „и,=О, 1,...; Огп й„=со. — О- "' ."О О-.О Положим в (9) й=й„.
Получим а <а, + 2' ,6, Чт > й„. Следовательно, 1=й„ 1пп а <ай + ",1 , '6,, для всех и =1, 2,... Отсюда при и — йоо имеем !пп а„< О < 1пп а, = !!ш а„. Но всегда !!ш а„(!пп а„, поэтому !пп а„= 1пп а . ООО' — Ю В И О О О Отсюда следует существование предела (ай). Далее, при й = 0 из (9) следует ограниченность (ай) сверху. Поэтому, если (а„) ограничена еще и снизу, то 1!гп ай конечен. П й ОО Лемма 3. Пусть числовая последовательность (Ьй) такова, что 2; 6,<со й-о Ьй .. ) Ьй — 6„6й ) 0 < й = О, 1,..., Тогда ай=О(й '), й=1,2,..., т. е. найдется постоянная В>0 такая, что 0<ай<Вй ', й=1,2,...
(11) Доказательство. Если а =0 при некотором т > й„то из ~10) следует, что ай =0 при всех й > т, и оценка (11) становится тривиальнои— в (1)) достаточно взять В =т шах ай Поэтому пусть а„>0 при всех 1 Чй Ч О и > йо. Тогда из (10) имеем а„1 а„а а„1 а„„1 Суммируя эти неравенства по и от й до некоторого й — 1 > й, получаем а,,' — а„1 ) А(й — й ) или ай ( А '(й — йо) ', й > йо. Но (й — йо) ' < (йо + +1)й ' при й > й, поэтому О< ай <(й +1)А 'й '. Если 1< й < йо, то 0 < ай = йайй ' < й. ( шах ай)й ', Остается в (11) принять В = шах((й + 1чййй, + 1)А ', й шах ай). П 1<й<1й Тогда существует йп Ьй > — оо, Если (ЬйТ ограничена еи!в и сверху, то 1пп Ьй конечен.
й ОО Эта лемма сводится к лемме 2, если принять Ьй = — ай, й = О, 1,... Л е м м а 4. Пусть числовая последовательность (а„) такова, что ай >О, й =О, 1,...; ай — ай, >Аай, й > йо>0. (10) 0<ай<ОЙ ', й=1,2, (16) Доказательство. Можем считать, что А > В+ С, так как если неравенство (13) верно для некоторого А = Ао > О, то оно верно для всех А > А,.
Выберем натуральное число й так, чтобы 4<й,'<(й +1)'<6 (17) Убедимся в том, что такое число существует. Для этого перепишем (17) в равносильном виде: 4' < йо < 6' — 1, где г = р ' > 1. Существование такого числа й, будет доказано, если покажем, что длина отрезка 14',6' — Ц при любом г > 1 не меньше 1, т. е. 6' — 4' — 1 > 1 или д(г) = 6' — 4' > 2 при всех г > 1. Но д'(г) =6'!пб — 4'!п4>!пб(6' — 4') >О, г >1, так что д(г) строго монотонно возрастает при г > 1.
Следовательно, д(г) > д(1) = 2 для всех г > 1. Таким образом, при каждом р, 0 < р < 1, число йо, удовлетворяющее условиям (17), существует. Покажем, что а „,<2А(й, +1) О. (18) Может случиться, что й е То. Тогда воспользуемся неравенством (13).
Заметим, что функция Яа) = а — а'А '+ Ай 'О достигает своего максимума на числовой оси при а= А/2, и поэтому /й(а) < /й(А/2) = А/4+ Ай '" для всех а > 1, й = 1, 2,... Тогда из (13) с учетом неравенств (17) имеем а, ю < /й(а. ) < А/4+Ай;" < А/4+А/16 < (5А/16)6(й,+1)-1' < 2А(йо+1)-О, Если же й, Е Ео то возможно и й +1 Е Х1. Тогда из (14), (17) следует, что а„„, < В(йо+ 1) " < В(й, + 1)-'/4 < 2А(й, + 1)- .
Если й Е 71, но йо+ 1 Е То, то из (14), (15), (17) полУчим а „( Вйо '" + Сйо йй ( Айо " < 2А(йо + 1) '. Оценка (18) доказана. Далее, сделаем индуктивное предположение: пусть пРи некотоРом й > йо+ 1 веРна оценка ай < 2АЙ '. Возможно, что й е То. Тогда с учетом (17) имеем ай < 2Ай ' < 2Айо ' < А/2. Поскольку /й(а) 91 б б. ВСПОМОГАТЕЛЬНЫЕ ПРЕДЛОЖЕНИЯ 90 Гл. 2.
КЛАССИЧЕСКАЯ ТЕОРИЯ ЭКСТРЕМУМА где Тогда ь ! !п(в+2)~ й !ьс!п(й+2) с (28) Тогда монотонно возрастает на отрезке [О, А/2], то из (13) следует, что ай„, < </,(ай) < /й(2Ай с) =2Ай о — ЗАй с' < 2А(й "— й '"). Но при 0 < р (1 справедливй соотношения й й — й с' <(й'+1) ' <(й'+йо ') ' = й ой'(й+1) ' <(й+1) ', (19) поэтому а й! < 2А()с+1) й. Если же й е1 и й+ 1 е 1,, то из (14), (17) получим а „, ( В(й + 1) йо < В(й + 1) "(йп+ 1) й < 2А(й+ 1) о.
Если й е 1„но й + 1 е 1, то из (14), (15), (17), (19) имеем < (В .! Со)й-йо ( Ай-со ( А(йо 1)й-йо ( < А(йз — 1)й-" =А(й- — й-") <2А(й+ Ц- . Этим показано, что ай<2Ай ' при всех й>йь+ 1. Если 1 < й < йп, то а,= =й"а й с<йпй 'таха,. Остается в (16) принять.0= шах(2А; й таха). П !пйпй, !чйпй, Л е м м а 6. Пусть числовая последовательность (юй) такова, что 0 ( юй „, ( (1 — зй)юй + с(йо й = 1, 2,, ю, > О, (20) гдг 0< а < 1, с(й )О, й = 1,2,..., 2 ай =со, 1ип с(й/ай =О.
(21) й оо Тогда !ип и = О. Д о к а з а т е л ь с т в о. Поскольку 1 — х < е ' при 0 < х < 1, то 1 — з, < е '*. Из неравенства (20) тогда имеем 0< юй+, < юйе ч+с(, й =1, 2,... Отсюда с помощью индукции нетрудно получить, что 0< юй„, < (ю!+ ~; с(! ехр(~; зз)) ехр( — ~ зз), й =1,2,... (22) Далее воспользуемся известной теоремой Штольца (1352, ч, 1, с. 88!), ко- торая представляет собой разностный аналог правила Лопиталя и гла- сящей, что если последовательность (у,) монотонно возрастает, предел 1ип (х, — х,,)/(уй — дй,) существует, 1!т уй = оо, то также существует и й й оо предел 1ип хй/уй, причем !ип х /у = 1!т (хй — х,)/(уй — уй,).
й й оо Положим дй оо ехР( — 2 з,.), хй оч ю, + 2' ,д,. ехР( 2; зз), й = 1, 2,... Из !'= ! условий (21) следует, что (уй) монотонно возрастает и стремится к беско- нечности. Кроме того, !ип й " ' = !1т дй ехР(+ 2 зт) й оо уй Ьй-! (ехР( — 2,' зт) — ехР( — 2 з!)) =!ип — "-,— = 11гп ® ", =О, так как функция х/(1 — е *) ограничена на множестве 0 < х < 1. По теореме Штольца с учетом неравенства (22) получим !ип ю = йт хй/уй = 1ип (х — хй,)/(у, — уй,) =О.
й оо й оо й о Заметим, что неравенство (22) по существу представляет собой оценку скорости сходимости последовательности (ю„). Однако правая часть оцен- ки (22) трудно обозрима. Поэтому полезно иметь другие, быть может, более грубые, но более обозримые оценки. Здесь может быть полезна следующая простая Л е м м а 7. Пусть числовая последовательность (ю,) такова, что 0< ю,„, <(1 — з,)ю, +Ай, й =1,2,..., ю, >О, (23) 0< зй < 1, с!й > О, й =1,2,..., зир с(й/зй = с < оо. (24) йй! 0<юй<ю,+с, й=1,2,... (25) Доказательство легко проводится по индукции. При й = 1 оценка (25) очевидна.
Если (25) верно для некоторого й > 1, то из (23), (24) следует 0< ю„, <(1 — з )(ю, +с)+ с!й < (1 — зй)ю, +(1 — з )с+сз < ю, +с, что и требовалось доказать. С) Покажем, как может быть применена лемма 7 для оценки конкретных последовательностей. Л е м м а 8. Пусть числовая последовательность (ай) такова, что 0< ай, ((1 — 1/й)ай+с /й', й =1,2,..., с, =сонэ(>0, а, >О.
(26) Тогда справедлива оценка 0< ай < с,1п(й+1)/й, й =1,2,..., ой =сонэ! >О. (27) Доказательство. Сделаем замену ю =а й(1п(й+1))-' и, пользуясь леммой 7, докажем ограниченность Тюй). Из (26) имеем 0<ю <(! — — ) — — ю +с 1Х А+1 !пса+1! ь+1 Ь) й !п(А+2) " ' Ьз)п(Ь+2)' Таким образом, !',юй) удовлетворяет условиям (23) при Нетрудно видеть, что' 0 < зй < 1, !ип дй/зй = с„так что зцр с(й/зй = с, < со. й й — ! йй! Из леммы 7 имеем 0 < ю, < ю, + с„й = 1, 2,..., что равносильно оценке (27) с с = с, + а, / 1й 2. П Лемма 9.
Пусть числовая последовательность(а,) такова, что 0< а „, <(1 — 1/йз)а +с!/йсз, й =1,2,..., с, =сонэ!>О, 0()3 (1, а, >О. 0<а < (а!+ — !р) —,, й=1,2,... (29) Доказательство, Сделаем замену юй оо йзай. Тогда из (28) имеем 4 1. ПОСТАНОВКА ЗАДАЧИ 95 :"1 А„= аз о ..., а,„ а,„„„..., а,„ А„= А„= а,„„„..., акч у 1. Постановка задачи Х(х) = с'х' + сэхэ+... + с" х" х'>О, ЬЕХй, при условиях (2) апх'+ аих'+...
+ а,„х" < Ь', ч „ь (4) а!х +аэх +...+а, х =6, г 11~., ГЛАВА 3 Элементы линейного программировании Изучение методов минимизации функций многих переменных начнем с методов решения с авннтельно простых н достаточно хорошо изученных задач линейного программирования, К од линейным программированием понимается раздел теории экстремальных задач, в кото. ром изучаются задачи минимизации (нлн макснмнэацнн) линейных функций на множествах, задаваемых системами линейных равенств н неравенств.
Различные аспекты теории н методов линейного пРограммирования, его приложения к технико-экономическим задачам изложены, например в 11; 13; 33; 48; 49; 52-54; 61; 76; 116; 135; !79; 203; 204; 214; 2!6; 231; 232; 243; 252; 259; 295; 297 299; 304; 317; 320; 330! 356; 361; 370; 373; 374; 398; 410; 422; 466; 470; 471; 487; 499; 506," 5!6; 517; 525; 541; 566; 584-586; 601; 612; 620; 636; 644; 652; 670; 676; 683; 685; 686; 688; 690; 719; 725; 736; 746; 747; 750-752; 775; 776; 796; 818]. 1.
Общая задача линейного программирования может быть сформули рована следующим образом: минимизировать функцию где с', ая, Ь*, з =1,..., в, 7' =1,..., и заданные числа, пРичем не все из чисел с' н не все из ая равны нулю, Хй — заданное подмножество индексов нз множества (1, 2,..., и). В частности, здесь возможно, что Х~ = О или 1й = (1, 2,..., п); не исключаются случаи, когда отсутствуют ограничения типа равенств (тп = в) или типа неравенств (т = 0). Если ввести векторы с =(с',..., с"), а,. =(а,.„... ..., аы), х = (х',..., х"), то задачу (1)-(4) можно кратко записать так: 1(х) = (с, х) — ~ 1п1, х Е Х = (х Е Е": х" > О, )с Е 1„, (аг, х) < 6', з = 1,..., т; (аг, х) = 6", з = го+ 1,, в), где (с, х), (аг, х) — скалярное произведение соответствующих векторов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
