Составители:
Рубрика:
97
перпендикулярных к нормальному вектору С=(с
1
, с
2
, c
3
), который указывает направление
наиболее интенсивного возрастания целевой функции. В направлении вектора С=(с
1
, с
2
,
c
3
) целевая функция (2.2.127) возрастает равномерно. Будем называть плоскость уровня
целевой функции допустимой, если она имеет хотя бы одну общую точку с выпуклым
многогранником М, определяемым условиями задачи. Выпуклым многогранником М
определяется область определения целевой функции. Допустимую плоскость уровня,
отвечающую наибольшему значению целевой функции z = z
маx
, будем называть опорной
плоскостью уровня. Ясно, что вследствие монотонного возрастания целевой функции в
направлении нормального вектора С выпуклый многогранник будет всегда расположен по
одну сторону от опорной плоскости, а именно — в сторону, противоположную
направлению вектора С. Поэтому опорная плоскость может проходить либо через одну из
вершин, либо через ребро или грань выпуклого многогранника. В первом случае мы
имеем единственное оптимальное решение (вершину), которое является опорным, во
втором случае мы имеем бесчисленное множество оптимальных решений (каждая точка
ребра или грани — оптимальное решение), среди которых имеется не менее чем два
опорных решения (вершины, являющиеся концами ребра, или угловыми точками грани).
Если задача линейного программирования (2.2.127)—(2.2.128) не имеет решения,
то это геометрически означает, что область, определяемая условиями задачи (2.2.127) —
(2.2.128), либо пуста (система противоречива), либо представляет выпуклую мно-
гогранную область, не ограниченную в направлении нормального вектора С=(с
1
, с
2
, с
3
).
Геометрический смысл задачи минимизации аналогичен геометрической
интерпретации задачи максимизации, с той лишь разницей, что выпуклый многогранник
М располагается по одну сторону от опорной плоскости, вместе с нормальным вектором
С=(с
1
, с
2
, с
3
).
Рассмотрим теперь задачу линейного программирования с п>3 переменными х
1
,
х
2
,...,х
п
. Формулировка задачи остается прежней. Требуется найти неотрицательный вектор
X = [x
1
, x
2
,…, х
n
], максимизирующий целевую функцию
z = CX (2.2.130)
при условиях:
A
i
X = b
i
, i=1, 2,..., m, (2.2.131)
где n-мерные векторы С, А
i
и числа b
i
являются заданными постоянными.
В этом случае все построения теряют реальную наглядность, так как они
представляются абстрактно в n-мерном пространстве. Однако, по аналогии с трехмерным
пространством, геометрическая интерпретация задачи (2.2.130)—(2.2.131) остается той же
самой, что и в трехмерном случае. Единственное различие будет состоять в том, что слово
«плоскость» заменяется на «гиперплоскость».
В (2.2.3) была доказана важная теорема об опорных решениях: если каноническая
задача линейного программирования имеет оптимальное решение, то существует по
крайней мере одно оптимальное опорное решение.
Учитывая геометрический смысл опорного решения как некоторой вершины
выпуклого многогранника М, мы можем утверждение этой теоремы осмыслить
следующим образом: если существуют точки области М, в которых целевая функция
(2.2.130) достигает своего наибольшего значения z = z
маx
, то это z
маx
достигается по
крайней мере в одной из вершин области М.
Мы знаем, что при решении задачи симплексным методом каждая таблица
отвечает некоторому опорному решению, т. е. некоторой вершине области М. Переход от
одной симплексной таблицы к другой геометрически означает переход от данной
вершины к одной из соседних вершин (в случае невырожденности задачи), через которую
проходит гиперплоскость уровня целевой функции с большим значением параметра z.
Страницы
- « первая
- ‹ предыдущая
- …
- 95
- 96
- 97
- 98
- 99
- …
- следующая ›
- последняя »
