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

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


    Доказательство. Действительно, для любой из точек v1 , L , v s справедливо
представление
                           m              m
                     v j = åa ji u i , åa ji = 1, a ji ³ 0,             j = 1, L s, i = 1,L, m .
                           i =1           i =1


                                                                   s
    Тогда для любых чисел b 1 ³ 0, L, b s ³ 0, å b j = 1 имеет место равенство
                                                                j -1


                                                            s           s    m         m
                                                                                           æ s        ö
    А        E                    B                   w = å b j v j = å b j åa ji ui =å çç å b ja ji ÷÷ ui .
                                                          j =1        j =1  i =1      i =1 è j =1     ø

                                                                   æ                        ö÷
                                                          å ççççèå b a                       ÷÷ = å b j å (a ji ) = å b j = 1, ,
                                                            m           s                          s    m            s


                                                            i =1       j =1
                                                                                   j   ji
                                                                                              ÷ø j =1 i=1           j=1
                  М

                                                      Очевидно, что

                                                                              åb a
                                                                               s
                                                                                                  ³ 0, i = 1,L, m
                                      C                                       j =1
                                                                                        j    ji
             F
    D
                                                 и точка w будет выпуклой комбинацией точек
            Рис. 2
                                                 u1 ,L , u m . Теорема доказана.

    Из доказанной теоремы легко выводится, например, что любая точка n -
мерного куба является выпуклой комбинацией своих вершин. Действительно,
покажем это на примере двухмерного куба (квадрата). На рис. 2 видно, что
точка M является выпуклой комбинацией точек E и F . Те, в свою очередь,
являются выпуклыми комбинациями вершин A, B и C, D , соответственно.
Таким образом, точка M является выпуклой комбинацией вершин куба.

        В тех случаях, когда рассматриваемое множество не выпукло, бывает
полезно расширить его до выпуклого множества.

    Определение 21. Пересечение всех выпуклых множеств, содержащих
множество U Ì R n , называется выпуклой оболочкой множества и обозначается
символом co U .

    Множество co U выпукло как пересечение выпуклых множеств, и оно
содержится в любом выпуклом множестве, содержащим U . Таким образом,
                                                       20