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

UptoLike

Рубрика: 

Линейное программирование
4
§1. Общая постановка задачи линейного программирования
Графическое решение задач линейного программирования
Задачей линейного программирования (ЗЛП) называется задача нахо-
ждения в векторном пространстве R
n
такого вектора
*
x
, который обеспечи -
вает оптимальное (максимальное или минимальное ) значение линейной
функции
=
=
n
j
jj
xcxL
1
)( и при этом принадлежит некоторой области
n
R
, заданной линейными ограничениями
()
axbim
ijj
j
n
i
=
==
1
1,,,...,
(
)
njx
j
,...,1,,0
=
знак на я требованинет .
Функцию
)
(
x
L
называют целевой функцией ЗЛП, ее оптимальное зна-
чение обозначают
*
L
. Множество
n
R
называют допустимым мно -
жеством, его элементы - допустимыми векторами, а вектор
x
*
- решени-
ем задачи (оптимальной точкой).
Прежде чем рассматривать методы решения общей задачи линейного
программирования в R
n
, рассмотрим алгоритм графического метода, кото-
рый используется в R
2
для решения задачи следующего вида:
(
)
cxcx
1122
+
maxmin
(
)
axaxbim
iii1122
1
+
=
=
,,,...,
(
)
знакнатребованиянетxx ,0,
21
.
1. Построение допустимого множества.
Заметим , что каждое ограничение задачи определяет некоторую полуплос -
кость (в случае неравенства) или прямую (в случае равенства). Допустимым
множеством является пересечение этих полуплоскостей и прямых. Таким об -
разом , для построения допустимого множества нужно:
а ) для каждого ограничения нарисовать прямую , соответствующую ра-
венству
axaxbim
iii1122
1
+
=
=
,,...,
;
б) если ограничение задается неравенством вида axaxb
iii1122
+
или
axaxb
iii1122
+
, то определить полуплоскость, задаваемую данным нера-
венством . Это легко сделать, если подставить в него координаты точки , не
расположенной на соответствующей прямой. Если неравенство оказывается
справедливым , то выбрать полуплоскость, содержащую данную точку, в про-
тивном случае - выбрать противоположную полуплоскость.
Линейное программирование




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

      Задачей линейного программирования (ЗЛП) называется задача нахо-
                                 n
ждения в векторном пространстве R такого вектора x * , который обеспечи-
вает оптимальное (максимальное или минимальное) значение линейной
                   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 * - решени-
ем задачи (оптимальной точкой).
      Прежде чем рассматривать методы решения общей задачи линейного
                       n
программирования в R , рассмотрим алгоритм графического метода, кото-
                          2
рый используется в R для решения задачи следующего вида:
                         c1x 1 +c2 x 2 → max(min )
                              ai1 x1 +ai 2 x 2 ≤(≥=
                                                  , )bi , i =1,..., m
                       x1 , x 2 ≥0 (≤, нет требования на знак ) .
       1. Построение допустимого множества.
Заметим, что каждое ограничение задачи определяет некоторую полуплос-
кость (в случае неравенства) или прямую (в случае равенства). Допустимым
множеством является пересечение этих полуплоскостей и прямых. Таким об-
разом, для построения допустимого множества нужно:
       а) для каждого ограничения нарисовать прямую, соответствующую ра-
венству ai1 x1 +ai2 x 2 =bi , i =1,..., m ;
       б) если ограничение задается неравенством вида ai1x 1 +ai2 x 2 ≤bi или
ai1 x1 +ai2 x 2 ≥bi , то определить полуплоскость, задаваемую данным нера-
венством. Это легко сделать, если подставить в него координаты точки, не
расположенной на соответствующей прямой. Если неравенство оказывается
справедливым, то выбрать полуплоскость, содержащую данную точку, в про-
тивном случае - выбрать противоположную полуплоскость.

                                        4