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

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


A j1 ,L, A j k   надо        добавить         столбцы                      A jk +1 , L , A jr   так, чтобы полученная

совокупность столбцов A j ,L , A j матрицы A была линейно независима. Это
                                        1          r



можно сделать, так как ранг матрицы A равен r . Номера j1 , L, j r будут
искомыми. Необходимость доказана.

                                æ v1 ö
                                ç ÷
       Достаточность. Пусть v = ç L ÷ Î U и
                                ç n÷
                                èv ø

                                                  v = av1 + (1 - a )v2                                            (6)

при некоторых v1 , v 2 Î U ,a Î (0,1) . Покажем, что равенство (6) возможно только
при v1 = v 2 = v .

       Прежде всего заметим, что если v j = 0 , то из 0 £ a × v1j + (1 - a ) × v 2j = 0
следует v1j = v2j = 0 . Остается показать, что v1j = v 2j и при тех номерах j , для
которых v j > 0 . Перечислим все такие номера: j1 , L, j k . В силу условия 2)
теоремы k £ r . Поскольку координаты вектора v отличны от нуля только для
номеров j1 , L, j k , то из равенства (1) следует

                                            Av = A j1 v j1 + L + A jk v jk = b .                                  (7)

       Из включения vi Î U следует равенство Av i = b, i = 1,2 . Координаты вектора
vi отличны от нуля тоже только для номеров j1 , L, j k , поэтому

                                     Avi = Aj1 vij1 + L + Ajk vi jk = b , i = 1,2 .

       В силу v j > 0,L, v j > 0 справедливо вложение {A j ,L, A j } Ì {A j ,L, A jr }. По
                     1           1                                                               1    k    1



условию 1) теоремы столбцы A j ,L , A j линейно независимы, следовательно,
                                                       1               r



линейно независимы и столбцы A j ,L , A j . Вектор b выражается через
                                                               1                k



столбцы A j ,L, A j единственным образом. Тогда
                 1       k




                                            v1 p = v 2 p = v p , p = 1, L, k .
                                              j            j       j




       Достаточность доказана.


                                                                   64