Математическое программирование (линейное программирование). Киселева Э.В - 15 стр.

                                                                              Преобразуем ее к каноническому виду. Для того чтобы нера-
                                                                          венства типа ≤ преобразовать в равенства, к их левым частям
                                                                          прибавим дополнительные (балансовые) неотрицательные пере-
                                                                                                   (               )
                                                                          менные xn + i ≥ 0 i = 1, m , после чего система ограничений при-
                                                                          мет вид:

                                                                                                                                                            (i = 1,m).
                                                                                                            n

                                                                                                           ∑a x
                                                                                                            j =1
                                                                                                                       ij       j   + xn + i = bi

                                                                              Дополнительные (балансовые) переменные xn + i i = 1, m                                     (       )
                                                                          вводятся в целевую функцию с коэффициентами, равными нулю.
                                                                              Каноническая форма модели примет вид:
                                                                                                      n                     m
                                                                                              Z = ∑ c j x j + ∑ 0 ⋅ xn + i → max ,                                           (3.4)
                                                                                                   j =1                 i =1


                                                                                                                                              (i = 1, m),
                                                                                                  n
                                                                                                 ∑ aij x j + x n +i = bi                                                     (3.5)
                                                              ∗
         Рис. 3.1. Z min = − Z1max и достигается в точке X                                       j =1

    Функция Z1 = − f ( x) представляет собой зеркальное отраже-                                            xj ≥ 0                   ( j = 1, n + m) .                        (3.6)
ние функции Z = f (x) относительно оси ОХ, ее максимум дости-                   Теорема 3.1.              Каждому решению ( x10 , x 20 , K , x n0 ) нера-
                            ∗
гается в той же точке X , что и минимум функции f (x) . Оче-                           n
                                                                          венства ∑ a j x j ≤ b соответствует единственное реше-
видно, имеет место соотношение min Z = − max Z1 .                                      j =1
                                                                                                                                                n
                                                                          ние ( x10 , x 20 , K , x n0 , x n0+1 ) уравнения ∑ a j x j + x n +1 = b и нера-
    3.4. Переход от одной формы модели задачи линейного                                                                                        j =1
                 программирования к другой                                венства x n +1 ≥ 0 , и наоборот.
                                                                              Из данной теоремы следует эквивалентность систем ограни-
         3.4.1. Переход к канонической форме модели
                                                                          чений исходной стандартной формы модели задачи и полученной
     Пусть исходная ЗЛП задана в стандартной форме                        канонической формы. А так как дополнительные переменные
                                 n
                            Z = ∑ c j x j → max ,                 (3.1)   x n0+i (i = 1, m) входят в целевую функцию с коэффициентами,
                                j =1                                      равными нулю, то значения целевых функций (3.1) и (3.4) при со-
                      n
                     ∑ aij x j ≤ bi             (i = 1, m),       (3.2)   ответствующих         допустимых   решениях   ( x10 , K , x n0 ) и
                     j =1
                                                                          ( x10 , K , x n0 , x n0+1 , K , x n0+ m ) одинаковы. Отсюда следует, что целе-
                            xj ≥ 0          ( j = 1, n) .         (3.3)   вые функции (3.1) и (3.4) на множестве соответствующих допус-
                                       31                                                                                                32