30. Матричные игры. Верхняя чистая цена игры. Принцип минимакса-максимина

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

Рассмотрим конечную игру двух игроков А и В, в которой игрок А может применить одну из стратегий

а игрок В – одну из стратегий

Будем предполагать везде далее, что игрок А выигрывает, а игрок B проигрывает

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

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

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

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

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

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

31. Понятия смешанной стратегии игрока, цены игры.

27

3 2. Графическое решение игр вида

33. Метод ветвей и границ.

Приводим матрицу расстояний про строкам и столбцам. Находим нижнюю границу всего множества маршрутов f (R) = ∑v i = 1^n + ∑v j = 1 ^ n Bj.

2) Каждый 0 в приведенном матрице условно заменяем на ∞ и находим сумму констант приведения αi + βj, найденное значение записываем рядом с 0.

Исключаем из Гамильтоново контура дугу ij, для которой сумма констант приведения max. Для этого заменяем эл ij на ∞.

Приводим полученную матрицу расстояний и определяем нижнюю границу Pij.

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

Приводим сокращенную матрицу и находим нижнюю границу P(ij).

Проверяем размер сокращенной матрицы. Если она размера 2х2, то переходим к 9 пункту, если больше, то к 8.

8) Сравниваем нижние границы подмножеств гамильтоновых контуров и переходим к пункту 2. Если Pij <Pij То разбиению подлежит P(ij), если наоборот, то P(ij)

9) Определяем гамильтонов контур и его длину

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

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

34. Задача коммивояжера.

В задаче коммивояжера для формирования оптимального маршрута объезда n городов необходимо выбрать один лучший из (n-1)! вариантов по критерию времени, стоимости или длине маршрута. Эта задача связана с определением гамильтонова цикла минимальной длины. В таких случаях множество всех возможных решений следует представить в виде дерева - связного графа, не содержащего циклов и петель. Корень дерева объединяет все множество вариантов, а вершины дерева — это подмножества частично упорядоченных вариантов решений.

Математическая модель задачи коммивояжера

Сформулированная задача - задача целочисленная. Пусть х_ij = 1 , если путешественник переезжает из i -ого города в j-ый и х_ij = 0, если это не так.  Формально введем (n+1) город, расположенный там же, где и первый город, т.е. расстояния от (n+1) города до любого другого, отличного от первого, равны расстояниям от первого города. При этом, если из первого города можно лишь выйти, то в (n+1) город можно лишь придти.  Введем дополнительные целые переменные, равные номеру посещения этого города на пути. u₁ = 0, u_n+1 = n . Для того, чтобы избежать замкнутых путей, выйти из первого города и вернуться в (n+1) введем дополнительные ограничения, связывающие переменные x_ij и переменные u_i. ( u_i целые неотрицательные числа).      u_i-u_j+nx_ij ≤ n-1, j = 2..n+1, i=1..n, i≠j, при i=1 j≠n+1  0≤ u_i ≤ n, x_in+1 = x_i1, i=2..n

35. Метод динамического программирования

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

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

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

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

Типовой алгоритм решения задач методом динамического программирования:

1. Описать строение оптимальных решений.

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

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

4. Пользуясь полученной информацией, построить оптимальное решение.

Наша лабораторная по Динамическому программированию:

Ссылка на онлайн калькулятор:

http://math.semestr.ru/dinam/dinamprog.php

36 Симплексная таблица. Разрешающий элемент. Алгоритм решения

Симплексные таблицы

Приведя ЗЛП к предпочтительному виду, её заносят в симплексную таблицу.

 

max Z = 18x1 + 20x2 + 32x3

18x1 + 15x2 +12x3 + x4 = 720;

6x1 + 4x2 + 8x3 + x5 =384;

5x1 + 3x2 + 12x3 + x6 = 360;

 

Базисные переменные	Коэффициенты		A0		X1	X2		X3		X4		X5	X6
					18	20		32		0		0	0
X4	0		720		18	15		12		1		0	0
X5	0		384		6	4		8		0		1	0
X6	0		360		5	3		12		0		0	1
Zj - Cj		0		-18		-20	-32		0		0		0

 

∆₀ = 0*720 + 0* 384 + 0* 360 = 0;∆₀ = Z(x₀)

∆_I = ∑ коэфф. * a_ij  - c­_j;

∆₁ = 0*18 + 0*6+ 0*5 – 18= -18

 

Правило прямоугольника

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