Элементы теории игр и нелинейного программирования

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ 

УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ 

СТАВРОПОЛЬСКИЙ ГОСУДАРСТВЕННЫЙ АГРАРНЫЙ УНИВЕРСИТЕТ

ЭЛЕМЕНТЫ ТЕОРИИ ИГР И

НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Учебное пособие

г. Ставрополь

2017

УДК 51 (075.8)
ББК 22.1я73

Литвин, Д.Б.
Элементы теории игр и нелинейного программирования: Учебное пособие / 
Д.Б. Литвин, С.В. Мелешко, И.И. Мамаев. – Ставрополь : Сервисшкола, 2017. –
84с.

Пособие предназначено для студентов направления Экономика - 38.03.01 оч
ной и заочной форм обучения. 

Содержание материала в целом соответствует второй части дисциплины 

«Методы оптимальных решений». 

ОГЛАВЛЕНИЕ

1. ЭЛЕМЕНТЫ ТЕОРИИ ИГР................................................................................... 4

1.1. Основные понятия. Принцип «минимакса»................................................. 4
1.2. Решение матричных игр в чистых стратегиях............................................. 6

Задания для решения в аудитории ......................................................................... 7

1.3. Смешанные стратегии в матричных играх ................................................ 17

1.4. Методы решения простейших игр .............................................................. 18

Дублирующие и заведомо невыгодные стратегии.......................................... 18

Аналитическое решение игры 2х2.................................................................... 19
Графическое решение игры 2х2........................................................................ 21

Графическое решение игр  2хn и  mх2.............................................................. 30

Задания для решения в аудитории ....................................................................... 36

1.5. Решение матричных игр  методами линейного 
программирования................................................................................................. 38

Задания для решения в аудитории ....................................................................... 42

2.
ЗАДАЧИ НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ................................. 49

2.1. Геометрический метод решения задачи нелинейного 
программирования................................................................................................. 49

Задания для самостоятельного решения.......................................................... 54

2.2. Выпуклое программирование...................................................................... 60

2.2.1. Краткие теоретические сведения.......................................................... 60

2.2.2. Теорема Куна — Таккера ...................................................................... 61

2.3. Численные методы........................................................................................ 62

2.3.1. Метод возможных направлений ........................................................... 62
2.3.2. Метод условного градиента .................................................................. 73

Задание для самостоятельного решения .......................................................... 78

2.4. Использование надстройки «Поиск решения» пакета 
Microsoft Excel........................................................................................................ 82

Литература ................................................................................................................. 84

1. ЭЛЕМЕНТЫ ТЕОРИИ ИГР

1.1. Основные понятия. Принцип «минимакса»

Конечная игра, в которой игрок А имеет т стратегий, а игрок В – n

стратегий, называется игрой m n
 .

В дальнейшем, для удобства сторону А будем условно именовать 

«мы», а сторону В – «противник». Будем обозначать наши стратегии

1
2
m
A ,A ,...A ; стратегии противника
1
2
n
B ,B ,...B .

Пусть каждая сторона выбрала определенную стратегию; для нас 

это будет 
iA для противника 
j
B .

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

j
B однозначно определяет исход игры – наш выигрыш. Обозначим его 
ij
a .

Пусть нам известны значения 
ij
a выигрыша при каждой паре страте
гий. Значения 
ij
a
можно записать в виде прямоугольной таблицы (матри
цы), строки которой соответствуют нашим стратегиям (
iA ), а столбцы –

стратегиям противника (
j
B ). Такая таблица называется платежной матри
цей или просто матрицей игры.

B

A

1
B
2
B
n
B

1A
11
a
12
a
1n
a

2
A
21
a
22
a
2n
a

m
A
m1
a
m2
a
mn
a

Оптимальной стратегией игрока в теории игр называется такая 

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

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

Выбирая стратегию 
iA мы всегда должны рассчитывать на то, что 

противник ответит на нее той из стратегий 
j
B для которой наш выигрыш 

ij
a
минимален. Определим это значение выигрыша, т.е. минимальное из 

чисел 
ij
a в i-й строке. Обозначим его 
i :


i
ij
j
mina .
 
(1)

Выбирая какую-либо стратегию 
iA мы должны рассчитывать на то, 

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

наиболее разумного противника (т. е. избегая всякого риска), мы должны 
остановиться на той стратегии 
iA , для которой число 
i
 является макси
мальным. Обозначим это максимальное значение  :

i
i
maxa ,
 

или, принимая во внимание формулу (1),

ij
i
j
maxmina .
 

Выпишем числа 
i

рядом с матрицей справа в виде добавочного 

столбца:

B

A

1
B
2
B
n
B
i


1A
11
a
12
a
1n
a
1


2
A
21
a
22
a
2n
a
2


m
A
m1
a
m2
a
mn
a
m


j

1

2

m


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

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

Число  лежит в определенной строчке матрицы, и та стратегия иг
рока А, которая соответствует этой строчке, называется максиминной 
стратегией.

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

Это – тот гарантированный минимум, который мы можем себе 

обеспечить, придерживаясь наиболее осторожной («перестраховочной») 
стратегии.

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

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

найдем минимальное из 
j
 .

j
ij
i
maxa ,
 
j
j
min



,    
ij
j
i
minmaxa .
 

Величина  называется верхней ценой игры, иначе – минимаксом.

Соответствующая минимаксному выигрышу стратегия противника называется его «минимаксной стратегией».

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

Принцип 
осторожности, 
диктующий 
игрокам 
выбор 
соот
ветствующих стратегий называют «принципом минимакса». 

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

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

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

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

стратегии являются устойчивыми. Это те игры, для которых нижняя цена 
равна верхней:





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

Пример 1. Пусть игра 4
4

задана матрицей:

B

A
1
B
2
B
3
B
4
B
i


1A
0,4
0,5
0,9
0,3
0,3

2
A
0,8
0,4
0,3
0,7
0,3

3
A
0,7
0,6
0,8
0,9
0,6

4
A
0,7
0,2
0,4
0,6
0,2

j

0,8
0,6
0,8
0,9

Найдем нижнюю и верхнюю цену игры: 
0,6
 
;  
0,6
 
.

Они оказались одинаковыми, следовательно, у игры есть чистая це
на, равная 
v
0,6





.

Элемент 0,6, выделенный в платежной матрице, является одновре
менно минимальным в своей строке и максимальным в своем столбце.

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

Седловой точке соответствует пара минимаксных стратегий (в дан
ном примере
3
A и 
2
B ). Эти стратегии называются оптимальными, а их со
вокупность – решением игры.

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

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

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

Мы видим, что в случае игры с седловой точкой минимаксные стра
тегии обладают своеобразной «устойчивостью»: если одна сторона придерживается своей минимаксной стратегии, то для другой может быть 
только невыгодным отклоняться от своей. 

Заметим, что в этом случае наличие у любого игрока сведений о 

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

Задания для решения в аудитории

1. Найти нижнюю и верхнюю цены игры с платежной матрицей

2
0
1

3
4
2
C
.
2
1
0

5
1
5










 









2. В конфликтной ситуации участвуют две стороны: А - государственная 

налоговая инспекция; В – налогоплательщик с определенным годовым доходом, налог с которого составляет 13 % годовых.

У стороны А два возможных варианта поведения. А1 – не контролировать 

доход налогоплательщика; А2 – контролировать доход налогоплательщика В и 
взимать с него: налога в размере 13 % годовых, если доход заявлен и соответствует действительности; налога в размере 13 % годовых и штрафа в размере 7%, 
если заявленный в декларации доход меньше действительного, или в случае сокрытия всего налога.

У стороны В три стратегии поведения: В1 – заявить о действительном до
ходе; В2 – заявить доход меньше действительного и реально налог в этом случае составит 7%; В3 – скрыть доход, тогда не надо будет платить налог.

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

2. Для отопления помещения надо заготовить топливо. Расход топлива и 

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

Показатели

Зима

мягкая
нормальная
суровая

Расход, т
7
12
20

Цена, руб. за 1 т
200
300
400

Летом можно уголь закупить по минимальной цене 200 рублей, а неис
пользованный остаток продавать весной по 100 рублей за тонну. Определите 
оптимальную стратегию в закупке топлива: А1 – 7 т, А2 – 12 т и А3 – 20 т.

Рассчитайте оптимальные затраты (выберите оптимальную стратегию 

закупки топлива) на покупку топлива в расчете на одно помещение с учетом 
данных таблицы. (Обозначим состояние погоды (стратегии погоды) зимой: 
мягкая зима – В1, нормальная – В2, суровая – В3.)