Линейные задачи оптимизации. Ч.1. Линейное программирование. Лутманов С.В. - 117 стр.

UptoLike

ВУЗ: 

ПГНИУ | Пермь

Составители: 

Рубрика: 

5. ПРИМЕНЕНИЕ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ В ТЕОРИИ ИГР
117
(
)
{}
(
)
{
}
{
}
,min,,,
UU
IUVIUVUUVV
Î
³"Î"Î
и определения наилучшей гарантирующей стратегии второго игрока следует,
что для всех
{
}
UU
Î
при
VV
*
имеет место условие
(
)
{}
(
)
{}
{}
(
)
,min,maxmin,
UUUU
VV
IUVIUVIUVI
***
ÎÎ
Î
³==
. (7)
Аналогично из неравенства
(
)
{}
(
)
{
}
{
}
,max,,,
VV
IUVIUVUUVV
Î
£"Î"Î
и определения наилучшей гарантирующей стратегии первого игрока следует,
что для всех
{
}
VV
Î
при
UU
*
=
имеет место условие
(
)
{}
(
)
{}
{}
(
)
,max,minmax,
UU
VVVV
IUVIUVIUVI
*
**
Î
ÎÎ
£==
. (8)
Из (7) и (8) с учетом равенства (5) получим
(
)
(
)
{
}
{
}
,,,,
IUVIUVUUVV
**
³"Î"Î
. (9)
Полагая в (9) последовательно ,
UUVV
**
==
, будем иметь
(
)
(
)
{
}
,,,
IUVIUVVV
***
³"Î
,
(
)
(
)
{
}
,,,
IUVIUVVV
***
³"Î
.
Последние неравенства и означают выполнение двойного неравенства (1).
Достаточность доказана.
Определение 7. Антагонистическую игру двух лиц, в которой существует
седловая точка, будем называть вполне определенной, а величину
*
*
== III
0
–
ценой игры.
5.3. Матричные игры. Рассмотрим антагонистическую игру двух лиц, в
которой каждый игрок располагает конечным числом различных стратегий. В
частности, пусть множество
{
}
U
содержит
m
элементов, а множество
{
}
V
-
n
элементов. Обозначим
(
)
{
}
{
}
{
}
{
}
,,,,1,,,1,,
ijijij
aIUVUUVVimjn
=ÎÎÎÎ
LL
.
Вся информация об исходах игры содержится в матрице
11121
21222
12
n
n
mmmn
aaa
aaa
A
aaa
æö
÷
ç
÷
ç
÷
ç
÷
ç
÷
ç
÷
=
÷
ç
÷
ç
÷
ç
÷
ç
÷
ç
÷
÷
ç
èø
ç
÷
L
L
LLLL
L
. 
5. ПРИМЕНЕНИЕ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ В ТЕОРИИ ИГР


                          I (U ,V ) ³ min I (U ,V ) , "U Î {U } , "V Î {V }
                                       U Î{U }


и определения наилучшей гарантирующей стратегии второго игрока следует,
что для всех U Î {U } при V = V* имеет место условие
                         I (U ,V* ) ³ min I (U ,V* ) = max min I (U ,V ) = I * .                      (7)
                                      U Î{U }                V Î{V } U Î{U }


Аналогично из неравенства
                           I (U ,V ) £ max I (U ,V ), "U Î {U } , "V Î {V }
                                       V Î{V }


и определения наилучшей гарантирующей стратегии первого игрока следует,
что для всех V Î {V } при U = U * имеет место условие
                          I (U * ,V ) £ max I (U* ,V ) = min max I (U ,V ) = I * .                    (8)
                                       V Î{V }                 U Î{U } V Î{V }


    Из (7) и (8) с учетом равенства (5) получим
                                  I (U ,V* ) ³ I (U * ,V ) , "U Î {U } , "V Î {V } .                  (9)

     Полагая в (9) последовательно U = U * , V = V* , будем иметь
              I (U ,V* ) ³ I (U * ,V* ) , "V Î {V } ,       I (U * ,V* ) ³ I (U * ,V ), "V Î {V } .

Последние неравенства и означают выполнение двойного неравенства (1).
Достаточность доказана.
    Определение 7. Антагонистическую игру двух лиц, в которой существует
седловая точка, будем называть вполне определенной, а величину I 0 = I * = I * –
ценой игры.
    5.3. Матричные игры. Рассмотрим антагонистическую игру двух лиц, в
которой каждый игрок располагает конечным числом различных стратегий. В
частности, пусть множество {U } содержит m элементов, а множество {V } - n
элементов. Обозначим
               aij = I (U i ,V j ), U i Î {U } , V j Î {V }, i Î {1,L, m} , j Î {1,L, n} .

     Вся информация об исходах игры содержится в матрице
                                           æ a11 a12          L a1n ö÷
                                           çç                          ÷
                                            çç a     a22      L a2 n ÷÷÷
                                      A = çç 21                        ÷.
                                             çç L L           L L ÷÷÷
                                              çç                       ÷÷
                                               çèam1 am 2     L amn ÷÷ø


                                                     117

Страницы