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

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


игроков соответственно. Покажем, что именно эти стратегии образуют
                                                                                     1
седловую точку в матричной игре, а величина d =                                        - служит ее ценой. В самом
                                                                                     s
деле,
                                           1                           1
                       AT x0 £ en Þ AT u0 £ en = d n , Ay0 ³ em Þ Av0 ³ em = d m .                            (7)
                                           s                           s
        По теореме 4.8 (равновесия) всякий раз из неравенства y0j > 0 следует

равенство ( AT x0 ) = 1, j Î {1,L, n} . Отсюда и в силу равенства (6) выводим
                       j




                                       x0 , Ay0 = AT x0 , y0 = å ( AT x0 ) y0j = e n , y0 = s .
                                                                              n
                                                                                    j
                                                                                                              (8)
                                                                              j=1


                1                         1
С учетом u0 = x0 , v0 = y0 из (8) находим
                s                         s
                                                                                    1
                                          su0 , A( sv0 ) = s Þ u0 , Av0 =             =d .                    (9)
                                                                                    s
        Объединяя условия (7) и (9), приходим к неравенствам

                      ( AT u0 ) £         u0 , Av0 £ ( Av0 ) , i Î {1,L, m} ,           j Î {1,L, n} Þ
                                  i                                 j




               å a u £ åå a u v                            £ å aij v0j , "j Î {1,L, n} , "i Î {1,L, m} .
                m                     m       n               n
                              i                      i j
                           ij 0                   ij 0 0
               i =1                   i =1 j =1               j=1


Тогда по теореме 4 смешанные стратегии u0 , v0 образуют седловую точку.
Теорема доказана.
        Пример 5. Рассмотрим матричную игру с матрицей
                                                        æ1 2 7 2 4 ö÷
                                                        çç                    ÷
                                                         çç 2 1 5 3 8 ÷÷
                                                          çç                  ÷÷
                                                   A = çç 0 5 5 9 2 ÷÷÷ .
                                                           çç                  ÷÷
                                                            çç 6 3 2 1 4 ÷÷÷
                                                             çç 4 13 46 25 38÷÷
                                                              è                 ø÷

Наименьший элемент среди наибольших элементов из каждой строки равен 6.
В то же время наибольший элемент среди наименьших элементов из каждого
столбца равен 4. Таким образом,
                                                            I* = 5 < 6 = I * ,

и седловая точка в классе чистых стратегий в данной матричной игре не
существует.

                                                                        123