Введение в теорию исследования операций. Гермейер (1971) (Введение в теорию исследования операций. Гермейер (1971).djvu), страница 9
Описание файла
DJVU-файл из архива "Введение в теорию исследования операций. Гермейер (1971).djvu", который расположен в категории "". Всё это находится в предмете "теория игр и исследование операций" из 11 семестр (3 семестр магистратуры), которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр DJVU-файла онлайн
Распознанный текст из DJVU-файла, 9 - страница
Для вогнутых функций справедливо обратное неравенство. Легко убедиться, что функции 5 гпах ~ У аь»уху+с»» » /=1 выпуклы. Действительно, птах ~ ~х'„', аь»У (Лхг+ (1 — Л) У ) +с»»~ = = гпах ( Л (~з аь»уху+ с»») +(! — Л) (~;аь»,.у + с»») ] ( 1 г (. Л щах (~ аь»тку+ сь») + (! — Л) гпах фаь»,.у -1- с,») ').
Отсюда следует, что любая непрерывная в ограниченной области функция г"(ху) с любой заранее данной степенью точности приближенно равна гп!п!»(ху), где все !'»(ху) — выпуклые функции, т.е. приближенно равна минимуму, взятому по конечному семейству выпуклых функций. Разумеется, сглаживая кусочно-линейные выпуклые ь) Совершенно аналогично доказывается выпуклость функции вида шах !»(х), если все 1»(х) выпуклы. » Точно так нее ппп <р»(х! вогнута, если вогнуты все ~р» (х). » 50 О ФОРМАЛИЗАЦИИ ИССЛИДОЯАИИЯ ОПИРАЦИЙ [ГЛ. ! функции, можно всегда считать ~А(х~) достаточно гладкими, если это потребуется. 3.
Теорема !Ч может быть использована и для приближенного представления зависимости критерия эффективности от контролируемых и неконтролГ)руемых факторов. Таким образом, любой непрерывный!критерий эффективности может бьлть представлен как минимакс семейства линейных функций или как миниз(ум семейства выпуклых функций.
Анализ примеров моделей в З 2 показывает широту применения операций максимума и минимума при формировании критериев, что как будто усиливает практическую значимость теоремы 1Ч. Обратим внимание и на то, что, например, ! Х вЂ” У1=гпах1 Х вЂ” У; У вЂ” Х!. 4. Как сказано в условиях теоремы, й, ~а+2, т.е. по существу не зависит от точности и области представления. Наоборот, 1, находится, вообще говоря, в сильной зависимости от точности представления е и области, в которой эта точность достигается. Если функция Р(Уг) удовлетворяет условиям Липшица по всем аргументам, то, как нетрудно понять, просматривая доказательство теоремы, 1,«К.
Это неравенство совместно с Й, С з+ 2 достаточно точно описывает возможную степень сложности приближенной записи критериев с помощью действий суммирования и взятия максимума и минимума. Итак, теоремы 1 — 1Ч достаточно убедительно показывают полноту данных в $ 3 элементарных способов соединения критериев, если К, = г (%' ). Если же )р',= г((Р',з а), где а — неконтролируемый параметр, то, используя при фиксированном а уже доказанное и соединяя это с элементарным соединением Ч1, получим подтверждение полноты способов соединения и при наличии неконтролируемых факторов. В заключение отметим, что приближенное представление критериев по теореме 1Ч может быть иногда удобным инструментом исследования.
Однако нет математического в 51 ПРИМЕРЫ СВЕРТЫВАНИЯ КРИТЕРИЕВ способа получения такого представления, если исходить из свойств функции г (11' ). Будет интересно произвести соответствук)щее исследование. Пока же можно обратить внимание на следующее. Если известно, что )с(Ж'~) при всех ((У~ больше, чем 3 любая из линейных форм ~ а! Ф'-+Ь!, то г (Ф',), очеу=! видно, больше чем шах( ~ а! )!' +Ь;, так что последМ=! няя функция может рассматриваться как приближенная оценка снизу (гарантирующая) критерия Р(Ж'~).
Точно так же, если Р(%',.) для всех (Р~ меньше, чем хотя бы одна из указанных линейных форм, то Ь'(В'Р) меньше, чем ппп ~ (а!;Ф';+Ь,). ! у=! Так же легко могут быть получены и оценки снизу типа максимина линейных форм и аналогичные оценки сверху. На практике могут существовать соображения, дающие возможность непосредственно получать оценки такого рода. ф 5. Примеры свертывания критериев способами ! и Ч Наличие общей теоремы 1Ч только увеличивает интерес к различным частным случаям точного выражения суммарных критериев с помощью приемов 1 и Ч. Дадим несколько примеров, практическое значение которых станет ясным при рассмотрении вопроса о неопределенностях третьего типа.
Отметим, в частности, подобные выражения и для способа свертывания Ш и способа 11 в варианте (Р', = 1; — оо. А. Нетрудно проверить, что 5 !п1 Х Х!()Р'! — )Р'1) =— х!ьо !=! если хоть одно )р'!, < Ф';., или, что то же, ппп (Ф'! — Ф7) < О. 1' !~!св 52 О ФОРМАЛИЗАЦИИ ИССЛЕДОВАНИЯ ОПВРАЦИЙ (ГЛ. 3 С толь же очевидно равенство щ)п,~~ Л;(%'1 — 12'1') = О, АоЬа1=1 если для всех 1(Р'1) ГГ'1, или, что то же, ппп (%'1 — Щ))0.
1<1< Отсюда ясно, что Ф',= 1+ 1п! ~ Л1(1Р',— %'о) = А1ЬВ1=1 5 о = и! ~ Х Л,)Р,. +! — Х ЛУ; Тьо 1=1 1=1 есть запись способа объединения Ц через 1 и Ч, причем Ло 1 Х Л11" 12 1=1 а Л~) О означает Л1)0 при 1<1<а. В этой формуле и во всех аналогичных далее, как легко проверить, достаточно взять дискретный (но бес- конечный) набор Ль например, принять Л1 = и, где Л=О, 1, 2,... Б.
На практике часто свертывание критериев уР'1= = г1 (Х, Г) осуществляют, вводя «основной» критерий яу,=г,(Х, У), который стремятся увеличить при обяза- тельных требованиях на остальные 121 ~~ )УГо. Такой способ является обобщением !1 способа свертыва- ния и может быть записан путем введения единого сум- марного критерия Ж',= %',=г,(Х, Г) при пнп (УР'1 — У!))О, 2~1<о — ОО при 2п1п (1Р'1 — Ж'!) < О. 2<1-о Точно так же, как и в предыдущем случае, легко прове- ряется для этого критерия справедливость выражения о о )Р, = 1 ! 1гж', + ~ Л,)Р,— ~ Л,)Р,, (.. где Л=(Л„..., Л,]. 53 Д 5! ПРИМЕРЫ СВЕРТЫВАНИЯ КРИТЕРИЕВ В.
Пусть все !Р! неотрицательны, а зпр Ф'1= = Впрах!(Х, )') — конечные верхние границы критериев при заданных областях изменения Х и г'. Образуем для каждого ! критерий ФР по способу П (см. пункт А): Ф;= !п1 Л1(уР'! — Впр уР'1)+ !. А,>О ' Далее для каждого Й(е образуем по способу 1 критерий »-! (Р» =- ~ епр Ю'1Ф1+%'», где числа зцр%'! играют роль Х1. Наконец, пусть Х„= =(!.!»,, )!» !»), тогда г»-! '!Р',= шах (Р"»= шах !п1 ~~ч~ ~зпр И71)!! !Р1+Ф' + !<»<з »» 1=! »-! + ~~.", зпр 1Р1(! з"Р !Р11)!!») ° 1=! Эта формула образована по типу теоремы 1У с той лишь разницей, что при каждом л коэффициенты линейной формы пробегают бесконечное число значений. утверждается, что написанное уР", совпадает со способом объединения Ш. Действительно, если при данных Х и Г достигнуты еир е11 для !(Й» — 1, но уР»,(зцр%'», то критерий по способу объедннейия Ш равей, очевидно, ~~.", зпР !»'1+ !Р" », 1=1 Но тогда и для записанного выше %'„очевидно, при этом имеем (при й(й,) г»-! »-1 !п1 ~ ~ епр Ф'1)!!» (!Р'! — Еир %'1)+ '~ ~Вар Ж'1+ е!» А» 1=! 1=! »-! = ~ ЕНР Ф'1+ %'», 1=1 54 о чогмллизлцци исслвдовлния опвгАций [гл.
! а при я > [5, + 1, очевидно, из-за К5 < зцр К„ Гь-! 1( — ! !п1 ~ ~ зцр Ф'1Л1ь[К! — зцр К1)+ ~ зцр [5'1+[5(„=- — ((о. !5 1= ! (=1 Поэтому из-за неотрнцательности [551, а значит и зир 971, 55 — ! получим, что и [[[5, = ~ зцр [5(1+ К5 . Обратно, если в вы!=! ражении 15', для данных Х н У, т. е. для данных [551, максимум по Й достигается при 1=я„то это, очевидно, может случиться только тогда, когда Ф'„< зцр !((5 и [51!= зцр (5'! прн ! < я,. А этого достаточно для того, чтобы убедиться в тождественности В'.
данного пункта и способа объединения 1П. Г. Если в способе объединения 1 о Л1 не известно 5 ничего, кроме Л1>0, ~ Л,=!, то, как следует из даль1=1 нейшего, представляет интерес объединение %',=щ!п~ч~ ~Л1771. ! 1=1 Очевидно, что [Р',=п![пч~" ,Л1%'1= ппп %'1, ! <1<5 если Х Л~[Р1=1 1=! Л>0 и Пусть теперь 5 Л1~ )Л5> О, 1=1 =1, Х Л1[р!4 х<!. 1=1 учитывая, что ~„Л[!([5'15=1, 1=! Л( — Л! Тогда, полагая Л1(!(= — ' ! — 5 т. е.
равно одному из способов свертывания 51. Непосредственным обобщением этого является равенство 5 К,=п!!и ~~' Л1%'1= !п!п Х 1=! 1«<5"'1 ф 51 ПРИМЕРЫ СВЕРТЫВАНИЯ КРИТЕРИЕВ и используя только что полученное равенство, имеем !р',=ппп ~ Л,.Я7,.= ~' Л,'!у«у+(1 — «)ппп ~ Лу)уу(гу.=- А Х, у=! = ~1, Луо(уу'у-!-(1 — «) ппп —,' .
у=! !оо ' Если г=О, то и Л,'=О, и рассматриваемый случай превращается в предыдущий. Наоборот, если г=1, то получаем способ свертывания ! при заданных Л;=Л,'. Д. Связи, указанные в предыдущем пункте, изменяются, если частные критерии расположены в порядке«важности», т. е. если имеются дополнительные ограничения Лу) ЛуР,)О 5 при сохранении ~~, Л;==1. у=! Положив при этом Л,„=О, получим Уо=ппп~~ ЛуЯ7у=ппп У (Лу — Л„,) ~,' В' = Х У ! А У ! у ! о у =щ!и'~ ру „((г,, р у=! у=! где о о р;=Л; — Л+„) О, ~ уру = У ~' р =~ч'" „Лу=1.
у=! у=! у=у у=! 1!оэтому по результатам предыдущего пункта при Л;) о )Лу+!)О и ~Л;=1 у=! агу (о«,=гп!п ~ч' Лу(о«у= ппп у=! у ! < у гС о Обобщая это на случай ~ Лу!о«!о=! при у=! вследствие !УУо ~ч~~ (УУо ~ р '~' (!!УоЛ у=! 'с=! 66 о еогмллизации исслндозлиии оцииаций [гл. 1 имеем У мгг Ф',=пс[п ~ ЛсФ'с= пс!и с'; Х 1=1 1«<е ~Ч;с с=! Наконец, если Х Л Ф" 0=1 с=с Л;)гс Лс+,)О, с-1 то, вводя [ьс= Лс[Ц г~ (с (з — 1), [ь, = Л, имеем*) с=с %7~ г, р,=1. [сс ~~ [сс+1 Поэтому для этого случая Е.