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

1. ЭЛЕМЕНТЫ ВЫПУКЛОГО АНАЛИЗА


                                    min l , a £ c( B , l ), " l Î S (0, 1) .                                          (1)
                                     aÎ A



     Доказательство. Необходимость. Пусть A I B ¹ Æ . Справедлива цепочка
неравенств

                  min l , a £ min l , q £ c( A I B, l ) £ c ( B, l ), " l Î S (0, 1) ,
                   aÎ A            qÎ AI B



     что и доказывает необходимость.

      Достаточность. От противного в силу теоремы 25                                                         приходим к
существованию вектора l * Î S (0, 1) , для которого

                                     min l * , a > max l * , b = c B (l * ) .
                                      aÎ A              bÎB



     Последнее соотношение противоречит (1). Теорема доказана.

     Одним из важных следствий отделимости выпуклых множеств является
теорема Фаркаша. Пусть заданы целые числа                                      m £ k £ s, матрицы B* , B** , B

размеров m´ n, (k - m)´ n, ( s - k )´ n , соответственно. Полагаем

                             K = {e Î R n       B* e £ 0, B** e ³ 0, Be = 0} ¹ Æ .

     Теорема 28 (Фаркаша). Для вектора                                      d Î Rn       неравенство             d, e £ 0

выполняется при всех e Î K в том и только в том случае, когда существует
вектор

                       ïìï    æ v * ö÷                                                               ïüï
                         ïï   çç ÷                                                                     ï
                                       ÷
              v Î V% = ív = çç v** ÷÷ Î R s v * Î R m , v * ³ 0, v ** Î R k-m , v ** ³ 0, v Î R s-k ïý
                          ïï   çç ÷÷                                                                   ïï
                           ï    çè v ÷÷ø                                                                ï
                           îï                                                                           þï

     такой, что d = B*T v * - B**T v ** + B T v .

     Доказательство. Необходимость. Пусть для всех e Î K                                                     справедливо
неравенство d, e £ 0 . Требуется доказать, что

                              d Î X = { x = B*T v* - B**T v** + B T v v Î V%} .




                                                           42