ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 25.03.2025
Просмотров: 1122
Скачиваний: 2
Рассуждения для второго игрока аналогичны. Оптимальная стратегия Q обеспечивает игроку V средний выигрыш, не больше, чем цена игры ν , при любой стратегии первого игрока. В том числе и против каждой чистой стратегии первого игрока. Для m чистых стратегий первого игрока получаем
a11
WiT AQ = (0,...,1,...,0) ...
am1
... a1n
... ...
... amn
q |
||||
1 |
= |
|||
... |
||||
qn |
||||
(q1 ai1 +... + qn ain ), i =1,...,m.
и выполнены неравенства
q1 ai1 +... + qn ain |
≤ν, j =1,...,m. |
(11.8) |
||||||||||||
Каждое из полученных неравенств разделим на ν , при этом |
||||||||||||||
можно считать, что ν > 0. Введём новые переменные |
||||||||||||||
y |
= q1 |
ν |
,....., y |
n |
= qn |
ν |
. |
(11.9) |
||||||
1 |
||||||||||||||
Тогда (11.7) примет вид |
||||||||||||||
ai1 x1 +... + ain yn |
≤1, |
j =1,...,n. |
(10.10) |
|||||||||||
Разделим равенство (11.2) на цену игры ν |
> 0. Тогда, используя |
|||||||||||||
обозначения (11.9), |
получаем |
|||||||||||||
y1 + y2 +…..+ yn |
= 1/ ν . |
(10.11) |
||||||||||||
Минимизация цены игры |
ν |
эквивалентна максимизации |
||||||||||||
величины 1/ ν . Поэтому задачу определения y , i = 1,…,n, |
можно |
|||||||||||||
переформулирована следующим образом. |
i |
|||||||||||||
Определить значения переменных |
yi ≥ 0, i = 1,…,n, так, чтобы |
|||||||||||||
они удовлетворяли линейным ограничениям (11.10) и при этом |
||||||||||||||
линейная функция |
||||||||||||||
Z * |
= y |
1 |
+ y |
2 |
+... + y |
n |
(11.12) |
|||||||
обращалась в максимум.
Это задача линейного программирования на максимизацию функции Z*. Решая задачу (11.10), (11.12) для неотрицательных
93
yi ≥ 0, i = 1,…,n, можно найтивеличину 1/ ν и, значит, ценуисходной игры ν . Она будет равна цене игры, найденной ранее. По решению задачилинейногопрограммирования(изформул(11.9)) определяется оптимальная стратегия второго игрока.
Итак, решение матричной игры с матрицей А = Am×n = (aij),
i = 1,…,m, j = 1,…,n свелась к решению двух задач линейного программирования (11.5), (11.7) и (11.10), (11.12). Из этих формул следует, что это пара двойственных задач. Из прямой задачи линейного программирования (11.10), (11.12) (задача на максимум) находится оптимальная стратегия второго (минимизирующего) игрока. Из двойственной задачи линейного программирования (11.5), (11.7) (задачи на минимум) находится оптимальная стратегия первого (максимизирующего) игрока.
Пример 11.1. Решить матричную игру с матрицей А методом линейного программирования
3 |
6 |
8 |
||
9 |
4 |
2 |
||
А = |
. |
|||
7 |
5 |
4 |
||
Найдём нижнюю цену игры |
||||
νН = max min aij = мах{min{3, 6, 8}, min{9, 4, 2}, min{7, 5, 4}} = |
|
i |
j |
= мах{3, 2, 4} = 4 > 0.
Так как νН = 4 > 0, то задачи линейного программирования пишем непосредственно для матрицы А.
Запишем прямую задачу линейного программирования
(11.10), (11.12).
f (x) = x1 + x2 + x3 → max;
3x1 + 6x2 +8x3 ≤1,
9x1 + 4x2 + 2x3 ≤1, 7x1 +5x2 + 4x3 ≤1, x j ≥ 0, j =1,...,3.
94
Запишем двойственную задачу (11.5), (11.7)
f d (x) = y1 + y2 + y3 → min; 3y1 +9 y2 + 7 y3 ≥1,
6y1 + 4y2 +5y3 ≥1, 8y1 + 2 y2 + 4y3 ≥1, y j ≥ 0, j =1,...,3.
Представим прямую задачу линейного программирования в канонической форме
f (x) = x1 + x2 + x3 +0x4 + 0x5 +0x6 → max;
3x1 + 6x2 +8x3 + x4 =1; 9x1 + 4x2 + 2x3 + x5 =1,
7x1 +5x2 + 4x3 + x6 =1, xi ≥ 0; i =1,...,6.
Данные из канонической задачи, заносим в симплекс таблицу11.1. Таблица 11.1.
Заполнение таблицы стандартное. В столбце “Значения” у оценочной функции ставим 0, т.к. в функции цели постоянное слагаемое 0. Выделяем базисные переменные. Это переменные, для которых столбцы образуют единичную матрицу. Базис составляют x4, x5, x6. Остальные переменные являются свободными.
По заполненной симплекс таблице определяем решение, соответствующее этой (нулевой) итерации. Свободные
95
переменныеравны0. Базисныепеременныеизначениефункциицели находим из таблицы. Они представлены в столбце “Значение”. Отметим, что значение функции цели берём с противоположным знаком. Итак, x(0) = (0, 0, 0, 1, 1, 1), f (0) =0.
В оценочной строке имеются положительные числа. Это означает, что решение можно улучшить. Выберем наибольшее из положительных чисел. Если таких чисел несколько – берём любое из них, например, первое. Соответствующий столбец называем ведущим. По ведущему столбу и столбцу “Значения” определяем оценку строки. Число из столбца “Значение” делим на соответствующее число из ведущего столбца. Получаем оценку строки. По условию задачи это положительное число. Объявляем ведущей строкой ту, оценка у которой наименьшая. В таблице 11.1 ведущая строка и столбец выделены цветом. На их пересечении находится ведущий элемент. В нашем случае это число 9.
Переходим к первой итерации. Её суть состоит в том, чтобы свободную переменную x1 сделать базисной, а базисную переменную x5 - свободной. В таблице выполняем преобразования аналогичные элементарным строчным преобразованиям в методе Гаусса при решении системы линейных уравнений. В результате преобразований получаем
Таблица 11.2.
Из таблицы находим базисные переменные (свободные переменные равны 0) и значение функции. Это будет x(1) = (1/9, 0, 0, 1/11, 0, 2/9) и f(1) =1/9. Результат можно проверить. Полученные значения должны удовлетворять функции цели в канонической (стандартной) задаче линейного программирования.
Действительно1 1 |
9 |
+1 0 +1 0 = 1 |
9 |
, т.е. получили верное |
равенство.
96
Воценочнойстрокетаблицы11.2 имеетсяположительноечисло, значитможноперейтикследующейитерации. Втаблице11.2 цветом выделены ведущийстолбец иведущая строка. Суть второйитерации состоит в том, чтобы свободную переменную x3 преобразовать в базисную, а базисную переменную x4 сделать свободной. ПреобразованияпроводимпометодуГаусса. Результатыпредставлены в таблице 11.3.
Таблица 11.3.
Изтаблицынаходимбазисныепеременныеизначениефункции x(2) = (1/11, 0, 1/11, 0, 0, 0), f (1) =2/11.. Этотрезультатможнопроверить.
Действительно, 1 111+1 0+1 111=211, т.е. получили верное равенство.
В оценочной строке есть одно положительных чисел. Значит можно перейти к следующей итерации. В таблице 11.3 цветом выделены ведущий столбец и ведущая строка. Отметим, что оценка третьей строки равна 0. Суть третьей итерации состоит в том, чтобы свободную переменную x2 преобразовать в базисную, а базисную переменную x6 сделать свободной. Преобразования проводим по методу Гаусса. Результаты представлены в таблице 11.4.
Таблица 11.4.
В оценочной строке есть положительное число. Перейдём к следующей итерации. В таблице 11.4 цветом выделены ведущий
97
столбец и ведущая строка. Суть четвёртой итерации состоит в том, чтобы свободную переменную x5 преобразовать в базисную, а базисную переменную x3 сделать свободной. Преобразования проводим по методу Гаусса. Результаты представлены в таблице
11.5.
Таблица 11.5.
Воценочнойстрокенетположительныхчисел, значитсимплекс
–метод закончен. Обозначим через X и Y соответственно решение прямой(11.10), (11.12) идвойственной(11.5), (11.7) задачлинейного программирования. Выпишем это решение из последней симплекс – таблицы. Получаем
X = ( 1 |
27 |
, 4 |
27 |
,0)T , Y = (2 |
27 |
,0, 1 |
9 |
)T , |
fmax = fmind = 5 |
27 |
. |
Перейдём к решению матричной игры. Вначале найдём цену игры. Она определяется по формуле (11.6) (или по формуле
(11.11)). Получаем
x1 + x2 + x3 = 127 + 4 27 = 5 27 = 1ν , ν* = 275 = 5,4.
( y + y |
2 |
+ y |
3 |
= 2 |
27 |
+ 1 |
9 |
= 5 |
27 |
= 1 |
, ν* = 27 |
5 |
= 5,4). |
1 |
ν |
Из формулы (11.4) находим оптимальную стратегию первого игрока
x* = P = ν*Y = 27 5 ( 2 27,0, 19 )T = ( 2 5 ,0, 35 )T .
Из формулы (11.9) получаем оптимальную стратегию второго игрока
y* = Q =ν * X = 275 ( 127, 4 27,0)T = ( 15 , 45 ,0)T .
Окончательно проверим полученный результат для матричной игры по формуле
98