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

 

Область применения. Графический метод основан на геометрической интерпретации задачи линейного программирования и применяется в основном при решении задач двумерного пространства и только некоторых задач трехмерного пространства, так как довольно трудно построить многогранник решений, который образуется в результате пересечения полупространств. Задачу пространства размерности больше трех изобразить графически вообще невозможно.

Пусть задача линейного программирования задана в двумерном пространстве, т.е. ограничения содержат две переменные.

           Найти минимальное значение функции

                                      Z = C1x1 + C2 x2                     (2.3.1)

       при

a11x1  + a12x2   £ b1,

a21x1  + a22x2   £ b2,

..................................                                          (2.3.2)                                

 am1x1  + am2x2  £ bm,

 

x1  ³ 0,     x2  ³ 0.                                               (2.3.3)

        

Допустим, что система (2.3.2) при условии (2.3.3) совместна и ее многоугольник решений ограничен. Каждое из неравенств (2.3.2) и  (2.3.3), как отмечалось выше, определяет полуплоскость с граничной прямой: ai1x1  + ai2x2   =  bi (i = 1, 2, ..., m), x1  = 0, x2 = 0. Линейная функция (2.3.1) при фиксированных значениях Z является уравнением прямой линии:  C1x1 + C2 x2 = =const. Построим многоугольник решений системы ограничений (2.3.2) и график линейной функции (2.3.1) при Z = 0  (рис.2.2).

 

Рис. 2.2

 

Тогда поставленной задаче линейного программирования можно дать следующую интерпретацию. Найти точку многоугольника решений, в которой прямая  C1x1 + C2x2 = const  является опорной и функция Z при этом достигает минимума.

Значения   Z = C1x1 + C2x2 возрастают в направлении вектора N = (C1, C2), поэтому прямую Z = 0 передвигаем параллельно самой себе в направлении вектора N.

Из рис.2.2 следует, что прямая дважды становится опорной по отношению к многоугольнику решений (в точках А, С), причем минимальное значение принимает в точке А. Координаты точки А (x1; x2) находим, решая систему уравнений прямых АВ и АЕ.

Если многоугольник решений представляет собой неограниченную многоугольную область, то возможны два случая.

         Случай 1. Прямая C1x1 + C2x2 = const, передвигаясь в направлении вектора N или противоположно ему, постоянно пересекает многоугольник решений  и ни в какой точке не является опорной к нему. В этом случае линейная функция не ограничена на многоугольнике решений как сверху, так и снизу (рис. 2.3).

Рис. 2.3

 

         Случай 2. Прямая, передвигаясь, все же становится опорной относительно многоугольника решений (рис.2.4). Тогда в зависимости от вида области линейная функция может быть ограниченной сверху и неограниченной снизу (рис. 2.4, а), ограниченной снизу и неограниченной сверху (рис.2.4, б), либо ограниченной как снизу, так и сверху (рис. 2.4, в).

 

 

                          а)                                                                  б)

 

    

в)

Рис. 2.4

 

Пример 1. (Решить графически). Найти minZ = 2x1 – 10x2 при следующих ограничениях:

                                     x1 -  x2  ³  0,

                                     x1 - 5x2 ³ -5,

                                     x1          ³  0,

                                             x2  ³ 0.

 

Решение.  Заменив  знаки неравенств на знаки равенств, получим уравнения четырех прямых:

 

                                      x1  -   x2  =  0,                 (1)

                                      x1  - 5x2  = -5,                 (2)

                                      x1            =  0,                 (3)

                                                x2   =  0.                 (4)

 

Областью решений данной системы неравенств является неограниченная   фигура (рис.2.9). Точки О(0;0), А(х1;х2) являются вершинами полученной области решений. Так как точка А(х1;х2) – точка пересечения двух прямых, то, чтобы найти ее координаты, решаем систему:

 

                                     x1 -  x2  = 0,

                                     x1 - 5x2 = -5,           х1 = х2 = 5/4,   А(5/4;5/4).

 

                                                        

Рис.2.9

 

Вычислим значения функции Z в точках  О(0;0), А(5/4;5/4):

 

   ZA   =  -10;    ZO =  0,   Zmin = -10.

 

 

 Решение задач линейного программирования графическим методом, если  n  и  m  связаны соотношением  n – m = 2

 

         Вообще, с помощью графического метода может быть решена задача линейного программирования, система ограничений которой содержит n неизвестных и m линейно независимых уравнений, если n и m связаны соотношением  n – m = 2. Действительно, пусть поставлена задача линейного программирования.

Найти минимальное значение линейной функции  Z = C1x1 + C2 x2 + ... + +Cnxn при ограничениях

 

a11x1  + a12x2  + ... + a1nxn  = b1,

a21x1  + a22x2  + ... + a2nxn  = b2, 

.................................................                              (2.3.8)   

am1x1  + am2x2  + ... + amnxn = bm,

   

        xj ³ 0 (j = 1, 2, ... , n),     

 

где  все  уравнения  линейно  независимы   и   выполняется   соотношение n – m =2.

Используя метод Жордана – Гаусса, производим m исключений, в результате которых базисными неизвестными оказались, например, m первых неизвестных x1, x2, ...,  xm, а свободными – два последних: xm+1 и   xn, т.е. система ограничений приняла вид:

 

x1  + a¢1,  m+1 xm+1  + a¢1nxn  = b¢1,

x2  + a¢2,  m+1 xm+1  + a¢2nxn = b¢2, 

...............................................                              (2.3.9) 

xm  + a¢m,  m+1 xm+1  + a¢mnxn = b¢m 

 

        xj ³ 0       (j = 1, 2, ... , n).

             

С помощью уравнений  преобразованной системы выражаем линейную функцию только через свободные неизвестные и, учитывая, что все базисные неизвестные – неотрицательные: xj ³ 0 (j = 1, 2, ... , m), отбрасываем их, переходя к системе ограничений, выраженных в виде неравенств. Таким образом, окончательно получаем следующую задачу.

Найти минимальное значение линейной функции Z = C¢m+1xm+1 + C¢nxn  при ограничениях

a¢1,  m+1 xm+1  + a¢1nxn  £ b¢1,

a¢2,  m+1 xm+1  + a¢2nxn  £ b¢2, 

.................................................                               

a¢m,  m+1 xm+1  + a¢mnxn  £ b¢m,

 

        х m+1 ³ 0,  xn  ³ 0.

 

Преобразованная задача содержит два неизвестных; решая ее графическим методом, находим оптимальные значения х m+1, и  xn, а затем, подставляя их в (2.3.9), находим оптимальные значения х1,  x2, ..., х m.