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

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


имеет место тогда и только тогда, когда выполнено двойное неравенство
                    M (u0 , v ) £ M (u0 , v0 ) £ M (u, v0 ) , u Î U , v Î V .

     Лемма доказана.
     Справедлива     следующая            теорема,         утверждающая         существование
седловой точки в матричной игре в «смешанных» стратегиях.
     Теорема 5 (Джона фон Неймана). Всякая матричная игра в «смешанных»
стратегиях имеет седловую точку.
     Доказательство. Пусть A матрица игры. В силу леммы 1 все элементы
матрицы будем считать положительными. Рассмотрим задачу линейного
программирования.
     Задача 1.
                                        em , x ® max ,

                                   AT x £ en , x ³ 0, x Î R m ,

где en Î R n , em Î R m - вектора, координаты которых равны одному и тому же
числу 1. Построим двойственную к ней задачу.
     Задача 2.
                                         en , y ® min ,

                                   Ay ³ em , y ³ 0, y Î R n .

     Задача 2 имеет решение y0 , так как она допустима (любой вектор y с
достаточно    большими       положительными                координатами         удовлетворяет
ограничениям), а целевая функция задачи ограничена снизу. По теореме 4.6.
тогда и задача 1 имеет решение x0 . При этом справедливо равенство
                                    em , x0 = en , y0 = s .

Легко видеть, что

                           å x0i = em , x0 = s = en , y0 = å y0j .
                            m                                       n
                                                                                          (6)
                            i =1                                   j =1


Вектор y0 ³ 0 не может быть нулевым и поэтому s > 0 . Тогда вектора
    1         1
u0 = x0 , v0 = y0 являются «смешанными» стратегиями первого и второго
    s         s


                                              122