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

                                                     68


переходит в систему ограничений-равенств
                           ai1x1+ai2x2+…+ainxn+xn+i=bi (i=1, 2,…, m),
       где дополнительные переменные все неотрицательны: xn+1 ≥ 0, xn+2 ≥ 0,…, xn+m ≥ 0. Эти
дополнительные переменные можно считать содержащимися и в целевой функции (с нулевыми
коэффициентами). При неравенствах вида “ ≥ ” дополнительные переменные xn+i следует вычитать
из левых частей. Можно показать, что и от ограничений-равенств несложно перейти к
неравенствам. Принимая это во внимание, будем исходить из стандартной формы задачи, которая
особенно удобна для геометрической интерпретации.
       Таким образом, будем рассматривать модель и методы решения общей задачи линейного
программирования в стандартной форме, т.е. задачи, которая математически выражается так:
найти те значения переменных x1, x2,…xn, при которых имеют место следующие соотношения:
                              Z=c1x1+c2x2+…+cnxn → max (min);
                                  a11 x1 + a12 x2 + ... + a1n xn ≤ b1 ;
                                  a 21 x1 + a 22 x2 + ... + a 2 n xn ≤ b2 ;
                                      ......................................
                                 a m1 x1 + a m 2 x2 + ... + a mn x m ≤ bm ;
                                        x1 ≥ 0, x 2 ≥ 0,..., xn ≥ 0.



         4.6.2. Графический способ решения задачи линейного программирования

                    4.6.2.1. Геометрический смысл линейных неравенств

        Задачу линейного программирования и численный метод ее решения можно истолковать
геометрически. Геометрическое изображение дает ясное представление о ходе решения задачи
линейного программирования и приводит к простому графическому способу решения для того
случая, когда число независимых параметров управления сводится к двум.
        Приступая к изложению геометрической интерпретации, заметим, что прежде всего
необходимо геометрически осмыслить те три звена, из которых состоит задача линейного
программирования: 1) целевую функцию; 2) систему линейных ограничений; 3) требования
неотрицательности искомых параметров. С этой целью будем далее рассматривать
геометрические образы, возникающие на координатной плоскости двух переменных. Обычно в
этом случае оси координат обозначают буквами x и y, но, имея в виду дальнейшее обобщение на
многомерные пространства, будем обозначать оси координат буквами x1 и x2 (рис.6.1).