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

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


                                                      Bv = b Þ v = B -1b .

    Умножим обе части равенства (2) на B -1 слева
                                                          n
                                            u+        åB
                                                     k = r +1
                                                                    -1
                                                                         Ak u k = B -1b = v .                                                (3)

    Обозначим

                                                   æ g 1k ö
                                                   ç ÷
                                            B Ak = ç L ÷ , k = r + 1,L, n
                                                -1

                                                   çg ÷
                                                   è rk ø

и перепишем (3) в координатной форме

                                 u 1 = v1 - g 1r +1u r +1 - L - g 1k u k - L - g 1n u n ,

                            …………………………………………..

                                  u i = v i - g ir +1u r +1 - L - g ik u k - L - g in u n ,

                            …………………………………………..

                             u r = v r - g rr +1u r +1 - L - g rk u k - L - g rn u n .                                                       (4)

    Преобразуем целевую функцию
                                                                              n                            n
                            I (u ) = c, u = c , v -                         åB
                                                                           k = r +1
                                                                                      -1
                                                                                           Ak u k + å ck u k =
                                                                                                       k = r1




                                                                                                 å[ c, B                                ]
                        n                                       n                                  n
          = с, v -    å
                     k = r +1
                                c , B -1 Ak ×u k +             å ck u k = с , v -
                                                              k = r1                            k = r +1
                                                                                                                      -1
                                                                                                                           Ak - c k ×u k .   (5)

    В силу очевидного равенства c , v = c, v = I (v ) из (5) выводим, что

                                        n                                                                         n
               I (u ) = I (v) -        åD u
                                      k =r +1
                                                 k
                                                      k
                                                              , D k = c , B -1 Ak - c k =                       åc g
                                                                                                               s = r +1
                                                                                                                          s   sk   - ck .    (6)

    Информацию, содержащуюся в формулах (4),(6), удобно поместить в
таблицу (рис. 5).




                                                                           68