Ф.П. Васильев - Методы решения экстремальных задач (1125244), страница 66
Текст из файла (страница 66)
//-~ 1;, бж — елшах<г-01™«я' ~ ( А (т) — А1' ,Са+ А „С г! + + зп]з [ и !! В (т) — В; ,', + зпР' ,о ' ', С (т) — С! [-[ [ [ (т) — [; [) дт 0 е при г/-«сю. Оценки (27), (28) доказываются с использованием оце- нок (24), (26) совершенно так же как аналогичные оценки (! 24), (1.25).
Далее, рассуждая так же, как в леммах 1.3 и 1.4, с помощью оценок (24) †(28) получаем, что [/л ([я]ль Ол (')) — /(Ргг(Мы о)) [<Сабы, [/(и, Рж ([о]м)) — /ж(Ом (и), [о]ж) [ <С бж при всех (и], гн(/ль о ш У, и ш(/, [о] ~и 1', М=!, 2, ..., где Са = 2 Со + 2Сч + 2 ] р !. Из оценок (29), (30) следуют неравенства (4), (5). Таким образом, все условия теоремы ! выполнены. Отсюда следует, что 1пп /л,, =/ гг то Теорема 2 доказана. 370 Справедливы опенки ьпр зпр шах ]х(10 Рд, ([и]л,) о)— (и)не гзм ее |l 0 <а <зг хг([и]л, О!у(о))'<6 (27) зпР зцР пзах [х(/ьи, Р ([о] )) !о!дш Ум ишгг о«м -х;(О,,(и). [.]„)[<6„, !28) где 3. Кратко остановимся на условиях аппроксимации многократного максимина.
ПУсть Уб 1/ь 1=1, и,— некотоРые непУстые множества, фУнкция 1(и„о,, иг, о,, ..., и„, о„) определена на Угху,ХУгХУгХ... ...ХУмхум. Пусть требуется найти эцр ги1 зцр (п1 ч,щьг, щщ у, ч,ыиг г,ыу, эцр 'п( г (иг оь " ип г'и) = 1*. и сзы ь еи„ В качестве последовательности аппроксимирующих задач пусть взяты задачи; найти зцр (п1 ... зцр (п1 1„([и], 1")ычеы~м 1)гужуйся 1 )„мыипн 1]„мыупм [о)„,, [и]гм, [о]зм, ..., [и)„, [о[„,ч)=1м, А1=1, 2, „, (32) где У,, ]'г, г= 1, п,— заданные непустые множества, ! ([и) [о) „..., [и[„, [о] ) — функция, определеннав на У,чХ[' ыХ... ...ХУ„„ХУ„„й(=1, 2, ... Возникает вопрос: каким условиям должны удовлетворять мно.
жества Уг.. Уе „1=1, и, и фуннции 1, (]и),, ..., [о]„м) для того, чтобы последовательность задач (32) аппроксимировала задачу (ЗЦ по функции, т. е. !нп !, =г' 7 Ответ на этот вопрос дает следующая теорема. Т е о р е и а 3. Для того чтобы последовательность задач (32) аппрокгимировала задачу (31) по функции, необходилго и достаточно выполнения следующих двух воловий А и В: Усл овне Ан 1) а) существует отображение Р м.' У л -чУ,; б) для проиэюльного фиксированного [и] м ~ы У существует отображение Я .; У вЂ” !' м, 2) а) для имеющегося Р м ([и],) ы У и произвольного фиксированного о ~ы У существует отображение Р л У -ь Уг; б) для имеющихся [и] щ У „9 м (о, ) ев У и произвольного фиксированноео [и]з гж У существует отображение () л У -ь У и) а) длл уже имеющихся Р, ([и], ) ы У, о м ы У, Р „.
([и) .) гп У, о я Уы ..., Р„, ([и)„.) гы У„и для произвольного фиксированного оч т м ы У„существует отображение Р„л У„м -ь У„; б) для уже имеюи(ихся [и[ м ~= У м, (г м (о м) я У [ ),ч ~ У,м, (),ы(о,м) Узы, ", ~„э к (о„,„ч) ~ Ум хм п1юизвольного фиксированного [и]„м ~ 11я м существует отображение ч1чдн л ™пк. При этом для вжх этих отображений Р и, (г ль ..., Рпло ()пм и уже имеющихся фиксированных выиге элементов [и],ч, о,ч, . „, 13* 371 [и]„,, о„, [и]„,„справедливо неравенство Пгп (/н(1и1ь,„О,л,(о»/е) [и1»м Озм(игл<) ...
[и[ьм Онл,(г, с)) — /(Р л, (]и[ и), о м, Рзм ([и)~н), о~у, ..., Р„н (]и]нл), о„м)) 0 при всех о„м ш у Условие В: 1) а) сушрствует отображение О; У -ьУтл<, б) для произвольного фиксированного и ч ш У существует отображение Р: У -ьрэ; 2) а) для имеющегося О (и ч) <и У л и ароиэвольноео фиксированного [о1 ч «и У м существует отображение О н.. У„-ь У, м! б) длч имеющихсл и,у св У, Р м ([о1 т,) <ш Ут и пРоиэвольноео фиксиРованного ие,ч ш У, существует огпоброженнг Р ли 1'зл, -ь 1/; и) а) для уже имеюи;ихсл О (и,,) ш У „[г], л, ш у н, Оал, (а м) ш У лн ]о] м ш Учм, „,, О тл<(ин тл) <м 1/„ж и пооизвольного фиксированного [о], <и Ув эл, существует отображение О„л 1/„У„м! б) для уже име<ощихся и,л, ш Ут, Р м ([о] л,) ш [г, изл «и Уз, Рзн ([о4л) ш 1 г " Р -тм ([о[ь-»м) ш Уе-! п длл про иэВОЛЬНОга фиКСираеапкага иг у Ы Ун Сущгео»В/<Ет Отабражвпив Р„а 1 лл< л.
При этом дл.ч всех этих отображений О „, Р,м, ..., О„, Р„ и уже имеющихся фиксированных выше элементов и„,,, [о] ..„ин т,у, [о]ь эм, инл< справедливо неравенство 1'т ( (итл Р»/у ([о]тм) игл' зм ([~]зн) " инл Р ч ([о]нл')) — /л (Отл. (и л), [о]„, О и (и м), [о[ем...., О„л,(и„м), [о]»у))(0 при всех [о]нм ш У„ /[оказзтельство этой теоремы см. в [181.
4. В рассмотренных выше максиминных задачах (1),(2) или (31), (32) множества Ул Уп а также их <аппроксимаиии» У/н, У/л. не связаны между собой, поэтому такие задачи принята называть макси- минными задачами с несвязанными множествами. В приложениях, язпринер в теории игр с непротнвоиоложнымн интересами [76, 77, 121, 160, 161, 205, 2!8, 2!9[, часто встречаются макснминные задачи, в которых множества 1/и Рг и их «аппроксимации» связаны друг с другом. Такие задачи называют максиминными задачами со связанными множествами.
Рассмотрим простейшую задачу такого типа. Путь Х, У вЂ” множества произвольной природы, У вЂ” заданное подмножество из Х, и пусть каждой точке и <и У поставлено в соответствие множество У (и) ш У. Пусть функция /(и, о) определена прн всех (и, о) <ш Ух Г. Рассмотрим задачу: найти величину [33) ьнр [п! /(и, о)=г' .
ими шуги» 3?2 Пчсть Хм, 1' „У = 1, 2, ...,— некоторые множества произвольной природы, [/ — заданно множество из Х,, и пусть каждому [и] щ 17 поставлено в соответствие множество У ([и],) а' У1,, функция 1 (]и], [о],) определена при всех ([и]м, [о] )щ[т,хуа,. Рассмотрим последовательность задач: найти величины зцр 1п! !у ([и]ге [о]а) =lл' гУ =1 2 '" (34] 1ь!н щ сгн 1ь! н щ и ч [1и!н] В следующей теореме даются условия, при которых последовательность задач [34! аппраксимирует задачу [33) по функции, т.
е. Вгп 1, =г Л' со Т е о р е м а 4. Для того чтобы последовательность задач (34) пппроксиг~иоовола задачу [33) по функции, необходимо и достаточно выполнения глсдующих двух условий: 1] для каждого натурального числа дг гв 1 существует отображение Р: Х, -» Х и для произвольного 4 иксированного [и)ж щ стяг существует отображение !)ч: У -» У такие, что Р ([и]м) щ 11 при всех ]и], гм (тм, (33) (36) ггм(о] щ Уч([и]м) при всех ощ У (Ргг([и]м)), ]пп (! ~, ([и]ж, с]ч (огг)) — г' (Рм ([и]м), огг)) (О (37) при всех о щ У (Р, ([и]гс)), [и] „щ [/ 2! для каждого натурального числа У ) 1 существует отображеНис 9ч. Х-» Хм и дЛЯ ЛЮбОгО фиКСиРОВаппага иж Щ 17 СУЩЕСтВУЕт отображение Ргг' .У,-ь У такие, что О ° (и) щ [7, при всех и щ К Ргч (]о], ) гы У (им) пРи всех [о[!у гн У ч (!е~ (и )) 11щ (г' (ило Рл' ([о]м)) 71ч (1гм (иж), [о]у)) ~0 (40) при всех [о)л, гн !г ч (6лг (ич)), илг гн [7.
До к аз а тельство. Из определений верхней и нижней граней, величин l~, !гч следует, что 1! для каждого натурального Дг~[ существуют и, ги[7 такие, что 1пп (г — г'(имь, о ))(О при всех о, щ У(илг ); (41) 2] для каждого И ~ 1 существуют [и) щ сг такне, что 1ип (1 — 1 „([и],„, [о]1ч)) ( 0 (42) при всех [о[м щ Ум ([«]л.в); 3) для любого и ш У существует элемент о см )г(и ) такой, (43) [пп (! (и, о ) —,1„) О! М со о э 4) для любого [и) ш У существует [о] сж ]>, ([и],) такой, !нп (!» ([и]1„, [о]» ) — !» ) (О.
[44) Справедливость соотношений (41) — [44) устанавливается так >ке как и аналогичных соотношений (6) — (9). Необходимость. Пусть 1нп ! =,! . Определим отобра- Л>о жение Р: Х -»Х так: Р, ([и] ) — и „при всех [и] си Х „ !»=1, 2, ..., где и „сн У взят из (4!).
Ясно, что тогда включение (35) выполнено и, кроме того, согласно (4!) 1'"> (>о — > (Р,» ([и]л>) "л)) ~0, о» ш У (и» ), Л> со Возьмем произвольный элемент [и] сн У, по нему из [44) найаем соответствующий [о) сн ]> ([и] ) и определим отображение !)>»: )>-»'г'» так: 01,(о)=[о]ла жпри всех о ш )', Л>=1, 2, Тогда справедливо включение '36) и, кроме того, согласно (44) !>и> (!л>([и]гг, >7л(ол)) — 7л,)(0 Л> со Отсюда следует, что !— ; (! ([.], 4)„( )) — у(Р ([] ), о ))«- Л> со ~ !пп (7» — ! )+ 1пп (7,»([~]>», Ол (о>»)) — 7ж )+ л> ~о о Ф„ Л Л Лэ [, (! — ! (Рлг ([и]л,), ож)) ~0 при всех о, сн )> (Рм ([и]м)), [и], ш У,.
Необходимость условия !) доказана, Далее, определим отображение 1,),»> Х -» Х!» так: Ол>(и) = [и]!»„ при всех и ш Х, л> = 1, 2. ..,, где [и], взят из [42). Ясно, что тогда включение (38) выполнено и, кроме того, согласно (42) 1!ш (! — ! , [[3 (и ), [о] )) ( О. Возьмем произвольный элемент и ~ У, по нему из (43) найдем соответствующий о, ш ]> (и, ) и определим отображение Р л у, -» -»У так; Р,([о] )=о „пРи всех [о]>» см Уло Л'=1, 2, ... Тогда справедливо включение (39) и, кроме того, согласно (43) 1!ш (У (идо Рн ([ ]л))- у„) 0 Л> со 374 Отсюда следует, что 1(щ (! (ил), Р,ч ([о]м)) — у,ч (Ол (ом), [о!)т)) -=- «1!ш (7„— !ла)+ 1(ш (7(ом Р)т([о!л))— Л' со " Л) со — уэ)+ 1пп (1,„— ! ф (и ), [о] ))«О Л( со при всех [о]л((и Ул (Ол) ((сл.)), ил) (и [7. необходимость условия 2) также доказана.
Достаточность. Пусть выполнены условия 1), 2). Возьмем [и[ „~ [7 из (42), паложии и =Р ([и],„) и из (43) возьмем ом ш У (и ) =У (Рм ([и] )). Обозначим [о] =Од (о, ). Из (36) тогда имеем [о] (и У ([((]л, ),)У=1, 2, ... Пользуясь условием (37) при [и[л,— — [и]л,, о),— — ло)та, с учетом (42), (43) получим 1!гп (! „— ! )= 11ш (! — 7,([и] „, [о] ))+ М со " )т со + 1'ш (!л (["[лэ Ъ('л~)) у(1 л (["])е ) л ))+ + 1!и( (Х(и, о, ) — Х ) «О.
(~,— !Л а) .- 1!ш (уэ — у(иггэ, ол))+1(п) (у(ила Рм([о]ли))— — 1, (ОЛ,(и„), [о],„))+ [пп (! ([и]ч, [о] „„) — 1,„) «О. Л) оо Таким образом, 1пп 7, =-11ш 1, =у, т, е. 1пп !и = ! . Ли Ла э' ' ' Лв а' Теорема 4 доказана. Для иллюстрации теоремы 4 рассмотрим задачу (33) для случая, когда у(и, о)=[х[Т, и, о) — р]з, где к(1, и, о) — решение задачи (!6), и я Х=!.,' [!в, Т], о ~ У =].чв[!в, Т], множества [! и У имеют вид(17), (!В), а множество У (и) при каждом и ~ 1)' определяется так: т в (.) - (. в ) ! в (. ()), .
И) в в) . гв (45) 37$ Далее, возьмем и „ы 1)' из (41), положим [и)с=ОЛ (игг ) и из (441 возьмем соответствУющий элемент [о]л) ~ У)т ([и]л() = = У,. (Ол,(и „)). Обозначим ол) — — Р,([о) . ). Йз.[39) тогда следует, что ож й У (ил, ), Л)=1, 2, ... Почьзуясь условием (40) при и„=им,, [о) =[и], с учетом (41), (44) имеем Эту задачу кратко будем называть задачей (33), (15) — (!8), (45). Лля аппроксил~апии этой задачи рассмотрим последовательность задач (34), где ) ([и) „ [о) .) = 1 х,([и) „ [о],) — у,'; х,.([и] [о], ), 1 = О, У, — решение задачи (21), соответствующее управлениям [и)ж щ Хч —— Цлг, [о]м щ Улг — — Цлб! множества 1)х, У имеют вид (22), (23); а множество Уч ([и]м) при каждом [и],=(и, и, ...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
