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

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


    В силу(1), (2) для всех t Î R 1 справедливы равенства
            m                        m                 m                    m                       m          m

            å (a
            i =1
                   i   - tg i ) u i = å a i u i - t å g i u i = u,
                                     i =1           i =1
                                                                            å (a
                                                                            i =1
                                                                                      i   - tg i ) = å a i - t å g i = 1 .
                                                                                                    i =1      i =1



    Поскольку не все числа g 1 ,L, g m равны нулю, а их сумма равна нулю, постольку
среди них найдутся строго положительные.                                                   Полагаем I = {i Î {1,L , m} g i > 0}.

Определим номер s и число t * из условия

                                                            as        æa           ö
                                                   t* =        = min çç i          ÷÷ .
                                                            gs   iÎI
                                                                      ègi           ø

    Для     всех          номеров            i = 1, L, m         справедливо                     неравенство            a i - t *g i ³ 0 .

Действительно, для номеров i Ï I это очевидно, а для номеров i Î I вычисляем

                                                  as            a
                           a i - t *g i = a i -      g i ³ a i - i g i = 0, a s - t *g s = 0 .
                                                  gs            gi

    Таким образом, точку                           u         удалось представить в виде выпуклой
.комбинации меньшего, чем m числа точек из множества U . Теорема
доказана.

    1.8. Опорные функции и множества. Пусть U Ì R n - компактное
множество.

    Определение 22. Функция c : R n ® R1 , определенная равенством
                                                   c (U , v ) = max u, v , v Î R n ,                                                 (1)
                                                                      uÎU


называется опорной функцией множества U .
      В силу теоремы Вейерштрасса максимум в (1) действительно достигается
при любом v Î R n . Пусть для некоторого вектора c Î R n , c ¹ 0 справедливо
                                            u0 , c = max u, c = c (U , c) .                                                          (2)
                                                           uÎU


      Определение 23. Вектор c называется опорным вектором к множеству
U в точке u0 Î U . Множество

                                                   {
                                    V (c,U ) = u0 Î U             u0 , c = max u, c
                                                                                     uÎU
                                                                                                   }
называется опорным множеством к множеству U в направлении вектора c .
                                                                 22