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

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


      Найдем седловую точку в классе смешанных стратегий. Для этого
поставим   и   решим      следующие                 взаимодвойственные                       задачи   линейного
программирования:
                           x1 + x 2 + x 3 + x 4 + x 5 ® max,
                           x1 + 2 x 2 + 6 x 4 + 4 x 5 £ 1,
                           2 x1 + x 2 + 5 x 3 + 3x 4 + 13x 5 £ 1,
                           7 x1 + 5 x 2 + 5 x 3 + 2 x 4 + 46 x 5 £ 1,
                           2 x1 + 3x 2 + 9 x 3 + x 4 + 25 x 5 £ 1,
                           4 x1 + 8 x 2 + 2 x 3 + 4 x 4 + 38 x 5 £ 1,
                           x1 ³ 0, x 2 ³ 0, x 3 ³ 0, x 4 ³ 0, x 5 ³ 0,



                          y1 + y 2 + y 3 + y 4 + y 5 ® min,
                          y1 + 2 y 2 + 7 y 3 + 2 y 4 + 4 y 5 ³ 1,
                          2 y1 + y 2 + 5 y 3 + 3 y 4 + 8 y 5 ³ 1,
                          5 y 2 + 5 y 3 + 9 y 4 + 2 y 5 ³ 1,
                          6 y1 + 3 y 2 + 2 y 3 + y 4 + 4 y 5 ³ 1,
                          4 y1 + 13 y 2 + 46 y 3 + 25 y 4 + 38 y 5 ³ 1,
                          y1 ³ 0, y 2 ³ 0, y 3 ³ 0, y 4 ³ 0, y 5 ³ 0.

     Решениями этих задач будут соответственно векторы
                                         æ 701   22 ö              æ 701    81 ö
                                         çç ÷÷                     çç ÷÷
                                          çç 140213 ÷
                                                      ÷             çç 0 ÷÷
                                           çç ÷÷÷                    ç ÷÷÷
                                   x0 = çç 1402 117 ÷
                                                      ÷,    y0 = ççç 701   74 ÷
                                                                                 ÷.
                                            çç 111 ÷÷                çç 35 ÷÷
                                             çç 701 ÷÷÷               çç 701 ÷÷÷
                                              çç 0 ÷÷                  çç 8 ÷÷
                                              è ø÷                      èç 701 ø÷÷

                                                                                           198
     Общее     значение     целевых              функций                     равно    s=       .   Оптимальные
                                                                                           701
смешанные стратегии игроков здесь имеют вид
                                      æ 19 ö÷              æ 229 ö÷
                                      çç ÷                 çç ÷
                                       çç 39613 ÷
                                                ÷÷          çç 0 ÷÷
                                        ç        ÷           çç ÷÷÷
                                        ç    13 ÷
                               1                    1
                           u0 = x0 = çç 44 ÷÷ , v0 = y0 = çç 37          ÷
                                                                    99 ÷ ,
                               s        çç 37 ÷÷÷   s         çç 35 ÷÷
                                         çç 66 ÷÷              çç 198 ÷÷÷
                                          çç 0 ÷÷               çç 4 ÷÷
                                           è ø÷                  èç 99 ø÷÷

а цена игры равна
                                                   1 701
                                 M (u0 , v0 ) = d = =    .
                                                   s 198
                                                      124