Введение в теорию исследования операций. Гермейер (1971) (1186148), страница 19
Текст из файла (страница 19)
Если Х вЂ” ограниченное замкнутое множество, то оно имеет крайнюю точку. Такой точкой, например, является точка х' Е Х, наиболее удаленная от начала координат. *) В теории линейного программирования зта теорема доказывается часто для односторонних ограничений. Так как двусторонние ограничения могут быть записаны в виде двух односторонних, то теорема Ч!11, казалось бы, является просто следствием соответствующей теоремы из теории линейного программирования (см. Карпин). Однако при этом можно было бы утверждать лишь, что отличных от нуля х! не более 2А, а не й, как сказано в теореме Н!11.
Доказательство же остается практически без изменений. !!О оценка зФФективности стглтегий [гл. ! Действительно, если бы х'= Хх"с+(1 — Х)хсо при хинах"', О < Л < 1, то / х' [' = ~ (х,')' = Ъ„[Лхссс! + (! — Х) хс!!!) ' = = ~ [Лс(ха!о)'+2Л(1 — Х)х!"хс"'+(1 — Л)'(хс"')') < с=! л < ~, [Лс(хссс!)'+2Л(1 — Х)( ' ) ( с ) + 2 с=! П л (! Л)! (х)!!)!) Л ~~ (хго)в+ (! Л) ~~ (,свс)! с=! '=! Неравенство будет строгим, так как хотя бы для одного ! х',"чьхсс!! и О < Х < 1.
Но отсюда следуес, что [х'[ строго меньше наибольшего из чисел )х"с[, (х!" [, т. е. х' не является точкой, максимально удаленной от начала координат. Прежде всего отметим, что множество з допустимых точек, т. е. удовлетворяющих условию х; ~ О, с'; < л < ~ а;,х, < с,, выпукло. Действительно, пусть х'".= [х';") ~' = ! и х! ! = [х,'") принадлежат з. Тогда и для х=Хх"'-1- +(1 — Х) х' при О < Х < 1 выполнено Хх,'."+(1 — Л)х,"') О, л ~ а,, [Лх,"'+(1 — Л) х;"') = с=! = Х ~~.", а;;хс" + (1 — Х) ~ а; х';*! < с ..
с=! с=! Так же обстоит дело и со вторым ограничением. Множество з, решений задачи линейного программирования также выпукло, ибо если для х' и х'! достис!! гается одинаковый минимум нашей задачи, то в силу линейности минимизируемой функции он же достигается и при х=Хх"с+(1 — Х) хс*! для любых Х из отрезка [О; !). Очевидна, также замкнутость з и з„а з, по предположению и ограничено. ф 111 УЧЕТ СЛУ'!АЙНЫХ ФАКТОРОВ 111 Утверждается теперь, что крайняя точка з, (а она существует, как показано, если з,— не пустое множество) является и крайней точкой з. о о Действительно, пусть х — крайняя точка з;, х коо печно допустима, т.
е. принадлежит з. Если х — не крайняя точка з, то существуют различные х!') Е з и х!') Е з так, что х' = 1!х~'~ + (1 — А) х!') (О < )о < ! ). Но тогда о о о ~,()х)о>=Х ~ (,.х)о!+(1 Х) ~ (,.х)~. 1=! 1=! 1=! Чта Х 1(1Х,'.о Отсюда следует (из-за О < 1! < 1) = Х 11)х,'" = ~~ 11)х,"', или если первые две суммы не 1=! равны между собой, меньшая из них строго меньше третьей. В первом случае х!" и х!') также реализуют минимум и принадлежат поэтому к з;, тогда х — не (о) крайняя точка з„вопреки предположению.
Во втором же случае х' реализует не наименьшее значение, т. е. не принадлежит з,. Эти противоречия и доказывают требуемое. Для доказательства теоремы осталось показать, что любая крайняя в з точка х' имеет лишь Й отличных от нуля координат х11о!. Предположим противное, т. е. что имеется крайняя точка хораз, имеющая хотя бы я+1<а ненулевых координат х,'" ) О при 1 <11+ 1 (перестановка номеров значения не имеет), где /г ) л. Пусть с',— значения сумм Х а)1х!о! 1=1 (1 =-1, ..., Й), которые согласно предположению (х, Ез) удовлетворяют неравенствам с,' < с,' < с,.
Рассмотрим систему о+! Х а ах) = О; 1 = 1, ..., й. 1=1 Так как в этой однородной системе количество переменных превосходит ранг матрицы (не больший я), то 112 оценил зевекгивиости стелтегий (гл. и существует нетривиальное решение (х)!!) (1 ( й+ 1) системы. Дополним зту точку координатами х)!! =0 при 1)4+1 до полной размерности и обозначим ее через х"'. Поскольку х,')О, а при !(й+1 х!)О, то всегда найдется такое е, чтобы все координаты точек х'"-1- +ехсо и хпо — ехпо были неотрипательны.
Очевидно также, что л й+ ! „'Я~ ар (х)ч! ~ ех)!!) =,'У, 'а, (х)м ~ ех"') = с' 1=! /=1 и из-за с', < с! (с, точки хио.+. ехсо допустимы, т. е. принадлежат и. Но х!'> = — (х'+ ех!'!) + — (х' — ех!'!), а это в силу различности х'"+ехсо и хио — ех"!(х)!! не все равны нулю) противоречит предположению о том, что х' — крайняя точка е. Таким образом, любая крайняя точка в з, а значит, и любая крайняя точка в зч имеет не более й ненулевых координат. Этим теорема уже полностью доказана.
Очевидно, что доказательство не изменится, если вместо Условий с! ( л!'.! а!~х!(с, рассматривать более общие ус!=! ловия,Я~ а;!х!ЕЕр где Ет — любые замкнутые ограничен!=1 ные множества на числовой прямой. Аналогичные изменения могут быть, конечно, сделаны и в задачах (99)— (100) и (101) — (102). Возвращаясь к (101) — (102), видим, что при любом п имеется решение задачи, у которого разве лишь только г величин из х~1„и, „„! отличны от нуля.
Переход к пределу при и оо позволяет, пользуясь ограниченностью го получить следующую теорему. Теорема 1Х. Если г! меняются в ограниченных интервалах, а Р (г) и ао,(г) непрерывны, то задача оценки эффективности при неопределенном законе распределения Р(г), ограниченном неравенствами типа (98), имеет дискретное решение, а именно, низкое решение, й 111 УЧЕТ СЛУЧАйямк ФАКТОРОВ из что число точек г =(г„..., г ), имеющих ненулевую вероятность, не превышает г=,~~ я! — (т — 1).
в=! Как уже говорилось, эта теорема справедлива, когда на зависимость г; не накладывается ограничений, а ограничения (98) могут заменяться на ) а!А(г!) дР!(г;) Е Е;„, где Ед„— замкнутые множества числовой прямой, или на более общие ограничения, получающиеся в пределе из (102'). Для случая т=1 эта теорема впервые сформулирована и строго доказана (даже в более общем виде) в работе Э.
!. Давыдова на основе теории выпуклых множеств. Наметим примерно путь строгого доказательства теоремы 1Х. Пусть Р,(г) реализует оценку эффективности (т. е. минимум по Р(г) осредненных по г критериев). Тогда Р,(г) может быть заменен подходящим дискретным законом РаспРеделениЯ, т. е. (гы„.. „г !„) и х)„,, '. в„ (1<1!<и) таким, что прн и — оо эффективность прй дискретном законе стремится к эффективности прн Р,(г). Но тогда тем более минимум в задаче (101) †(102) стремится к эффективности при Р,(г), когда и — со. Для фиксированного и в силу теоремы ЧП1 существует Р„(г), решающий задачу (101) — (102) и такой, что только точки г"'(п), ..., г"'(и), ..., г '"'(и) (может быть, не все различные между собой) имеют ненулевые вероятности появления р,(п).
В силу ограниченности гввв(п) и р,(п) при 1< <в<У всегда можно выбрать подпоследовательность и' такую, что и ри и' — оо, гко (и) г'," и р, (и). р'„ l ~Р ре в=! В силу непрерывности 1Р и ам соответствующий переход к пределу показывает, что Р,(г), определяемая вероятностямн р,' на г',", дает ту же эффективность, что и Р,(г), т. е. реализует интересующую нас опенку эффективности. 114 ОЦЕНКА ЗФФЕКТИВНОСТИ СТРАТЕГИЙ [ГЯ. и Если изменение г; происходит в неограниченных интервалах, или если 1Р'(г) и а! (г) кусочно-непрерывны, то, используя теорему ГЧ для ограниченных интервалов непрерывности функций и устремляя их границы к точкам разрыва или к бесконечности, получим следующее.
Т е о р е м а Х. Нижняя грань эффективности при неопределенных Р(г), ограниченных (98), может быть получена в качестве нижней грани для дискретных РГ(г), каждьш" из которых определяет не более чем Г точек, имеющих ненулевую вероятность. Использование теорем 1Х и Х удобно потому, что при оценке эффективности нужно знать только сам минимум, а не реализующие его (Р(г)); тем самым достаточно знать хотя бы одну реализацию минимума и, конечно, желательно в каком-то смысле простейшую.
Именно эту возможность и предоставляет теорема 1Х. Чтобы оценить ее смысл не только качественно, отметим случай, когда СЕ =с, и т =!. Тогда количество точек гг с ненулевыми вероятностями должно быть не больше Г=й„но и не меньше, ибо иначе нельзя удовлетворить равенствам Но тогда или ру определяются однозначно при фиксированных г, или эта система вообще не имеет решения. Таким образом, определив р,(гт), приведем вариационную задачу к задаче поиска минимума функции Г переменных гр Как же все-таки оценивать эффективность при независимых г„..., гии т.
е. как решать задачу (97) — (98)? Можно представить себе в этом случае два варианта: 1. Фиксируя реализующие ш[п законы распределения Р,'(г,),..., Р' (г ) и используя теоремы 1Х вЂ” Х для Р,(г,) и %', осредненной по г„..., г„, получим Р,'(г,) с количеством точек г, с ненулевыми вероятностями не более )Г,; продолжив этот процесс, в конечном итоге можем утвер!кдать, что оценку эффективности в данном случае можно искать на дискретных Р(г) таких, что ненулевыми вероятностями обладают разве лишь й, й, ...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
