Общая структура статистической модели

   Задачи статистического моделирования:

   1) построение объекта моделирования;

   2) формирование случайных взаимодействий;

   3) организация статистической обработки данных моделирования;

   4) задача планирования эксперимента.

Иными словами: применение метода Монте-Карло . Этот метод является численным методом статистических испытаний на ЭВМ и включает в себя следующие операции:

" выработка случайных значений параметров элементов в соответствии с их законами распределения вероятностей;

" анализ (Марковской) цепи (расчёт функции цепи для каждой случайной реализации значений параметров элементов, то есть для каждого испытания;

" обработка результатов статистических испытаний, то есть расчёт вероятностных характеристик функции цепи;

" оценка достоверности получаемых результатов, которая проводится, как правило, в процессе испытаний.

Исследование операций.

Цель и задачи изучения дисциплины. Объект, предмет и метод исследования . Методология исследования операций и практика. Исторический аспект развития теории исследования операций в трудах отечественных и зарубежных ученых.

Основные понятия и принципы исследования операций .

Процесс принятия решения, его участники и этапы. Исследование операций как комплексное научно-прикладное направление поддержки принятия решения. Принцип системности. Рациональный подход. Понятия операции , оперирующей стороны, активных средств проведения операции , действующих факторов операции , решения, альтернативных планов, цели, критерия эффективности. Классификация операций с позиций учета неопределенности действующих факторов. Примеры операций в экономических системах. Типы задач исследования операций .

Тема 2. Математическое моделирование - язык и инструментарий рационального исследования операций .

Понятия модели, моделирования. Виды моделей. Цели моделирования в науке. Особенности моделирования экономических явлений и процессов. Оптимизация как способ описания рационального поведения. Элементы оптимизационной модели. Основные этапы моделирования операции .

Раздел 2. Исследование операций в условиях определенности. Модели и методы математического программирования.

Тема 3. Программируемые проблемы в экономике.

Различные типы экономических проблем по степени их структуризации. Примеры программируемых проблем. Математическое программирование - аппарат решения оптимизационных задач. Допустимое множество. Множество оптимальных планов.

Исследование операций как наука. Источник формирования -оптимизация действий на войне.

Значительное развитие методов исследования операций имело место не только на основе группы, рассчитывавшей использование ВМС, но и за счет создания новых подразделений. Так, в США группа по исследованию операций ВМС превратилась в расширенную группу оценки операций (под руководством Джакинто Стейнхарда), работающую по контракту с Массачусетским технологическим институтом. ВВС США также расширили свои отделы исследования операций (под началом Ле-Рой А.Бразерса), а в 1948 г. командование сухопутными войсками США по контракту с университетом Джона Гопкинса сформировало управление по исследованию операций . В 1949 г. объединенный комитет начальников штабов создал группу оценки систем вооружения, первым техническим директором которой был назначен Филип М.Морз. В то же время в ВВС учредили Проект РЭНД при авиационной корпорации "Дуглас", а в 1949 г. это подразделение стало уже корпорацией РЭНД.

Следуя изложенным соображениям о философских аспектах науки, можно сказать, что в исследовании операций используется научный метод для изучения и объяснения явлений, связанных с функциональными системами, так как в рамках данной дисциплины изучается определенный круг явлений реальной действительности. Такие системы нередко включают людей и механизмы, которые действуют в условиях реального мира, причем слову "механизм" мы придаем достаточно общее значение, охватывающее все случаи - от механических устройств, обычно определяемых их названиями, до сложных социальных структур, функционирующих в соответствии с установленными правилами.

Научная дисциплина, называемая исследованием операций , наблюдает реальные явления, связанные с функциональными системами, разрабатывает теории (которые многие исследователи называют моделями), предназначенные для объяснения данных явлений, использует эти теории для описания того, что произойдет при изменении условий, и проверяет прогнозы новыми наблюдениями.

Таким образом, исследование операций - наука, так как эта дисциплина использует метод для получения соответствующих знаний и отличается от других наук предметом исследований. Она изучает явления, связанные с функциональными системами, в том аспекте, который почти не рассматривается другими науками.

Учитывая этапы реализации научного метода, для любой научной дисциплины можно ожидать систематических публикаций четырех категорий, в которых соответственно, приводятся результаты, получаемые при наблюдении явлений, и специальные способы проведения таких наблюдений; даются построения математических моделей; описывается применение этих моделей для составления прогноза на основе полученных результатов; проводится проверка прогнозов сравнения с результатами новых наблюдений.

Совокупность математических моделей исследования операций можно разбить на три группы.

К первой группе относятся детерминированные модели: линейное программирование, целочисленное программирование, теория графов, потоки в сетях, геометрическое программирование, нелинейное программирование, программирование для случая задач большой размерности, теория оптимального управления.

Ко второй группе относятся стохастические модели: случайные процессы, теория массового обслуживания, теория полезности, анализ управляющих решений, теория игр, теория поиска, имитационное моделирование и динамическое программирование.

Третью группы составляют наиболее важные модели, разработанные применительно к группам процессов, являющихся достаточно общими для многих областей применения методов исследования операций :

" прогнозирования;

" учета;

" финансовой деятельности и управления экономикой;

" сбыта и рекламы;

" управления трудовыми ресурсами;

" экономического анализа инвестиций;

" информационных систем для управления;

" вычислительных и информационных систем;

" выбора, планирования и управления разработкой проекта;

" управления запасами;

" составления календарных планов производства и последовательности работ;

" замены, ремонта и анализа надежности оборудования;

" размещения и загрузки производственных мощностей;

" планирования производства.

Наиболее хорошо развиты были методы исследования операций (1975) для следующих областей:

" военные проблемы,

" работа государственных органов,

" городские системы,

" здравоохранение,

" системы образования,

" транспорт,

" коммунальное обслуживание,

" отрасли промышленного производства

" технологические процессы.

Исследование операций (ИО) ( англ. Operations Research (OR)) - дисциплина, занимающаяся разработкой и применением методов нахождения оптимальных решений на основе математического моделирования, статистического моделирования и различных эвристических подходов в различных областях человеческой деятельности. Иногда используется обозначение математические методы исследования операций .

Характерной особенностью исследования операций есть системный подход

к поставленной проблеме и анализ. Системный подход является главным методологическим принципом исследования операций. Он заключается вот в чем.

Любая задача, которая решается, должна рассматриваться с точки зрения влияния на критерии функционирования системы в целом. Для исследования операций характерно то, что при решении каждой проблемы могут возникать новые задачи.

Важной особенностью исследования операций есть стремление найти оптимальное решение поставленной задачи (принцип "оптимальности").

Однако на практике такое решение найти невозможно по таким причинам:

1) отсутствие методов, дающих возможность найти глобально оптимальное решение

задачи;

2) ограниченность существующих ресурсов (к примеру, ограниченность

машинного времени ЭВМ), что делает невозможным реализацию точных методов

оптимизации. В таких случаях ограничиваются поиском не оптимальных, а

достаточно хороших, с точки зрения практики, решений. Приходится искать

компромисс между эффективностью решений и затрат на их поиск. Одна из

важнейших особенностей исследования операций - это то, что оно дает

инструмент для поиска таких компромиссов.

ИО тесно связано с наукой управления , системным анализом, математическим

программированием, теорией игр, теорией оптимальных решений, эвристическими подходами, теорией минимакса, теория сетевых графиков, теорией массового обслуживания, метаэвристическими подходами и методами искусственного интеллекта, такими как теория удовлетворения ограничений и нейронные сети.

Из истории ИО

ИО широко применялось для планирования боевых действий. Так, специалисты по исследованию операций работали в командовании бомбардировочной авиации США, дислоцированном в Великобритании. Ими исследовались многочисленные факторы, влияющие на эффективность бомбометания. Были выработаны рекомендации, приведшие к четырёхкратному повышению эффективности бомбометания.

Формализация процесса принятия решения состоит из следующих этапов: построение математической модели операции; анализ и выбор метода решения; определение критериев эффективности; количественная оценка альтернатив и определение оптимальных; принятие решения; оценка результатов. По сути это еще одно название прикладного математического программирования.

Лекция 7. Метод теории игр в принятии решений. Основные понятия теории игр.

___

Сущность теории игр и область ее применения; правила построения теоретико-игровых моделей; классификация таких моделей, математические методы, поиска оптимальных способов действий.

_____

Среди большого числа приложений кибернетики(теории управления) одним из наиболее важных является так называемое "исследование операций", сложившееся и оформившееся еще до 'появления ЭВМ и формирования основных понятий кибернетики. Исследование операций - прикладная наука, использующая математические методы и потому относящаяся к разряду точных наук. Предмет ее изучения – в первую очередь работа организованных коллективов людей. "Операцией" называется любая конкретная деятельность коллектива, руководимая единым замыслом и чаще всего из единого центра, протекающая при использовании оборудования, с точно определенной целью и имеющая, как правило, характер повторяемости. Производство, транспорт, связь, торговля, строительство, боевые действия -- все это суть "операции"

Интересно отметить некоторые особенности проведения работ по исследованию операций. Прежде всего, в исследовании конкретной операции всегда участвует коллектив ученых различных специальностей. В группу исследователей, как правило, включается математик, которому часто принадлежит ведущая роль, затем специалист в данной области: инженер, экономист, офицер, и, наконец, специалист побочной специальности, часто -- психолог или педагог, если исследование касается вопросов взаимоотношений в коллективе. Вся работа по проведению исследования как теоретическая, так и экспериментальная ведется группой совместно лишь с частичным разделением труда по специальностям.

Вторая интересная особенность состоит во взаимоотношениях группы исследования с руководителями самой операции: администрацией, армейским командованием и т.д. Группа исследования не вмешивается в руководство.

Исполнительная власть и ответственность сохраняется за руководством операцией(ЛПР-лицами принимающими решения). Группа исследования получает всю имеющуюся информацию о цели, средствах и ходе операции, на основании которой и решается задача о наилучшем управлении; результат исследования и полученные рекомендации в кратком и понятном изложении доводятся до сведения руководителей, которые одни только уполномочены принять решение об их использовании.

При исследовании операций, как правило, применяются точные методы исследований. Факторы, не поддающиеся точному выражению в числах, но существенные для операции, часто также оцениваются численно, хотя бы приближенно. Основой изучения операций является алгоритмизация изучаемых процессов, построение абстрактных математических моделей операции,-метод, типичный для кибернетики.

При исследовании операции, в зависимости от характера изучаемого явления, применяются многие разделы математики: анализ, теория вероятностей и математическая статистика, математическая логика, численные методы. В ходе развития постепенно сложились характерные типы задач. Одновременно появились и развились специальные математические приемы и методы решения типичных задач. К числу таких методов относятся, например, линейное программирование, динамическое программирование, теория массового обслуживания, теория статистических решений и, наконец, математическая теория игр.

..

Теория игр изучает абстрактную модель конфликтной ситуации, т.е. ситуации, в которой участвуют по крайней мере две стороны, представляемые лицами, коллективами или управляющими системами, деятельность которых целеустремленно направлена, причем интересы сторон оказываются частично или полностью противоположными. Обилие таких ситуаций в реальной действительности делает теорию игр весьма актуальной. Не будет преувеличением сказать, что теория игр является математической основой военного искусства.

Но, кроме военных, имеется много других операций, в которых отдельные виды деятельности, отдельные части коллектива имеют различные цели, что часто приводит к типично конфликтным ситуациям. Раздел теории игр, рассматривающий "игры с природой", непосредственно смыкается с теорией статистических решений и математической статистикой. Этот раздел теории имеет дело с выработкой наилучшего поведения в ситуации, когда человеку противостоит обстановка, известная ему лишь отчасти, изучаемая им и требующая от него некоторой реакции. Теория игр, таким образом, имеет дело со всякого рода борьбой интересов.

Весьма существенно то, что задачи, имеющие дело с конфликтными ситуациями, не могут быть полноценно решены без математической теории игр. Подобно тому как задачи о случайных событиях не могут решаться методами только классического анализа и находят решение лишь с помощью нового математического аппарата -- теории вероятностей и математической статистики, так и конфликтные ситуации для своего моделирования не могут обойтись только теорией вероятностей и требуют новой математической дисциплины -- теории игр.

..Попытки решать игровые задачи неигровыми методами приводят к принципиальным затруднениям, к необходимости вводить гипотезы о том, "какое из возможных решений примет противник", или о том, "каково будет распределение вероятностей над множеством его возможных решений". При этом приходится намеренно закрывать глаза на то, что противник представляет собой разумное существо (или в некоторых случаях -- сложный автомат, изготовленный разумным существом), а не детерминированный простой механизм и не случайный процесс и, таким образом, однозначное решение противника или распределение вероятностей могут просто не существовать. Распределение вероятностей существует в том случае, когда противник пользуется некоторым случайным механизмом (бросанием жребия) для определения своих действий. Но в таком случае характеристики этого случайного механизма описываются именно в рамках теории игр как "смешанная стратегия".

Теория игр в ее современном состоянии не является еще законченной теорией. Ценность ее сегодня заключается главным образом "в отчетливой формулировке основных, принципиальных особенностей конфликтной ситуации, и это чрезвычайно важно для правильного подхода к задачам. Что же касается конструктивных методов решения игровых задач, то арсенал математической теории игр не может похвастать их обилием. Хорошо разработаны методы решения только одного типа игр, а именно конечных дискретных парных игр с нулевой суммой платы. Но даже для игр этого типа решение сколько-нибудь сложных игровых задач требует очень большой вычислительной работы. А в ряде задач (например, в непрерывных играх) общие методы решения еще мало разработаны

..

Основными в решении дискретных игр в нормальной форме являются методы линейного программирования.

..

Хотя практические методы решения игр и оставляют желать дальнейших усовершенствований, основные положения теории игр вполне строги, и знание их абсолютно необходимо для правильного подхода к формулировке и анализу конфликтных ситуаций.

Весьма важно и то, что теория игр четко ставит вопрос о критериях оценки качества, формулированного в пределах этой теории в виде "функции платы". Нужно сказать, что вопрос об определении или назначении платы в данной игре лежит вне теории игр, использующей плату как числовую меру успеха операции. То же можно сказать и о четком определении ограничений, наложенных на возможные действия участников операции. Правила игры однозначно определяют ограничения в виде "возможных ходов". Сама необходимость сформулировать правила игры и назначить плату заставляет исследователя задать себе целый ряд весьма существенных вопросов, выясняющих сущность задачи.

Во всей сумме проблем исследования операций вообще и в вопросах теории игр в частности должны правильно ориентироваться и руководители операций: администраторы, хозяйственные руководители, работники вооруженных сил и инженеры-разработчики оборудования и вооружения. Оценка пользы, приносимой данной операцией, оценка эффективности использования оборудования или вооружения, полезности тех или иных организационных мероприятий, определение наилучшего образа действия в данной ситуации -- все это является предметом изучения исследования операций и теории игр и представляет первостепенный интерес для работников промышленности и техники.

Основные понятия теории игр

В ситуациях, называемых конфликтными, предугадать исход и тем более определить действия, при которых этот исход оказался бы наиболее благоприятным, оказывается сложно. В простейшем случае сторон 2, их выигрыши и проигрыши агрегированы в числовой форме. Предположим, что сторона обладает способами действий, на каждой из которых сторонаможет ответить одним из способов. Пусть результат взаимных действийхарактеризуется критерием эффективности, который представляет собой выигрыш стороны. Тогда конфликтную ситуацию можно представить в виде матрицы эффективности (рис. 8.a.).

 

Рис. 8.a. 

 

 

Из рисунка 8.a. видно, что если сторона выбирает способ , то исход конфликта, характеризуемый критерием эффективности, будет целиком зависеть от выбора способа действий стороной. Аналогичный вывод можно сделать в отношении любого другого способа действий стороны. В этих условиях естественным подходом к выбору оптимального способа является сравнение между собой всех способов действия стороныпри условии выбора сторонойкаждого из способов.

 

Например, сравнивая способ со способом, можно в частном случае установить, что способобеспечивает достижение лучшего результата, если каждый элемент его строки больше соответствующего элемента (по столбцам) строки способа. Если путем подобного сравнения найдется такой способ, каждый элемент строки которого больше соответствующего элемента (по столбцам) любой другой строки, то целесообразно применить способ. В остальных случаях выбор способа сторонойможет быть осуществлен только для определенной гипотезы о действиях стороны.

 

Другой естественный подход состоит в определении математического ожидания величины критерия эффективности для -го способа действия стороныпо формуле

 

 

где — математическое ожидание величины критерия эффективности при выборе способа действия;

 

— вероятность выбора сторонойспособа действия.

 

Тогда способы действия стороны можно сравнить по величинеи выбрать тот, при которомбудет максимальным. При этом как в первом, так и во втором случае для обоснования решения достаточно использовать методы оптимизации.

 

Таким образом, для применения в условиях конфликтной ситуации обычных методов оптимизации необходимо задаться или гипотезой о действиях противника, или законом распределения их вероятностей. Однако для конфликтных ситуаций как раз характерным является то, что отдать предпочтение какой-либо гипотезе не представляется возможным, а методов определения законов распределения вероятности выбора противником своих способов действий просто не существует.

 

В связи с этим возникает необходимость в теории специфического класса математических моделей принятия оптимальных решений. Такой теорией является теория игр.

 

Теорию игр можно рассматривать, с одной стороны, как раздел математического программирования а с другой — как его уровень. В качестве раздела исследования операций теория игр представляет теорию математических моделей принятия оптимальных решений в конфликтных ситуациях. Как уровень исследования операций теория игр является теорией математических моделей принятия решений в условиях неопределенности. Однако не следует полагать, будто теория игр занимается вопросами принятия решений при полном неведении об обстановке. Известные элементы обстановки определяют множество способов действий сторон и значения критерия эффективности как функции, заданной на этом множестве. Неизвестные элементы обуславливают отсутствие любой, даже вероятностной информации о возможных реализациях того или иного способа действий противника. Таким образом, любую неопределенность можно расчленить на известную и неизвестную части, построить теоретико-игровую модель, на основании которой определяется оптимальное решение.

 

Для применения теории игр нужна схематизация конфликтной ситуации и представление ее в виде игры, игроки, имеют различные цели и располагают различными путями для их достижения. Причем обязательным является то, что достижение одним игрокам своей цели находится в непосредственной зависимости от выбора способа действий другим игроком. Более того, отличительная особенность игры по сравнению с реальной конфликтной ситуацией состоит в том, что первая ведется по заранее определенным правилам. В этом и заключается основное ограничение в применении теории игр. Ведь если теоретико-игровой подход, безусловно, правомерен в любой игре, то не всегда можно построить соответствующую математическую модель для конкретных условий обстановки.

 

Основное значение теории игр состоит в том, что она дает ориентацию тогда, когда применение другого математического аппарата сложно из-за отсутствия необходимой информации о действиях противника, а времени и, самое главное, других эффективных способов нет.

 

Применение теории игр для обоснования оптимального решения требует представления конфликтной ситуации в виде некоторой игры, которая по своему содержанию и форме является ее математической моделью.

 

Для построения модели конфликтной ситуации прежде всего должны быть сформулированы правила игры, то есть система условий, которая определяет возможные варианты действий игроков, последовательность ходов, объем информации каждого игрока о поведении другого и о функции выигрыша.

 Возможные варианты способов действий вытекают непосредственно из анализа конфликтной ситуации.

Выбор одного из возможных вариантов в процессе игры называется ходом.

Заранее определенная последовательность ходов в зависимости от информации о ходах противника и о случайно изменяющихся параметрах, законы распределения которых считаются заданными, называется стратегией игрока. Каждая стратегия предопределяет поведение игрока во все моменты игры, когда он должен делать выбор одного из всевозможных способов действий. Она может быть очень плохой или очень хорошей, но для анализа игры существенно описать все возможные планы или стратегии каждого игрока.

Совокупность сделанных игроками ходов в соответствии с выбранными ими стратегиями определяет ситуацию игры, которая является моделью складывающейся обстановки в результате конкретных действий, предпринятых противоположными сторонами. Ситуация, на основании которой определяется исход игры, называется заключительной.

 

Каждой заключительной ситуации всегда соответствует определенное значение критерия эффективности. Правило, по которому каждой заключительной ситуации ставится в соответствии величина критерия эффективности, называется функцией выигрыша. Это название обусловлено тем, что каждое ее значение можно представить как выигрыш, получаемый игроком в зависимости от сделанных ходов. На величину выигрыша оказывают влияние не только действия игроков, но и факторы, которые не находятся под их управлением. К таким факторам относятся эффективность, или стоимость имеющихся в распоряжении игроков сил и средств, их количество, гидролого-метеорологические условия и так далее. Поэтому при описании функции выигрыша учитываются не только возможные способы действий игроков, но и факторы, независимые от игроков. Однако по своей сущности функция выигрыша представляет выигрыш каждого игрока только как функцию стратегий, применяемых игроками. В этом смысле выигрыш является связующим звеном между множеством стратегий одного игрока и множеством стратегий другого; функция же выигрыша указывает, сколько один игрок может выиграть у другого, если первый выбирает конкретную какую-либо стратегию из множества стратегий, а другой игрок выбирает какую-либо стратегию из своего множества. Стоит отметить , что полностью справедливо это для игр с нулевой суммой.

 

Таким образом, выигрыш – это оценка ожидаемых результатов всех возможных сочетаний стратегий одного игрока со стратегиями другого. Для получения таких оценок могут применяться методы теории вероятностей, теории массового обслуживания, теории управления запасами, теории поиска и различные экономические показатели. Следовательно, теория игр исходит из заранее определенных значений того или иного критерия эффективности для конкретного сочетания стратегий обоих игроков, функция выигрыша задана.

 

Теоретико-игровые модели боевых действий классифицируются в зависимости от числа последовательных ходов и возможных способов действий игроков, характера и объема информации, доступной каждому игроку относительно действий другого, а также отношения каждого из игроков к значению функции выигрыша.

 

В зависимости от числа возможных способов действий игры подразделяются на конечные и бесконечные. Конечной называется игра, в которой у каждого игрока имеется конечное число возможных способов действий. В бесконечной игре по крайней мере один из игроков имеет бесконечное множество возможных способов действий.

 

Число последовательных ходов у любого из игроков определяет подразделение игр на одноходовые и многоходовые, или позиционные. В одноходовой игре каждый игрок делает только один выбор из возможных вариантов и после этого устанавливает исход игры.

 

Многоходовая, или позиционная, игра развивается во времени, представляя собой ряд последовательных этапов, каждый из которых наступает после хода одного из игроков и соответствующего изменения обстановки.

 

Многоходовые игры в зависимости от характера и объема информации каждого игрока о сделанных ходах противником подразделяются на два класса: игры с полной информацией и игры с неполной информацией. В играх с полной информацией каждый игрок на каждом этапе знает результаты всех предыдущих ходов. В зависимости от отношения каждого из игроков к значению функции выигрыша игры подразделяются на антагонистические и неантагонистические. В антагонистических играх интересы ее участников прямо противоположны. Это означает, что сколько один игрок выиграл, то столько же другой проиграл. В этих условиях каждый игрок стремится обеспечить себе максимальный выигрыш, а противнику максимальный проигрыш. Это приводит к тому, что выигрыш одного игрока соответствует проигрышу другого, Поэтому можно считать, что суммарный выигрыш обоих игроков антагонистической игры во всех ситуациях равен нулю. Отсюда эти игры иногда называют играми с нулевой суммой или нулевыми играми.

 

В неантагонистических играх игроки преследуют разные, но не прямо противоположные цели. Отсутствие антагонизма в смысле "равенства значений функций выигрыша по величине и противоположности по знаку" приводит к одному из классов неантагонистических игр, называемому биматричными играми.

Квазиматричные игры относятся к некоторому специальному классу позиционных антагонистических игр двух лиц со случайным ходом.

Игроками I и II, как и в матричных играх, являются противники, преследующие прямо противоположные цели и имеющие конечное число возможных вариантов действий. Случайный ход делает "природа", которая, не преследуя какой-либо цели (в силу объективных факторов, независимых от воли игроков), выбирает из конечного множества одну альтернативу. Такой выбор представляет собой случайный ход. Наличие "природы" как третьего игрока приводит теоретико-игровую задачу к классу позиционных игр, так как в этом случае число последовательных ходов будет всегда более двух. При этом если оба игрока не знают, какой ход сделает "природа", то такая игра в нормальной форме является матричной игрой. Однако анализ конфликтных ситуаций, моделью которых является конечные игры, показывает, что в целом ряде случаев стороны имеют различную информацию о ходах "природы". Так, например, I может знать, а игрок II — не знать, какой ход сделает "природа". Такие игры называются квазиматричными.

(вероятно следует вставить пример про Верду и Калимну)

 

Одноходовая конечная антагонистическая игра является теоретико-игровой моделью конфликтной ситуации, в которой противники для достижения диаметрально противоположных целей делают по одному выбору (ходу) из конечного числа возможных способов действий. В соответствии с выбранными способами действий (стратегиями) определяется достигаемый результат. Функция выигрыша в такой игре задается матрицей. (табл. 8.b).

 

Рис. 8.b. 

 

 

В этой матрице строки всегда для стратегий максимизирующего игрока, то есть игрока, который стремится к максимизации (игрок I).

 

Столбцы отводятся для стратегий игрока, который стремится к минимизации (игрок II). Клетки матрицы, стоящие на пересечении строк и столбцов, представляют результаты заключительных ситуаций и заполняются числами — значениями критерия эффективности, характеризующего выигрыш игрока I и соответственно проигрыш игрока II.

 

Обычно матрицу, имеющую строк истолбцов, называютматрицей и обозначают. Соответственно игру называют (игрой.

 

Позиционная (многоходовая) игра является теоретико-игровой моделью конфликтной ситуации, в которой противники для достижения своих целей последовательно делают по одному выбору (ходу) из конечного числа возможных способов действий на каждом этапе развития этой ситуации.

 

Процесс сведения (позиционной) игры к игре, описываемой матрицей, называется нормализацией, а получающаяся игра – игрой в нормальной форме. Действительно, в этой игре значения функции выигрыша можно всегда записать в виде прямоугольной таблицы (матрицы), строки которой соответствуют стратегиям игрока I, а столбцы – стратегиям игрока II.

Игра двух лиц с нулевой суммой в матричной форме занимает центральное место в современной теории игр, так как теория таких игр разработана практически до конца.

Итак, пусть имеется два игрока. В распоряжении первого игрока имеется всего n возможных ходов i=1,2,3,...,n; в распоряжении второго игрока имеется m возможных ходов j=1,2,3,...,n. Эти возможные ходы называютсячистыми стратегиями игроков.

Оба игрока делают одновременно по одному ходу, после чего игра считается законченной. Если первый игрок делает ход i, а второй - ход j,

то первый игрок получает выигрыш, равный.Очевидно, что выигрыш второго игрока равен. Эти данные можно записать в виде матрицы

,

в которой строки соответствуют ходу первого игрока, а столбцы ходу второго игрока. Эта матрица носит названиеплатёжной матрицы игры.

Как же должны действовать игроки в такой ситуации? Какие ходы они должны делать?

(далее на лекции приводится пример военной задачи о Верде и Калимне из Кванта)

Лекция 8.Оптимальные стратегии теории игр.

Игры с седловой точкой

Рассмотрим с этих позиций игру со следующей платёжной матрицей

.

Попробуем порассуждать с точки зрения первого игрока. Если он сделает ход i=1, то наихудшей для него будет ситуация, когда второй игрок сделает ходj=3, так как в этом случае он получит 0. Если первый игрок сделает ход i=2, то в наихудшем случае (при ходе второго игрокаj=1) он также получит 0. Аналогично, при i=3 он в наихудшем случае получит 4 (при j=2), при i=4- 2 (приj=3 ) и, наконец, при i=5 он в наихудшемслучае получит 0 (при j=3).

Стремясь сделать свой гарантированный выигрыш как можно больше, первый игрок должен выбрать ход i=3, так как в этом случае он гарантирует себе выигрыш, равный 4 (правда, и его максимальный выигрыш невелик - всего 5).

А теперь попробуем посмотреть на эту же матрицу с точки зрения второго игрока. Для него это - матрица егопроигрыша.

Если он выберет ход j=1, то его максимальный проигрыш будет равен 18 (если первый игрок сделает ход i=1). Аналогично, при j=2 его максимальный проигрыш будет равен 4, при j=3- 8, и, наконец, при j=4 его максимальный проигрыш будет равен 25. Стремясь сделать свой максимальный проигрыш как можно меньше, второй игрок должен выбрать ход j=2, так как в этом случае его максимальный проигрыш, равный 4, самый маленький.

Итак, мы пришли к выводу, что первый игрок должен ходить i=3, а второй j=2. Допустим теперь, что второй игрок, как говорят, “открывает карты” и заявляет первому игроку: “Я буду делать ход j=2”. Есть ли первому игроку необходимость менять свой ход? Нет, так как в этом случае его наилучший ход всё равно i=3.

Аналогично, если первый игрок заявит второму, что он будет ходить i=3, то второму игроку также нет смысла менять свой ход, так как наилучшим ответом будет всё равно j=2. Пара i=3, j=2 является, как говорят,уравновешенной парой, так как “открытие карт” игроками не даёт поводов противнику менять свою стратегию. Как говорят, пара i=3, j=2 естьрешение игры, а величина выигрыша при этом первого игрока (и одновременно величина проигрыша второго) - 4 - этоцена игры.

Оформим всё это математически. Итак, пусть первый игрок выбирает ход i. В наихудшей для него ситуации он выиграет

.

Стремясь сделать свой минимальный выигрыш максимальным, он выбирает свой ход из условия

.

Такая стратегия называется максиминной.

Аналогично, второй игрок, выбирая ход j, в наихудшей для себя ситуации проигрывает

.

Стремясь сделать свой максимальный проигрыш минимальным, он должен выбирать свой ход из условия

.

Такая стратегия называется минимаксной.

Каково же соотношение между и?

Теорема 1.Пусть имеются два числовых множестваи ;есть вещественная функция двух переменных прии. Тогда

,еслиисуществуют.

Доказательство

По определению минимума, имеем

.

Аналогично, по определению максимума,

.

Следовательно

.

Но заметим, что правая часть этого неравенства не зависит от x. Поэтому

.

Аналогично, левая часть не зависит от y. Поэтому

,

что и требовалось доказать.

Замечание.Возможность применения этой теоремы к нашей ситуации основана на том, что платёжную матрицуможно рассматривать как функцию двух переменных, гдеи. Поэтому

.

Обратите внимание на самую существенную деталь - меньше или равен . У нас же получилось, чтоиодинаковы и равны 4. Оказывается, именно в этом равенстве всё дело, именно это равенство обеспечивает и существование уравновешенной пары и цены игры. Дадим соответствующие определения и теоремы.

Определение.Пустьесть действительная функция, определённая

для всех .Точка,гденазывается седловойточкой функции ,<если выполнены следующие условия:

1. ;2..

Теорема 2. Пусть- действительная функция, определённая для всехи существуети. Тогда для того, чтобы

необходимо и достаточно, чтобы имела седловую точку.

Кроме того,если есть седловая точка функции,то

.

Доказательство

Достаточность.

Пусть есть седловая точка функции.

,

откуда следует, что

.

Аналогично,

,

откуда следует, что

.

Сводя всё вместе, получаем

.

Но так как

,

,

то отсюда следует, что

.

Сравнивая это с результатом теоремы 1, где было доказано обратное неравенство, получаем, что

.

Необходимость.

Пусть .

Пусть - это тот элемент множества, при которомпринимает своё максимальное значение, то есть

.

Аналогично, пусть - это тот элемент множества, при которомпринимает своё минимальное значение, то есть

.

Покажем, что <- седловая точка функции . В силупредположения о том, что, имеем

.(1)

По определению минимума, имеем

,

и поэтому из (1) следует, что

.

Отсюда следует, что

.(2)

Аналогично, по определению максимума,

,

и поэтому из (1) следует, что

.

Отсюда следует, что

.(3)

Объединяя вместе (2) и (3), получаем

,

что соответствует тому, что седловая точка функции.

Замечание.На основании интерпретации матрицы как функции двух переменныхотсюда следует, что седловая точкаплатёжной матрицыопределяется условием

,

то есть седловая точка матрицы есть элемент, который минимален в своей строке (), но максимален в своём столбце (). Это позволяет легко находить седловые точки матрицы.

Обратите внимание, что в том примере, с которого мы начинали наш раздел, точка была именно седловой точкой. Элемент платёжной матрицыхарактеризовался именно тем свойством, что он был максимальным в своём столбце и минимальным в своей строке.

Ответим еще на некоторые вопросы, касающиеся седловых точек.

Может ли у матрицы быть несколько седловых точек?

Ответ положительный - да, может. Так, в матрице

две седловых точки (i=1, j=1) и (i=1, j=3).

 

 Если седловых точек несколько, то не возникает ли каких-то противоречий между ними?

Ответ отрицательный. Более того, если () и () две седловые точки , то () и () тоже седловые точки и.

Докажем это для произвольной функции . Пустьидве седловые точки этой функции. Тогдаимеем

,

,

и мы имеем следующую цепочку

,

откуда следует, что на самом деле

.

Отсюда же следует, например, что

,

то есть также седловая точка.

 Все ли матрицы имеют седловую точку? Ответ отрицательный. У матрицы седловых точек нет.

..

Смешанные стратегии

Седловая точка в матричных играхвсё-таки скорее исключение, чем правило. А что же может гарантировать себе игрок, если седловой точки нет?

Давайте снова рассмотрим игру с платёжной матрицей

.

Здесь ,и междуиобразуется “дыра”Как можно её заполнить и чем?

Представим себя в позиции первого игрока. Он имеет гарантированный выигрыш (скорее, проигрыш), равный (-1). Как он может его повысить?

Конечно, если игра повторяется много раз, то он может изучить своего партнёра, придумывать всякие схемы игры и т.д. и т.п., но вряд ли это даст какие-то гарантии, если число партий невелико. Тут никакие схемы не помогут.

В такой ситуации единственный выход - выбирать свой ход случайным образом. Например, взять и подбросить монету. Упадёт она кверху орлом - делать ход i=1, выпадет решка - делать ход i=2. Что же это даст?

Выигрыш станет случайной величиной и оценивать его надо по математическому ожиданию. Пусть второй игрок делает ход j=1. Тогда математическое ожидание выигрыша первого игрока будет

.

Если второй игрок делает ход j=2, то математическое ожидание выигрыша первого игрока равно

.

Таким образом, выбирая свой ход случайно, первый игрок гарантирует себе (правда, в среднем, а не в каждой партии), выигрыш, равный нулю. А это всё-таки лучше, чем гарантированный выигрыш, равный (-1) .

Аналогично, второй игрок, бросая монету и выбирая ход в соответствии с её “указанием”, гарантирует себе в среднем проигрыш, равный 0. Это тоже лучше, чем проигрыш, равный 1.

Таким образом, оказывается, что случайный выбор хода повышает наши шансы на успех, хотя бы в среднем. И это является одной из основных идей теории игр. Подобный случайный выбор хода получил название смешанной стратегии. Конечно, вероятностный выбор хода не всегда приемлем.

Нахождение смешанной стратегии

Цена игры

Оформим теперь всё сказанное выше математически. Рассмотрим сначала ситуацию, когда все . Это гарантирует нам, что выигрыш первого игрока (и, соответственно, проигрыш второго) всегда будет положительным.

Пусть в распоряжении первого игрока имеется ходови он выбирает их случайным образом, так что ход номерделается с вероятностью. Набор чисели называется смешанной стратегией первого игрока. Так каквероятности, то

Пусть есть гарантированный средний выигрыш первого игрока. Но что значит гарантированный? Это означает, что при любом ходе второго игрока первый игрок получит в среднем не меньше, чем. Математически это означает, что

(4)

Заметим, что . Перейдём от величинк величинам. Тогда, деля все уравнения на, получим систему неравенств

Но у нас есть еще условие нормировки . Переходя к, запишем его в виде

.

В чем же заключается задача выбора оптимальной смешанной стратегии? Она заключается в том, чтобы так выбрать числа , чтобы гарантированный средний выигрышбыл максимальным. Но тогдабудет минимальным и задача приобретает вид

(5)

Это  типичная задача линейного программирования. Решая её, мы найдёми, откуда затем найдём и. Заметим, что дляможно написать и другую формулу

.

Встанем теперь на точку зрения второго игрока. Он ведь тоже может применить смешанную стратегию, выбирая свои ходы случайным образом с

вероятностями ,

для которых тоже верно

.

Он тоже имеет некоторый максимальный средний проигрыш ; слово “максимальный” означает, что при любом ходе первого игрока он не должен

проиграть в среднем больше, чем .Математически это означает, что

(6)

Заметим, что . Перейдём от величинк величинам.

Тогда,деля все уравнения (6) на , получим систему неравенств

Условие нормировки примет теперь вид.

Задача выбора оптимальной смешанной стратегии вторым игроком заключается, очевидно, в том, чтобы выбрать так, чтобыбыло минимальным. Это приводит к задаче

(7)

Это также стандартная задача линейного программирования. Решая её, мы найдём и, откуда легко найти и интересующие нас величины:

.

Тем самым определяется и оптимальная смешанная стратегия второго игрока.

А теперь обратите внимание на самый важный момент в этих рассуждениях. Задачи (5) и (7) являются парой двойственных задач линейного программирования! Но тогда, в силу первой теоремы двойственности, экстремальные значения линейных форм этих задач должны быть равны, то есть при оптимальных смешанных стратегиях обеих игроков должно выполняться соотношение,или.

Это общее значение иназывается ценой игры. Системы (5) и (7) позволяют, таким образом, найти оптимальные смешанные стратегии обеих игроков и цену игры, то есть они позволяют решить игру.

Обратите внимание на то, какую задачу мы решили. От смешанных стратегий средний выигрыш первого игрока (и, соответственно, средний проигрыш второго) будет равен

,

где и. Находя, мы решали задачу

,

то есть задачу нахождения

.

Находя мы решали задачу

,

то есть задачу нахождения

.

У нас получилось, что , то есть, чтоисовпадают! Это позволяет говорить о том, что в смешанных стратегиях всякая игра двух лиц с нулевой суммой имеетседловую точку. Это положение является основной теоремой, касающейся игр двух лиц с нулевой суммой.

Как и всякая седловая точка, пара стратегий иявляетсяуравновешенной парой. Это означает, что если противник знает, что я применяю стратегию, соответствующую седловой точке, то ему нет смысла менять свою смешанную стратегию - смена стратегии ничего не даст.

Отметим, что делать, если не выполняется условие . В этом случае следует перейти к игре с платёжной матрицей

(8)

где - произвольное положительное число. Для новой игры стратегии игроков останутся теми же, то есть мы найдёми. Что касается цены новой игры, то она связана с ценойстарой игры тем же соотношением, что и (8)

,

то есть

,

что и решает исходную задачу.

Геометрическое решение игры

В случае, когда число чистых стратегийодного из игроков (скажем, первого) равно двум, возможногеометрическое решение игры, то есть нахождение её цены исмешанных стратегийкаждого игрока.

Рассмотрим идею этого решения на случае n=m=2, когда платёжная матрица имеет вид

.

Пусть первый игрок применяет смешанную стратегию с .Тогда, так как должно быть.

 

Рассмотрим прямоугольную систему координат, где по оси абсцисс откладывается величина p (она занимает отрезок ), а по оси ординат - величина среднего выигрыша первого игрока.

Пусть второй игрок выбирает ход j=1. Тогда средний выигрыш первого игрока будет равен

,

что является отрезком прямой, соединяющей точки и. Если второй игрок выбирает ход j=2, то средний выигрыш первого игрока будет равен

,

что является отрезком прямой, соединяющей точки и.

Минимальный выигрыш первого игрока представляет собой минимальное значение из ординат этих двух прямых и на рисунке он изображен жирной линией. Из рисунка видно, что максимальное значение этого минимального выигрыша определяется точкой пересечения этих двух отрезков

и оптимальная смешанная стратегия первого игрока есть .

Аналогично, максимальный проигрыш второго игрока определяется максимальным значением из ординат этих двух прямых и на рисунке он изображен штриховой линией. Легко видеть, что минимальное значение этого максимального проигрыша также равно . Смешанная стратегия второго игрока есть, гденаходится из того условия, чтобы при любом ходе первого игрока проигрыш второго был бы равен одной и той же величине

и равен также .

Таким образом, мы нашли и цену игрыи оптимальные смешанные стратегии каждого игрока.

На рисунке приведен лишь самый интересный и стандартный случай. Возможны и другие варианты, два из который приведены ниже.

В варианте, приведенном на рис. 2, оптимальной для первого игрока является чистая стратегия с p=1, то есть первый игрок всегда должен выбирать первый ход; для второго игрока оптимальным является выбор второго хода, то есть i=1, j=2 является седловой точкой платёжной матрицы.

В ситуации, приведённой на рис. 3, есть целый отрезок оптимальных значений -, то есть оптимальная смешанная стратегия неоднозначна.

Эта методика легко переносится на случай, когда n=2, а m>2. Тогда платёжная матрица имеет вид

и мы должны нарисовать m отрезков прямых

,

соединяющих точки и. Затем нужно построить ломаную линию, соответствующую минимальному значению ординат всех этих отрезков. Максимальное значение этой ломаной и даст значение цены игры. Оптимальное значение p определится как точка пересечения тех прямых, которая даёт значение.

Рассмотрим это на примере. Пусть платёжная матрица имеет вид

.

Тогда мы должны построить три отрезка прямых

Они изображены на рис. 4, где также жирной линией

выделен минимальный выигрыш первого игрока.

Легко видеть, что максимальное значение этого минимального выигрыша определяется пересечением прямых, соответствующих j=2 и j=3, то есть определяется из условия

,

откуда следует, что , так что оптимальная смешанная стратегия

первого игрока есть .

Цена игры

.

Что касается второго игрока, то в образовании цены игры участвуют только j=2 и j=3. Поэтому ход j=1 он вообще не должен делать; считая, что ,, получим

,

то есть как при первом, так и при втором ходе первого игрока проигрыш второго должен быть равен . Отсюда получаем, что, то есть оптимальная смешанная стратегия второго игрока есть.

Игры двух лиц с ненулевой суммой

Рассмотрим теперь основные идеи, касающиеся игр двух лиц с ненулевой суммой. В этом случае игра задаётся двумя матрицами, которые обычно объединяют в одну и пишут в виде

Здесь - выигрыш первого игрока и- выигрыш второго, если первый игрок делает ход i, а второй - j. Однако в данном случае

В такой ситуации появляется принципиально новый момент, которого не было раньше - возможность сговора, совместных действий игроков. Когда, то интересы обоих игроков прямо противоположны ивозможность сговора исключена в силу противоположности интересов. Если, то интересы игроков могут хотя бы частично совпадать, что и определяет возможность хотя бы частичного сотрудничества между ними.

Игры двух лиц с ненулевой суммой принято разбивать на два класса - некооперативные и кооперативные. В некооперативных играх игроки не имеют возможности общаться друг с другом.

игра двух лиц

Пусть задана игра двух лиц с матрицей

.

В теории рассматриваются в основном две стратегии поведения игроков - это максиминная стратегия и так называемая стратегия угрозы.

Максиминная стратегия - это стратегия крайне осторожного человека, который, рассчитывая на наихудшую ситуацию, хотел бы иметь в этом случае максимум возможного.

Рассмотрим все стратегии с позиций первого игрока. Пусть он применяет смешанную стратегию , гдеиОбозначим его средний гарантированный выигрыш через. Тогда для среднего выигрыша первого игрока должно выполняться условие

.

Считая все ( как этого можно добиться говорилось выше), перейдём к величинам. Тогда имеем

,

.

Стремление добиться максимального выигрыша в наихудшей ситуации приводит к требованию

,

что приводит нас к следующей задаче линейного программирования

Решение этой задачи и определяет максиминную стратегиюпервого игрока, так как

,.

Вторая стратегия - это так называемая стратегия угрозы или минимаксная стратегия. При её использовании игрок ставит своей задачей не выиграть самому, а “наказать” второго игрока, действуя по принципу: “пусть у меня две коровы сдохнут, лишь бы у соседа корова сдохла”.

Встанем снова на позицию первого игрока. Пусть он снова применяет смешанную стратегию . Но, применяя её, он считает не свой выигрыш, а выигрыш второго игрока. Если второй игрок делает ход j, то его средний выигрыш составит величину

.

Первый игрок действует по принципу

,

то есть он минимизирует максимальный выигрыш второго игрока.

Если обозначить максимальный выигрыш второго игрока через , то мы имеем

.

Считая все , что даёт, введём величины. Тогда получим

,

и желание минимизировать приводит нас снова к задаче линейного программирования

Решая эту задачу и находя , мы найдём ии смешанную стратегию первого игрока

Рассмотрим подробнее случай n=m=2. Тогда платёжная матрица игры имеет вид

.

Найдём геометрически максиминную стратегию и стратегию угрозы первого игрока.

Начнём с максиминной стратегии. Пусть первый игрок выбирает ход i=1 с

вероятностью .Тогда.Если второй игрок делает ход j=1, то средний выигрыш первого игрока будет равен,что даёт отрезок прямой, соединяющий точкии.

Если второй игрок делает ход j=2, то средний выигрыш первого игрока будет равен , что даёт отрезок, соединяющий точкии. Минимум из этих двух выигрышей на рисунке нарисован жирной линией, из которой ясно, как определяется гарантированный выигрыш

первого игрока и оптимальное значение :

.

Чему равен ив других случаях расположения этих двух прямых сообразите сами.

Теперь рассмотрим стратегию угрозы первого игрока. Пусть он снова применяет смешанную стратегию . Если второй игрок делает ход j=1, то средний выигрыш второго игрока будет равен, что даёт отрезок прямой, соединяющий точкии. Если второй игрок делает ход j=2, то его средний выигрыш будет равен.

Напомним, что первый игрок считает сейчас не свой выигрыш, а выигрыш второго игрока. Его задача - минимизировать его максимальный выигрыш. Максимальный выигрыш второго игрока изображен на рис. 6 жирной

линией; из рисунка же ясно, как находятся и:

.

Проиллюстрируем эти понятия на примере игры, которая имеет платёжную матрицу

и которая получила название “семейный спор”. Название возникло из-за следующей её интерпретации. Муж (игрок 1) и жена (игрок 2) могут выбирать одно из двух вечерних развлечений - футбол (i=1, j=1) или театр (i=2, j=2). Согласно обычному стандарту, мужчина предпочитает футбол, а женщина - театр. Однако им гораздо важнее идти вместе, чем смотреть своё предпочтительное зрелище. И если они поругаются и пойдут в разные стороны (i=1, j=2 или i=2, j=1), то оба проиграют, получая (-1,-1).

Найдём стратегии первого игрока (очевидно, что в силу симметричности платёжной матрицы стратегии второго игрока точно такие же).

Рассматривая максиминную стратегию первого игрока, когда он выбирает ход i=1 с вероятностью p, получим, что его выигрыш будет равен

при,

при.

Соответствующие прямые изображены на рис. 7. Величина находится из условия

,

откуда имеем ,так чтосмешанная стратегияпервого игрока естьи его гарантированный выигрыш равен

.

Применяя стратегию угрозы, он считает выигрыш второго игрока, который будет равен

при,

при.

 

Соответствующие прямые изображены на рис. 8. Величина находится из условия

откуда следует, что p=3/5, так что смешанная стратегия первого игрока есть (3/5,2/5). При этом выигрыш второго игрока будет в любом случае равен

.

Таким образом, применяя максиминную стратегию первый игрок может гарантировать себе выигрыш, равный 1/5; применяя стратегию угрозы он может быть уверен, что второй игрок получит не более 1/5.

Кооперативная игра двух лиц. Переговорное множество

Прежде, чем говорить о кооперативных играх, вернёмся еще раз к последнему примеру  игре “семейный спор”. Пусть первый игрок используетсмешанную стратегию(p,1-p), второй  стратегию (q,1-q). Тогда средние выигрыши игроков будут равны

,

.

Тем самым пара (p, q) превращается в пару .

Рассмотрим плоскость . Перебирая все возможные значения пар (p, q) мы получим на плоскостинекоторую область, которая изображена на рис. 9. Она ограничена прямыми, проходящими через пары точек ( 1,  1), (1, 2) и ( 1,  1), (2, 1), а также куском параболы. В ней есть “провал”, ограниченный именно этой параболой.

А теперь вернёмся к общему случаю игры двух лиц с платёжной матрицей

и допустим, что игроки имеют возможность договариваться о совместных действиях.

Раньше ход номер i первого игрока выбирался с вероятностью и ход номер j второго игрока с вероятностьюиходыобоих игроков были независимы так что комбинация (i, j) появлялась с вероятностью. Сейчас ходы выбираются совместно и поэтому комбинация ходовпоявляется с некоторой совместной вероятностью. Совместная игра сводится таким образом к выбору совместной смешанной стратегии. При этом, очевидно,

.

При такой совместной смешанной стратегии средние выигрыши первого и второго игроков равны соответственно

.

(9)

Представим себе плоскость.Какую область заполняют в ней значенияи, получаемые по формулам (9)?

Эту область R можно построить следующим образом. Представим себе, что на плоскости мы поставилиточек с координатами. Тогда R есть так называемая выпуклая оболочка этих точек. Наглядно её можно представить так: вообразите себе, что в точкахвбиты гвоздики. Далее мы берём кольцо из резинки, растягиваем его, надеваем снаружи на все эти гвоздики и отпускаем резинку. Она сократится и обтянет всю эту систему гвоздей, ограничивая как раз ту область, которая и называется выпуклой оболочкой. Точкиокажутся при этом либо в вершинах получившегося многоугольника, либо внутри области.

Так в игре типа “семейный спор” область R есть выпуклая оболочка точек (-1,-1), (2, 1) и (1, 2) (см. рис. 11).

Сравните эту область с той, которая изображена на рис. 9. Мы видим, что применение совместных стратегий позволило заполнить ту “впадину”, которая была при некооперативной игре.

О чем же теперь могут договориться наши игроки? Пустьиесть максиминные выигрыши первого и второго игроков соответственно. Нанесём на наше множество R точку с координатами. Эта точка называется точкой status quo. Очевидно, что ни один из игроков не согласится получать в результате совместной игры меньше, чем даёт ему максиминная стратегия  зачем ему такая договорённость, если он может

гарантировать себе илибез всяких договорённостей.

Поэтому из нашего множества R сразу отбрасывается область, где или.

Рассмотрим теперь оставшуюся область, где и.

Определение 1. Точканазывается подчинённой точкеесли одновременнои, причем хотя бы одно из этих неравенств строгое.

Очевидно, что если точка подчинена точке, то в процессе торговли игроки безболезненно откажутся от точкив пользу точки, так как при таком переходе хотя бы одному становится лучше, а другому  не хуже. Очевидно также, что точки, которым подчинена точка, лежат правее и выше на множестве R.

Определение 2. Множество точек из R, которые не подчинены никаким другим точкам и для которых выполняется условие, называется переговорным множеством или множеством Парето.

Легко догадаться, что переговорное множество это та часть правой верхней (или, как еще говорят, северо-восточной) границы множества R, для которой

выполнены условия .

Теперь очевидно, что собственно торговля и согласование стратегий игроков будут вестись на переговорном множестве. До чего они там доторгуются  с имеющимися данными сказать заранее нельзя, на этом множестве интересы игроков прямо противоположны. Результат зависит от умения вести переговоры, т.е. фактически задача расширяется.

Итак, в определённом смысле, решить кооперативную игру двух лиц означает построить переговорное множество. Напомним основные этапы его построения.

На плоскости нанести точки ,,.

Построить выпуклую оболочку этих точек.

Найти максиминные выигрыши обеих игроков и построить точку status quo.

Нарисовать северо-восточную границу построенного множества, удовлетворяющую условиям

На этом работа алгоритма пока заканчивается. Выбор решения по переговорам естественно иногда можно формализовать как игру, когда аргументы поддаются количественной оценке.

Кстати, для игры типа “семейный спор” переговорное множество  это отрезок прямой, соединяющей точки (1, 2) и (2, 1).

10. Арбитраж

Итак, математик сделал своё дело и уходит в сторону, а игроки торгуются. Чем окончится торг - неизвестно. К сожалению, встречаются люди (и не только люди, а целые государства), которые, желая получит себе возможно больше, торгуются очень упорно, пуская в ход всё, даже угрозы. В результате переговоры оканчиваются ничем, угрозы приводятся в исполнение… Чем это кончается можно очень часто наблюдать в жизни.

Одним из выходов из этой ситуации является приглашение со стороны некоторого арбитра, который бы одинаково относился к обеим сторонам, и предложить ему указать совместную стратегию “по справедливости”. Если арбитр действительно “справедливый” и “беспристрастный”, он может вынести устраивающее обоих игроков решение. Но что означает “справедливый” и “беспристрастный”?

Достаточно очевидно, что к такому арбитру должны быть предъявлены следующие требования.

Арбитражное решение должно быть элементом переговорного множества.

Арбитражная схема должна быть независимой от имён или обозначений игроков.

Если две игры близки между собой в каком-то смысле, то и арбитражные решения должны быть близки.

Арбитражное решение должно отражать действенность угроз игроков.

В теории игр для решения подобных задач часто используют аксиоматический метод, когда подобные требования пытаются формализовать в виде математических аксиом. Ниже мы изложим систему таких аксиом, принадлежащую Дж. Нэшу. В дальнейшем считается, что игрок № 1 имеет ходов, игрок номер 2 -ходов, платёжная матрица имеет вид,,. Черезмы будем обозначать выпуклую оболочку точек,- переговорное множество,- точка status quo,- решение арбитра.

Аксиома 1. (Оптимальность по Парето). Точкадолжна быть элементом переговорного множества, то есть

;

;

в нет точки, отличной от точки, такой, что,.

Аксиома 2. (Симметрия).Пусть игра обладает следующими свойствами:

;

если точка ,

то и точка .

Тогда должно выполняться условие .

 

Другими словами, если игроки находятся в совершенно одинаковой ситуации, то и арбитражное решение должно быть одинаковым.

Следующие две аксиомы далеко не столь очевидны, как предыдущие.

Аксиома 3. (Инвариантность относительно линейного преобразования).Пусть имеются две игры с одинаковым числом ходов для каждого игрока и с платёжными матрицами, связанными соотношениями

.

Тогда арбитражные решения для них также должны быть связаны соотношениями

Аксиома 4. (Независимость несвязанных альтернатив).Если к игре добавить новые ходы для игроков с добавлением новых элементов платёжных матриц таким образом, что точка status quo не меняется, то либо арбитражное решение также не меняется, либо оно совпадает с одной из добавленных сделок.

Дж. Нэш показал, что существует единственная арбитражная схема, удовлетворяющая этим четырём аксиомам. Арбитражное решение должно выноситься из условия

,

то есть “справедливое” решение арбитра должно удовлетворять условию

для всех точек принадлежащих переговорному множеству.

Кстати, в игре “семейный спор”, в силу симметрии обеих игроков, арбитражным решением для таких аксиом должна быть точка (3/2, 3/2), лежащая на середине отрезка, соединяющего точки (1, 2) и (2, 1). Она получается при следующей совместной стратегии

.

Муж и жена должны ходить вместе на футбол или в театр одинаково часто (например, по очереди).

Как можно понять, уже аксиома 2 не всегда выполняется в реальности, так как реальные переговоры оказываются по сути отдельной игрой. Тем не менее подход оптимальности по Парето позволяет искать решения задач многокритериальной оптимизации.

Игры n лиц с постоянной суммой .

Теория игр с числом игроков, большим 2, развита несколько слабо, мы изложим лишь основные понятия.

Имеется принципиальная разница между ситуацией, когда имеется лишь два игрока, и ситуацией, когда число игроков больше двух. Она заключается в том, что в последнем случае могут образовыватьсякоалицииигроков, действующих совместно против остальных игроков. В диаде не может быть большинства, но простое добавление третьего члена делает возможным появление такого большинства. В общем, может возникнуть вариант-- “против кого дружим?”.

Именно эта возможность  ---возможность образования коалиций  и привела к тому, что теория игр n лиц заметно отличается от теории игр двух лиц.

Другая особенность коалиций  это так называемые побочные платежи, иначе взятки. Доходы, получаемые коалицией, могут перераспределяться внутри неё, так что некоторые члены коалиции кроме собственного выигрыша могут получать часть доходов других игроков, которые платят им за то, что те остаются в коалиции. Это перераспределение доходов ещё больше усложняет ситуацию.

А теперь дадим некоторые основные понятия, относящиеся к играм n лиц. Итак, игра n лиц состоит из следующих элементов.

Множество состоящее из n игроков;

n множеств стратегий ;

n действительных платёжных функций ,, …,, гдеплатёж i-му игроку, когда игрок 1 применяет стратегию, игрок 2  стратегию, … , игрок n  стратегию

Кроме того предполагается, что каждый игрок знает всю структуру игры и в своём поведении неизменно руководствуется желанием получить максимальный средний выигрыш.

Ниже будут рассматрены так называемые игры с постоянной суммой, когда

.

Это  аналог игр с нулевой суммой для двух игроков.

Характеристическая функция

Пусть есть подмножество игроков, решивших составитькоалициюв том смысле, что они будут принимать групповые решения об индивидуальных действиях, которые в совокупности дадут группе лучшее положение. Наихудшая ситуация, с которой может встретиться коалиция, будет тогда, когда все оставшиеся игрокитакже объединяться в коалицию. Тогда игра превращается в игру двух коалиций  коалициипротив коалициии её можно теперь рассматривать как игру двух лиц с постоянной суммой, теория которых рассматривалась в самом начале.

Обозначим через максиминный средний доход коалициикогда она играет против коалиции. Другими словами, у коалицииесть стратегия, обеспечивающая ей средний доходв наихудшей для неё ситуации.

Доходможно вычислить для любой возможной коалиции, то есть для любого подмножества игроков. Тем самым, мы получили функцию, определённую на подмножествах множества. Она и называетсяхарактеристической функцией.

Эта функция, очевидно, обладает следующими свойствами:

  ;

  ;

, s   где пустое множество;

 если идве непересекающиеся коалиции, то.

Последнее свойство самое важное. Оно утверждает, что доход целого не меньше суммы доходов его частей, или, объединяясь, две коалиции могут получить всё то, что они получали, действуя по отдельности, и, может быть, даже больше.

В теории игр обычно принимаются ещё следующие два предположения.

 Если каждому игроку выплачивать перед партией некоторую сумму(или он уплачивает, если<0), то это не изменит его поведения в ходе игры).

 Если все платежи увеличить в c раз (или уменьшить, если c<1), то это также не изменит поведения игроков.

Это приводит к тому, что две игры n-лиц с характеристическими функциямии, определённые на одном и том же множестве игроков и связанные соотношением

,

описывают, по сути дела, одну и ту же игру. Такие игры называются -эквивалентными.

Эти понятия позволяют привести все характеристические функции к некоторой нормальной форме. Пусть характеристическая функция игры. Рассмотрим характеристическую функцию

,

где означает коалицию, состоящую из единственного игрока i. Эта функция обладает следующими свойствами

;.

Она называется (0, 1) нормализацией характеристической функции.

Предпосылки и решение

Итак, игроки объединились в коалиции и играют “стенка на стенку”. Что же они могут в результате получить?

Пусть образовалась коалиция , которая играет против коалиции, и пусть средний доход (или убыток, в зависимости от знака)-го игрока равен. Какие ограничения накладываются на? Достаточно разумными выглядят следующие ограничения:

. Действительно, кто же будет вступать в коалицию, в которой он получит меньше, чем получил бы, играя в полном одиночестве.

 

. Весь доход коалиции распределяется между игроками.

 

. Игра с постоянной суммой и весь доход игроков должен быть равен этой сумме.

Набор, удовлетворяющий этим ограничениям, называется предпосылкой. В принципе, любая предпосылка имеет право на реализацию в виде соответствующих коалиций. Вот только какие из них реализуются?

Чтобы понять идею, рассмотрим пример. Пусть дана игра трёх лиц с постоянной суммой. В (0, 1) нормализации мы имеем:

;

.  С другой стороны, так как, например,,то.

.

Рассмотрим множество A, состоящее из следующих трёх предпосылок

,,.

Давайте предположим, что реализовалась первая предпосылка, игроки 1 и 2, объединившись в коалицию, получают по 1/2, третьему игроку остаётся ноль.

А теперь допустим, что первый игрок пожадничал и ему хочется большего. Он идёт к третьему игроку и предлагает ему коалицию {1, 3}, в которой доходы будут выглядеть так: . Всё разумно  оба игрока, первый и третий, увеличили свои доходы на 1/4.

Но теперь, когда реализовалась предпосылка , в обиде второй игрок. Он идёт к третьему игроку и предлагает ему новую коалицию {2, 3}, в которой доходы будут делиться поровну,. Третьему игроку это выгодно, он соглашается и возникает коалиция {2, 3} c распределением доходов

.

Что же произошло? Первый игрок пожадничал и в результате потерял всё. А мы снова оказались во множестве A.

Получается, что множество A обладает своеобразной внутренней устойчивостью, уходя из него, в него же и возвращаются. Кроме того, ни одна предпосылка из множества A не лучше другой. Подобные множества Дж. фон Нейман и О. Моргенштерн и предложили считать решением игры n лиц.

Попробуем формализовать эти идеи. Пусть имеются две предпосылки и. Говорят, что предпосылка y доминирует над предпосылкой x по отношению к коалиции T, если T  непустое множество и если выполняются следующие условия:

 1. ;

 2. .

Другими словами, игрокам выгодно объединиться в коалицию T все они от такого объединения выигрывают.

Говорят, что коалиция y доминирует над x (обозначение ) если имеется по крайней мере одно непустое множество T такое, что y доминирует над x по отношению к коалиции T.

Если имеются две предпосылки x и y, то могут быть следующие случаи:

y доминирует над x, но x не доминирует над y;

y доминирует над x и x доминирует над y (естественно, по отношению к разным коалициям);

ни одна из предпосылок x и y не доминирует одна над другой.

Решение игры n лиц определяется как любое множество A. такое, что

если x и y  предпосылки, входящие в A, то ни одна из них не доминирует над другой;

если z  предпосылка, не входящая в A, то найдётся по крайней мере одна предпосылка x принадлежит A, которая доминирует над z.

Практическое значение всех этих понятий невелико. Во-первых, трудно вычислить характеристическую функцию игры. Во-вторых, решение в данном выше смысле неоднозначно, существует целое множество решений. И, в третьих, коалиции в реальности часто образуются числом более 2х.

Игры против природы

Особое место в теории игр занимают игры против природы, которые ещё носят название выбора решений при неопределённости. Природа хотя и делает случайные ходы, но не является злонамеренным игроком, так как она не стремится сделать как можно хуже своему противнику. Поэтому и выбор решения в такой ситуации имеет свои особенности.

Итак, предположим, что Природа может находиться в одном из состояний; в каком состоянии она находится сейчас - нам неизвестно. В нашем распоряжении имеетсявозможных действий. Если Природа находится в состоянии, а мы выбираем действие, то мы получаем платёж. Таким образом, как и в игре двух лиц, мы имеемплатёжную матрицу

.

Какое же действие нам выбрать? В теории игр предлагается несколько критериев такого выбора, рассчитанных на разных людей.

Максиминный критерий

Этот критерий поведения рассчитан на достаточно пессимистичного человека; ему предлагается выбирать своё действие из условия

,

то есть действовать так, чтобы в наихудшем для себя случае получить максимум.

Критерий минимаксного сожаления

Пусть , то естьэто максимум того, что может получить игрок при j-м состоянии Природы.

Перейдём от величин к величинам

,

которые можно трактовать как “сожаление”, то есть недополученная выгода от того, что при j-м состоянии Природы игрок сделал неправильный ход. Тогда в качестве критерия для выбора хода предлагается следующий

,

то есть минимизация максимального “сожаления”.

Критерий пессимизма-оптимизма Гурвица

Пусть ,, то естьиесть минимум и максимум того, что может получить игрок, выбирая ход номер i. Свяжем с каждым ходом величину

и будем выбирать свой ход из условия

.

Коэффициент носит название показателя пессимизма игрока. При=1 мы имеем крайне пессимистичного человека, и этот критерий переходит в критерий максимина. При=0 перед нами убеждённый оптимист.

Принцип недостаточного основания

Этот принцип сформулировал ещё Я. Бернулли и он заключается в том, что все состояния. Природы считаются равновероятными. Действие игрока выбирается поэтому из условия

.

После всего сказанного, перед игроком против Природы встаёт, пожалуй, ещё более сложная проблема - какой критерий выбирать для принятия своих реальных решений.

Лекция 8. Особенности приведения задачи игры к задаче линейного программирования.

(может выше это изложено?)

Вероятно, имеет смысл повторить важнейшие методы вычисления решении задачи.

Игра m × nв общем случае не имеет наглядной геометрической интерпретации. Ее решение достаточно трудоемко при большихm и n, однако принципиальных трудностей не имеет, поскольку может быть сведено к решению задачи линейного программирования. Покажем это. Пусть играm × nзадана платежной матрицейp = (a_ij ), i = 1, 2, ..., m; j = 1, 2, ..., n. ИгрокАобладает стратегиямиA₁ , A₂ , ..., A_m , игрокВ— стратегиямиB₁ , B₂ , ..., B_m . Необходимо определить оптимальные стратегииS*_A = ( p*₁ ,  p*₂ , ... ,  p*_m )иS*_B = ( q*₁ , q*₂ , ... ,  q*_n ), гдеp*_i,q*_j— вероятности применения соответствующих чистых стратегийA_i,B_j,  p*₁  + p*₂ +...+ p*_m =1,q*₁ + q*₂ +...+ q*_n = 1.

Оптимальная стратегия S*_A удовлетворяет следующему требованию. Она обеспечивает игрокуАсредний выигрыш, не меньший, чем цена игрыv, при любой стратегии игрокаВи выигрыш, равный цене игрыv, при оптимальной стратегии игрокаB. Без ограничения общности полагаемv > 0: этого можно добиться, сделав все элементыa_ij ≥ 0. Если игрокА применяет смешанную стратегиюS*_A = ( p*₁ ,  p*₂ , ... ,  p*_m )против любой чистой стратегииB_j игрокаВ, то он получаетсредний выигрыш, илиматематическое ожидание выигрышаa_j = a_1j p₁ + a_2j p₂ +...+ a_m j p_m , о = 1, 2, ..., n(т.е. элементыj-го столбца платежной матрицы почленно умножаются на соответствующие вероятности стратегийA₁ , A₂ , ..., A_mи результаты складываются).

Для оптимальной стратегии S*_Aвсе средние выигрыши не меньше цены игрыv, поэтому получаем систему неравенств:

(3.11)

Каждое из неравенств можно разделить на число v > 0. Введем новые переменные:

x1 =  p1/v, x2 = p2/v , ...,  pm/v

(3.12)

Тогда система (11) примет вид:

(3.13)

ЦельигрокаА— максимизировать свой гарантированный выигрыш, т.е. цену игрыv. Разделив наv ≠ 0равенствоp₁ + p₂ + ...+ p_m = 1 , получаем, что переменныеx₁ (i = 1, 2, ..., m)удовлетворяют условию:x₁ + x₂ + ...+ x_m = 1/v. Максимизация цены игрыvэквивалентна минимизации величины1/v, поэтому задача может быть сформулирована следующим образом:определить значения переменных x_i ≥ 0, i = 1, 2, ..., m, так, чтобы они удовлетворяли линейным ограничениям (13) и при этом линейная функция

Z = x1 + x2 + ...+ xm,

(3.14)

обращалась в минимум. Это задача линейного программирования. Решая задачу (3.13)—(3.14), получаем оптимальное решениеp*₁ + p*₂ + ...+ p*_m и оптимальную стратегиюS_A . Для определения оптимальной стратегииS*_B = (q*₁ + q*₂ + ...+ q*_n) следует учесть, что игрокВстремится минимизировать гарантированный выигрыш, т.е. найти. Переменныеq₁ , q₂ , ..., q_nудовлетворяют неравенствам:

(3.15)

которые следуют из того, что средний проигрыш игрока Вне превосходит цены игры, какую бы чистую стратегию не применял, игрокА. Если обозначить

yj =  qj/v, j = 1, 2, ..., n,

(3.16)

то получим систему неравенств:

(3.17)

Переменные y_j (1, 2, ..., n)удовлетворяют условию. Игра свелась к следующей задаче Определить значения переменныхy_j ≥ 0, j = 1, 2, ..., n,  которые удовлетворяют системе неравенств (3.17) и максимизируют линейную функцию

Z' = y1 + y2 + ...+ yn,

(3.18)

Решение задачи линейного программирования (3.16), (3.17) определяет оптимальную стратегию S*_B = (q*₁ + q*₂ + ...+ q*_n) . При этом цена игры

v =  1 / max, Z' = 1 / min Z

(3.19)

Составив расширенные матрицы для задач (3.13), (3.14) и (3.17), (3.18), убеждаемся, что одна матрица получилась из другой транспонированием:

Таким образом, задачи линейного программирования (3.13), (3.14) и (3.17), (3.18) являются взаимно-двойственными. Очевидно, при определении оптимальных стратегий в конкретных задачах следует выбрать ту из взаимно-двойственных задач, решение которой менее трудоемко, а решение другой задачи найти с помощью теорем двойственности. Приведем примеры экономических задач, которые описываются игровыми моделями т х п и могут быть решены методами линейного программирования.

Пример 3.5.1.

Обозначив x_i =  p_i/v, i = 1, 2, 3 и y_j = q_j/v , j = 1, 2, 3, составим две взаимно-двойственные задачи линейного программирования (см. (3.13)-(3.14) и (3.17)-(3.18)).

Пример 3.5.2

При решении произвольной конечной игры размера m × nрекомендуется придерживаться следующей схемы:

Исключить из платежной матрицы заведомо невыгодные стратегии по сравнению с другими стратегиями. Такими стратегиями для игрока А(игрокаВ) являются те, которым соответствуют строки (столбцы) с элементами, заведомо меньшими (большими) по сравнению с элементами других строк (столбцов).

Определить верхнюю и нижнюю цены игры и проверить, имеет ли игра седловую точку. Если седловая точка есть, то соответствующие ей стратегии игроков будут оптимальными, а цена совпадает с верхней (нижней) ценой.

Если седловая точка отсутствует, то решение следует искать в смешанных стратегиях. Для игр размера m × nрекомендуется симплексный метод, для игр размера2×2,2×n,n×2возможно геометрическое решение.

На практике реализация оптимального решения в смешанных стратегиях может происходить несколькими путями. Первый состоит в физическом смешении чистых стратегийA_i  - в пропорциях, заданных вероятностямиp_i . Другой путь — при многократном повторении игры — в каждой партии чистые стратегии применяются в виде случайной последовательности, причем каждая из них — с частотой, равной ее вероятности в оптимальном решении.

Рассмотрим еще один пример задачи, сводящийся к игровой модели.

Пример 3.5.3

Предприятие выпускает скоропортящуюся продукцию, которую может сразу отправить потребителю (стратегия A₁), отправить на склад для хранения (стратегияA₂) или подвергнуть дополнительной обработке (стратегияA₃) для длительного хранения. Потребитель может приобрести продукцию: немедленно (стратегияB₁), в течение небольшого времени (B₂), после длительного периода времени (B₃). В случае стратегийA₂иA₃, предприятие несет дополнительные затраты на хранение и обработку продукции, которые не требуются дляA₁, однако приA₂следует учесть возможные убытки из-за порчи продукции, если потребитель выберет стратегииB₂илиB₃. Определить оптимальные пропорции продукции для применения стратегийA₁,A₂,A₃руководствуясь "минимаксным критерием" (гарантированный средний уровень убытка) при матрице затрат, представленной табл. 3.6.

Таблица 3.6

Решение. Получаем игру с платежной матрицей

В этой матрице первую строку можно отбросить как невыгодную (ее элементы меньше соответствующих элементов второй строки). Матрица примет вид

Элементы первого столбца больше соответствующих элементов второго столбца, поэтому его можно отбросить.

Игра упростилась:

По формулам (3.7) и (3.8) находим:

Вывод: оптимальная стратегия производителя продукции , т.е. стратегияA₁не применяется,1/3продукции отправляется на склад (стратегияA₂),2/3продукции дополнительно обрабатывается (стратегияA₃), при этом цена игры

Принципы метода динамического программирования.

Динамическое программирование— это вычислительный метод для решения задач определенной структуры. Возникло и сформировалось в 1950-1953 гг. благодаря работам над динамическими задачами управления запасами. В простейшией формулировке динамическое программирование представляет собой направленный последовательный перебор вариантов, который обязательно приводит к глобальному максимуму.

Основные необходимые свойства задач, к которым возможно применить этот принцип:

Задача должна допускать интерпретацию как n-шаговый процесс принятия решений.

Задача должна быть определена для любого числа шагов и иметь структуру, не зависящую от их числа.

При рассмотрении k-шаговой задачи должно быть задано некоторое множество параметров, описывающих состояние системы, от которых зависят оптимальные значения переменных. Причем это множество не должно изменяться при увеличении числа шагов.

Выбор решения (управления) на k-м шаге не должен оказывать влияния на предыдущие решения, кроме необходимого пересчета переменных.

Идея динамического программирования состоит в разбиении задачи на несколько независимых подзадач, решении каждой из них, а затем вычислении исходного результата. Для решения подзадач этот же алгоритм применяется рекурсивно. При этом для каждой подзадачи запоминается вычисленный ответ, и если на каком-то шаге встретилась подзадача второй раз, то вычисления для нее не производятся. За счет большого количества пересекающихся подзадач это может значительно уменьшить время работы.

Задача о выборе траектории, задача последовательного принятия решения, задача об использовании рабочей силы, задача управления запасами — классические задачи динамического программирования.

Суть:

Первая формулировка: оптимальная стратегия (поведение) системы не зависит от ее предыстории, а зависит лишь от состояния системы в данный рассматриваемый момент времени.

Вторая формулировка: если в пространстве состояний системы некоторым образом построена оптимальная траектория, то любой ее участок, отсчитываемый от конца,  также оптимальная траектория.

Обычная процедура оптимизации, осуществляемая от начала к концу процесса, сводится к процедуре поэтапной оптимизации от конца процесса к его началу. Также, если говорить формально задача оптимизации функции n  переменных сводится к n  процедурам оптимизации функции одной  переменной.

Основная идея метода---предполагается, что конечная цель достигнута и ищется оптимальная стратегия на последнем участке (точнее на всех возможных предпоследних участках), далее ищется оптимальная стратегия на всех предпоследних и последних участках и т.д(рекурсия)

Решение задачи динамического программирования.

Процедура построения оптимального управления методом динамического программирования распадается на две стадии: предварительную и окончательную. На предварительной стадии для каждого шага определяется условное оптимальное управление, зависящее от состояния -Q системы (достигнутого в результате предыдущих шагов), и условный оптимальный выигрыш на всех оставшихся шагах, начиная с данного, также зависящий от состояния Q.

На окончательной стадии для каждого шага определяется окончательное (безусловное) оптимальное управление. Предварительная (условная) оптимизация проводится по шагам, в обратном порядке: от последнего шаги к первому; Окончательная (безусловная) оптимизация-также по шагам, но в естественном порядке: от первого шага к последнему.

Введем следующие обозначения: Пусть - это условный оптимальный выигрыш, получаемый на всех последующих шагах, начиная с i-го и до конца; он достигается при оптимальном управлении на всех этих шагах и равен максимальному выигрышу, который можно получить на всех этих шагах вместе, если перед их началом система находится в состоянии.-условное оптимальное управление на i-ом шаге, которое, совместно с оптимальным управлением на всех последующих шагах, обращает выигрыш на всех шагах, начиная с данного, в максимум. Поставим задачу-построить алгоритм определения функций условного оптимального выигрышаи условного оптимального управлениядля всех шаговРассмотрим i-ыи шаг процесса управления. Пусть в результате i-1 предыдущих шагов система пришла в состояние, и мы выбираем какое-то управлениена i-ом шаге. Если мы его применим, то, во-первых, получим на данном i-ом шаге какой-то выигрышОн зависит от состояния системы Q так и от управления :(1) Кроме того, мы получим какой-то выигрыш на всех оставшихся шагах. На основании принципа оптимальности, будем считать, что он максимален. Чтобы найти этот выигрыш, мы должны знать состояние системы перед следующим, (i+1)-м шагом. Под влиянием управленияна i-ом шаге система из состояния Q   (в котором она была перед этим шагом) перейдет в какое-то новое состояниеЭто новое состояние будет зависеть, опять-таки, от прежнего состояния Q и примененного управления(2) Запишем выигрыш, который мы получим на всех шагах, начиная с i-го, если на i-ом шаге будет применено любое (возможно, не оптимальное) управлениеа на всех последующих (i+1)-го до N-го оптимальное управление. Этот выигрыш будет равен выигрышу zi на данном i-ом шаге, плюс условный оптимальный выигрыш на всех последующих шагах, начиная с (i+1)-го, определяемый для нового состояния системы;(3) обозначим такой "полуоптимальный" выигрыш черезтогда учитывая (2) и (3),(4) Теперь, в соответствии с принципом оптимальности, мы должны выбрать такое управлениепри котором величина (4) максимальна и достигает значения:(5) То управлениепри котором этот максимум в (5) достигается, и есть условное оптимальное управление на i-ом шаге, а сама величина (5)-условный оптимальный выигрыш (на всех шагах, начиная с i-го и до конца). В уравнении (5) функциииизвестны. Неизвестными остаются функции:

и; из них первая выражается через вторую. Формула (5) представляет собой так называемое основное функциональное уравнение динамического программирования или уравнение Беллмана. Оно позволяет определить функцию Zi(Q) , если известна следующая за ней по порядкуЧто касается функции(условный оптимальный выигрыш на последнем шаге), то она может быть определена очень просто. Действительно, за последним шагом нет следующего, и нужно обратить в максимум выигрыш на этом шаге:(6) Максимум в формуле (6) берется не по всем возможным управлениям XN на N-ом шаге, а только по тем, которые приводят в систему в заданную областьт.е. по тем, для которыхЭто всегда нужно иметь в виду при использовании формулы (6). То управлениепри котором достигается максимум выигрыша, и есть условное оптимальное управление на последнем шаге.

Теперь построим всю цепочку условных оптимальных управлений. Зная можно по общей формуле (5), полагая в ней i+1=n , найти функциюи соответствующее оптимальное управление; затемии так далее , вплоть до последнего шага от конца т.е. первого шага, для которого будут найдены функции Z1(Q) и X1(Q) . Функция Z1(Q) есть условный оптимальный выигрыш за всю операцию, т.е. на всех шагах начина с первого и до последнего (если первый шаг начинается с определенного состояния Q1). Таким образом предварительная оптимизация закончена-найдены условный оптимальный выигрыш и условное оптимальное управление для каждого шага.

Рассмотрим вторую стадию оптимизации-нахождение безусловного или окончательного оптимального управления

Начнем с первого шага.

Предположим, что исходное состояние Q1 нам полностью известно. Подставим это состояние Q1 в формулу для условного оптимального выигрыша Z1(Q). Получим:(7) Одновременно найдем оптимальное управление на первом шагеДалее, зная исходное состояние Q1 и управление X1 , можем найти состояниесистемы после первого шага:Зная это состояниеможно найти оптимальное управление на втором шагезатеми т. д. Таким образом, идя по цепочке(8) мы определили одно за другим, все шаговые оптимальные управления операций в целома также конечное состояние системыЭто условие будет выполняться, т.к. мы выбираем управление на последнем шаге так, чтобыРассмотрим теперь случай, когда исходное состояние системы ограничено условием.   В этом случае нужно найти такое начальное состояниепри котором условный минимальный выигрыш за все шаги максимален.(9) То начальное состояниедля которого этот максимум достигается и нужно взять в качестве исходного. Далее оптимальное управление строится в соответствии с выражением (8), заменяя Q1 на(8a) При изложении материала мы использовали систему символических формул, которая непригодна для непосредственного вычисления. Однако с их помощью можно организовать процедуру динамического программирования в следующей последовательности:

Выбрать способ описания процесса, т.е. параметры характеризующие состояние системы, фазовое пространство и способ деления операции на шаги.

Записать выигрыш на i-ом шаге в зависимости от состояния системы Q перед этим шагом и управления Xi

Записать для i-го шага функцию, выражающую изменение состояния системы от Q к Q` под действием управления Q`

Записать основное функциональное уравнение (5)

Найти условный оптимальный выигрыш последнего N-го шага при этом должно выполняться условиеОдновременно определить условное оптимальное управление Xn(Q) на последнем шаге.

Зная Zn(Q) по уравнению (5) для конкретного вида функций Zi(Q,Xi) и найти последовательно Wn-1(Q),Wn-2(Q),:,W1(Q) и соответствующие им условные оптимальные уравнения

Если начальное состояние системы Q1 задано, найти оптимальный выигрыш Zmax=Z1(Q1) и безусловные оптимальные управления в последовательности, указанной выражением (8).

Если начальное состояние Q1 задано условием то для определения Zmax нужно использовать выражение(9). Определение безусловных оптимальных управлений провести по схеме(8а).

Отметим преимущества и недостатки метода динамического программирования. К числу положительных качеств можно отнести:

1)МДП дает возможность решать задачи, которые раньше не исследовались из-за отсутствия годного математического аппарата.

2)МДП в ряде случаев сокращает объем при поиске оптимальных решений.

К недостаткам относятся:

1)Отсутствие универсального алгоритма, который был бы пригоден для решения всех задач (мы имеем только схему).

2)Трудности при решении задач большой размерности.

Несомненна привлекательность идеи разбиения задачи большой размерности на подзадачи меньшей размерности, включающие всего по нескольких переменных, и последующего решения общей задачи по частям. Метод можно использовать для решения весьма широкого круга задач, включая задачи распределения ресурсов, замены и управления запасами, задачи о загрузке. Характерным для динамического программирования является подход к решению задачи по этапам, с каждым из которых ассоциирована одна управляемая переменная. Набор рекуррентных вычислительных процедур, связывающих различные этапы, обеспечивает получение допустимого оптимального решения задачи в целом при достижении последнего этапа. Происхождение названия динамическое программирование, вероятно, связано с использованием методов ДП в задачах принятия решений через фиксированные промежутки времени (например, в задачах управления запасами). Однако методы ДП успешно применяются также для решения задач, в которых фактор времени не учитывается. По этой причине более удачным представляется термин многоэтапное программирование, отражающий пошаговый характер процесса решения задачи. Фундаментальным принципом ДП является принцип оптимальности. По существу, он определяет порядок поэтапного решения допускающей декомпозицию задачи (это более приемлемый путь, чем непосредственное решение задачи в исходной постановке) с помощью рекуррентных вычислительных процедур. Динамическое программирование позволяет осуществлять оптимальное планирование управляемых процессов. Под «управляемыми» понимаются процессы, на ход которых мы можем в той или другой степени влиять. Пусть предполагается к осуществлению некоторое мероприятие или серия мероприятий («операция»), преследующая определенную цель. Спрашивается: как нужно организовать (спланировать) операцию для того, чтобы она была наиболее эффективной? Для того, чтобы поставленная задача приобрела количественный, математический характер, необходимо ввести в рассмотрение некоторый численный критерий W, которым мы будем характеризовать качество, успешность, эффективность операции. Критерий эффективности в каждом конкретном случаи выбирается исходя из целевой направленности операции и задачи исследования (какой элемент управления оптимизируется и для чего). Сформулируем общий принцип, лежащий в основе решения всех задач динамического программирования («принцип оптимальности»): «Каково бы ни было состояние системы S перед очередным шагом, надо выбрать управление на этом шаге так, чтобы выигрыш на данном шаге плюс оптимальный выигрыш на всех последующих шагах был максимальным». Динамическое программирование – это поэтапное планирование многошагового процесса, при котором на каждом этапе оптимизируется только один шаг. Управление на каждом шаге должно выбираться с учетом всех его последствий в будущем. При постановке задач динамического программирования следует руководствоваться следующими принципами: 1. Выбрать параметры (фазовые координаты), характеризующие состояние S управляемой системы перед каждым шагом. 2. Расчленить операцию на этапы (шаги). 3. Выяснить набор шаговых управлений x_i для каждого шага и налагаемые на них ограничения. 4. Определить какой выигрыш приносит на i-ом шаге управление x_i, если перед этим система была в состоянии S, т.е. записать «функцию выигрыша»: . 5. Определить, как изменяется состояние S системы под влиянием управление xi на i-ом шаге: оно переходит в новое состояние . (1.1) 6. Записать основное рекуррентное уравнение динамического программирования, выражающее условный оптимальный выигрыш Wi(S) (начиная с i-го шага и до конца) через уже известную функцию Wi+1(S). (1.2) Этому выигрышу соответствует условное оптимальное управление на i-м шаге xi(S) (причем в уже известную функцию Wi+1(S) надо вместо S подставить измененное состояние ) 7. Произвести условную оптимизацию последнего (m-го) шага, задаваясь гаммой состояний S, из которых можно за один шаг дойти до конечного состояния, вычисляя для каждого из них условный оптимальный выигрыш по формуле 8. Произвести условную оптимизацию (m-1)-го, (m-2)-го и т.д. шагов по формуле (1.2), полагая в ней i=(m-1),(m-2),…, и для каждого из шагов указать условное оптимальное управление xi(S), при котором максимум достигается. Заметим, что если состояние системы в начальный момент известно (а это обычно бывает так), то на первом шаге варьировать состояние системы не нужно - прямо находим оптимальный выигрыш для данного начального состояния S0. Это и есть оптимальный выигрыш за всю операцию

9. Произвести безусловную оптимизацию управления, «читая» соответствующие рекомендации на каждом шаге. Взять найденное оптимальное управление на первом шаге ; изменить состояние системы по формуле (1.1); для вновь найденного состояния найти оптимальное управление на втором шаге и т.д. до конца. Данные этапы рассматривались для аддитивных задач, в которых выигрыш за всю операцию равен сумме выигрышей на отдельных шагах. Метод динамического программирования применим также и к задачам с так называемым «мультипликативным» критерием, имеющим вид произведения:( выигрыши wi считаются положительны). Эти задачи решаются точно так же, как задачи с аддитивным критерием, с той единственной разницей, что в основном уравнении (1.2) вместо знака «плюс» ставится знак «умножения»

Можно рассматривать непрерывный вариант метода ДП.

Метод динамического программирования

базируется на методе вариационного исчисления, при выводе его основных соотношений используется следующий принцип оптимальности.