Руководство по решению задач по курсу "Вариационное исчисление и методы оптимизации". Шарапов В.Г. - 17 стр.

      4. Линейное программирование
      Стандартная задача линейного программирования:
                      z = c1x1 + c2x2 + …+ cnxn → max
      при условиях:
                      ⎧ a11 x1 + a12 x2 + K + a1n x n ≤ b1
                      ⎪ a x + a x +K + a x ≤ b
                      ⎪ 21 1         22 2          2n n      2
                      ⎨                                            (1)
                      ⎪       ...  ...    ... ... ...   ...
                      ⎪⎩a m1 x1 + a m 2 x 2 + K + a mn xn ≤ bm
                      x1 ≥ 0, x2 ≥ 0, …, xn ≥ 0.                   (2)
      Двойственная ей задача линейного программирования:
                      w = b1y1 + b2y2 + …+ bmym → min
                      ⎧ a11 y1 + a 21 y 2 + K + a m1 y m ≤ c1
                      ⎪a y + a y + K + a y ≤ c
                      ⎪ 12 1       22 2           m2 m       2
                      ⎨                                        ,
                      ⎪              K K K
                      ⎪⎩a1n y1 + a 2 n y 2 + K + a mn y m ≤ cn
                        y1 ≥ 0, y2 ≥ 0, …, ym ≥ 0.
       Каждое неравенство в (1) и (2) определяет полупространство. Мно-
жество точек, удовлетворяющих (1) и (2), есть пересечение полупро-
странств и, следовательно, есть выпуклый многогранник. Он называется
областью допустимых решений. Множество точек, в которых z = a есть
гиперплоскость
                        c1x1 +…+ cnxn= a.
Отсюда следует, что экстремальные значения целевая функция z принима-
ет в вершинах этого многогранника.
       Стандартная и двойственная ей задачи решаются одновременно
симплекс-методом, который состоит в следующем:
       1) Ограничения в стандартной задаче заменяются равенствами вве-
дением дополнительных переменных s1, …, sm в каждом из m нера-
венств:

                ⎧ a11 x1 + K + a1n x n + s1 = b1
                ⎪ a x +K + a x + s = b
                ⎪ 21 1            2n n      2    2
                ⎨                                                  (3)
                ⎪ ... ... ... ... ... ...
                ⎪⎩a m1 x1 + K + a mn x n + sm = bm
                                    17