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

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


     Усложним задачу. Потребуем, чтобы для построенной точки w еще
выполнялось бы неравенство I ( w) < I (v) . В силу формулы (6) справедливо
равенство

                                            I ( w) = I (v) - D k u *k ,                                     (8)

поэтому номер k Î {r + 1,L , n} следует искать из множества K = {k                             D k > 0} .

     Теорема 3. Пусть K = Æ . Тогда угловая точка v является решение задачи
2.
                                                                            n
     Доказательство. Из равенства I (u ) = I (v) -                        åD u
                                                                          k =r +1
                                                                                    k
                                                                                        k
                                                                                            , положительности

величин u k , k = r + 1, L , n для всех u Î U и условия теоремы следует, что
I (u ) ³ I (v ), "u ÎU . Последнее и означает, что точка v – решение исходной

задачи. Теорема доказана.

     Теорема 4. Пусть K ¹ Æ и существует номер k Î K , такой, что g ik £ 0 для
всех i = 1,L, r . Тогда I * = -¥ .

     Доказательство. В силу неположительности коэффициентов g ik для всех
i = 1, L, r из (7) следует, что w i ³ 0,                    i = 1, L, r , при любом u *k ³ 0 . Тогда в

соответствии с формулой (8) выбором u*k > 0 можно добиться, чтобы
величина I (w) была меньше любого наперед заданного числа. Теорема доказана.

     Рассмотрим случай, когда K ¹ Æ и для всех номеров k Î K множество
I k = {s Î {1, L, r} g sk > 0} ¹ Æ . Для произвольного индекса k Î K определим номер i *

из условия
                                                   *
                                              vi               ì vs ü
                                                       = min í ý .
                                             gi k
                                                *
                                                         sÎ I k g
                                                               î sk þ
                                      *
                                 vi
     Для величины u =       k
                            *             все правые части в равенствах (7) будут
                                g i *k

неотрицательны. Действительно, это утверждение очевидно, если g ik £ 0 . Для
случая g ik > 0 его справедливость можно проверить из формулы
                                                       70