3  Общая задача линейного программирования и методы их решения

 

Формулировка задачи.  Даны линейная функция

                         Z = C1x1 +  C2x2 +…+ C nxn                                                                    (2.1.1)

и система линейных ограничений

 

                   a11x1 + a12x2 +…+ a1jxj +…+ a1n  xn = b1,

                              a21x1 + a22x 2 +…+ a2jxj +…+ a2n  xn  = b2,

                     … …………………………………                                    (2.1.2)

                   ai1x1 + ai2x2 +…+ a ij xj  +…+ a in  xn   = bi,

                             …………………………………………

                   a m1x1+ a m2x2 +…+ amjxj +…+ amnxn =bm, 

          

                     xj ≥ 0 (j =1, 2,…, n),                                                             (2.1.3)         

  где  aij, bi   и  Cj – заданные постоянные величины.

Найти такие неотрицательные значения х1, х2,…, xn которые удовлетворяют системе ограничений (2.1.2) и доставляют линейной функции (2.1.1) минимальное значение.

 Как отмечалось ранее, в системе ограничений (2.1.2) все bi, (i=1,2,…,m) можно считать неотрицательными. Общая задача имеет несколько форм записи.

         Векторная форма записи.  Минимизировать линейную функцию

Z= CX при ограничениях  A1x1  + A2x2  +…+ A nxn = A0,    X ≥ 0         (2.1.4)

где С = (с1, с2,… , сn); X = ( x1, x2,…, xn); СХ- скалярное произведение; векторы

 


          a 11                     a 12                                          a1n                         b1 

 A1=   a21       ,     A2=     a 22          ,  …  ,    An=        a2n      ,   A0=       b2       ,                                                                             

              …..                              …..                                          …..                          ……

             a m1                          am2                                           amn                         bm

 

 

состоят соответственно из коэффициентов при неизвестных и свободных членов.

Матричная форма записи. Минимизировать линейную функцию

Z = CX при ограничениях   AX = A0, X ≥ 0, где С = (с1, с2,…. , cn )- матрица-строка;    А = ( a ij  ) - матрица системы;

 


         x1                                                                                        b1       

 Х=    x2         - матрица-столбец,              A0=       b2       -  матрица-столбец.

              …                                                                                       …  

             xn                                                                                                                              bm

 

 

Запись с помощью знаков суммирования.   Минимизировать линейную функцию Z = ,      при ограничениях

aij x j = b i, i = 1, 2, …, m;   x j ≥ 0 ,  j = 1, 2, …, n.

                     

Определение 1. Планом или допустимым решением задачи линейного программирования называется вектор Х = ( x1, x2,… ,xn); удовлетворяющий условиям (2.1.2) и  (2.1.3) .

Определение 2.  План Х = ( x1, x2,… , xn) называется опорным, если   векторы Аi (i = 1, 2,…, m), входящие в разложение (2.1.4) с положительными коэффициентами xi, являются линейно независимыми.

Так как векторы  Аi  являются m- мерными, то из определения опорного плана следует, что число его положительных компонент не может превышать m.

Определение 3. Опорный план называется невырожденным, если он содержит m положительных компонент, в противном случае опорный план называется вырожденным.

Определение 4. Оптимальным планом или оптимальным решением задачи линейного программирования называется план, доставляющий наименьшее (наибольшее) значение линейной функции.

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