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

3. МЕТОДЫ РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ


       Из доказанной теоремы, в частности, следует, что число угловых точек у
                                                                                     n!
множества U           не превосходит величины Cnr =                                                и, следовательно,
                                                                                r !(n - r )!

конечно.

       Определение 2. Систему векторов A j ,L , A j будем называть базисом
                                                                      1         r



угловой точки v , а соответствующие им координаты v j ,L, v j – базисными                      1         r




координатами точки v .

       Определение          3.    Если           все     базисные             координаты                угловой           точки
положительны (строго больше нуля), то ее называют невырожденной.

       Теорема 2. Если угловая точка невырожденная, то она имеет единственный
базис.

       Доказательство. Пусть A j ,L , A j – невырожденный базис угловой точки
                                                 1       r



v множества U . Покажем, что любой другой базис A j ,L, A j                                        1*             r*
                                                                                                                       этой же

угловой точки с ним совпадает. Действительно, по условию 2) теоремы 1 для
всех     индексов            {
                         j Ï j1* ,L , j p*   }       должно           выполняться                  v j = 0.            Тогда   из

невырожденности базиса A j ,L, A j следует, что j Ï { j1 ,L, j r } и
                                        1            r




                                        { j1 ,L , j r } Ì {j1 ,L, j r }.
                                                                  *       *                                                    (8)

       Число элементов в каждом из множеств { j1 ,L , j r } , { j1 , L, j r                         *         *   }    конечно и

одинаково, поэтому вложение (8) влечет за собой искомое совпадение базисов.
Теорема доказана.

       Пример 4. Пусть

                   ì    æ u1 ö                          æ u1 ö                                 æ u1 ö   ü
                   ï    ç 2÷                            ç ÷                                    ç 2÷     ï
                   ï    çu ÷            æ1   3 1 2 9 ö ç u 2 ÷ æ11ö                            çu ÷     ï
                   ï                    ç            ÷ ç 3÷ ç ÷                                ç 3 ÷ ³ 0ï .
               U = íu = ç u 3 ÷ Î R 5   ç 2 -1 4 1 1÷ × çu ÷ = ç 2 ÷,                            u      ý
                        ç ÷                                                                    ç ÷
                   ï    çu 4 ÷          ç -1 2 2 -1 2÷ çu 4 ÷ ç 1 ÷                            çu 4 ÷   ï
                   ï                    è            ø         è ø                                      ï
                        ç 5÷                            ç 5÷                                   ç 5÷
                   ïî   èu ø                            èu ø                                     u
                                                                                               è ø      ïþ

       Здесь

                                                             65