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

UptoLike

ВУЗ: 

ПГНИУ | Пермь

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

Рубрика: 

5. ПРИМЕНЕНИЕ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ В ТЕОРИИ ИГР
116
(
)
(
)
(
)
(
)
{
}
,,,,,, WVUVUIVUIVUI Î"££
****
(2)
(
)
(
)
(
)
(
)
{
}
,,,
~
,
~
,
~
,
~
WVUVUIVUIVUI Î"££ (3)
Положим в (2) слева VV
~
= , справа UU
~
= , а в (3) слева
*
= VV , справа
*
= UU . Тогда
(
)
(
)
(
)
(
)
(
)
VUIVUIVUIVUIVUI
~
,
~
,
~
,
~
,
~
,
*****
££££ , (4)
откуда вытекает равенство
(
)
(
)
VUIVUI
~
,
~
, =
**
. Из неравенств (2) и (4) следует,
что при любом
{
}
VV Î
выполняется
(
)
(
)
(
)
VUIVUIVUI
~
,,,
****
=£ ,
а из неравенств (3) и (4) – что при любом
{
}
UU Î выполняется
(
)
(
)
(
)
VUIVUIVUI
~
,
~
,
~
~
, £=
**
.
Оба эти неравенства дают
(
)
(
)
(
)
(
)
{
}
WVUVUIVUIVUI Î"££
***
,,
~
,
~
,,
,
что и означает
(
)
EÎ
*
VU
~
, . Соотношение
(
)
EÎ
*
VU,
~
получается благодаря
аналогичным рассуждениям. Теорема доказана.
Установим связь между седловыми точками функции платы и наилучшими
гарантирующими стратегиями игроков. Справедливо следующее утверждение.
Теорема 3. Для выполнения включения
(
)
EÎ
**
VU , необходимо и
достаточно, чтобы
**
VU , были наилучшими гарантирующими стратегиями
первого и второго игроков соответственно, и имело место равенство
*
*
= II . (5)
Доказательство. Необходимость. Пусть
(
)
EÎ
**
VU ,
и, следовательно,
выполнено двойное неравенство (1). Тогда
(
)
(
)
{
}
{}
(
)
(
)
,,,max,,
VV
IUVIUVVVIUVIUV
******
Î
,
(
)
(
)
{
}
{}
(
)
(
)
,,,min,,
UU
IUVIUVUUIUVIUV
******
Î
³"ÎÞ³
.
Таким образом,
{}
{}
(
)
{}
(
)
(
)
{}
(
)
{}
{}
(
)
minmax,max,,min,maxmin,
UUUUUU
VVVVVV
IIUVIUVIUVIUVIUVI
*
*******
ÎÎÎ
ÎÎÎ
=££££=
. (6)
Из теоремы 1 следует, что в соотношении (6) все знаки «
£
» надо
заменить знаками «=». Отсюда следует справедливость необходимости.
Достаточность. Из очевидного неравенства 
5. ПРИМЕНЕНИЕ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ В ТЕОРИИ ИГР


                                  I (U * ,V ) £ I (U * ,V* ) £ I (U ,V* ), "(U ,V )Î {W },                                               (2)
                                        (~        ~ ~
                                                     ) (      ~
                                                                   ) (           )
                                       I U ,V £ I U ,V £ I U ,V , "(U ,V ) Î {W },                                                       (3)
                                       ~                               ~
Положим в (2) слева V = V , справа U = U , а в (3) слева V = V* , справа U = U * . Тогда
                                   (     ~
                                                 )            ~         ~ ~
                                                                            () ( ) ( )~
                                  I U * ,V £ I (U * ,V* ) £ I U ,V* £ I U ,V £ I U * ,V ,                       (4)
                                                          I (U ,V ) = I (U ,V ) . Из неравенств (2) и (4) следует,
                                                                         ~ ~
откуда вытекает равенство                                     *    *


что при любом V Î {V } выполняется
                                                                                     ~
                                                                                       (
                                                 I (U * ,V ) £ I (U * ,V* ) = I U * ,V ,            )
а из неравенств (3) и (4) – что при любом U Î {U } выполняется
                                                      (     ~
                                                                  ) (
                                                                  ~ ~           ~
                                                                                 ) (
                                                     I U * ,V = I U * ,V £ I U ,V .             )
Оба эти неравенства дают
                                                      ~
                                                          (      ~
                                                                  ) (            )
                                 I (U * ,V ) £ I U * ,V £ I U * ,V , " (U ,V ) Î {W },

что и означает (U * ,V )Î E . Соотношение (U ,V* )Î E получается благодаря
                                       ~                                                   ~

аналогичным рассуждениям. Теорема доказана.
     Установим связь между седловыми точками функции платы и наилучшими
гарантирующими стратегиями игроков. Справедливо следующее утверждение.
     Теорема              3.    Для         выполнения                      включения                   (U * ,V* )Î E       необходимо    и
достаточно, чтобы U * ,V* были наилучшими гарантирующими стратегиями
первого и второго игроков соответственно, и имело место равенство
                                                                   I* = I * .                                                            (5)
      Доказательство. Необходимость. Пусть (U * ,V* )Î E и, следовательно,
выполнено двойное неравенство (1). Тогда
                          I (U* ,V ) £ I (U * ,V* ) , "V Î {V } Þ max I (U * ,V ) £ I (U * ,V* ) ,
                                                                                 V Î{V }


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


      Таким образом,
   I * = min max I (U * ,V ) £ max I (U * ,V ) £ I (U* ,V* ) £ min I (U ,V* ) £ max min I (U ,V* ) = I * . (6)
        U Î{U } V Î{V }                V Î{V }                                        U Î{U }                  V Î{V } U Î{U }


      Из теоремы 1 следует, что в соотношении (6) все знаки « £ » надо
заменить знаками «=». Отсюда следует справедливость необходимости.
      Достаточность. Из очевидного неравенства
                                                                           116

Страницы