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

                                                 83


        После введения дополнительных переменных yi можно сказать, что каждая вершина
многогранника ограничений обладает тем свойством, что в ней какие-то n из числа переменных x1,
x2,…, xn, y1, y2,…, ym обращаются в нуль. Например, в задаче 1 раздела 4.6.2.3 (см. рис. 6.14)
вершина А, как точка пересечения прямых (l1) и (l2), определяется тем, что в ней y1=0, y2=0, где
через y1 и y2 обозначены: y1=5-(-x1+2x2), y2=7-(x1+x2), или в другой записи y1=-(-x1)+2(-x2)+5, y2=(-
x1)+(-x2)+7. Точно также вершина В, как точка пересечения прямых (l2) и (l3), алгебраически
характеризуется тем, что в ней y2=0, y3=0, где через y2 и y3 обозначены y2=(-x1)+(-x2)+7; y3=2(-
x1)+9-x2)+11; вершина С (точка пересечения прямых (l3) и (l4)) характеризуется тем, что в ней
y3=0, y4=0, где y3=2(-x1)+(-x2)+11; y4=-(-x1)-2(-x2)-7.
        В задаче 5 раздела 4.6.2.3 для вершины С (см. рис. 6.18) x11=0, y1=0, где
                                          y1=(-x11)+(-x12)+3.
        Итак, повторим снова, что в каждой вершине какие-то n переменных обращаются в нуль.
Но обратное утверждение неверно. Если в какой-то точке n переменных из системы x1, x2,…, xn; y1,
y2,…, ym обращаются в нуль, то эта точка необязательно является вершиной многогранника
ограничений. Например, если многоугольник ограничений имеет вид OABCDE (рис. 6.20), то для
вершины O x1=x2=0, для вершины E x2=y4=0, для вершины C y2=y3=0.




        Но если рассмотреть точку К, в которой пересекаются продолжения отрезков BC и DE, то в
ней будет y2=y4=0, хотя точка К не является вершиной рассматриваемого многоугольника. Точно
так же набор x1=y3=0 не дает вершины, а дает точку N, в которой пересекаются несоседние
стороны: x1=0 (ось x2) и y3=0 (прямая CD).
        Как же алгебраически отличить набор, дающий вершину, от набора, не дающего вершины?
Ответ на этот вопрос опять-таки подсказывается геометрией. Дело в том, что вершина
характеризуется не только тем, что в ней какие-то n переменных обращаются в нуль, но и тем, что
все остальные m переменных остаются неотрицательными, т.к. вершина принадлежит
многограннику ограничений. А для такой точки, как торчка К на рис.6.20, две переменные (y2 и y4)
обращаются в нуль, но не все остальные переменные остаются неотрицательными; например, для
точки К будет y3 ≤ 0 , т.к. точка К лежит с той стороны от прямой y3=0, которая не заштрихована.
Точно так же для точки N две переменные x1 и y3 обращаются в нуль, но y1<0 и y2<0. Все это
связано, конечно, с тем, что точки К и N лежат вне многоугольника OABCDE.
        Таким образом, всякая вершина многогранника ограничений вполне определяется тем, что
в ней n переменных из числа x1, x2,…, xn; y1, y2,…, ym обращаются в нуль, а остальные m
переменных остаются неотрицательными.
        Если в данной вершине только n переменных из числа x1, x2,…, xn; y1, y2,…, ym обращаются
в нуль и, следовательно, все остальные m переменных строго положительны, то будем называть
такую вершину регулярной; если же в данной вершине обращаются в нуль больше, чем n
переменных из числа x1, x2,…, xn; y1, y2,…, ym, то будем ее называть нерегулярной (или говорить, что
в этой вершине имеет место вырождение).