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

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


     Заметим, что

                                                                           æ g 1k ö r
                                                                           ç ÷
                             Ak = B × B Ak = ( A1
                                               -1
                                                                  L Ar ) × ç L ÷ = å As g sk .                            (11)
                                                                           ç g ÷ s =1
                                                                           è rk ø

     Подставим (11) в (10):
                                 r
                                                     é r         ù r
                             åa
                             s =1
                                      s   As + a k × ê å As g sk ú = å (a s + a k g sk ) As + a k Ai* g i*k = 0 .
                                                     ë s =1      û s =1*
                                                                                                                          (12)
                             s ¹ i*                                    s ¹i



     Вектора A1 , L , Ai , L , Ar составляют базис точки v , поэтому они линейно
                             *




независимы и равенство (12) возможно лишь при

                                 a s + a k g sk = 0, s = 1,L , r, s ¹ i * ; a k g i k = 0 .
                                                                                      *




     Коэффициент g i*k > 0 , так как это разрешающий элемент симплекс-

таблицы.      Тогда          a k = 0, a s = 0, s = 1,L , r, s ¹ i ,             что        доказывает                линейную

независимость векторов A1 ,L , Ai -1 , Ai +1 ,L , Ar , Ak , а вместе с тем и теорему.
                                                       *      *




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

     Из доказанной теоремы 5 вытекает, что w – угловая точка множества U с
базисом A1 ,L , Ai -1 , Ai +1 ,L , Ar , Ak . Заметим, что w ¹ v , так как I (w) < I (v ) . Для
                    *    *




угловой точки w вновь можно составить симплекс – таблицу, провести анализ
ее коэффициентов и. т. д. В силу конечности числа угловых точек множества U
процесс     счета       обязательно                        закончится          по         одному         из         критериев,
сформулированных в теоремах 3,4.

       3.4. Алгоритм симплекс метода. Пусть выполнены предположения
относительно канонической задачи линейного программирования, принятые в
предыдущем пункте. Приведем последовательность действий реализующих
симплекс метод решения этой задачи.

       1. Преобразовать ограничения задачи (3.1) к виду (3.4).

       2. С помощью формул (3.4) исключить из выражения для целевой
функции базисные переменные и привести его к виду (3.6).
                                                                  72