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

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


                                                                                  æ vi           ö
                                                                    *                       *
                                                              vi                          vi
                                  w = v - g ik ×
                                   i         i
                                                                         = g ik × ç     -        ÷ ³ 0.
                                                              g i *k              ç g ik g *     ÷
                                                                                  è        i k   ø

                                            æ vi                        ö
                                                 *              *                                         *
                                                   vi                   ÷ = 0 , а величина u *k = v
                                                                                                     i
      Заметим, что w = g i k i*
                                           ×ç    -                                                            – максимально
                                       *
                                            çg *                        ÷
                                            è i k g i *k                ø                         g i *k

возможная, при которой правые части всех равенств в (7) будут положительны.

      Определение 6. Элемент g i k > 0 назовем разрешающим элементом
                                                                 *




симплекс-таблицы.
                                                          *
                                                     vi
      Таким образом, при u =                 k
                                             *                          точка w , строящаяся по формулам (7),
                                                     g i *k

принадлежит множеству U и имеет вид:

                                             æ 1                                  ö
                                                                              *
                                                             i
                                             ç v - g 1k × v                       ÷
                                             ç            g i *k                  ÷
                                             ç      L                             ÷
                                             ç                                    ÷
                                             ç       0                            ÷
                                             ç      L *                           ÷
                                             ç               i                    ÷
                                             çv - g × v
                                                r                                 ÷
                                           w=ç       rk
                                                          g i *k                  ÷.                                     (9)
                                             ç                                    ÷
                                             ç       0                            ÷
                                             ç      L*                            ÷
                                             ç      vi                            ÷
                                             ç                                    ÷
                                             ç     g i *k                         ÷
                                             ç      L                             ÷
                                             çç                                   ÷÷
                                              è      0                             ø

      Теорема 5. Точка w , определенная формулой (9), является угловой для
множества U .

      Доказательство. Из (9) следует, что базис для точки w Î U могут
образовать лишь столбцы A1 ,L, Ai -1 , Ai +1 ,L, Ar , Ak матрицы A . Убедимся в том,
                                                          *              *




что они действительно составляют базис. Для этого достаточно доказать их
линейную          независимость.                     Пусть                        для     некоторого          набора   чисел
a1 ,L , a i* -1 , a i* +1 ,L , a r , a k выполнено равенство

                             a1 × A1 + L + a i* -1 × Ai* -1 + a i* +1 × Ai* +1 + L + a r × Ar + a k × Ak = 0 .          (10)

                                                                             71