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

                                                          85


и при условиях неотрицательности
                                     x1 ≥ 0, x2 ≥ 0,..., xn ≥ 0.
                                                        (3)
       При помощи дополнительных переменных y1, y2,…,ym можно записать ограничения (2) в
таком виде, как в предыдущем разделе:
                     y1 = a11 (− x1 ) + a12 (− x 2 ) + ... + a1n (− xn ) + b1 ≥ 0;
                    y 2 = a 21 (− x1 ) + a 22 (− x2 ) + ... + a 2 n (− xn ) + b2 ≥ 0;
                                                                                           (2’)
                         ...............................................................
                   y m = a m1 (− x1 ) + a m 2 (− x 2 ) + ... + a mn (− xm ) + bm ≥ 0.
          Из геометрических соображений следует, что max Z достигается в какой-то вершине
многогранника ограничений, т.е. в такой точке, для которой значения n переменных из числа x1,
x2,…, xn; y1, y2,…, ym становятся равными нулю (базисные переменные), а значения прочих m
переменных остаются неотрицательными (внебазисные переменные). Можно поэтому наметить
такой общий ход решения задачи линейного программирования:
          1) исходя из какой-то определенной вершины, т.е. исходя из какого-то набора базисных и
внебазисных переменных, прежде всего выясним, не достигается ли максимум целевой функции
именно в этой вершине;
          2) если оказалось, что максимум еще не достигнут, то перейдем от данной вершины к
другой и повторим прежний анализ.
          Надо, однако, иметь в виду что даже при сравнительно небольших m и n (порядка 20 – 30)
число вершин n–мерного гипермногогранника может быть чрезвычайно большим. Пожалуй, и
современные быстродействующие ЭВМ не справятся с необходимыми вычислениями в разумное
время, если стать на путь простого перебора всевозможных вершин. В связи с этим
устанавливается такой порядок вычислений, который обеспечивает не простой переход от одной
вершины к другой, а такой, при котором значение целевой функции «улучшается» (т.е. при задаче
на максимум – увеличивается). В этом и заключается смысл так называемого метода
последовательного улучшения плана в теории линейного программирования. По-видимому, проще
всего будет переходить от данной вершины к какой-то соседней, причем следует иметь в виду, что
в случае двумерной задачи каждая вершина имеет две соседние, а в случае пространства большего
числа измерений вершина может иметь весьма много соседних. Но что такое «соседняя вершина»
в случае n-мерной задачи? Для того чтобы это осмыслить, надо определить понятие «соседняя
вершина» алгебраически. Нам известно, что одна вершина отличается от другой составом
базисных и внебазисных переменных.
          Рассмотрим пример. Для вершины А многоугольника (см. рис.6.20) базисными
переменными будут x1, y1, а внебазисными – x2, y2, y3, y4. Для вершины D базисными переменными
будут y3, y4, а внебазисными – x1, x2, y1, y2 (и так же для остальных вершин). Возьмем теперь две
соседние вершины, например, А и В. Для вершины A базисные переменные x1, y1; внебазисные – x2,
y2, y3, y4. Для соседней вершины В базисные переменные y1, y2; внебазисные – x1, x2, y3, y4. Видно,
что при переходе от А к В базисная переменная x1 становится внебазисной, а внебазисная
переменная y2 становится базисной. То же самое имеет место в случае пространственного
многогранника (см. рис.6.22). Например, если уравнения граней многогранника рис. 6.22
следующие: грань OEFC – x1=0; OADE – x2=0; OABC – x3=0; DEFG – y1=0; BGFC – y2=0; ABGD –
y3=0, то для вершины С базисные переменные x1, x3, y2; внебазисные – x2, y1, y3; для соседней
вершины О базисные переменные x1, x2, x3; внебазисные – y1, y2, y3. Замечаем, что при переходе от
С к О переменные y2 и x2 поменялись ролями. Точно так же при переходе от А к D поменяются
ролями переменные x3 и y1.
          Таким образом, чтобы перейти от некоторой вершины к какой-то соседней вершине, надо
одну из базисных переменных сделать внебазисной и одну из внебазисных – базисной. Это значит,
что при переходе от некоторой вершины к соседней надо одну из переменных, которой
приписывалось значение нуль, сделать отличной от нуля и придать ей такое значение, чтобы
другая переменная, значение которой ранее не было равным нулю, стало равным нулю. Это
обстоятельство можно пояснить еще следующим образом. Пусть мы находимся в вершине А (см.
рис. 6.22), для которой x2=0; x3=0; y3=0. Чтобы перейти в соседнюю вершину D, будем двигаться
по ребру AD, для которого x2 и y3=0, но x3 ≠ 0. Это движение по ребру AD надо совершать до тех