ВУЗ:
Составители:
Рубрика:
Линейное программирование
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
