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

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

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

Цель – состояние, к которому мы стремимся, реализуя операции.

Операция: статическая и процесс (последовательность операций).

Процесс – последовательность взаимосвязанных операций, направленных на достижение цели.

Оперирующая сторона:

1) лицо, принимающее решение

2) аналитик (предлагает операции);

3) эксперт (представитель, разбирающийся в области задач).

Ресурсы (деньги, люди, приборы, технологии, сырье и т.д.).

Способы действий – способы использования ресурсов для достижения целей.

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

Неконтролируемые факторы делятся на:

1) детерминированные – факторы, значение которые известны и каждое конкретное действие приводит к конкретному результату;

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

3) неопределенные:

· неопределенности, связанные с действиями разумной стороны, имеющей свои ресурсы, цели;

· природные неопределенности (расположение нефтяных пластов), проявление в том, что они недостаточно изучены;

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

Классификация некоторых факторов позволяет разделить задачи принятия решения на 3 класса:

1) Детерминированные задачи (конкретное решение приводит к конкр. рез-ту, который может быть вычислен);

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

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

Понятие рациональности и эффективности, их соотношение.

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

Рациональность:

- действия (инструментальная);

- целей (аксиопотическая) – вопрос оценки цели с точки зрения разумности, гуманистичности;

Исследование операций (Саати) –

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

 

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

 

Исследование операций – это постановка задач и построение математических моделей, на основе которых находятся и обосновываются решения.

Разделяют аспекты:

1) теоретический (построение моделей, поиск решений, анализ решений);

2) практический (подстройка моделей и решений под проявление конкретных внешних и внутренних условий и внедрение решений);

«Делать нужно не то. Что хочет заказчик, а то, что ему необходимо».
3. Понятие системы, сложные системы. Системный анализ и исследование операций.

 

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

Система – целостное множество элементов, взаимодействующих между собой для достижения целей.

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

Большая (сложная) система – эта система, которая превосходит по сложности возможность исследования в некоторых аспектах, важных для принятия решения.

ЭМЕРДЖЕНТНОСТЬ — качество, свойства системы, которые не присущи ее элементам в отдельности, а возникают благодаря объединению этих элементов в единую, целостную систему.

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

В сист. анализе существует два подхода:

· описательный (дескриптивный) ориентирован на описание системы;

· нормативный ориентирован на поиск решения по уравнению системы (которая хотя бы от части является управляемой).

Исследование операций – это постановка задач и построение мат. моделей, на основе которых находится и обосновывается решение.

Разделяют аспекты:

· теоретический (построение моделей, поиск решения, анализ решения);

· практический (подстройка модели и решения под проявление конкретных внешних и внутренних условий и внедрение решений).

 

Метод абсолютных уступок.

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

; ; целесообразен, если суммарные улучшения по всем превосходят соммарные ухудшения по

, при этом критерии должны быть нормированы!!!.

Частное проявление этой схемы: 1) если если учитываем значимость цели, вводим коэффициент значимости :

2)

Недостатком является доминирование локальных критериев с большими абсолютными значениями эффективности (за счет коэффициента значимости это можно ослабить)

Метод относительных уступок

Сначала строется абсолютное изменение а потом на их базе строятся относительные изменения. если

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

“+”- нормировка критериев не нужна.

Частные случаи:

1)

2) если нельзя перемножать то

3) если хотим учесть значимость то введем степенную функцию:

4) для логарифмической схемы с учетом значимости:

“-“ – значимости критериев остаются проблемой: лучше иметь 1% от миллиона чем 10% от тысячи.

Метод квазиравенста

 

ВОЗ на множестве объектов

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

Пример:

 

 

Вопрос распределения инвестиций

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

ВОЗ на множестве условий

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

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

Локальные оценки обычно однородны.

ВОЗ на множестве этапов

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

Локальные оценки однородны.

 

Примеры:

 

 

Самолет:

• Взлет
• Крейсерский полет
• Посадка

 

ВОЗ на множестве постановок

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

Эффективность любой постановки характеризуется локальным критерием, эффективность системы в целом – глобальным критерием.

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

Пример:

 

 

(задачи в условиях неопределенности пересекаются с этим ВОЗ)

СМО, типы задач.

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

СМО без очереди.

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

Вероятность простоя каналов обслуживания

.

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

Р = = .

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

P =1- P =1- .

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

A = λ Р .

Среднее число занятых каналов

P _обсл.

Доля каналов, занятых обслуживанием, составляет

q= .

Замкнутые СМО.

В замкнутой СМО циркулирует одно и то же конечное число потенциальных требований. Пока потенциальное требование не реализовалось в качестве требования на обслуживание, считается, что оно находится в блоке задержки. В момент реализации требование поступает в саму систему. Пусть n - число каналов обслуживания, s - число потенциальных заявок, n < s, λ - интенсивность потока заявок каждого потенциального требования, μ -интенсивность обслуживания,

ρ = .

Вероятность простоя системы определяется формулой

Р ₀= .

Финальные вероятности состояний системы

P_k = при k < n, P_k = при .

Среднее число занятых каналов:

= P ₁+2 P ₂+…+ n (P_n + P_{n +1}+…+ P_s)

или

= P ₁+2 P ₂+…+(n -1) P_{n -1}+ n (1- P ₀- P ₁-…- P_{n -1})_.

Абсолютная пропускная способность системы:

A= .

Среднее число заявок в системе

М = s - = s - .

 

52. СМО с неодинаковыми приборами.

СМО с приоритетами.

Абсолютные приоритеты

Такие заявки прерывают обслуживание заявок более низкого приоритета.

Wk =∑ ni =1 ρi ⋅ tk 1−∑ k −1 i =1 ρi +∑ ki =1 ρiti ⋅(1− ν 2 i)2⋅(1−∑ k −1 i =1 ρi)⋅(1−∑ ki =1 ρi)

W 1= ρ 1⋅ t 11− ρ 1=0.3⋅11−0.3=0.422

W 2= ρ 1⋅ t 21− ρ 1+ ρ 1⋅ t 1+ ρ 2⋅ t 2(1− ρ 1)⋅(1− ρ 1− ρ 2)=0.3⋅21−0.3+0.3⋅1+0.5⋅2(1−0.3)⋅(1−0.8)=10.14

 

Многофазные СМО.

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

λ₁ СМО₁СМО₂СМО₃

Каждая i-я СМО имеет характеристику m _i и у всех СМО_iN_i®¥.

СМО без потерь означает, что все заявки проходят все фазы, т.е. l_i=l₁, i =1,2... n. Имея данные для каждого СМО_i - l _i, m _i- можно рассчитать характеристики каждого узла как одноканальных СМО с бесконечной очередью.

Характеристик многофазной СМО рассчитываются в соответствии со следующими выражениями:

,

 

Cети СМО представляют собой множество СМО (узлы сети), потоки заявок обслуживаются в нескольких узлах. Последовательность прохождения заявок в сети определяется топологией сети, которая задается вероятностями перехода заявок от одного узла к другому .

 

Будем рассматривать пуассоновские сети СМО, т.е. из источника поступает пуассоновский поток заявок, а время обслуживания в каждом узле i распределено по экспоненциальному закону.

СМО в каждом узле - одноканальная с бесконечной очередью.

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

Анализ сетей СМО заключается в расчете потоков заявок в каждом узле . После чего можно рассчитать характеристики СМО в каждом узле .

 

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

1. Конфликтные ситуации

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

оптимизационную задачу и найти ее решение.

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

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

Ситуация, в которой имеется несколько участников с различными интересами, называется

конфликтной ситуацией или конфликтом.

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

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

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

 

Основные элементы

Будем рассматривать парную игру, в которой участвуют два игрока А и В с противоположными интересами. Под «игрой» будем понимать мероприятие, состоящее из ряда действий сторон А и В. Чтобы игра могла быть подвергнута математическому анализу, должны быть точно сформулированы правила игры. Под «правилами игры» разумеется система условий, регламентирующая возможные варианты действий обеих сторон, объем информации каждой стороны о поведении другой, последовательность чередования «ходов» (отдельных решений, принятых в процессе игры), а также результат или исход игры, к которому приводит данная совокупность ходов. Этот результат (выигрыш или проигрыш) не всегда имеет количественное выражение, но обычно можно, установив некоторую шкалу измерения, выразить его определенным числом. Например, в шахматной игре выигрышу можно условно приписать значение +1, проигрышу –1, ничьей 0.

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

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

При этом сторона А («мы») будет всегда рассматриваться как «выигрывающая», а сторона В («противник») как «проигрывающая». Это формальное условие, очевидно, не означает какого-либо реального преимущества для первого игрока; легко видеть, что оно заменяется противоположным, если знак выигрыша изменить на обратный.

Развитие игры во времени мы будем представлять состоящим из ряда последовательных этапов или «ходов». Ходом в теории игр называется выбор одного из предусмотренных правилами игры вариантов. Ходы делятся на личные и случайные. Личным ходом называется сознательный выбор одним из игроков одного из возможных в данной ситуации ходов и его осуществление. Пример личного хода — любой из ходов в шахматной игре. Выполняя очередной ход, игрок делает сознательный выбор одного из вариантов, возможных при данном расположении фигур на доске. Набор возможных вариантов при каждом личном ходе регламентирован правилами игры и зависит от всей совокупности предшествующих ходов обеих сторон.

Случайным ходом называется выбор из ряда возможностей, осуществляемый не решением игрока, а каким-либо механизмом случайного выбора (бросание монеты, игральной кости, тасовка и сдача карт и т.п.). Например, сдача первой карты одному из игроков в преферанс есть случайный ход с 32 равновозможными вариантами. Чтобы игра была математически определенной, правила игры должны для каждого случайного хода указывать распределение вероятностей возможных исходов.

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

Игры классифицируются не только по характеру ходов (личные, случайные), но и по характеру и по объему информации, доступной каждому игроку относительно действий другого. Особый класс игр составляют так называемые «игры с полной информацией». Игрой с полной информацией называется игра, в которой каждый игрок при каждом личном ходе знает результаты всех предыдущих ходов, как личных, так и случайных. Примерами игр с полной информацией могут служить шахматы, шашки, а также известная игра «крестики и нолики».

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

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

Игрок, выбравший стратегию, может теперь не участвовать в игре лично, а заменить свое участие списком правил, которые за него будет применять какое-либо незаинтересованное лицо (судья). Стратегия может быть также задана машине-автомату в виде определенной программы. Именно так в настоящее время играют в шахматы ЭВМ. Чтобы понятие «стратегии» имело смысл, необходимо наличие в игре личных ходов; в играх, состоящих из одних случайных ходов, стратегии отсутствуют.

В зависимости от числа возможных стратегий игры делятся на «конечные» и «бесконечные». Конечной называется игра, в которой у каждого игрока имеется только конечное число стратегий. Конечная игра, в которой игрок А имеет m стратегий, а игрок В — n стратегий, называется игрой mxn.

 

Или

 

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

 

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

56. Матричные игры с седловой точкой. Оптимальные стратегии. (2 команды, конечная, с неполной информацией, 1 ход MINMAX & MAXMIN)

Матричные игры и понятие седловой точки. Рассмотрим более подробно антагонистические игры и их основные свойства. Удобным способом задания игры двух участников с нулевой суммой является платежная матрица. Отсюда, кстати, происходит еще одно их название — матричные игры. Каждый элемент платежной матрицы а_ij содержит числовое значение выигрыша игрока I (проигрыша игрока II), если первый применяет стратегию i, а второй — стратегию j. Термины выигрыш и проигрыш следует понимать в широком смысле, т. к. они могут принимать отрицательные значения и с житейской точки зрения означать противоположное. Нетривиальность задачи прежде всего заключается в том, что каждый из игроков делает свой выбор, не зная о выборе другого, что существенно осложняет процесс оптимизации выбираемой стратегии.

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

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

Более сложная и содержательная платежная матрица может быть получена, если несколько модифицировать предложенную игру. Допустим, что оба участника имеют право загадывать числа от 1 до 4, что составляет их соответствующие стратегии. В случае, если результат сложения задуманных чисел будет четным, то второй игрок выплачивает первому получившуюся сумму, а если нечетным, то первый — второму. Запишем платежную матрицу для такой игры:

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

Как уже отмечалось, важнейшим в теории игр является вопрос об оптимальности решения (выбора стратегии) для каждого из игроков. Проанализируем с этой точки зрения некоторую матричную игру, для которой задана платежная матрица А =║ a_ij ║ _{m x n} . При выборе игроком I стратегии i его гарантированный доход независимо от действий игрока II составит min a_i,j. Поскольку он может выбирать i самостоятельно, то целесообразно этот выбор сделать таким, чтобы он при любой стратегии противника максимизировал величину гарантированного дохода, т. е. обеспечивал получение max (min a_i,j). Такой принцип выбора стратегии получил название «принцип максимина». С другой стороны, аналогичные рассуждения могут быть проведены по поводу действий второго игрока. Его наибольший проигрыш при выборе стратегии j составит max a_i,j, и, следовательно, ему следует выбирать стратегию так, чтобы минимизировать величину проигрыша при любых действиях соперника, т. е. обеспечить min (max a_i,j).в этом суть принципа минимакса.

Можно доказать справедливость следующего соотношения:

Однако очевидный интерес представляет ситуация, при которой значение выигрыша (платежа), получаемого игроком I при выборе им максиминной стратегии, равно платежу (проигрышу) II-го игрока при минимаксной стратегии

В этом случае говорят, что игра имеет седловую точку. Совпадение значений гарантированных выигрышей игроков при максиминной и минимаксной стратегии означает возможность достижения в игре некоторого оптимального (стабильного, равновесного) состояния, от которого невыгодно отклоняться ни одному из участников. Понятие «оптимальность» здесь означает, что ни один разумный (осторожный) игрок не стремится изменить свою стратегию, так как его противник, в принципе, сможет выбрать такую стратегию, которая даст худший для первого результат. Стратегии i* и j *, образующие седловую точку, называются оптимальными, а значение v = a_i*j* называют ценой игры. Тройка (i*, j*, v) считается решением матричной игры с седловой точкой.

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