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

UptoLike

ВУЗ: 

ПГНИУ | Пермь

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

Рубрика: 

5. ПРИМЕНЕНИЕ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ В ТЕОРИИ ИГР
114
Пусть первый (второй) игрок применяет наилучшую гарантирующую
стратегию
{
}
UU Î
0
(
{
}
VV Î
0
). Тогда, как бы не действовал второй (первый)
игрок, результат игры для первого (второго) игрока будет не хуже, чем
*
I
(
*
I ).
Теорема 1. Справедливо неравенство
{}
{}
(
)
{}
{}
(
)
VUIIIVUI
VV
UUUU
VV
,maxmin,minmax
Î
Î
*
*
Î
Î
=£= . (3)
Доказательство. Запишем очевидное неравенство
(
)
(
)
,max,
VV
IUVIUV
Î
£
, (4)
имеющее место для всех
UU
Î
и
VV
Î
. Возьмем минимум по всем
UU
Î
от обеих частей неравенства (4). В результате получим
{}
(
)
{}
{}
(
)
{}
(
)
(
)
1
min,minmax,min
UUUUUU
VV
IUVIUVIUI
ÎÎÎ
Î
£==
. (5)
Неравенство (5) справедливо для всех
VV
Î
. Возьмем максимум по всем
VV
Î
от обеих частей неравенства (5). Учитывая, что правая часть этого
неравенства не зависит от стратегии
VV
Î
, будем иметь
{}
{}
(
)
{}
(
)
(
)
2
maxmin,max
UU
VVVV
IIUVIVI
*
*
Î
ÎÎ
==£
,
что и требовалось доказать.
Таким образом, «минимакс» всегда не меньше «максимина». В
соотношении (3) возможен как знак равенства, так и знак строгого неравенства.
Убедимся в этом на конкретных примерах.
Пример 1. Пусть
{
}
{
}
[
]
(
)
VUVUIVURVU ×=-==Î ,,1,1,,
1
.
Тогда
(
)
(
)
[]
0max
1,1
1
=Þ=×=
*
-Î
IUVUUI
V
, (6)
(
)
(
)
[]
0min
1,1
2
=Þ-=×=
*
-Î
IVVUVI
U
. (7)
Из равенств (6) и (7) следует, что 0==
*
*
II .
Пример 2. Пусть
{
}
{
}
{
}
(
)
VUVUIVURVU ×=-==Î ,,1,1,,
1
.
Тогда 
5. ПРИМЕНЕНИЕ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ В ТЕОРИИ ИГР


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


        Доказательство. Запишем очевидное неравенство
                                            I (U ,V ) £ max I (U ,V ) ,                              (4)
                                                              V ÎV


имеющее место для всех U Î {U } и V Î {V } . Возьмем минимум по всем U Î {U }
от обеих частей неравенства (4). В результате получим
                    min I (U ,V ) £ min max I (U ,V ) = min I ( ) (U ) = I * .                       (5)
                                                                                          1
                   U Î{U }                  U Î{U } V Î{V }                     U Î{U }


        Неравенство (5) справедливо для всех V Î {V } . Возьмем максимум по всем
V Î {V } от обеих частей неравенства (5). Учитывая, что правая часть этого

неравенства не зависит от стратегии V Î {V } , будем иметь

                               I * = max min I (U ,V ) = max I (2) (V ) £ I * ,
                                       V Î{V } U Î{U }                     V Î{V }


что и требовалось доказать.
        Таким образом, «минимакс» всегда не меньше «максимина».                                  В
соотношении (3) возможен как знак равенства, так и знак строгого неравенства.
Убедимся в этом на конкретных примерах.
     Пример 1. Пусть
                             U ,V Î R 1 , {U } = {V } = [- 1,1], I (U ,V ) = U × V .

Тогда
                                   I (1 ) (U ) = max U × V = U Þ I * = 0 ,                           (6)
                                                 V Î[ -1,1]


                                                I (2 ) (V ) = min U × V = - V Þ I * = 0 .            (7)
                                                              U Î[ -1,1]


Из равенств (6) и (7) следует, что I * = I * = 0 .
     Пример 2. Пусть
                             U ,V Î R 1 , {U } = {V } = {- 1,1}, I (U ,V ) = U × V .

Тогда

                                                              114

Страницы