Численные методы. Корнюшин П.Н. - 84 стр.

                                                     84


        Например, если (в трехмерной задаче) многогранник – четырехгранная пирамида (рис.
6.21), то вершины A, B, C, D – регулярные вершины, а S – нерегулярная вершина. В многограннике
же, изображенном на рис. 6.22, все вершины – регулярные.




       Введем теперь важное в теории линейного программирования определение. Будем
называть n переменных из числа x1, x2,…, xn; y1, y2,…, ym, которые обращаются в данной вершине
многогранника ограничений в нуль, базисными переменными, остальные же m переменных –
внебазисными переменными.
       Таким образом, понятие базисных и внебазисных переменных связывается с
рассматриваемой вершиной многогранника ограничений – каждой вершине соответствует своя
система базисных и внебазисных переменных, при переходе к другой вершине состав базисных и
внебазисных переменных изменяется. Далее, в случае регулярной вершины базисные и
внебазисные переменные определяются однозначно – те и только те m переменных, которые в
регулярной вершине положительны, – это небазисные переменные, а те и только те n переменных,
которые в ней обращаются в нуль, – это базисные переменные. В случае же нерегулярной
вершины базисные и внебазисные переменные определяются неоднозначно, здесь переменных,
обращающихся в нуль, в рассматриваемой вершине больше, чем n, но только некоторые n из их
числа определяются как базисные переменные, а остальные m переменных, среди которых также
имеются обращающиеся в этой вершине в нуль, определяются как внебазисные переменные.
Именно это обстоятельство отмечается в задачах линейного программирования как «случай
вырождения».
       Нужно запомнить следующее: в регулярном случае все внебазисные переменные
положительны, а в случае вырождения некоторые внебазисные переменные в данной вершине
равны нулю.



                                  4.6.3. Симплексный метод

                            4.6.3.1. Геометрическая подготовка

       Пусть дана общая задача линейного программирования на максимум
                             Z=c1x1+c2x2+…+cnxn → max      (1)
при ограничениях
                            a11 x1 + a12 x2 + ... + a1n x n ≤ b1 ;
                           a 21 x1 + a 22 x 2 + ... + a 2 n xn ≤ b2 ;
                                                                         (2)
                                ......................................
                           a m1 x1 + a m 2 x2 + ... + a mn x m ≤ bm