12.11. Зведення матричної гри до задачі лінійного програмування

Розглянемо гру, у якій матриця А має розмірність m • n, A = {%}. Матриця не містить сідлової точки, тому рішення гри знаходиться в змішаних стратегіях x*= (x1, x2,     xm), y*= (yi, y2,

-, yn).

При оптимальній стратегії гравця А виконується умова:

m

X x, • ap > v (для гравця А),

, = 1

X y ■ ■ ar < v (для гравця Б).

Таким чином, можна розглянути задачу пошуку оптимальної стратегії гравця А, для якої мають місце такі обмеження:

«іЛ + а21Х2 + ... + amixm > V

^ 1,Л ~r"2n-A'2^-^ "mn-^m ^

X x, = 1

Розділимо кожен рядок на v.

t =x

v

«11t1 + «21t2 + ... + «m1tm > 1 a12t1 + a22t2 + ... + am2tm > 1

la1nt1 + a2nt2 + ... + amntm > 1


Аналогічну систему запишемо для гравця Б.

\апУі + аиу2 +... + а1пУп < v

«21У1 + «22у2 + ... + а2пуп < V

a 1 Vi + a 2 y2 +... + a   y < v

1  1      2   2     п п

IVi = 1


V


, тоді


v

a11d1 + a12d2 +... + a1ndn < 1 a21d1 + a22d2 +... + a2ndn < 1

«m 1d1 + am2d2 + ... + anmdn < 1

i i

I yj =I djv.

У j

Величина v (ціна гри) не відома, але можна вважати, що вона більша ніж 0. Ця умова виконується завжди, якщо елементи мат­риці не є негативні (якщо є негативні елементи, то потрібно додати до всіх елементів матриці деяке позитивне число). Рішення гри по­винне максимізувати значення v для гравця А (f (x) = v -> max),

значить функція Z = I ti -> min, тому що tt

Отже, отримана задача лінійного програмування. Цільова фу­нкція має вигляд:

Z = I ti — min

i=1

обмеження:

I ayt, > 1

i

1

Li=1 v


Розв'язуючи цю систему, знайдемо и і відповідну величину — ,

V

а потім знайдемо значення хі = V • іі. Аналогічно для гравця Б:

D = £ dj —> max , £a;yJy < 1,(z = 1,...,от)

Розв'язуючи систему, знайдемо dj і —.

v

Е^/ =- > З7/ = v • (і:.

Ця задача називається парою двоїстих симетричних задач лі­нійного програмування. Використовуючи властивість симетрич­ності, можна розв'язати одну з задач, що вимагає менше обчис­лень, а розв'язання другої задачі знайти на підставі оптимального плану двоїстої. Для розв'язання таких задач у математичному програмуванні розроблені спеціальні методи, наприклад симпле­ксний метод.