Введение в теорию исследования операций. Гермейер (1971) (1186148), страница 54

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 54)

т множества ограничены вслед за ограниченностью а;(шахг,(х) и р (шахе,(у). к У Множества и и о, очевидно, выпуклы, так как из 1 а,'" =- ~ г, а[, (х) о а,'" = ~ г; (х) с[1, (х) и о немедленно следует, что при О ( ). ( 1 1 Хао+(1 — к)а)м= ) г;(х)с[(Ц,(х)+(1 — 'к)~,(х)), о Геометрически (354) означает, что существует гиперплоскость ~ Ь;г;=й, проходящая через точку у и такая, 1=! т. е. вектор Ха'о+(1 — Х)аы'Еи.

Множества и и о замкнуты в силу непрерывности г;(х) и з~(у) и свойств интеграла Стилтьеса, данных в леммах [и2223. Таким образом, решение игры (351) связано с решением конечной игры с билинейным платежом (353), заданной на ограниченных выпуклых замкнутых множествах и и о. Такая игра называется конечной выпуклой игрой и имеет седловую точку согласно теореме из й 16. Задача решения игры (351) распадается на получение решения а,, Ц, игры (353) н нахождение ),(х) и у,(у), соответствующих и„ ф, в силу отображения (352). Разумеется, как правило, ~,(х) и д,(у) не единственны, но различные 1,(х) совершенно эквйвалентны между собой.

Для дальнейшего будет нужна Лемма 1. Пусть Х вЂ” выпуклое замкнутое множествз в и-мерном пространстве, и пусть точка у= (у„..., у„) этого пространства не принадлежит Х. Тогда суи[ествует векгпор В=(Ь„..., Ь„) такой, что [п1 ~~ РЬ;х; > ~~'., Ь~Уг=й.. (354) .гчх~=~ з 271 нггы с глздзлвмой пллтзжной фгикцвзй 343 что все множество Х расположено от нее по одну стоРону ~ Ьх! — д>0 при хЕХ. !=! Дадим доказательство этой леммы. Пусть х' — такая граничная точка Х, что (множество замкнуто): ч~~ ~(у! — х,')'= 1п1 ~/~ (у; — х;)' > О. (355) !=! ««х г ю=! Если х Е Х> то и х'+ !(х — х') Е Х при О (((1. Поэтому согласно определению х; Д! 1»!+г(х! — »!) — У!)'~ Эх! (»,' — У;)*. !=! !=! Отса!да получаем 2( ~~~ ~(х — 4) (хч — у!) + («,У, '(х; — х!)' 0 1=1 с=! илн 2 ~~', (х,— х!)(х~ — у;)+( ~~Р (х; — х))! ' 0 ! =! !=1 при 0(Г(1.

Тогда, положив ! =О, пол)чим ~, (х! — »!) (х,' — у!) > 0 1=! или « « ~~Р ~х!(х) — у!)> 2 х,'(»,' — у,ь 1=! !=! Но по (355) и, следовательно, ~ч~ х~ (х,' — у;) > ~~'., у;(»1 — у;). с=! 344 иггы с плктежными эвикциями члстного вилл [гл. ч Поэтому Х х;(х' — у ) > Х 7(х) — у!) > Х у!( 7 — у).

!=1 !=! !=! Положив Ь! = х1 — уо получим, очевидно, ненулевой вектор В, удовлетворяющий ь ь ь ~ х;Ь!> ~ х,'ь!> ~ уА, !=1 !=1 !=! а это и есть требуемое. Имеют место несколько теорем, уточняющих связь между играми (351) и (353) и структуру решений. Введем в рассмотрение кривые С и Р, заданные соот- ветственно в и и и-мерных пространствах (содержащих и и о) параметрическим представлением: !х!(х)=;(х)„0<х<1 1<1<щ ~~(у) = вг(у), О < у < 1, О < 1 < т. Лемма П. Множество и есть выпуклая оболочка С, т. е. состоит из точек, являющихся линейными комбина- циями вида ~~.",Льа(х ), Ль>0, )~Л„=[, или пределами таких комбинаций. Точно так же о есть выпуклая обо- лочка Р.

Доказательство. Ввиду полной аналогии ограни- чимся доказательством связи между и и С. Пусть а, есть точка выпуклой оболочки С; а, = =,~~Льа(х), и пусть Гь(х)=0 при х <хе и ~ь(х)=1 ! при х>х„. Очевидно, что ит(х„)=-~ г,.(х)с~„(х). о Возьмем ~,(х)=~ч~',ЛД(х); из выражения а!(хь) через 1„(х) следует для й,= (аЯ ! и!= ) г~(х)Щ,(х), о т. е. а„являясь образом ~, (х), принадлежит и. Если же !х„ не будучи само линейной комбинацией указанного вида, есть предел таких комбинаций, то она принадлежит и ввиду '[олько что доказанного и замкнутости ![. й йт! «ггм с глзлеа«мой пакт«жной вен«пней 346 Итак, выпуклая оболочка С содержится в и. Пусть теперь, наоборот, й б и, но не принадлежит выпуклой оболочке С; с!' пусть является образом функ! ции )'(х), т. е.

а! =-~г,(х)Щ" (х). о Поскольку выпуклая оболочка С в силу определения выпукла н замкнута, то по лемме ! существует гипери плоскость,У, Ь,г; = й, проходящая через а' так, что выпук8=! лая оболочка лежит по одну сторону от гнперплоскости.

Тогда, очевидно, для любой ие из выпуклой оболочки и и ~ч~ Ь!а; —,у' ,Ь!!х,' > О, а в силу замкнутости этой оболочки 1=! ' 1=1 и и ;Я Ьр,' — Х ЬрФ>6 > О. В частности, при а) =а!(х) для любого х е и Х Ь!сс! — Х Ьгх!(х)> 6 > О. !=! Интегрируя это неравенство, имеем в силу и; = ! = ) а!(х) й~'(х) о и и ! е е в!е! — меч 1(е !е! — д !е !и~!!'! )~ ! ! ! ! о !-, !=! ! >6) 4'(х) =6 > О. о Получающееся противоречие показывает, что йу принадлежит выпуклой оболочке С, и лемма полностью доказана. Л е м м а П1.

Пусть Š— замкнутое ограниченное множество в и-мерном прооиранстве, а Е,— его выпуклая оболочка. Тогда любая точка х, ЕЕе может быть представлена в виде линейной комбинации не более чем (и+ 1) точек и+! е+! множества Е, т. г. х,= 2, 'Л!х»!; Л!>О; ~~.", Л!= 1; 1=! 8=1 х"' ч Е. 346 игеы с пллтвжамми Фьнкциямн частного анлл (гл.

т Пусть х, = ~ Л;х"'; Л;>О; !=! Доказательство. Г ~ Л,=! и г > и+1. Покажем, что количество г точек !=! х'о в этой линейной комбинации может быть уменьшено. Действительно, г (и+1)-мерных векторов (1, х',", ...,х!!!) должны быть линейно зависимы, т. е. существуют не все равные нулю числа р„..., р, такие, что Г l „'У',р!=О, ~р!х)о=-О; 1=1, ...,а. Последние равенства могут быть записаны в виде Г ~(1!х<п=О. !=1 Всегда, очевидно, найдется такое е, что для всех ! Л!+в~!~~0 (все Л; > О, поскольку предположено, что в линейной комбинации участвуют г векторов) и хотя бы для одного !, Л; +ар! =О. Тогда имеем Г Г Г Г х, = ~~.", Л;хго = ~ Л;х"'+ е ~ р!х<о = ~!! (Л;+ зр!) х"', ю=! с=! !=! !=! где Л!+е~!) О; ~ (Л!+ар!) = ~ Л;=1 и притом Л!,+е~!,=О.

Но это значит, что в представлении х, как линеййой комбинации хгп Е Е количество векторов может быть уменьшено, если г > и+1. Итак, всегда можно считать г=п+1. Если же х, есть л+! предел точек вида ~ Л1"!х1!! при й оо, то в силу вам!=! кнутости и ограниченности Е может быть выбрана подпоследовательность й' оо такая, что х~) х',о Е Е и Л!!" /л+! и!. ! Лча)О~;)~~ ~Л'"= 1).

Тогда х,= ~ Л'"х',о, и лемма !=! 1=! доказана. В теории выпуклых множеств (см. Карлик, Приложение Б-2) доказывается, что если Е не более чем а связно, то г может быть уменьшено до г=л. ф Щ иггы с глзднлимой лллтижной еьнкцинй 34! Леммы П и 11! с этим добавлением позволяют указать прием получения оптимальных ~, (аналогично, уо), если известен оптимальный вектор а, (ро) в игре (353).

Для этого нужно представить а, в виде ~ Ла(х!) (1(п, Л!)0); !=1 ~, Л;=1, а(х;) = (г,(х;)... г„(х!)), что в силу этих лемм !=1 всегда возможно. Далее, пусть 1!(х) =0 при х ( х;; 1о(х) =! при х) х! так, что а (х!) есть образ 1!(х), т. е. ! г, (х;) = ) г; (х) сЦ (х). о ! ФУнкциЯ 1о(х)= ~~Л!1!(х) тогда и есть оптимальнаЯ !=1 смешанная стратегия, ибо а, есть образ го(х), т. е. ! а!"' — — ) г~(х)!(1о(х); 1=1, ..., и, о и, следовательно, п!ах ппп Р(), у) =-и!ах ппп ~ а!~аг()ь= к а к = ш(п ~и~ а!!а!о!~,, = ш(п Р (! „д). !,! о Из сказанного следует, что всегда существуют оптимальные смешанные стратегии 1(х), составленные не более чем из п чистых стратегий хг Точно так же существуют оптимальные д(х), состоящие не более чем из т чистых стратегий у .

Можно также утверждать существование у обоих сторон оптимальных стратегий, состоящих не более чем из ппп(п, т1 чистых стратегий. Это обстоятельство легко следует из того, что при т и платеж (351) может быть переписан в виде о! г л ги ~~'., ~ ~~~ а!гг!(х)! зь(у) = ~ г,' (х) зь(у), (=! !=! (=1 348 яггы с пллтяжнымя егнкциямя члстяого яидл [гл. т для которого утверждаемое следует из одинаковости числа функций гг(х) и з~(у).

Что касается решения игр (353), то здесь применимы приемы, подобные решению обычных матричных игр. Подробное изложение их не входит в задачи книги, но содержится все в той же книге Карлина. Отметим только кратко следующее. 1. Если все г,(х))0, з~(у))0 и,КТ;г;(х) — 1, !=! юи ~ч", 6 з (у) = — 1 для некоторых у, > 0 и 5~ > О, то рассма(=1 триваемая задача решения игры (351) (а значит и (353)) может быть сведена к обычной матричной игре. Лля этого достаточно вместо г! (х) и з~ (у) ввести г,' (х) = у;г! (х); э! (У) = ам = бгт~(у) и заменить ау на — =а;~. тА Тогда вместо (353) имеем у'(», у) = Х Х а! г! (х) з! (у).

!=! г=! Соответствующая этой игре выпуклая конечная игра (353) примет вид л т ,Я~ ~! а;р!)11, причем, очевидно, л П$ а,') 0; Ц ) О и ~ а! = 1; ~ р! = 1. !=! /=! Тем самым эта игра есть обычная матричная игра, решаемая в смешанных стратегиях. 2. Иногда решение (351) и (353) получается очень просто через так называемые критические точки игры (351). С этой целью рассмотрим вместо (351) платеж вида а л и И ~,Е а!,г!(х)з,,(у)+ ~ Ь!гДх)+ ~ч.", с~з,(у) +!1. (357) 1=! 1=! 1=1 1=! Будем называть зту форму канонической, если ) ау) Ф О.

ф 271 нггы с глздзлниой пллтвжной ьункцнзй 349 Поскольку любая (351), как уже отмечалось, приводится к виду )~~ г;(х)з/(у), причем здесь >=! 1 0 ... 0 О 1 ... 0 ~а! ~= 00 ... 1 то, значит, любая игра (351) может быть приведена к каноническому виду. Для (357) соответствующая (353) будет л» » >> г,(а, 5) = Х .Яа>~а>8/+ ХЬ;с!>+ Х сф/+И= л /» л ~~.", ~,~, 'а>/з>+с/) р/+,)' Ь/з!+И= >! >! ! ! п / » й = ~ ~ ~ а>/р/+Ь,) сс>+ )'' „с/5/+ д.

(358) Решения систем ,Я~ а>/з1+с/ —— О, Ю=! л ~.", аЯ+Ь!=О, 1=1, ...,и; >=1, ...,п, Р (ав» р) ~~ Ье!>о>+ ( сопл( Р (с!>е> р>е>) >=! Точно так же для любой а г"!(а, р>л>)= Х с,ц>+М=Г,( >!>, р>4>). в силу условия существуют и могут называться критическими точками и"' и р>ь> игры (358). Если а>!> принадлежит множеству и, а ()>ь> — множеству о для задач (357) — (358), то к>л> и р>!> есть оптимальные стратегии в (358).

Характеристики

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