Линейное программирование. Азарнова Т.В - 8 стр.

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


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

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

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

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


                                                10