Линейное программирование. Элементы теории, алгоритмы и примеры. Азарнова Т.В - 9 стр.

                                                                    Линейное программирование


    λx 1 +x 2 ≤3                        λx 1 −x 2 ≤−2
    x1 ≥0, x 2 ≤0                       x1 ≥0, x 2 ≤0 .
3. Привести пример графической интерпретации и составить на основании
полученного чертежа математическую запись задачи, обладающей следую-
щими свойствами:
      1) имеется единственное оптимальное решение для задачи на минимум
         и для задачи на максимум;
      2) максимальное значение целевая функция достигает в бесчисленном
         множестве точек, а минимальное значение в единственной точке;
      3) на минимум задача неразрешима из-за неограниченности целевой
         функции, а максимальное значение достигается в единственной точ-
         ке;
      4) на максимум и на минимум задача неразрешима из-за неограни-
         ченности целевой функции;
      5) минимальное значение целевой функции достигается в бесчислен-
         ном множестве точек, из которых только одна является вершиной.

    §2. Разные формы записи задачи линейного программирования

     В §1 приведена общая постановка задачи линейного программирования
(ЗЛП). Часто для удобства исследования и при построении метода решения
фиксируется та или иная запись задачи. Так, часто используется задача в сле-
дующей форме:
                                         n
                                        ∑cjxj       → max
                                         j =1
                                 n
                                ∑ a ij x j      ≤bi , i =1,..., m
                                j =1
                                       x j ≥0,      j =1,..., n .

Такая форма записи ЗЛП называется стандартной или симметричной формой
задачи линейного программирования. Кроме того, выделяют каноническую
форму записи ЗЛП:
                                         n
                                        ∑cjxj       → max
                                         j =1
                          n
                         ∑ a ij x j     =bi , bi ≥0, i =1,..., m
                         j =1
                               x j ≥0, j =1,..., n .
      Вне зависимости от того, как записана исходная задача, она может
быть переписана в любой желательной форме. При этом существуют прави-
ла, позволяющие это сделать эквивалентным образом. С этой целью обсудим


                                             11