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

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


     Теорема 8. Множество U Ì R n выпукло тогда и только тогда, когда оно
содержит все выпуклые комбинации любого конечного числа своих точек.

     Необходимость. Пусть множество U выпукло. Проведем индукцию по
числу m . При m = 2 справедливость утверждения теоремы вытекает сразу из
определения выпуклого множества. Предположим, что утверждение теоремы
верно    для      любого            k £ m - 1, m > 2 .        Рассмотрим             произвольную       выпуклую
комбинацию каких-либо m точек этого множества
                                m                                                     m
                      u = å a i u i , u1 ,L , u m ÎU , a 1 ³ 0, L , a m ³ 0,          åa     i   = 1.
                            i =1                                                      i =1



     Для определенности примем, что a m < 1 . Тогда

                                                                   m -1

                                              m -1
                                                     ai            åa     i

                                              å1-a            =    i =1
                                                                   m -1
                                                                              =1,
                                              i =1        m
                                                                   åa
                                                                   i =1
                                                                          i




               m -1
                    æ ai        ö
и точка v = å çç                ÷÷ u i является выпуклой комбинацией точек u1 ,L , u m -1 ÎU . В
               i =1 è 1 - a m    ø

силу предположения индукции v ÎU . Нетрудно видеть, что справедливо
равенство u = (1 - a m )v + a m u m . Отсюда и из выпуклости множества U следует
u ÎU . Необходимость доказана.

     Достаточность. Если множество U Ì R n                                          содержит все выпуклые
комбинации любого конечного числа своих точек, то оно содержит, в
частности, и любые выпуклые комбинации любых своих двух точек,
следовательно, оно выпукло. Достаточность доказана.

     Приведем одно простое свойство выпуклых комбинаций конечного числа
точек из R n .

     Теорема 9. Пусть u1 , L , u m Î R n – фиксированные точки и v1 , L , v s – их
произвольные выпуклые комбинации. Тогда любая выпуклая комбинация точек
v1 , L , v s является выпуклой комбинацией точек u1 , L , u m .



                                                              19