Математика (стр. 9 )

М(Р, Q ) = a11p1q1 + a12p1q2 + …. + a1np1qn +

+ a21p2q1 + a22p2q2 + …. + a2np2qn +

……………………………………..

+ am1pmq1 + am2pmq2 + … + amnpmqn,

или, кратко,

М(Р, Q ) = S S aijpiqj (2)

i =1 j=1

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

М(Р, Q*) £ n £ М(Р*,Q) (3)

где Р и Q — произвольные стратегии игроков.

Из неравенств (3) следует, что n = М(Р*, Q*), то есть цена игры совпадает с математическим ожиданием выигрыша первого игрока (проигрыша второго) при условии, что оба игрока применяют свои оптимальные стратегии. Напомним, что решить матричную игру - это значит найти оптимальные стратегии игроков Р* и Q* и цену игры n. Для того, чтобы проверить, являются ли некоторые стратегии Р* и Q*‚ оптимальными, нет необходимости сравнивать их с любыми стратегиями игроков, как это следует из определения (3). достаточно сравнить их с чистыми стратегиями игроков, которых, как известно, имеется конечное множество.

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

М(Рi, Q*) £ n £ М(Р*, Qj ) (4)

где Рi (i = 1, 2, ..., m) — всевозможные чистые стратегии первого игрока,Q (j = 1, 2, ..., n) всевозможные чистые стратегии второго игрока.

Основная теорема теории игр (теорема фон Неймана). Любая матричная игра имеет решение, то есть существуют оптимальные стратегии и цена игры.

Седловой точкой матрицы А называется точка (i0, j0), если элемент ai0j0 является наименьшим в своей строке и наибольшим в своем столбце.

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

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

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

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

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

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

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

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

A =

Прежде всего, проверим, имеет ли матрица (1) седловую точку. Наименьший элемент -3 первой строки не является наибольшим в третьем столбце; наименьший элемент -1 второй строки не является наибольшим в первом столбце; наконец, наименьший элемент 2 третьей строки является одновременно наибольшим в третьем столбце. Следовательно, матрица (1) имеет седловую точку (3, 3), в которой расположен элемент а33= 2. Значит, игра имеет решение в чистых стратегиях, а именно;

Р*3 = (0, 0, 1) — оптимальная стратегия первого игрока;

Q*3 = (0, 0, 1, 0) - оптимальная стратегия второго игрока;

n = 2 — цена игры. -

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

A = 2

-

В матрице (2) нет седловой точки, следовательно, игра имеет решение в смешанных стратегиях.

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

А’ = 2

-1 1 -2

Прибавив ко всем элементам матрицы А’, например, число с = 3, получим матрицу

А” =

2 4 1

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

Задача 1 Задача 2

Max ¦(X) = x1 + x2 + x3 Min g(Y) = y1 + y2

при условиях: х1 ³ 0, х2 ³ 0, х3 ³ 0, при условиях: y1 ³ 0, y2 ³ 0,

 

5х1 +7х3 £ 1, 5y1 + 2y2 ³ 1,

2х1 + 4х2 + х3 £ 1. 4y2 ³ 1, (5)

7y1 + y2 ³ 1.

Решим задачу 1 симплекс-методом. Она задана в форме общей задачи. Сведем ее к основной при помощи дополнительных неизвестных х4 ³ 0, х5 ³ 0. В результате получим следующую задачу.

5х1 + 7х3 + х4 = 1,

2х1 + 4х2 + х3 + + х5 = 1, (6)

xj ³ 0 ( j = 1 ¸ 5) , (7)

¦ (X) = x1 + x2 + x3 ¾ max. (8)

			0	1	1	1	0	0
		Баз.	х0	х1	х2	х3	х4	х5
	0	х4	1	5	0	7	1	0	Табл.1 q= 1/4
	0	х5	1	2	4	1	0	1
		¦	0	-1	-1	-1	0	0
	0	х4	1	5	0	7	1	0	Табл.2 q =1/7
®	1	х2	¼	1/2	1	1/4	0	1/4
		¦	¼	-1/2	0	-3/4	0	1/4
®	1	х3	1/7	5/7	0	1	1/7	0	Табл.3
	1	х2	3/14	9/28	1	0	-1/28	1/4
		¦	5/14	1/28	0	0	3/28	1/4
			g	y3	y4	y5	y1	y2

Задача (6)—(8) — каноническая и, применив к ней алгоритм симплекс-метода, получим симплексные таблицы вида

Из столбца х0 индексной строки табл.3 выпишем оптимальные планы пары двойственных задач (5), а именно:

Х*=(0, 3/14, 1/7); Y*=(3/28,1/4),

Причем ¦(Х*)=g(Y*)= 5/14.

Из решений двойственных задач (5) получим цену игры и оптимальные стратегии игроков в игре с матрицей A²:

n²= 1/¦(X*) = 1/g(Y*) = 14/5;

P*= n² × Y* = 14/5(3/28, 1/4) = (3/10, 7/10);

Q*= n² × X*= 14/5(0, 3/14, 1/7) = (0, 3/5, 2/5)

Игра с матрицей А’ будет иметь те же оптимальные стратегии P* и Q*, что и игра с матрицей А”, причем цена игры

n¢ = n² - c = 14/5 - 3 = - 1/5

И, наконец, исходная игра с матрицей А имеет оптимальные стратегии

P*=(0,3/10,7/10) и Q*= (0, 3/5, 0, 2/5,0) и цену игры n = n¢ = -1/5.

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

Проверить правильность решения игры можно с помощью критерия оптимальности стратегий. Для этого в неравенства (79) следует подставить компоненты найденных оптимальных стратегий Р* и Q* компоненты чистых стратегий Рi (i = 1, 2, 3) и Qj (j = 1, 2, 3, 4, 5) и цену игры n = -1/5

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

A’ = 2 -3 4

-1 1 -2

То в задаче 1 целевая функция будет не ограничена сверху на множестве планов, а в задаче 2 вообще не будет планов, однако, как мы убедились выше, игра с матрицей А’ имеет решение.

Глава 6. Задача коммивояжера.

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

Рассмотрим постановку задачи дискретного программирования. Пусть на множестве W = {w} состоящем из конечного числа элементов произвольной природы, задана числовая функция j(w), то есть каждому элементу wÎW соотнесено число j(w). В множестве W требуется найти такой элемент w*‚ на котором функция j(w) принимает свое наименьшее (наибольшее) значение, то есть требуется найти такой элемент w*ÎW, что j(w*) £ j(w) (j(w*) ³ j(w)) для любого wÎW. Кратко этот факт записывается следующим образом:

j(w*) = min j(w) ( j(w*) = max j(w) )

wÎW wÎW

Одним из методов решения этой задачи является метод ветвей и границ, состоящий в многократном повторения двух следующих операций: 1) вычисление нижней г 2) ветвление множества. Рассмотрим каждую из этих операций.

1. Вычисление нижней границы. Нижней границей значений функции j(w)на множестве W‚ (коротко нижней границей) называется всякое число j, для которого выполнено соотношение j £ j(w) для любого wÎW, тем самым j £ minj(w). Для каждого типа задач дискретного программирования разрабатывается свой метод вычисления нижней границы.

2. Ветвление множества. Под ветвлением данного множества понимается разбиение этого множества на несколько попарно непересекающихся подмножеств (то есть не имеющих общих элементов), в “сумме” составляющих множество. Графически ветвление будем изображать в виде рис. 2.

W

W1 . Wк

W2 . . .

Рис. 2.

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

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

Постановка задачи коммивояжера.

Пусть имеется граф и заданы длины его дуг. Требуется среди всех контуров, проходящих точно по одному разу через каждую из вершин графа, найти контур наименьшей длины. Контуры такого вида будем называть маршрутами. Свое название задача получила от одной из возможных конкретизаций: коммивояжер (бродячий торговец) должен объехать n городов, побывав в каждом из них по одному разу, и вернутся в исходный город. Ясно, что здесь разумно использовать маршрут кратчайшей длины. Условия задачи обычно задаются в виде так называемой матрицы расстояний, то есть таблицы следующего вида

i j	1	2	…	n
1	a11	a12	…	a1n
2	a21	a22	…	a2n
…	…	…	…	…
n	an1	an2	…	ann

Здесь i — номера вершин графа, aij — длина дуги xixj выходящей из вершины хi и входящей в вершину хj. Если дуги хixj в графе нет, то вместо числа аij будем ставить прочерк “—“. Длины дуг xixj и хjxi могут быть различными, то есть не обязательно aij =