3. Среди оставшихся невычеркнутыми элементов матрицы С второй столбец содержит единственный 0 (c₄₂=0). Поэтому считаем, что x₄₂=1, а все остальные элементы 4-ой строки и 2-го столбца матрицы X равны 0. В матрице С исключаем из дальнейшего рассмотрения 4-ю строку и 2-ой столбец.

4. Среди оставшихся невычеркнутыми элементов матрицы С нет строк или столбцов, содержащих единственный 0. Поэтому выбираем любой нулевой элемент (например, c₂₄=0) и считаем, что x₂₄=1, а все остальные элементы 2-ой строки и 4-го столбца матрицы X равны 0. В матрице С исключаем из дальнейшего рассмотрения 2-ю строку и 4-ый столбец.

5. Т.к. c₃₅=0, то x₃₅=1.

Итак, оптимальное решение задачи о назначениях:

Z_min= 5 + 11 + 2 + 4 + 0 = 22.

Решим задачу о назначениях с использованием средств MS Excel.

Для решения нашей задачи создадим в Excel книгу с именем «Решение задачи о назначениях». Подготовим данные на листе.

Сначала определим ячейки, в которые будут вводиться элементы матрицы С. Пусть это будут ячейки B3:F7. Заполним их и оформим заголовки строк и столбцов. Определим ячейки, куда будет помещен результат решения. Пусть это будут ячейки B12:F17, сделаем у них заголовки. В этих ячейках нет данных, их должен будет рассчитать Excel, они выделены цветом. Заведем строку 18 для целевой функции. Цветом выделена ячейка, в которой будет находиться значение целевой функции для найденного оптимального решения.

В ячейки G12:G16 введем нахождение сумм неизвестных по строкам, в ячейки B17:F17 - нахождение сумм неизвестных по столбцам, в ячейку D18 - формулу для нахождения целевой функции.

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

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

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

Результаты поиска решений:

Получили . Решение совпадает с найденным венгерским методом.

Интерпретация решения:

Первый филиал должен выпускать 1-ый вид изделий, второй филиал должен выпускать 4-ый вид изделий, третий филиал должен выпускать 5-ый вид изделий, четвертый филиал должен выпускать 2-ой вид изделий, пятый филиал должен выпускать 3-ий вид изделий. При таком распределении себестоимость выпуска изделий будет минимальна и составит 22 у.е.

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

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

Пример 2

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

Составим математическую модель задачи:

Пусть

i = 1,2,3,4,5, j = 1,2,3,4

Каждый станок должен выполнять не более одной работы

Каждая работа должна выполняться только одним станком:

Условие неотрицательности переменных:

x_ij 0, i = 1,2,3,4,5, j = 1,2,3,4

Суммарная производительность:

Z = 5x₁₁ + 11x₁₂ + 6x₁₃ + 11x₁₄ + 10x₂₁ + 11x₂₂ + 9x₂₃ + 11x₂₄+ 7x₃₁ + 8x₃₂ +6x₃₃ + + 8x₃₄ + 6x₄₁ + 4x₄₂ + 3x₄₃ + 7x₄₄+ 4x₅₁ + 2x₅₂ + 5x₅₄ max

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

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

Этап 1

Этап 2

Этап 3

Порядок составления матрицы X:

1. Т.к. в 5-ом столбце преобразованной матрицы имеется единственный элемент равный 0 (c₅₅=0), то x₅₅=1, а все остальные элементы 5-го столбца и 5-ой строки матрицы X равны 0. В матрице С исключаем из дальнейшего рассмотрения 5-ю строку и 5-ый столбец.

2. Среди оставшихся невычеркнутыми элементов матрицы С нет строки или столбца, содержащих единственный 0. Поэтому, выберем любой 0, например, c₁₂=0. Поэтому считаем, что x₁₂=1, а все остальные элементы 1-ой строки и 2-го столбца матрицы X равны 0. В матрице С исключаем из дальнейшего рассмотрения 1-ю строку и 2-ой столбец.

3. Среди оставшихся невычеркнутыми элементов матрицы С нет строки или столбца, содержащих единственный 0. Поэтому, выберем любой 0, например, c₂₁=0. Поэтому считаем, что x₂₁=1, а все остальные элементы 2-ой строки и 1-го столбца матрицы X равны 0. В матрице С исключаем из дальнейшего рассмотрения 2-ю строку и 1-ый столбец.

4. Т.к. в 3-ем столбце преобразованной матрицы имеется единственный элемент равный 0 (c₃₃=0), то x₃₃=1, а все остальные элементы 3-го столбца и 3-ей строки матрицы X равны 0. В матрице С исключаем из дальнейшего рассмотрения 3-ю строку и 3-ий столбец.

5. Т.к. c₄₄=0, то x₄₄=1.

Итак, оптимальное решение задачи о назначениях:

Z_max= 11 + 10 + 6 + 7 = 34.

Интерпретация решения:

Первый станок должен выполнять 2-ю работу, второй - 1-ю работу, третий станок - 3-ю работу, четвертый станок - 4-ю работу, пятый станок не будет выполнять никакой работы. При таком распределении работ производительность будет максимальна и составит 34 единицы.



2.2 Теория игр

2.2.1 Основные понятия

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

Примеры конфликтных ситуаций:

- любая ситуация в ходе военных действий;

- планирование военных операций;

- конкурентная борьба в экономике;

- выборы в парламент;

- салонные игры (например, шашки, шахматы, карты).

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

· Для математического анализа конфликтной ситуации отбрасывают второстепенные факты и строят формализованную модель конфликтной ситуации - игру. Конфликтные стороны называются игроками. Игра ведется по определенным правилам. Правила игры устанавливают возможные действия игроков, объём сведений каждой стороны о поведении другой, результат, к которому приводит каждая совокупность ходов. Правила определяют так же конец игры, когда больше ходов делать не разрешается. Каждый игрок делает ход - выбор одного из вариантов действий, предусмотренных правилами игры. Ходы бывают личные и случайные. Личный ход - сознательный выбор игроком допустимого действия. Случайный ход - выбор допустимого действия с помощью механизма случайного выбора (например, подбрасывания монеты) и его осуществление. Будем считать, что в конце игры любой игрок получает выигрыш. Можно провести классификацию игр:

- По числу игроков:

· одного лица (например, пасьянс);

· двух лиц - парная игра (например, шахматы);

· n лиц - множественная (они делятся на коалиационные, когда несколько лиц могут заключить союз, и бескоалиационные).

- По количеству и характеру ходов:

· с полной информацией (например, шахматы);

· с неполной информацией (например, карты. Большинство игр - с неполной информацией).

- По количеству ходов:

· конечные (у каждого игрока имеется конечное количество ходов);

· бесконечные (например, дуэль).

- По выигрышу:

· с нулевой суммой (парная игра, в которой выигрыш одной стороны равен проигрышу другой);

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

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

Далее будем рассматривать парные игры m n с нулевой суммой.

Пусть имеется игра двух игроков A и B. Пусть у игрока A имеется m стратегий A₁, A₁,…, A_m, а у игрока B имеется n стратегий B₁, B₁,…, B_n. Пусть a_ij - выигрыш (положительный или отрицательный) игрока A при выборе стратегии A_i игроком A и стратегии B_j игроком B. Если ходы случайные, то a_ij - математическое ожидание выигрыша игрока A. Платёжной матрицей или, матрицей игры называется матрица

B A	B1	B2	…	Bn
A1	a11	a12	…	a1n
A2	a21	a22	…	a2n
…	…	…	…	…
Am	am1	am2	…	amn

Пример 1. (Игра "поиск").

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

Стратегии игроков:

игрок A: A₁ - спрятаться в убежище № 1,

A₂ - спрятаться в убежище № 2;

игрок B: B₁ - искать в убежище № 1,

B₂ - искать в убежище № 2;

Платежная матрица:

B A	B1	B2
A1	-1	1
A1	1	-1

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

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

2.2.2 Нижняя и верхняя цены игры. Принцип минимакса

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

B A	B1	B2	…	Bn	min в строке
A1	a11	a12	…	a1n	1
A2	a21	a22	…	a2n	2
…	…	…	…	…
Am	am1	am2	…	amn	m
max в столбце	1	2		n

Величина называется нижней ценой игры или максимином).

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

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

Теорема 1 Для игры двух лиц с нулевой суммой .

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

Пример 2.

Найдем нижнюю и верхнюю цены игры из примера 1.

B A	B1	B2	min в строке
A1	-1	1	-1
A2	1	-1	-1
max в столбце	1	1	= -1 = 1

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

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

Пример 3

Двое играют в следующую игру: одновременно выбрасывают 1, 2 или 3 пальца. Выигрывает тот, у кого больше пальцев (выигрыш равен разности выброшенных пальцев). Если оба выбросили одинаковое количество пальцев, то никто не выиграл. Платежная матрица:

B A	B1	B2	B3	min в строке
A1	0	-1	-2	-2
A2	1	0	-1	1
A3	2	1	0	0
max в столбце	2	1	0	= 0 = 0

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

2.2.3 Решение игр в смешанных стратегиях

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

Смешанной стратегией игрока A называется набор вероятностей , где p₁ + p₂ +… + p_m = 1, с которыми он чередует свои стратегии A₁, A₁,…, A_m. Аналогично определяется смешанная стратегия игрока B как набор где q₁ + q₂ +… + q_n = 1. В этом случае выигрыш А определяется как (математическое ожидание).

Теорема 2 (Фон-Неймана)

Для любой конечная игра m n двух лиц существуют смешанные стратегии игрока А и и игрока В, что для любых других стратегий и выполняется неравенство:

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

Теорема 3 (о цене игры)

Цена игры удовлетворяет неравенству .



2.2.4 Решение матричных игр 2х2 в смешанных стратегиях

Игра 2х2 - наиболее простой случай конечных игр. Рассмотрим игру, не имеющую седловой точки, с платежной матрицей

	В1	В2
А1	a11	a12
А2	a21	a22

Пусть и - смешанные стратегии игроков. Найдем оптимальные смешанные стратегии игроков. Если игрок В придерживается стратегии В₁, то средний выигрыш А составит . Если игрок В придерживается стратегии В₂, то средний выигрыш А составит . По свойству оптимальных смешанных стратегий эти средние выигрыши должны совпадать и быть равными цене игры. Получаем систему:

Решаем систему

Аналогично, составляем систему для игрока В:

Решая систему, находим:

Цена игры

Решение игры 2х2 можно найти так же геометрически. Для этого на оси абсцисс отложим отрезок А₁А₂ длиной 1. Левый конец отрезка (p=0) соответствует стратегии А₁, правый - стратегии А₂. Промежуточные точки отрезка соответствуют смешанным стратегиям первого игрока. Причем расстояние от промежуточной точки отрезка до правого края - это вероятность p₂ стратегии А₂, а расстояние до левого края - вероятность p₁ стратегии А₁. Через концы отрезка А₁А₂ проведем прямые, перпендикулярные оси абсцисс, на них будем откладывать выигрыши при стратегиях А₁ и А₂ соответственно. Если игрок В применяет стратегию В₁, то выигрыши первого игрока при стратегии А₁ составляет a₁₁, а при стратегии А₂ составляет a₂₁. Отложим эти выигрыши на перпендикулярах и соединим полученные точки прямой В₁В₁. Если игрок А применяет смешанную стратегию, то его выигрышу соответствует некоторая точка на отрезке В₁В₁. Аналогично строим отрезок В₂В₂, соответствующий применению вторым игроком стратегии В₂. В соответствии с принципом минимакса ломаная В₁NВ₂ - нижняя граница выигрыша, получаемого игроком А. Точка N, в которой выигрыш максимален, определяет цену игры и ее решение. Для нахождения оптимальной стратегии игрока А достаточно составить уравнения прямых и найти точку пересечения.

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

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

Аналогично можно решить игру с матрицей mxn. В этом случае строят верхнюю границу выигрыша и на ней определяют минимум.

Пример 4

Игра задана платежной матрицей .

1) Решить игру аналитически.

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

Решение:

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

B A	B1	B2	min в строке
A1	10	7	7
A2	8	11	8
max в столбце	10	11	= 8 = 10

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

Найдем аналитически оптимальную стратегию игрока А и соответствующую цену игры .

Так как - оптимальная, то она должна гарантировать средний выигрыш игроку А, равный цене игры, при любом поведении игрока В:

для стратегии В₁: ;

для стратегии В₂: .

С учетом того, что сумма вероятностей смешанной стратегии равна 1, получаем систему уравнений:

Вычтем из первого уравнения второе: или . Значит:

Итак:, = 9.

Аналогично получаем систему для нахождения смешанной стратегии игрока В.

Вычтем из первого уравнения второе: Откуда, подставим в первое уравнение (Вместо подставим найденное значение для игрока А

= 9):

Итак:.

Ответ: , .

2. Проведем моделирование результатов решения с помощью таблицы равномерно распределенных случайных чисел. Для 30 партий хватит 60 чисел, на основе которых будут выбираться стратегии игроками. Используемые случайные числа сгенерированы в MS Excel функцией =СЛЧИС(). В приложении достаточно много чисел, но использовать для моделирования можно любые 60, выбранные произвольно с любого места таблицы. Выберем 60 чисел:

0,02988	0,12558	0,25974	0,17641	0,00937	0,52264	0,08086	0,84858	0,99427	0,49452
0,61109	0,49042	0,61076	0,65834	0,25579	0,80641	0,07675	0,84419	0,18268	0,29702
0,76606	0,95854	0,20704	0,45154	0,27367	0,56261	0,30037	0,96485	0,47252	0,55084
0,73868	0,56421	0,07183	0,99420	0,11184	0,80524	0,42897	0,45031	0,05350	0,67078
0,94483	0,25710	0,39190	0,72491	0,88888	0,03791	0,50773	0,63034	0,94091	0,80165
0,41647	0,88664	0,83519	0,46930	0,39285	0,34159	0,77252	0,65987	0,48750	0,79735
0,51314	0,22625	0,06211	0,39299	0,84336	0,80859	0,52694	0,73306	0,36874	0,93390
0,71749	0,46727	0,18182	0,45791	0,08667	0,58570	0,75495	0,68645	0,90270	0,87484
0,99401	0,82235	0,89122	0,33631	0,42694	0,37053	0,70413	0,59805	0,40425	0,96181
0,41244	0,24426	0,37553	0,09464	0,56208	0,68889	0,59503	0,92378	0,03108	0,33182

Будем выбирать стратегии игроков, используя геометрическое определение вероятности. Так как все случайные числа из отрезка [0; 1], то чтобы стратегия А₁ появлялась примерно в половине случаев, будем ее выбирать если случайное число меньше 0,5; в остальных случаях выбирается стратегия А₂. Аналогично для игрока В. Стратегию В₁ будем выбирать, если соответствующее случайное число меньше 2/30,67, в противном случае выбираем стратегию В₂.

Заполним расчетную таблицу (Средний выигрыш игрока А считаем, как отношение накопленного выигрыша к количеству сыгранных партий):

Номер партии	Случайное число игрока А	Стратегия игрока А А1: < 0,5	Случайное число игрока В	Стратегия игрока В В1: < 0,667	Выигрыш А	Накопленный выигрыш А	Средний выигрыш А (цена игры)
1.	0,029	А1	0,125	В1	10	10	10,000
2.	0,611	А2	0,490	В1	8	18	9,000
3.	0,766	А2	0,958	В2	11	29	9,667
4.	0,738	А2	0,564	В1	8	37	9,250
5.	0,944	А2	0,257	В1	8	45	9,000
6.	0,416	А1	0,886	В2	7	52	8,667
7.	0,513	А1	0,226	В1	10	62	8,857
8.	0,717	А2	0,467	В1	8	70	8,750
9.	0,994	А2	0,822	В2	11	81	9,000
10.	0,412	А1	0,244	В1	10	91	9,100
11.	0,259	А1	0,176	В1	10	101	9,182
12.	0,610	А2	0,658	В1	8	109	9,083
13.	0,207	А1	0,451	В1	10	119	9,154
14.	0,071	А1	0,994	В2	7	126	9,000
15.	0,391	А1	0,724	В2	7	133	8,867
16.	0,835	А2	0,469	В1	11	144	9,000
17.	0,062	А1	0,392	В1	10	154	9,059
18.	0,181	А1	0,457	В1	10	164	9,111
19.	0,891	А2	0,336	В1	8	172	9,053
20.	0,375	А1	0,094	В1	10	182	9,100
21.	0,009	А1	0,522	В1	10	192	9,143
22.	0,255	А1	0,806	В2	7	199	9,045
23.	0,273	А1	0,562	В1	10	209	9,087
24.	0,111	А1	0,805	В2	7	216	9,000
25.	0,888	А2	0,037	В1	8	224	8,960
26.	0,392	А1	0,341	В1	10	234	9,000
27.	0,843	А2	0,808	В2	11	245	9,074
28.	0,086	А1	0,585	В1	10	255	9,107
29.	0,426	А1	0,370	В1	10	265	9,138
30.	0,562	А2	0,688	В2	11	276	9,200

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

Из 30 партий игрок А 18 раз применял стратегию А₁, 12 раз - стратегию А₂. Игрок В 21 раз применял стратегию В₁, 9 раз - стратегию В₂. Частоты использования игроками своих чистых стратегий соответственно равны: p=(18/30;12/30)=(0,6;0,4),q=(21/30;9/30)=(0,7;0,3). Сравнивая с теоретическими оптимальными стратегиями =(0,5; 0,5) и =(0,67; 0,33) можно сделать вывод, что результаты моделирования достаточно близко соответствуют теоретическим вероятностям даже для небольшого количества партий.

Пример 5

Решить графически игру, заданную платежной матрицей .

Решение

Матрица игры имеет размер 2х3, поэтому решение игры будем искать для игрока А. Отложим отрезок единичной длины А₁А₂, каждой точке которого поставим в соответствие некоторую смешанную стратегию первого игрока - (p₁, p₂). В частности, точке А₁ соответствует стратегия А₁, точке А₂ - стратегия А₂.

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

В соответствии с принципом минимакса ломаная В₁NMВ₃ - нижняя граница выигрыша, получаемого игроком А. Точка N, в которой выигрыш максимален, определяет цену игры и ее решение. Для нахождения оптимальной стратегии игрока А достаточно составить уравнения прямых и найти точку пересечения прямых В₂В₂ и В₃В₃.

Уравнение прямой, проходящей через 2 точки (x₁,y₁) и (x₂,y₂) имеет вид . Прямая В₂В₂ проходит через точки (0,3) и (1,5), следовательно, ее уравнение или -2x+y=3. Прямая В₃В₃ проходит через точки (0,11) и (1,2), следовательно, ее уравнение или 9x+y=11. Для нахождения точки пересечения прямых В₂В₂ и В₃В₃ решим систему:

Вычтем из первого уравнения второе, получаем -11x=-8 x=8/11, y=3+2x=49/11. Точка N(8/11,49/11), следовательно, p₂=8/11, p₁=1-8/11=3/11, =49/11.

Таким образом, , при цене игры .

Из рисунка видно, что стратегия В₁ не входит в оптимальную смешанную стратегию, поэтому q₃=0, и мы можем найти оптимальную смешанную стратегию, удалив из платежной матрицы первый столбец. Получаем матрицу , при этом столбцы ее соответствуют активным стратегиям В₂, В₃.

Так как - оптимальная, то она должна гарантировать средний выигрыш игроку В, равный цене игры, при любом поведении игрока А:

для стратегии А₁:

для стратегии А₂:.

С учетом того, что сумма вероятностей смешанной стратегии равна 1, цена игры получаем систему уравнений:

Вычтем из первого уравнения второе:

Решая систему, находим

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

В .

Ответ: ,

Пример 6

Решить графически игру, заданную платежной матрицей .

Решение

Матрица игры имеет размер 4х2, поэтому решение игры будем искать для игрока В. Аналогично примеру 5 отложим отрезок единичной длины В₁В₂, каждой точке которого поставим в соответствие некоторую смешанную стратегию второго игрока - (q₁, q₂). В частности, точке В₁ соответствует стратегия В₁, точке В₂ - стратегия В₂.

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

В соответствии с принципом минимакса ломаная А₁NА₄ - верхняя граница выигрыша, получаемого игроком А. Точка N, в которой выигрыш минимален, определяет цену игры и ее решение. Для нахождения оптимальной стратегии игрока В достаточно составить уравнения прямых и найти точку пересечения прямых А₁А₁ и А₄А₄.

Уравнение прямой, проходящей через 2 точки (x₁,y₁) и (x₂,y₂) имеет вид . Прямая А₁А₁ проходит через точки (0,6) и (1,5), следовательно, ее уравнение или x+y=6. Прямая А₄А₄ проходит через точки (0,1) и (1,8), следовательно, ее уравнение или -7x+y=1. Для нахождения точки пересечения прямых А₁А₁ и А₄А₄ решим систему:

Вычтем из первого уравнения второе, получаем 8x=5 x=5/8, y=6-x=43/8. Точка N(5/8,43/8), следовательно, q₂=5/8, q₁=1-5/8=3/8, =43/8.

Таким образом, , при цене игры .

Из рисунка видно, что стратегии А₂ и А₃ не входят в оптимальную смешанную стратегию, поэтому p₂=0 и p₃=0, и мы можем найти оптимальную смешанную стратегию, удалив из платежной матрицы вторую и третью строку. Получаем матрицу , при этом строки ее соответствуют активным стратегиям А₁, А₄.

Так как - оптимальная, то она должна гарантировать средний выигрыш игроку А, равный цене игры, при любом поведении игрока В:

для стратегии В₁:

для стратегии В₂:.

С учетом того, что сумма вероятностей смешанной стратегии равна 1, цена игры получаем систему уравнений:

Вычтем из первого уравнения второе:

Решая систему, находим

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

А .

Ответ: , ,

Таким образом, имеем следующий алгоритм графического решения простейших матричных игр 2хn ( или mx2):

1. Строим n (m) прямых, соответствующих стратегиям второго (первого) игрока.

2. Строим нижнюю (верхнюю) границу выигрыша.

3. Выбираем на границе выигрыша точку с максимальной (минимальной) ординатой.

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

5. Находим координаты точки максимума (минимума) и решение игры.

2.2.4 Сведение матричной игры к задаче линейного программирования

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

Найдем решение игры с платежной матрицей m n:

Пусть матрица игры не содержит седловой точки. Тогда решение игры будем искать в смешанных стратегиях p= (p₁, p₂, …, p_m) и q = (q₁, q₂, …, q_m), где p₁ + p₂ +… + p_m = 1 и q₁ + q₂ +… + q_n = 1

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

Будем считать, что цена игры больше нуля. Действительно, если 0, то это означает, что некоторые элементы матрицы игры не положительные. Тогда найдём число M>0, которое прибавим ко всем элементам матрицы игры и получим новую матрицу с положительными элементами. Это сложение сделает цену новой игры, равную +M, положительной, но не изменит решения игры.

Разделим обе части всех неравенств на положительное число и обозначим

.

тогда система ограничений примет вид

Далее, так как p₁ + p₂ +… + p_m = 1, то .

Игрок A стремится максимизировать свой средний выигрыш , то есть минимизировать отношение

Таким образом, получаем задачу линейного программирования:

Заметим, что эта задача всегда имеет оптимальное решение . Его можно найти симплекс-методом или с использованием средств Excel. Тогда цена игры . Оптимальная смешанная стратегия первого игрока , где .

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

Обозначим .

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

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

Пример 7

Найти решение игры, заданной платежной матрицей:

Решение:

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

B A	B1	B2	B3	min в строке
A1	-1	1	6	-1
A2	5	2	-3	-3
A3	-2	4	5	-2
max в столбце	5	4	6	= -1 = 4

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

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

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

Из условия p₁ + p₂ + p₃ = 1, разделив обе части уравнения на >0 (цена игры больше нуля, т.к. все элементы преобразованной матрицы больше нуля), получаем целевую функцию . Цель игрока А - получить максимальный средний выигрыш, т.е. max, а значит . Если обозначить (i=1, 2, 3), то целевая функция .

Перейдем в системе ограничений к переменным x_i, разделив каждое неравенство на >0:

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

Решим задачу средствами табличного редактора MS Excel.использованием настройки Поиск решения.

1. Для решения нашей задачи создадим в Excel книгу с именем «Решение игры». Подготовим данные на листе.

Сначала определим ячейки, в которые будет помещен результат решения. Пусть это будут ячейки В2, С2, D2, сделаем у них заголовки. В этих ячейках нет данных, их должен будет рассчитать Excel, они выделены цветом. Далее заполним коэффициенты при неизвестных и правые части системы ограничений (строки 5-7). Заведем строку 10 для целевой функции. Цветом выделена ячейка, в которой будет находиться значение целевой функции для найденного оптимального решения.

Для ячеек B2:D2 и D10 установим числовой формат с 4 знаками после запятой. Для этого выделим эти ячейки, в контекстном меню по правой кнопке мыши выберем команду Формат ячеек… и в появившемся окне Формат ячеек на вкладке Число установим нужный формат.

В ячейки F5, F6, F7 ведем формулы для зависимостей левых частей системы ограничений, а в ячейку D10 - формулу для зависимости целевой функции.

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

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

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

Результаты поиска решений:

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

Окончательный результат: .

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

Из условия q₁ + q₂ + q₃ = 1, разделив обе части уравнения на >0, получаем целевую функцию . Цель игрока В - получить минимальный средний проигрыщ, т.е. min, а значит . Если обозначить , (j=1, 2, 3), то целевая функция .

Перейдем в системе ограничений к переменным y_j, разделив каждое неравенство на >0:

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

Решим задачу средствами табличного редактора MS Excel.использованием настройки Поиск решения.

1. Подготовим данные на листе.

В ячейки F5, F6, F7 ведем формулы для зависимостей левых частей системы ограничений, а в ячейку D10 - формулу для зависимости целевой функции.

2. Далее необходимо воспользоваться надстройкой Поиск решения.

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

Результаты поиска решений:

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

Окончательный результат: .

Ответ: , .

2.2.5 Игры с природой

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

Пусть статистик может использовать m стратегий А₁, А₂, …, А_m, а природа может реализовывать n различных состояний Р₁, Р₂, …, Р_n. Условия игры с природой так же задаются платежной матрицей

,

в которой элемент а_ij равен выигрышу статистика, если он использует стратегию А_i, а природа находится в состоянии P_j.

При выборе оптимальной стратегии статистика используют ряд критериев. При этом опираются как на платежную матрицу, так и на матрицу рисков R. Элементы матрицы r_ij представляют разность между максимальным выигрышем, который получил бы статистик, если бы достоверно знал, что природа будет находиться в состоянии P_j, и выигрышем а_ij, который он получит, используя стратегию А_i, т.е.

, где .

Рассмотрим критерии:

1. Критерий недостаточного основания Лапласа.

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

2. Максиминный критерий Вальда.

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

3. Критерий минимаксного риска Сэвиджа

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

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

4. Критерий Гурвица.

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

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

Пример 8

Сельскохозяйственное предприятие планирует посадить некоторую сельскохозяйственную культуру двух сортов. Посевная площадь 1 га. Сорта отличаются друг от друга требованиями к влаге во время вегетационного периода. Проанализировав погодные условия, выделены 4 состояния погоды (S1, S2, S3, S4), отличающиеся режимом осадков. Средняя урожайность (ц/га) каждого сорта на всем участке для каждого состояния погоды приведена в таблице:

	S1	S2	S3	S4
Сорт 1	23	29	31	37
Сорт 2	36	33	28	24

Возможные варианты посева:

А1) сорт 1 посадить на 100% площади;

А2) сорт 1 посадить на 75% площади, сорт 2 посадить на 25% площади;

А3) сорт 1 посадить на 50% площади, сорт 2 посадить на 50% площади;

А4) сорт 1 посадить на 25% площади, сорт 2 посадить на 75% площади;

А5) сорт 2 посадить на 100% площади;

Определить оптимальную стратегию с помощью критериев недостаточного основания Лапласа, максиминного критерия Вальда, критерия минимаксного риска Сэвиджа, пессимизма-оптимизма Гурвица (коэффициент пессимизма взять равным 0,4).

Решение

Составим платежную матрицу игры. Рассчитаем ее элементы:

Платежная матрица: A

Результаты расчетов будем заносить в таблицу:

	S1	S2	S3	S4	Лапласа	Вальда	Сэвиджа	Гурвица
А1	23	29	31	37	30	23	13	31,4
А2	26,25	30	30,25	33,75	30,06	26,25	9,75	30,75
А3	29,5	31	29,5	30,5	30,13	29,5	6,5	30,4
A4	32,75	32	28,75	27,25	30,19	27,25	9,75	30,55
A5	36	33	28	24	30,25	24	13	31,2
Выбранная по критерию стратегия	А5	A3	A3	А1

1. Критерий недостаточного основания Лапласа

Находим среднее значение элементов каждой строки по формуле

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

2. Максиминный критерий Вальда

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

3. Критерий минимаксного риска Сэвиджа

Рассчитаем матрицу рисков. В каждом столбце находим максимальный элемент _j.

	S1	S2	S3	S4
А1	23	29	31	37
А2	26,25	30	30,25	33,75
А3	29,5	31	29,5	30,5
A4	32,75	32	28,75	27,25
A5	36	33	28	24
j	36	33	31	37

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

	S1	S2	S3	S4
А1	13	4	0	0
А2	9,75	3	0,75	3,25
А3	6,5	2	1,5	6,5
A4	3,25	1	2,25	9,75
A5	0	0	3	13

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

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

Для каждой строки рассчитываем значение критерия по формуле:

. По условию =0,4.



	S1	S2	S3	S4
А1	23	29	31	37	23	37
А2	26,25	30	30,25	33,75	26,25	33,75
А3	29,5	31	29,5	30,5	29,5	31
A4	32,75	32	28,75	27,25	27,25	32,75
A5	36	33	28	24	24	36

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

Ответ:

1) Стратегия А1 является оптимальной согласно критерию пессимизма-оптимизма Гурвица.

2) Стратегии А2, А4 не являются оптимальными ни по одному из критериев.

3) Стратегия А3 является оптимальной согласно пессимистическим критериям Вальда и Сэвиджа.

4) Стратегия А5 является оптимальной согласно критерию Лапласа.

Вопросы для самопроверки

1. Сформулируйте постановку задачи о назначениях с минимизацией, максимизацией функции? В чем отличия в их решениях?

2. В чем заключается алгоритм венгерского метода решения задачи о назначениях?

3. Что такое стратегия игрока? Какая игра называется парной с нулевой суммой?

4. Что такое платежная матрица?

5. Как определить верхнюю и нижнюю цену игры? Каково соотношение между ними?

6. Какая игра имеет седловую точку? Что означает решение игры в чистых стратегиях?

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

8. Сформулируйте основную теорему теории игр - теорему Фон-Неймана.

9. Как можно графически решить игру?

10. На чем основана связь матричной игры и ЗЛП?

11. В чем отличие игр с природой?

12. Перечислите основные критерии решения игр с природой.



3. Многоцелевые задачи

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

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

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

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

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

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

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

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

3.1 Множество Парето

Рассмотрим на плоскости (U, V) произвольное множество .

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

Точки множества можно разбить на три класса:

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

- второй класс образуют граничные точки, перемещением которых по границе можно увеличить только одну из координат при сохранении значения второй (вертикальный отрезок АВ и горизонтальный отрезок CD на границе множества );

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

Множество точек третьего класса принято называть границей (множеством) Парето данного множества .

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

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