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

5. ПРИМЕНЕНИЕ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ В ТЕОРИИ ИГР


где d n Î R n , d m Î R m - вектора, координаты которых равны одному и тому же
числу u0 , Av0 . Умножим первое неравенство в (3) скалярно на вектор v Î V .

Учитывая, что v ³ 0 , имеем
                                                                   æ n      ö
                AT u0 , v £ d n , v = å u0 , Av0 v j = u0 , Av0 ççç å v j ÷÷÷ = u0 , Av0 .
                                        n
                                                                                                      (4)
                                      j =1                        çè j =1 ÷ø

Аналогично, второе неравенство в (3) умножим на вектор u Î U . Учитывая,
что u ³ 0 , в результате получим
                                                                   æ m ö
           Av0 , u = u , Av0 ³ d m , u = å u0 , Av0 u i = u0 , Av0 çç å u i ÷÷÷ = u0 , Av0 .
                                          m
                                                                                                      (5)
                                         i=1                       èç i =1 ø

Из (4) и (5) выводим, что
                             AT u0 , v £ u0 , Av0 £ u, Av0 , "u Î U , "v Î V .

       Последнее двойное неравенство означает выполнение условия (1)
Достаточность доказана.
       Матрица A игры может быть произвольной матрицей размера m ´ n . Тем
не менее, при необходимости можно все ее элементы считать положительными
числами. Это следует из следующего утверждения.
       Лемма 1. Пара стратегий (u0 , v0 ) Î U ´V образует седловую точку в

матричной игре с матрицей A тогда и только тогда, когда для любого числа
a Î R1 . Эта же пара стратегий образует седловую точку в матричной игре с

матрицей A , где матрица A составлена из элементов вида aij = aij + a,
i Î {1,L, m},   j Î {1,L, n}

       Доказательство. Обозначим функцию платы в игре с матрицей A
символом M . Тогда для всех u Î U , v Î V имеем

         M (u, v ) = åå aij u i v j = åå (aij + a ) u i v j = åå aij u i v j + a åå u i v j =
                      m     n                m    n                     m   n             m     n


                      i=1   j=1             i =1 j =1                  i=1 j =1           i =1 j =1


                                         æ n       ö
            = åå aij u i v j + a å u i ççç å v j ÷÷÷ = åå aij u i v j + a å u i = M (u, v ) + a .
                m   n             m                    m   n               m


              i =1 j=1           i=1     çè j =1 ÷ø i =1 j =1             i=1


Таким образом, двойное неравенство
                                M (u0 , v ) £ M (u0 , v0 ) £ M (u, v0 ) , u Î U , v Î V


                                                         121