И. Н. Булгакова, Ю. В. Бондаренко, Г. Д. Чернышова

И.Н.Булгакова, Ю.В.Бондаренко, Г.Д.Чернышова

Теория игр и

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

 

Методическое пособие

 

 

ВОРОНЕЖ

СОДЕРЖАНИЕ

§ 1. Основные понятия исследования операций. Математическая модель операции
§ 2. Понятие игры. Классификация игр……………………………...
§ 3. Антагонистические игры в нормальной форме………………..
3.1 Определение антагонистической игры в нормальной форме. Матричные игры…………………………………………………………..
3.2 Ситуация равновесия в смешанных стратегиях: понятие и существование……………………………………………………………..
3.3 Смешанное расширение игры………………………………………..
3.4 Методы решения матричных игр…………………………………….
3.5 Существование оптимальных стратегий. Теорема фон Неймана-Нэша……………………………………………………………………….
3.6 Доминирование стратегий……………………………………………
3.7. Игры с частными случаями платежных матриц
§ 4. Игры в условиях неопределенности и риска (игры с природой)
§ 5. Позиционные игры
§ 6. Задачи теории расписаний.
6.1 Задача о двух станках
6.2 Алгоритм Джонсона
§ 7. Задача о назначениях	.
7.1 Задача о назначениях, вербальная и математическая модели
7.2 Венгерский метод
§ 8. Задача коммивояжера
8.1 Задача коммивояжера, вербальная и математическая модели.
8.2 Метод ветвей и границ.
§ 9. Оптимизация на сетях
9.1 Задачи о кратчайшем и критическом пути
9.2 Задача о максимальном потоке
§ 10. Модели управление запасами
§ 11. Модели сетевого планирования и управления проектами
Задания для самостоятельной работы
Список литературы………………………………………………………

Основные понятия исследования операций. Математическая модель операции

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

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

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

Оперирующей стороной (ОС) называется совокупность лиц, которые стремятся в данной операции к поставленной цели.

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

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

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

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

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

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

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

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

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

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

(1.1)

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

С учетом изложенного получаем математический объект , где:

X - множество (пространство) допустимых стратегий, ;

Y - множество значений неконтролируемых факторов, ;

W - функция, определенная на прямом произведении .

Этот объект называется статической (нормальной) формой математической модели операции.

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

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

- Для построения математической модели операции в общем случае рекомендуется выполнить следующую последовательность работ:

- изучение условий задачи и определение важнейших факторов;

- выделение известных и неизвестных параметров;

- выявление управляемых и неуправляемых факторов;

- анализ информации о значениях параметров и дополнение условий задачи недостающими сведениями;

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

- определение принципа оптимальности (в общем случае весьма нетривиальный и ответственный этап) и формулировка задачи.

Примеры

 

Пример 1. Рассмотрим следующую игру. Игроки выбирают одновременно одно из трех чисел: «один», «два», «три». Выигрыш Р1 (проигрыш Р2) положителен и равен названному числу, если он правильно угадал выбор второго игрока и 0 в противном случае.

 

В данной задаче , а матрица игры имеет следующий вид:

.

Пример 2. Оборона города (игра полковника Блотто).

Полковник Блотто (игрок Р1) имеет 4 полка, а его противник (Р2) – 3 полка. Противник защищает 2 позиции. Позиция будет занята полковником Блотто, если на ней наступающие полки окажутся в численном превосходстве.

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

Если число полков Р1 и Р2 на позиции одинаково, то имеет место ничья и никто ничего не получает.

Считая, что суммарный выигрыш Р1 равен сумме его выигрышей по двум позициям и игра является антагонистической, сформировать матрицу игры.

 

Решение

Стратегией первого игрока является пара , , где – число полков, отправленных Блотто на позицию 1, – на позицию 2. Тогда . Аналогично для второго игрока . Матрица игры имеет следующий вид:

.

Рассмотрим формирование элементов матрицы на примере – величины выигрыша Р1 при условии, что он предпринял стратегию (4,0), а второй игрок стратегию (1,2). На первой позиции полки полковника Блотто оказываются в численном превосходстве (4>1), поэтому он выигрывает число полков противника (1) плюс 1 за захват позиции (всего выигрыш по позиции равен 2). На второй позиции наоборот, полки Р2 оказываются в превосходстве (0<2) и тогда Блотто теряет все свои полки на этой позиции (0) и 1 за поражение на позиции (всего выигрыш по позиции равен -1). Суммарный выигрыш Блотто по двум позициям: . Аналогично формируются остальные элементы матрицы.

 

3.2 Ситуация равновесия в чистых стратегиях: понятие и существование

 

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

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

 

Замечание 1. Для матричной игры , .

 

Лемма 1. Для любой антагонистической игры справедливо: .

 

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

 

Определение 3. В антагонистической игре ситуация называется ситуацией равновесия или седловой точкой, если выполнены следующие неравенства:

, для всех стратегий , .

 

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

 

Замечание 2. В матричной игре ситуация называется ситуацией равновесия или седловой точкой матрицы А, если выполняются неравенства: , , . Другими словами, элемент является одновременно минимумом в строке и максимумом в столбце .

 

Свойства ситуаций равновесия

Пусть , – ситуации равновесия в антагонистической игре . Тогда справедливо следующее:

1) ;

2) , – ситуации равновесия.

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

 

Теорема 1. Для того, чтобы в игре существовала ситуация равновесия, необходимо и достаточно, чтобы существовали верхняя и нижняя цены игры:

, ,

и выполнялось равенство: .

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

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

Пусть – ситуация равновесия. Докажем, что . Согласно лемме 1, , и поэтому достаточно показать выполнение неравенства .

По определению ситуации равновесия:

, , .

Тогда , а следовательно, .

Так как , то

. (*)

Аналогично:

. (**)

Из (*), (**) следует: , что и требовалось доказать.

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

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

Пусть и ;

и .

Докажем, что – ситуация равновесия.

;

.

Тогда, так как правые части неравенств равны по условию, то

,

и

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

 

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

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

 

Лемма 2. (Лемма о масштабе)

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

 

Примеры

Пример 1. Найти верхнюю и нижнюю цены игры и ситуацию равновесия, при условии, что она существует, если матрица имеет вид:

.

Решение

Найдем нижнюю цену игры.

Если Р1 выберет первую стратегию, то он получит гарантированно .

Если Р1 выберет стратегию 2, то он получит гарантированно .

Если Р1 выберет стратегию 3, то он получит гарантированно .

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

Найдем верхнюю цену игры.

Если Р2 выберет первую стратегию, то он проиграет гарантированно не больше .

Если Р2 выберет стратегию 2, то он проиграет гарантированно не больше .

Если Р2 выберет стратегию 3, то он проиграет гарантированно не больше .

Тогда выбором своей стратегии Р2 может проиграть, по крайней мере, не меньше . Так как =1, то равновесием является пара и v= 1.

 

Пример 2. Пусть дана матрица выигрышей игрока P1 . Найти ситуации равновесия.

Решение

В данной игре , , и поэтому игра не имеет ситуации равновесия. Если игрок P1 выбирает свою чистую максиминную стратегию , то игрок P2, выбрав свою минимаксную стратегию , проигрывает только 20 единиц. В этом случае P1 выгодно выбрать стратегию , то есть отклониться от своей максиминной стратегии и выиграть 30. Тогда P2 будет выгодно отклониться от своей чистой минимаксной стратегии и проиграть 10. В свою очередь, игрок P1 должен выбрать свою 2-ю стратегию, чтобы выиграть 40, а P2 ответит выбором 2-й стратегии и т. д.

 

Упражнения к § 3.1. – 3.2

 

№ 1. Найдите верхнюю, нижнюю цену игры, ситуации равновесия (если они существуют) для игр, заданных следующими матрицами:

1) ; 2) ; 3) ;

4) ; 5) .

 

№ 2. В игре Морра с тремя пальцами каждый игрок показывает 1, 2 или 3 пальца одновременно, называя число пальцев, которые покажет его оппонент. Выигрывает тот, кто правильно назовет число пальцев, показанных противником. Выигрыш равен сумме пальцев, показанных обоими игроками. Написать матрицу игры и показать, что она не имеет ситуации равновесия.

 

№ 3. Каждый из двух игроков имеет n рублей. Они хотят получить некоторый предмет стоимостью C>0. Каждый дает за него i рублей () так, чтобы другой не знал, сколько дал первый. Тот, кто предложил больше денег, получает предмет и выплачивает другому игроку ту сумму, которую он сам предлагал. Если оба игрока давали одинаковую цену, то предмет без всякой компенсации отдается одному из партнеров – это решается бросанием монеты. Тогда каждый имеет ожидаемую долю в этом предмете. Напишите матрицу выигрыша и определите, имеет ли она седловую точку.

 

№ 4. (Дискретная игра типа дуэли). Игроки продвигаются навстречу друг другу на n шагов одновременно. После каждого сделанного шага игрок может выстрелить или нет, но во время игры он может выстрелить только один раз. Считается, что вероятность того, что игрок попадет в своего противника, если выстрелит, продвинувшись на k шагов, равна (). Стратегия каждого игрока – принять решение стрелять на i-ом (j-ом) шаге. Выигрыш P1 равен разности вероятностей того, что он попадет в противника, и того, что попадут в него. Написать матрицу игры. Имеются ли ситуации равновесия?

 

№ 5. В системе ПВО объекта могут применяться 3 типа средств поражения воздушной цели (1, 2, 3), которые должны быть распределены между двумя стартовыми установками. У противника (P2) имеется 2 типа самолетов (тип 1, тип 2). Вероятности поражения самолета одним средством сведены в таблицу

	тип 1	тип 2
	0,3	0,5
	0,5	0,3
	0,1	0,6

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

 

№ 6. На каждой из двух торговых баз ассортиментный минимум составляет один и тот же набор из n видов товаров. Каждая база должна поставить в свой магазин только один из этих видов товара. Магазины, обозначим их A и B, конкурируют между собой. Один и тот же вид товара в обоих магазинах продается по одной и той же цене. Однако, товар, поставляемый в магазин B, более высокого качества. Если магазин A завезет с базы товар i -го вида , отличный от товара j -го вида , завезенного в магазин B, то товар i- го вида будет пользоваться спросом и магазин A получит прибыль денежных единиц. Если же в магазины A и B завезены товары одинакового вида i=j, то товар i -го вида в магазине A спросом пользоваться не будет, поскольку такой же товар, по такой же цене, но более высокого качества можно купить в магазине B, и поэтому магазин A понесет убытки по транспортировке, хранению и, возможно, порче товара i -го вида в размере денежных единиц.

Требуется формализовать данную конфликтную ситуацию и построить матрицу игры при n=3.

 

№ 7. Торговый агент должен встретиться с иногородним клиентом и собирается лично вручить ему заказ на 3000 у.д.ед.

Если агент поедет поездом, то потеряет день на работе, который принес бы ему 1500 у.д.ед.

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

 

№ 8. Фирма А производит некоторый сезонный товар, имеющий спрос в течение n единиц времени, и который она может поставить на рынок в один из моментов i .

Для конкурентной борьбы с фирмой А дочерняя фирма В концерна D, не заботясь о собственных доходах, производит аналогичный товар, который поступает на рынок в один из моментов j . Цель фирмы В – разорение фирмы А, после чего, используя капитал концерна D, ей будет легко наверстать упущенное. Единственным законным средством фирмы В в конкурентной борьбе является выбор момента поставки товара на рынок, так как понижение цены на поставляемый товар запрещено определенным соглашением. Для разорения фирмы А фирма В должна минимизировать ее доходы. Пусть технология выпуска товара такова, что чем дольше он находится в производстве, и, следовательно, позже поступает на рынок, тем качество его выше, а реализуется товар только более высокого качества (так как цена на товары разного качества одна и та же). Доход от продажи товара в единицу времени составляет с денежных единиц.

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

 

3.3 Смешанное расширение игры

 

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

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

Рассмотрим матричную игру c матрицей . Обозначим через

– множество чистых стратегий первого игрока; – множество чистых стратегий второго игрока.

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

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

. (1)

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

 

Определение 5. Решением смешанного расширения матричной игры называется такая пара смешанных стратегий , что

, , .

 

Для смешанного расширения игры справедлива лемма о масштабе.

 

Лемма 3. Пусть , – матричные игры, причем , где , (, ). Тогда множества оптимальных стратегий игроков в и совпадают, а .

 

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

 

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

1. Пусть – математическое ожидание выигрыша первого игрока в игре с ценой v. Необходимым и достаточным условием оптимальности векторов , для P1 и Р2 соответственно является выполнение следующих неравенств:

.

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

, .

При этом – математическое ожидание выигрыша первого игрока (проигрыша второго) при условии, что Р1 выбрал свою i -ю чистую стратегию, а Р2 смешанную ;

– математическое ожидание выигрыша первого игрока (проигрыша второго) при условии, что Р1 выбрал свою смешанную стратегию , а Р2 чистую стратегию j.

3. Для матричной игры с ценой