Линейное программирование. Филькин Г.В. - 4 стр.

     Анализируя предыдущие задачи приходим к общей постановке задач
линейного программирования.
     Общая задача ЛП:
     Z=c1x1+c2x2+…+cnxn       → min(max)
      ⎧а11 x1 + a12 x1 + ... + a1n xn ⊗ b1
      ⎪
      ⎪a21 x1 + a22 x2 + ... + a2 n xn ⊗ b2
      ⎪
      ⎨...........................................
      ⎪a x + a x + ... + a x ⊗ b
      ⎪ m1 1         m2 2                mn n      m
      ⎪⎩ x j ≥ 0, j = 1,2,...n
     где ⊗ один из следующих трех знаков -
          ⎧≤
          ⎪
      ⊗ = ⎨≥
          ⎪=
          ⎩

     Графическое решение задач ЛП

      В тех случаях , когда в задачах ЛП только 2 переменные, их можно ре-
шить графическим способом.
      Замечание. Иногда графическим способом можно решать задачи ЛП и
в тех случаях, когда число переменных больше 2.
      Основные идеи графического метода решения задач рассмотрим на
примере задачи использования сырья (1).
      Z=50x1+40x2       → max
      ⎧2 x1 + 5 x2 ≤ 20
      ⎪8 x + 5 x ≤ 40
      ⎪ 1          2
      ⎨                                                                  (1)
      ⎪5 x1 + 6 x2 ≤ 30
      ⎪⎩ x1 , x2 ≥ 0
         Решение задачи графическим способом распадается на 2 этапа. На пер-
вом этапе строим область допустимых решений, удовлетворяющую системе
всех ограничений.
         На втором этапе среди всех допустимых решений выбирается опти-
мальное решение. Для этого используют линии уровня или градиент целевой
функции.
1.Рассмотрим декартову систему координат на плоскости x1Ox2 . Допусти-
мым решением задачи оптимизации называется упорядоченный набор чисел
x1 , x2 ,..., xn , удовлетворяющий всем ее ограничениям. Такой упорядоченный
набор можно считать точкой в пространстве R n . Множество всех допусти-
мых решений называется областью допустимых решений. В задаче заданы

                                                       3