Методы оптимальных решений. Страницы 13-14

yurii Сен 01, 2016

Находим решение игры в смешанных стратегиях.

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

найти минимум функции F(x) при ограничениях:

4x1+2x2 ≥ 1

3x2 ≥ 1

6x1+x2 ≥ 1

F(x) = x1+x2 → min

найти максимум функции Ф(y) при ограничениях:

4y1+6y3 ≤ 1

2y1+3y2+y3 ≤ 1

Ф(y) = y1+y2+y3 → max

 

Определим максимальное значение целевой функции F(X) = x1 + x2 + x3 при следующих условиях-ограничений.

4x1 + 6x3≤1

2x1 + 3x2 + x3≤1

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

4x1 + 0x2 + 6x3 + 1x4 + 0x5 = 1

2x1 + 3x2 + 1x3 + 0x4 + 1x5 = 1

 

Базис B x1 x2 x3 x4 x5 min
x4 1 4 0 6 1 0 1/6
x5 1 2 3 1 0 1 1
F(X1) 0 -1 -1 -1 0 0 0
Базис B x1 x2 x3 x4 x5  
x3 1/6 2/3 0 1 1/6 0  
x5 5/6 4/3 3 0 -1/6 1  
F(X1) 1/6 -1/3 -1 0 1/6 0  
Базис B x1 x2 x3 x4 x5 min
x3 1/6 2/3 0 1 1/6 0
x5 5/6 11/3 3 0 -1/6 1 5/18
F(X2) 1/6 -1/3 -1 0 1/6 0 0
Базис B x1 x2 x3 x4 x5  
x3 1/6 2/3 0 1 1/6 0  
x2 5/18 4/9 1 0 -1/18 1/3  
F(X2) 4/9 1/9 0 0 1/9 1/3  

 

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

 

Оптимальный план можно записать так:

x3 = 1/6

x2 = 5/18

F(X) = 1•1/6 + 1•5/18 = 4/9

 

Цена игры будет равна g = 1/F(x)

вероятности применения стратегий игроков: qi = g*yi; pi = g*xi.

В нашем случае

Цена игры: g = 1/4/9 = 9/4

p1 = 9/4 • 1/9 = ¼

p2 = 9/4 • 1/3 = ¾

Оптимальная смешанная стратегия игрока I:

P = (1/4; 3/4)

q1 = 9/4 • 0 = 0

q2 = 9/4 • 5/18 = 5/8

q3 = 9/4 • 1/6 = 3/8

Оптимальная смешанная стратегия игрока II:

Q = (0; 5/8; 3/8)

Поскольку ранее к элементам матрицы было прибавлено число 1, то вычтем это число из цены игры. 9/4 — 1 = 5/4

Цена игры: v=5/4/

Поделиться этим