Page 58 - 6449

 ~ ~ ~ ~
 a 11 x 1  a 21 x 2  a 31 x 3  ...  a m 1 x m  1
 ~ ~ ~ ~
a 12 x  a 22 x  a 32 x  ...  a m 2 x  1
 1 2 3 m , (2.21)
.......... .......... .......... .......... .......... .......... ...
 ~ ~ ~ ~
a 1n x  a 2n x  a 3n x  ...  a mn x  1
 1 2 3 m

Причому для змінної x ставиться умова
i
x  , 0 i 1 ,..., m.
i
Таким чином, (2.21) вже задовольняє всім умовам, що висуваються
до ОДР задачі лічильного програмування. Необхідно встановити вид
цільової функції: оскільки з (2.20) випливає така умова:
m 1
 x i  , (2.22)
 i 1 
при цьому враховується (2.15), то остаточно можна форматувати наступну
задачу лінійного програмування: оскільки величина γ повинна бути
_
якнайбільшою, то обернена величина  повинна бути якнайменшою. Тому
потрібно знайти:
m 1
Z   x i  _  min (2.23)
 i 1 
за умов (2.21):

 ~ ~ ~ ~
 a11 x 1  a21 x 2  a31 x 3  ...  am1 x m  1
 ~ ~ ~ ~
a
 12 x 1  a22 x 2  a32 x 3  ...  am2 x m  1
 .......... .......... .......... .......... .......... .......... ...
 (2.24)
 ~ x ~ x ~ x  ... ~ x
 a n1 1  a n2 2  a n3 3  amn m  1
x i  0

 i  ,...,m1 .

Задача (2.23)-(2.24) вирішується симплекс методом з
використанням методу штучного базису: спочатку знаходимо величини x ,
i
після чого знаходимо величини за такою схемою:
1 ~
n ~ m  p  x 
x   x     x   i i (2.25)
i i i  ~
 i 1  i 1
     M
– якщо  0 – ситуація виграшна для гравця А;
– якщо  0 – ситуація програшна для гравця А;

– якщо  0 – ситуація нічийна.
Приклад 3: розв’язати гру, задану матрицю знайдемо нижню ціну
гри:

58