Составители:
Рубрика:
30
кой форме (2) с n положительными переменными и m условиями типа
равенство. При этом требование положительности переменных озна+
чает, что точки принадлежат области n+мерного пространства, где
все координаты положительны (положительный ортант). Равенства
определяют (n–m)+мерную гиперплоскость, пересечение которой с по+
ложительным ортантом и дает многогранник допустимых решений.
1 1
1
11 1
Рис. 3
Вид допустимого множества для случая, когда n = 3 и m = 1, изоб+
ражен на рис. 3. При этом условие положительности задает положи+
тельный октант трехмерного пространства, а одно (m = 1) условие+
равенство задает двухмерную (n–m = 2) плоскость. В результате до+
пустимым множеством, в котором выполняются все условия, стано+
вится сечение октанта плоскостью (заштрихованный треугольник).
Экстремум линейной целевой функции может достигаться только в
одной из трех вершин треугольника.
Чтобы найти вершины многогранника, заметим, что на границе
ортанта одна или более переменных равны нулю (на рис. 3 на ребре
(x
1
,x
2
) переменная x
3
= 0). Тогда, чтобы найти вершину, нужно как
можно большее число переменных приравнять нулю, а остальные
найти из условий+равенств. Так как при этом должна возникать сис+
тема линейных уравнений с n неизвестными, для ее однозначного
решения необходимо n уравнений, т. е. имеющиеся m условий необ+
ходимо дополнить n–m равенствами вида x
i
= 0.
Тогда в каждой вершине многогранника будет m ненулевых коор+
динат, которые образуют базис. Остальные n–m координат входят в
небазисный набор. Обратите внимание, что базис однозначно опреде+
ляет координаты вершины. Следовательно, задачу можно было бы
Страницы
- « первая
- ‹ предыдущая
- …
- 28
- 29
- 30
- 31
- 32
- …
- следующая ›
- последняя »
