Методы условной оптимизации: Рекомендации к выполнению лабораторных и практических работ. Шипилов С.А. - 4 стр.

                   1. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ
      Линейным программированием (ЛП) называется раздел математики, в
котором изучаются методы нахождения минимума или максимума линейной
функции конечного числа переменных при условии, что переменные удовле-
творяют конечному числу дополнительных условий (ограничений), имеющих
вид линейных уравнений или линейных неравенств.

       1.1. Основные понятия и определения. Постановка задачи ЛП

      Задача ЛП в общем случае может быть сформулирована следующим об-
разом. Найти такие значения действительных переменных x1, x2, …, xn, для ко-
торых линейная целевая функция f(x) принимает минимальное (или максималь-
ное) значение, т.е.
                                    n
                            f (x) = ∑ c j ⋅ x j → min (max)                   (1)
                                    j =1
при условии, что
                            n
                           ∑ aij ⋅ x j ≤ bi , i = 1, m ,                      (2)
                            j =1
и
                            n
                           ∑ aij ⋅ x j = bi , i = (m + 1), p ,                (3)
                            j =1
Такая постановка называется задачей ЛП в произвольной форме записи.
       Задача, в которой требуется найти максимум линейной формы (1) при ус-
ловиях (2) и условиях
                                  x j ≥ 0 , j = 1, n ,                         (4)
что в матричной форме представляется в виде:
                                 f (x) = c Τ ⋅ x → max ⎫
                                        A⋅x ≤ b        ⎪
                                                       ⎬                       (5)
                                          x≥0          ⎪
                                                       ⎭
называется симметричной формой записи задачи ЛП (или стандартной зада-
                                       n
чей ЛП). Здесь x=(x1, x2, …, xn)T∈R , cT=(c1, c1, …, cn), A –матрица (aij) размера
m х n, b=(b1, b2, …, bn)T.
       Совокупность чисел x=(x1, x2, …, xn)T, удовлетворяющих ограничениям
(2) - (4) задачи ЛП, называется допустимым решением (или планом). Все до-
пустимые решения образуют область допустимых решений (ОДР).
       План x*=(x1*, x2*, …, xn* )T, при котором целевая функция (1) принимает
минимальное (максимальное) значение, называется оптимальным планом или
решением задачи ЛП.
       Известна также каноническая форма записи задачи ЛП, которая будет
подробно рассмотрена ниже.


4