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

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

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

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

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

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

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

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

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

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

Задача теории игр — выявление оптимальных стратегий игроков.

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

Если в игре участвуют два игрока — игра называется парной.

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

Парная игра с нулевой суммой называется антагонистической.

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

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

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

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

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

Рассмотрим конечную парную игру с нулевой суммой, в которой участвуют два игрока «A» и «B», имеющие противоположные интересы. Так как выигрыш игрока «A» равен выигрышу игрока «B» с противоположным знаком, то нас может интересовать только выигрыш игрока «A» — «a». Естественно игрок «A» стремится максимизировать «a», а игрок «B» минимизировать «a».

Пусть у игрока «A» имеется «m» стратегий: «A₁, A₂, …, A_m», а у игрока «B» — «n» стратегий: «B₁, B₂, …, B_n» (такая игра называется игрой m×n); «a_ij» — выигрыш игрока «A» в случае, если он воспользуется стратегией «A_i», а игрок «B» стратегией «B_j».

Предположим, что для каждой игры стратегий «A_i — B_j» выигрыш «a_ij» известен, тогда можно составить прямоугольную таблицу (матрицу), в которой перечислены выигрыши игроков и их стратегии.

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

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

Рассмотрим пример: пусть задана игра 3×4; игрок «A» имеет 3 стратегии: «A₁, A₂, A₃»; игрок «B» имеет 4 стратегии: «B₁, B₂, B₃, B₄».

Минимум строк — минимальный выигрыш игрока «A».

Гарантированный выигрыш игрока «A» max_imin_j=4 называется нижней ценой игры, а гарантированный минимальный проигрыш игрока min_imax_j=4 — верхней ценой игры.

Если верхняя и нижняя цены игры совпадают, то говорят, что цена игры равна 4. Стратегии («A₂», «B₃») — чистые стратегии, соответствующие седловой точке.

гиперболический параболоид

Пара чистых стратегий («A₂», «B₃») называется парой оптимальных стратегий.

Вывод: игра имеет решение в чистых стратегиях только тогда, когда нижняя и верхняя цены игры совпадают.

3. Доминирующие и дублирующие стратегии. Решение игр в смешанных стратегиях. Условия применения смешанных стратегий. Основная теорема теории игр. Решение игр в смешанных стратегиях. Пример: два игрока поочередно выкладывают на стол монеты, если совпадают «герб-герб» или «решка-решка», то игрок «A» выигрывает.

Нижняя граница не равна верхней границе, значит нет решения в чистых стратегиях. Необходимо смешивать стратегии.

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

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

Если все выигрыши строки «A_i» равны соответствующим выигрышам строки «A_k», то стратегия «A_i» называется дублирующей.

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

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

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

В игре, в которой отсутствует седловая точка, в соответствии с основной теоремой теории игр оптимальное решение существует и определяется парой смешанных стратегий игрока «A» S_A^*=(p₁^*, p₂^*) и игрока «B» S_B^*=(q₁^*, q₂^*). p₁^*, p₂^* — оптимальные вероятности, с которыми игрок «A» использует первую и вторую стратегии (смешивает стратегии); q₁^*, q₂^* — —//— игрок «B» —//—. Выигрыш игрока «A» (проигрыш игрока «B») — случайная величина, математическое ожидание которой является ценой игры.

Пусть игра задана матрицей 2×2

p₁^*, p₂^* — оптимальные вероятности (частоты), с которыми игрок «A» применяет стратегии «A₁» и «A₂»; q₁^*, q₂^* — оптимальные вероятности (частоты), с которыми игрок «B» смешивает стратегии «B₁» и «B₂».

p₁^*+p₂^*=1

q₁^*+q₂^*=1

Средний выигрыш игрока «A», если он использует оптимальную смешанную стратегию S_A^*, а игрок «B» — чистую стратегию «B₁», равен:

ν=a₁₁*p₁^*+a₂₁*p₂^*

ν=a₁₂*p₁^*+a₂₂*p₂^*

p₁^*+p₂^*=1

p₁^*=(a₂₂-a₂₁)/(a₁₁+a₂₂-a₁₂-a₂₁)

p₂^*=(a₁₁-a₁₂)/(a₁₁+a₂₂-a₁₂-a₂₁)

ν=(a₂₂*a₁₁-a₁₂*a₂₁)/(a₁₁+a₂₂-a₁₂-a₂₁)

Отыщем оптимальную стратегию игрока «B». Средний проигрыш игрока «B», соответствующий первой чистой стратегии игрока «A» («A₁»), имеет вид:

ν=a₁₁*q₁^*+a₁₂*q₂^*

При использовании игроком «A» второй чистой стратегии («A₂») средний проигрыш игрока «B» равен:

ν=a₂₁*q₁^*+a₂₂*q₂^*

ν=a₁₁*q₁^*+a₁₂*q₂^*

ν=a₂₁*q₁^*+a₂₂*q₂^*

q₁^*+q₂^*=1

q₁^*=(a₂₂-a₁₂)/(a₁₁+a₂₂-a₁₂-a₂₁)

q₂^*=(a₁₁-a₂₁)/(a₁₁+a₂₂-a₁₂-a₂₁)

ν=(a₂₂*a₁₁-a₁₂*a₂₁)/(a₁₁+a₂₂-a₁₂-a₂₁)

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

4. Задача Л. Эйлера. Граф. Основные понятия неориентированного графа (вершины, инцидентные ребра и вершины, степень вершины, висячие вершины, маршрут, цепь, диаметр графа). Эйлеров граф и эйлеров цикл. Граф G(X, U) — есть пара множеств X и U, где множество X≠Ø (не пустое), а пересечение множеств пусто X∩U=Ø. Каждому элементу множества U соответствует два элемента множества X. Элементы множества X — вершины, а элементы множества U — ребра.

X={x₁, x₂, …, x_n}

U={u₁, u₂, …, u_n}

U={(x₁, x₂), (x₂, x₃), …, (x_n-1, x_n)}

(x₁; x₂)=(x₂; x₁) — ребро

(x₁; x₂)≠(x₂; x₁)—дуга (x₁, x₂ образуют упорядоченную пару)

Граф, содержащий только ребра, называется неориентированным, а граф, содержащий только дуги, называется ориентированным графом.

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

Иногда изолированную вершину называют пустой.

Висячая вершина — это вершина, которая имеет ровно одно ребро.

Тупиковая вершина или вершина-сток — это вершина, в которую дуги только входят.

Антитупиковая вершина или вершина-источник — это вершина, из которой дуги только выходят.

Вершина и ребро инцидентны, если эта вершина является одной из концевых вершин ребра.

a₁, u₁ — инцидентны

a₁’, u₁’ — инцидентны

Две вершины называются смежными, если существует соединяющее их ребро.

(a₁’, a₂’) — смежные

(a₂’, a₁’) — несмежные

Два ребра называются смежными, если они имеют общую вершину.

Маршрут в графе — это последовательность вершин и ребер (x₁, u₁, x₂, u₂, …, x_n-1, u_n-1, …, x_n, u_n), таких что каждая вершина x_i инцидентна ребрам u_i-1, u_i, т. е. каждая конечная вершина одного ребра является началом следующего ребра (нет разрыва).

В маршруте ребра могут повторяться.

Маршрут, в котором ребра не повторяются, называются цепью.

В цепи вершины могут повторяться, а ребра нет.

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

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

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

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

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

Диаметр графа — это число, которое равно максимальному расстоянию из вершины «a» в вершину «b», взятого по всем вершинам (a, b)€X (принадлежащих множеству вершин).

D=3

Степень вершины «a» (или локальная степень) — это число, равное количеству ребер инцидентных данной вершине.

ρ(a)=3

ρ(a)=4

5. Части графа. Связность графа. Дерево. Лес. Гамильтонов цикл и гамильтонов граф. Взвешенный граф. Рассмотрим граф g(X, u). Рассмотрим подмножество вершин X’cX и подмножество ребер u’cU.

Подграф — это граф G’(X’, U’), представляющий собой пару множеств, которая порождается множеством X’. Если при этом X’ совпадает с множеством X, т. е. X’=X, то граф G’(X, U’) называется суграфом или остовным графом. Иногда говорят, что суграф — это пара множеств (X, U’), порожденная множеством U’.

Подграф и суграф являются частями графа.

Пример:

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

Пример:

Имеются специальные части графа, напр. звезда.

Звезда вершины «a» — это часть графа, которая содержит вершину «a», все инцидентные ей ребра и вторые концы этих ребер.

Граф называется связным, если для любых двух вершин «a», «b» существует цепь из «a» в «b».

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

Граф называется конечным, если у него число вершин и ребер конечно.

Если граф не является связным, а состоит из нескольких деревьев, то такой граф называется лесом.

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

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

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

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

Граф, содержащий гамильтонов цикл, называется гамильтоновым графом.

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

6. Ориентированный граф. Путь и длина пути в графе. Простой путь и контур. Заходящие и исходящие дуги. Полустепень исхода и полустепень захода вершины. Матрица смежности графа. Матрица инциденций. Граф, содержащий только дуги, называется ориентированным графом.

Ориентированный маршрут — это маршрут, в котором направление каждой участвующей в нем дуги совпадает с направлением маршрута.

Ориентированная цепь (орцепь, путь) — это ориентированный маршрут, в котором дуги не повторяются, а вершины могут повторяться.

Ориентированный цикл (контур, орцикл) — это циклический ориентированный маршрут, в котором дуги не повторяются.

Простая орцепь (простой путь) — это путь, в котором вершины не повторяются.

Простой контур (простой орцикл) — это контур, в котором вершины не повторяются.

Полустепень выхода (входа) для вершины «a» — это два числа ρ⁺(a) (полустепень выхода) и ρ^-(a) (полустепень входа), которые равны числу дуг, входящих в вершину «a» (ρ^-(a)) и выходящих из нее (ρ⁺(a)).

Пример:

ρ^-(a)=2

ρ⁺(a)=3

Одной из форм представления графа являются матрицы смежности и инциденции.

Матриц смежности две: матрица смежности вершин и матрица смежности ребер.

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

Рассмотрим матрицу смежности ребер для ориентированного графа. Она представляет собой квадратную матрицу, на главной диагонали которой стоят 0, а в клетке ij ставится 1 только в том случае, если дуга U_i непосредственно предшествует дуге U_j, 0 — в противном случае.

Пример:

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

Пример:

Если граф взвешенный, то в матрице инциденции целесообразно в соответствующих клетках вместо +1 и -1 указывать «веса» дуги.

7. Понятие сети. Двухполюсная сеть. Сеть (транспортная сеть) — это совокупность следующих объектов: 1). Ориентированный граф G(X, U) конечный без петель и кратных дуг; 2). Вершина-источник, т. е. вершина, из которой дуги только выходят (обозн.: «a»); 3). Вершина-сток, т. е. вершина, в которую дуги только входят (обозн.: «z»); 4). Каждой дуге из множества «U» поставлено в соответствие число C(x, y)≥0 — пропускная способность дуги.

Под C(x, y) понимается верхняя граница количества вещества, протекающего по дуге (x, y).

Введем обозначения Γx — образ вершины x при отображении Γ, т. е. множество вершин, куда идут дуги из вершины x.

Γx — прообраз вершины x при отображении Γ, т. е. множество вершин, из которых дуги идут в вершину x.

Замечание: иногда в сети бывает несколько источников. Напр., заводы — поставщики продукции. Также в сети может быть несколько вершин-стоков. Напр., склады, принимающие на хранение продукцию.

8. Потоки в сетях. Свойства потока. Разрез сети. Теорема о максимальном потоке и минимальном разрезе. Потоком величины «U» в сети (X, U) из источника «a» в сток «z» называется функция, определенная на множестве дуг U, которая удовлетворяет следующим условиям: 1).

2). 0≤f(x, y)≤C(x, y) для всех (x, y)€U.

Разъяснения:

f(x, y) — поток по дуге (x, y)

—сумма потоков по дугам, выходящим из вершины x

—сумма потоков по дугам, входящим в вершину x

Т. о., условие 1 означает, что сумма потоков по дугам, выходящим из вершины-источника «a», равна «U».

Сумма потоков, входящих в вершину-сток «z», равна «-U».

Для любой промежуточной вершины (x≠a, x≠z) сумма потоков по всем входящим в нее дугам равна сумме потоков по всем выходящим из данной вершины дугам.

Условие 1 представляет собой систему «n» линейных уравнений, где «n» — число вершин (уравнение баланса потоков для каждой вершины). Неизвестными являются дуговые потоки f(x, y); их число равно «m» — числу дуг.

Условие 2 означает, что поток f(x, y) по дуге ограничен максимальной пропускной способностью дуги.

Разрезом сети (X’, X’) называется множество дуг (x_ix_j), для которых начало x_i€x’, а x_j€x’.

Разъяснение: разрез сети отделяет вершину-источник от вершины-стока, т. к. a€X’, z€X’, т. е. разрез сети — это множество дуг, удаление которых из сети делает сеть несвязной. Говорят, что разрез сети блокирует сток.

Пример:

(X’, X’)={(x₂, z), (x₁, x₅), (x₄, x₅)}

Пропускной способностью или величиной разреза C(x’, x’) называют сумму пропускных способностей дуг, т. е.

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

Пример:

C(x, x’)=C(x₁, x₂)+C(x₃, x₄)

По аналогии с пропускной способностью разреза можно определить значение потока на разрезе

Имеет место основная теорема теории потоков, которая формулируется следующим образом (Форда-Фалкерсона): для любой сети (X, U) максимальная величина потока равна минимальной пропускной способности разреза.

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

при ограничениях

U≥0

0≤f(x, y)≤C(x, y) для всех (x, y)€U

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

Задача о потоке минимальной стоимости. Дана двухполюсная сеть (X, U) с источником «a», и стоком «z». Для каждой дуги (x, y)€U задана максимальная пропускная способность C(x, y) и стоимость доставки по ней единицы потока r(x, y). Необходимо найти поток от источника в сток заданной величины U, имеющий минимальную стоимость доставки.

Математическая модель в задаче имеет следующий вид:

при ограничениях

0≤f(x, y)≤c(x, y) для всех (x, y)€U

Задача коммивояжёра

Задача о замене оборудования.

C₀=1,6 млн

1 год — 0,5

2 — 1,0

3 — 1,5

4 — 2,2

1 год — станок приобретен

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

1). X_ij

2).

3). X_ij≤A_ij

X_ij — двоичн. или X_ij≥0

4). Строка «Всего»=Строка «Необходимо»

Во «Всего»: «Итого» в столбце – «Итого» в строке

В «Итого»: сумма по строке, сумма по столбцу

В «Необходимо»: Год 1=1

Год 5=-1

Год 2 — Год 4=0

Целевая функция: матрица стоимости*матрица неизвестных

Поиск кратчайшего пути. Компания занимается поставками продуктов в сеть различных пунктов. Необходимо определить кратчайший путь из вершины «H» в вершину «5».

Одной из форм представления графа является матрица смежности вершин или ребер. Чаще используется матрица смежности вершин.

Решение: