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

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


выпуклую оболочку множества U                               можно трактовать как минимальное
выпуклое множество, содержащее U .

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

    Доказательство. Пусть множество W является совокупностью всех
выпуклых комбинаций конечного числа точек из U . Покажем, что co U = W .
Вложение W Ì co U очевидно, так как в силу выпуклости множества co U оно
будет содержать все выпуклые комбинации конечного числа своих точек, в
частности, и точек из множества U Ì co U . Для доказательства обратного
вложения co U Ì W          достаточно установить выпуклость множества W .
Последнее сразу следует из теоремы 6, в силу которой любая выпуклая
комбинация конечного числа точек из множества W                                      будет выпуклой
комбинацией конечного числа точек из множества U . Теорема доказана.

    Теорема 11 (Каратеодори). Пусть U Ì R n – произвольное непустое множество.
Тогда любая точка u Î co U представима в виде выпуклой комбинации не более чем
n + 1 точки из U .

    Доказательство. По теореме 7 любая точка u Î co U представима в виде
                              m                                               m
                     u = åa i u i , a i ³ 0, u i Î U , i = 1,L , m, åa i = 1 .                  (1)
                              i =1                                            i =1



    Покажем, что число ненулевых слагаемых в этом выражении можно
уменьшить, если m > n + 1 . В пространстве R n +1 рассмотрим m векторов вида
       æu ö
u i = çç i ÷÷ , i = 1,L , m . Так как число таких векторов m > n + 1 , то они линейно
       è1ø
зависимы. Тогда существуют такие числа g 1 ,L, g m , не все равные нулю, что
будет выполняться
                       m
                                      æ ui ö       m               m

                      åg          i   çç ÷÷ = 0 Þ å g i u i = 0,   åg     i   =0.               (2)
                       i =1            è1ø        i =1             i =1




                                                          21