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

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


      §1. Общая постановка задачи линейного программирования
       Графическое решение задач линейного программирования

      Задачей линейного программирования (ЗЛП) называется задача нахо-
ждения в векторном пространстве R такого вектора x * , который обеспечи-
                                 n

вает оптимальное (максимальное или минимальное) значение линейной
                   n
функции    L( x) =∑ c j x j     и при этом принадлежит некоторой области
                   j =1

Ω ⊆ R n , заданной линейными ограничениями
                                  n
                                 ∑ aij x j ≤( ≥=
                                               , )bi ,   i =1,..., m
                                 j =1
                  x j ≥0 (≤, нет требования на знак ), j =1,..., n .
      Функцию L(x) называют целевой функцией ЗЛП, ее оптимальное зна-
чение обозначают L* . Множество Ω ⊆ R n называют допустимым мно-
жеством, его элементы - допустимыми векторами, а вектор x * - решени-
ем задачи (оптимальной точкой).
      Прежде чем рассматривать методы решения общей задачи линейного
программирования в R , рассмотрим алгоритм графического метода, кото-
                       n

рый используется в R
                          2
                              для решения задачи следующего вида:
                                 c1x1 +c2 x 2 → max(min )
                              ai1x 1 +ai 2 x 2 ≤( ≥=
                                                   , )bi , i =1,..., m
                       x1 , x 2 ≥0 (≤, нет требования на знак ) .
       1. Построение допустимого множества.
Заметим, что каждое ограничение задачи определяет некоторую полуплос-
кость (в случае неравенства) или прямую (в случае равенства). Допустимым
множеством является пересечение этих полуплоскостей и прямых. Таким об-
разом, для построения допустимого множества нужно:
       а) для каждого ограничения нарисовать прямую, соответствующую ра-
венству ai1x1 +ai2 x 2 =bi , i =1,..., m ;
       б) если ограничение задается неравенством вида ai1x 1 +ai2 x 2 ≤bi или
ai1x 1 +ai2 x 2 ≥bi , то определить полуплоскость, задаваемую данным нера-
венством. Это легко сделать, если подставить в него координаты точки, не
расположенной на соответствующей прямой. Если неравенство оказывается
справедливым, то выбрать полуплоскость, содержащую данную точку, в про-
тивном случае - выбрать противоположную полуплоскость.
       в) найти пересечение полученных полуплоскостей и прямых.
       2. Решение задачи путем анализа допустимого множества и поведения
целевой функции на этом множестве.

                                            3