Введение в теорию исследования операций. Гермейер (1971) (1186148), страница 33
Текст из файла (страница 33)
Если з превышает размерность вектора х (или у), то функции 1;(х) (или ф;(у)) зависимы. В этих условиях трудно рассчитывать на выпуклость М, и У, а значит, и на седловую точку. При независимых же ~;(х) и р; (у) всегда, очевидно, можно выбрать М, и У так, чтобы была обеспечена выпуклость М„и У, (или У;), а значит, и обеспечена седловая точка. Таким образом, для разделимых игр возможности получения седловых точек принципиально различны при з, не превышающих размерности векторов х и у, и в противоположном случае.
Исключительное внимание к играм с седловой точкой традиционно в теории игр. Объясняется это, видимо, известным недоверием к максимину как принципу оптимального выбора в том случае, когда нет седловой точки. Обычно считают: как же можно полагать максимин (нижнюю цену игры) оптимальным выбором, когда можно получить и минимакс (верхнюю цену игры)? В связи с этим и имеется стремление «заполнить» этот промежуток за счет применения обоими игроками (оперирующей стороной и противником) смешанных стратегий, которое, как будет показано далее, приводит к седловой точке и якобы преодолевает неоднозначность понимания оптимальности. При этом некоторые авторы полагают, что само применение смешанных стратегий гарантирует игроков от возможности обнаружения их решений, конкретных в каждой реализации игры. Не умаляя нисколько математической, а иногда и практической ценности такой тенденции, ее нельзя все же, по нашему мнению, положить в основу общей методологии исследования операций.
Причины этого уже были указаны ранее, но важность вопроса требует их повторения и развития. вдО (гл. П1 оптимлльныв стРАФЙГян 1. Применение смешанных стратегий оперирующей стороной представляет несомненный риск, когда операция (игра) не повторяется. 2. Если даже операция повторяется, то необходимо иметь уверенность в отсутствии у противника информации о конкретных решениях (чистых стратегиях) оперирующей стороны в каждом повторении. Само применение смешанных стратегий отнюдь не гарантирует этого.
3. Противник не обязан применять смешанные стратегии, равно как и стремиться к цели, противоположной цели оперирующей стороны. Во многих случаях (противник †приро) такие ограничения на действия противника вообще неправомерны, а в других случаях означают наличие у исследователя операции весьма подробной и, как правило, маловероятной, информации о действиях противника. Но без этих предположений разговаривать о седловой паре точек как реальности бессмысленно; а, значит, пропадают и претензии на однозначное понятие оптимальности в виде седловой пары точек. 4. Сказанного достаточно, чтобы ликвидировать стремление к обязательному получению седловых точек в смешанных стратегиях.
Но аналогичная критика относится и к большинству других ситуаций, когда доказывается существование седловых точек в чистых стратегиях. Для большинства этих случаев (примеры будут приведены ниже) характерно предположение о том, что противник применяет некоторое (довольно сложное) множество стратегий, рассчитанных на вполне определенную информацию о выборе стратегий оперирующей стороной. Кроме того, опять-таки полагается известной цель противника (как правило, предполагающаяся противоположной цели оперирующей стороны). И вся эта информация уже есть у исследователя операции. Ясно, что это не соответствует ни практике, ни даже сути постановки вопросов в исследовании новых операций.
А если эти предположения нарушены, то нет и седловых точек. 5. В чем же теоретическая суть различия постановки вопроса, основанной на стремлении к получению седловых точек, от просто максиминных подходов. В классической теории игр исследователь операции находится как бы в роли арбитра. Он в равной степени осведомлен об обоих игроках, об их целях и информи- 201 й 16) о садлазых точклх рованности. Поэтому он и «сожалеет» об отсутствии седловой точки, которая «примирила» бы обоих игроков и создала как бы «объективное» понятие оптимальности. Информированность и цели обоих игроков здесь фиксированы.
В предлагаемой здесь методологии исследователь операции отнюдь не арбитр; он, как уже говорилось, принадлежит к одной из сторон и не имеет информации большей, чем оперирующая сторона, т. е. является одним из «игроков». Исследователь операции более или менее знает цель и ожидающуюся информированность оперирующей стороны (во всяком случае, знает, какой информации она добивается).
Его информированность о противнике совсем другая, и, конечно, как правило, меньшая. Именно поэтому он не может утверждать во многих случаях, что есть седловая точка, что противник применит смешанные стратегии и преследует противоположные цели. Единственным разумным общим принципом для него и является принцип гарантированного результата и оптимальность в смысле максимина. Противоположность целей противника есть, как правило„не результат информированности о противнике, а наихудший случай его целей. Применение смешанных стратегий — это рекомендация оперирующей стороне, а не противнику. Большая информированность противника это не обязательно факт, а худший случай, когда нет данных о его информированности и т.
д. Само существование седловой точки оказывается при этом зачастую не «объективным» фактом, а наихудшим случаем. Мало того, каждая операция не есть математически определенная игра, а целая совокупность возможных игр в зависимости от той или иной информированности оперирующей стороны и противника и его целей, среди которых будет, как правило, относительно мало игр с седловой точкой.
Принцип гарантированного результата позволяет рассматривать только наихудшие для оперирующей стороны игры. Остается, при фиксированной цели, лишь вариация информированности оперирующей стороны (да и то не всегда); но эта вариация есть необходимый элемент исследования. 202 [Ел.. их оптимьльныв стглтегии Сказанного достаточно, чтобы уяснить разницу междуг чистым максиминным подходом и стремлением к седловым: точкам как основе понятия оптимальности. Однако отсюда~ не следует никак, что понятие о седловых точках несу.- щественно.
Выше уже говорилось, что седловая точка~ на М, х У означает несущественность информации сторож друг о друге в случае противоположности интересов Этот вывод весьма важен как в теоретическом, тая и в; практическом отношении. Именно тем и ценны, в первую очередь, теоремы Х[Х вЂ” ХХ1. Кроме того, отыскание седловых точек представляет собой более привычную задачу, чем отыскание оптимальной гарантирующей стратегии, к которой возможно применить обычные методьь поиска оптимумов и оптимального управления. Чтобы иметь всегда такие возможности, а также показать, что с формально-математической стороны нет принципиальной разницы между максимином и ситуациями с седловой точкой, обратим внимание на следующую достаточно простую теорему (для упрощения, хотя зто и не необходимо, будем считать все верхние и нижние грани достижимыми).
Теорема ХХН. Пусть М вЂ” произвольное множество стратегий х=х(у) при у~У. Пусть, даме, Ум — множество всех стратегий у=у(х) при уЕУ. (у(х) — функционал со значениями из У). Если Ум~У, т.е. содержит все функционалы у=у=сопз1 при уЕ У, то шах пипР(х, у)=шах пипР(х, у)=пип шахР(х, у). ««и у«н ««и еенн е«нм ««и Оптимальная х, на МхУ является оптимальной и на МхУм и, следовательно, входит в седловую пару точек на МхУ„.
В самом деле, из-за У~Ум имеем шах пипР(х, у))шах пип Р(х, у). ««и в«Ф ««м егнм Но, с другой стороны, из-за того, что все значения у принадлежат У, для любого уЕУм Р(х,'у)) пипР(х, у), вен йоз й 1б) о седловых точкех а значит, и для любого хЕ М ппп Р (х, у) ) ппп Р (х, у). РЕУМ УЕМ Отсюда и из предыдущего имеем гпах пппР(х, у)=тахш(пР(х, у). «ЕМ УЕМ «ЕМ УЕЬм Фиксируем теперь произвольное хЕМ, и пусть у«аУ таково, что Р(х, уе)=пппР(х, р).
Тогда у«=у,(х) при- УЕУ надлежит, конечно, Жм, поскольку последнее множество содержит все стратегии р(х) при увал( (если какому-то х отвечает не одно у„то для уе(х) берем произвольно одно из значений у,). Имеем теперь, учитывая указанное выше, Р(х, уе) = Р (х, у,) = ппп Р (х, у) = ппп Р (х, у). УЕН УЕУМ Поэтому тахР(х, уе)=шах пппР(х, у), «Е М «Е М УЕЛИ и, следовательно, ппп гпах Р (х, у) ( шах Р (х, уе) = шах ппп Р (х, у). УЕум «ЕМ «ЕМ «ЕМ УЕЛм Поскольку всегда по (160) имеет место и обратное неравенство, то первое утверждение теоремы доказано.
Что касается второго утверждения, то оно немедленно следует из того, что Р(х„у)) ппп Р(х„у)=шах пппР(х, у)= УЕЯ «Е М УЕУ =шахини Р(х, у), «ЕМ УЕУм и из результатов теоремы ХЧ11!. Доказанная теорема подтверждает, что случай седловой точки дает наихудший возможный случай для оперирующей стороны, располагающей множеством М, поскольку 204 (гл. ш оитиыальнык стектегяи меньше чем гпах ппп Р(х, у), при разумном поведении «ем ре аг получить уже нельзя. Доказано одновременно, что всякий максимнн может формально трактоваться и как общее значение максимина и минимакса при некотором выборе случая информированности и множества стратегий противника.
Тем самым формально стирается различие между максимином и седловыми точками. Обратим внимание на то, что повторение идеи только что доказанной теоремы для стороны х означало бы введение стратегий типа х' =х(у). Поскольку среди у содержится и у, то среди х' содержатся и прежние х=х(у). Казалось бы, такая попытка «обнять» стратегии у, в свою очередь обнимающие х, должна привести к увеличению максимина. Однако нетрудно убедиться повторением доказательства теоремы ХХ11 (но при перемене игроков местами), что этого не происходит, поскольку больше чем гарантированный для противника результат ппп гпах Р(х, у) ее агм ««и получить нельзя, а последний равен шах ш)пР(х, у), уже ««М уел достигнутому оперирующей стороной ранее.
Сказанное имеет определенное отношение к процедурам, рассматриваемым в книге Лефевра* ). Теорема ХХ11 дает отнюдь не единственный способ организации седловой точки с сохранением заданного максимина; примером другого (более экономного) способа организации является следствие к теореме Х1Ч (что касается ХЧ1, то она является частным, но наиболее важным случаем ХХ11). С этой точки зрения, а также ввиду специального значения многошаговых игр, рассмотрим, как превращается в игру с седловой точкой много- шаговая операция (182) — (183"). Для этого рассмотрим семейство У, всех стратегий у противника вида у(хо иа; 1(й); уЕА(а(аа), (191) *) В.
А. Лефевр, Конфликтугощие структуры, «Высшая школа», Москва, 1967. 205 $16] О седловых точках пип Р (х, у) ( т 1и Р (х, у) »ЕУ» »» х Р, =гпах пип Р(х, у)(птах пипР(х, у). (192) »»м»»еу»»м» у»у» С другой стороны, пусть стратегия у,Е У„определяется следующим образом: Р,(а,') =Р",= пипР,(а,); а, Р, [х„а»(а„х,Ц = пип Р,(х„а,); »»» (»»»]», Р», [х„ » (, х)]=- пни Р»,(х„..., х» „а,,); а» ,»(а»- ]- а» , х» „а~(а» о х~)] = пип Р„(х„..., х„„а»); "( ].—., ., х„, у,(а», х,)]= пип Р(х„...,х„,у). » е м» (»») (193) Р„[х„ Р [х„ где, в свою очередь, а, есть функции а»(хо а„ ,; 1(Й вЂ” 1) и т. д.; а,— постоянная, принимающая любые допустимые для нее значения.
Здесь а;(х~, а,,) может принимать значения (при фиксированном а;,) только из множества (а»]„- Этот вид стратегий есть частный случай стратегии у(х) при определенном ограничении класса этих функционалов и х Е М„. Множество стратегий Ф, содержится в множестве всех функций у(х) и содержит У. Поскольку наличие возможно чем-то ограниченной связи между у и х в У„уменьшает область изменения у при данных х, то 206 оитиилльиык стелтигии !Рл. ш Тогда имеем !пах Р(х, у,) = «ЕМ» !пах и!ах Р(х„..., х„, у,)= (х! !ал х»! г(о; Екл — !) х!, (а», «2! ! < л! = и!Их !пах 2п|п Р(х„..., хл, у).= «« <ах, «2! У~л! Реп!(ал) = и!ах Рл(х„..., хл „сей) =- (х, (а!, «!; у(О; ! . х-!) !пах !пах гп!п Рл(х„..., х„„ал) = «;(»1, хги «х,(ал 2, х!! ахе(а») а! ! Л вЂ” 2 !пах Р,(х„..., х, „сел !) =... (х! (хе, «2; !(22! Е<2-2) .
= Р, (с!',) -- ш !п Г, (сс,) = Р,. а, Но тогда из-за (192) Еп!и щах Р(х, у)( Евах Р(х, у„)=-Р,~ УЕЛ!» «ЕЛ!» «ЕМ ( щах пп! и Р (х, у). .«Е М» ЕЕ У» Отсюда в силу всегда верной леммы (160) получаем щах пппР(х, у) =ппп п2ах Р(х, у). хеМ» РЕЯ» ЕЕН» «ЕМ» Таким образом, верна довольно общая Те о рема ХХ111. Если антагонистическая игра определена во множестве 214, стратегий оперирующей стороны типа (182), рассчитанных на постепенную локализацию возможных у множествами й1!(ее!), и на множестве У.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
