Решение матричной игры графическим методом

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

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

графическим методом.

Решение. В данном случае = 6, = 8, т.е., а поэтому для определения оптимальных смешанных стратегий игроков составляем задачи

(1)

(2)

Поскольку одна из задач содержит две переменные, то, решим ее графически, находим: =1/27,=1/9,=4/27.Используя формулы , получаем: 27/4,,.

Для определения оптимальной смешанной стратегии найдем сначала решение двойственной задачи. В оптимальном плане задачи (2) и ,поэтому оба ограничения двойственной задачи (1) ее оптимальным планом обращаются в равенства. Кроме того, значениями и второе ограничение задачи (2) обращается в строгое неравенство. Следовательно, в оптимальном плане задачи (1) соответствующая ему вторая переменная равна нулю, т. е. =0. Учитывая сказанное, для определения и получаем уравнения и , совместное решение которых дает =3/54, = 5/54. Используя формулы , определяем =3/8, =0,=5/8. Итак, решение игры найдено:

.

Решение игр с природой по различным критериям

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

			…
			…
			…
	…	…	…	…
			…

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

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

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

			…
			…
			…
	…	…	…	…	…
			…

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

.

Если игроку А представляются в равной мере правдоподобными все состояния природы, то иногда полагают и, учитывая "принцип недостаточного основания" Лапласа, оптимальной считают чистую стратегию , обеспечивающую

.

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

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

Оптимальной по критерию Гурвица считается чистая стратегия , найденная из условия

,

где принадлежит интервалу (0; 1) и выбирается из субъективных соображений. При =1 критерий Гурвица превращается в критерий Вальда, при = 0 — в критерий крайнего оптимизма, когда рекомендуется выбирать стратегию, обеспечивающую самый большой выигрыш. В связи с этим критерий Гурвица называют критерием пессимизма-оптимизма. При 0 < < 1 получается нечто среднее между тем и другим. Чем ответственнее ситуация, чем больше стремление подстраховаться в ней и не рисковать без должных оснований, тем ближе к единице выбирается коэффициент пессимизма .

Сетевое планирование и управление

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

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

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

• действительной, т.е. требующей затрат времени;

• фиктивной, т.е. формально не требующей затрат времени.

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

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

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

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

Рис.1. Кодирование работы

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

При построении сетевого графика необходимо следовать следующим правилам:

• длина стрелки не зависит от времени выполнения работы;

• стрелка может не быть прямолинейным отрезком;

• для действительных работ используются сплошные, а для фиктивных – пунктирные стрелки;

• каждая операция должна быть представлена только одной стрелкой;

• между одними и теми же событиями не должно быть параллельныхработ, т.е. работ с одинаковыми кодами;

• следует избегать пересечения стрелок;

• не должно быть стрелок, направленных справа налево;

• номер начального события должен быть меньше номера конечного события;

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

• не должно быть тупиковыхсобытий (т.е. не имеющих последующих событий), кроме завершающего;

• не должно быть циклов (рис.7.2).

Рис.2. Недопустимость циклов

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

• описанием предполагаемого проекта. В этом случае необходимо самостоятельно разбить его на отдельные работы и установить их взаимные связи;

• списком работ проекта. В этом случае необходимо проанализировать содержание работ и установить существующие между ними связи;

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

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

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

Если, согласно условию, несколько работ имеют общее начальное и общее конечное события, то они являются параллельными, имеют одинаковый код, что недопустимо. Для устранения параллельности работ вводят дополнительное событие и фиктивную работу (которой в реальности не соответствует никакое действие) таким образом, чтобы конечные события работ различались (рис.7.3.).

Рис.3 Устранение параллельности двух работ

Пример

Постройте сетевую модель, включающую работы A, B, C, ...,L, которая отображает следующее упорядочение работ:

1. A,BиC– исходные операции проекта;

2. AиBпредшествуютD;

3. BпредшествуетE,FиH;

4. FиCпредшествуетG;

5. EиHпредшествуютIиJ;

6. C,D,FиJпредшествуютK;

7. KпредшествуетL.