Основы автоматизированного проектирования химических производств. Миронов В.М - 117 стр.

UptoLike

ВУЗ: 

ТПУ | Томск

Составители: 

Рубрика: 

117
-3х
1
-х
2
+2х
4
-2х
5
=5;
х
1
≥0; х
2
≥0; х
4
≥0; х
5
≥0; х
6
≥0; х
7
≥0.
Основные определения линейного программирования формулируются
таким образом.
Допустимое решение – неотрицательный вектор-столбец х, для которо-
го выполняются ограничения Ax=b.
Допустимая область состоит из всех допустимых решений. Если до-
пустимая область пуста, то задача ЛП называется
противоречивой.
Оптимальное решение – это такой допустимый вектор х
*
, для которого
соответствующее ему значение целевой функции больше (меньше), чем для
любого другого допустимого решения.
Оптимальное значение задачи ЛП представляет значение целевой
функции, соответствующее оптимальному решению.
Неединственность оптимального решения – это более одного опти-
мального решения. В этом случае задача ЛП имеет различные оптимальные
решения.
Единственность оптимума – это отсутствие других оптимальных ре-
шений.
Неограниченный оптимум – это в том случае, если задача ЛП не обла-
дает ограниченным оптимумом, т.е. max Z→∞ или min Z→-∞.
7.7.3. Симплексный метод решения задач ЛП
Свое название метод получил от ограничения, входившего в одну из за-
дач, решенных этим методом. Это ограничение имеет вид
∑
=
≤
n
i
i
x
1
1 и пред-
ставляет собой выпуклый многогранник в n–мерном пространстве с верши-
нами на осях координат в точках x
i
=1 (i=1,...,n), называемый обычно симплек-
сом. При этом m<n, где m – число уравнений в системе ограничений.
Дополнительно к вышеприведенным определениям вводятся следующие:
Базисной матрицей называется невырожденная матрица размерности
mxm, образованная из m столбцов матрицы ограничений (7.6).
Базисным решением называется решение, которое получается после
приравнивания нулю (n-m) переменных и решения полученной системы от-
носительно остальных m переменных.
Допустимым базисным решением называется то, которое удовлетво-
ряет условию неотрицательности.
Невырожденным базисным решением называется то допустимое ба-
зисное решение, которое имеет m положительных компонент х
i
.
Геометрическая интерпретация решения задачи линейного программи-
рования – это вершина многогранника, ограничивающего область допусти-
мых решений. Таким образом, чтобы решить задачу ЛП достаточно пере-

Страницы