 |
 |
 |
 |
|
 |
 |
11
Нетрудно заметить, что «платой» за переход от общей формы задачи линейного программирования к
канонической является рост ее размерности, что, при прочих равных условиях, является фактором,
усложняющим процесс решения.
1.2. ОСНОВНЫЕ СВОЙСТВА ЗЛП И ЕЕ ПЕРВАЯ ГЕОМЕТРИЧЕСКАЯ ИНТЕРПРЕТАЦИЯ
1.2.1. Основные понятия линейной алгебры и выпуклого анализа, применяемые в теории
математического программирования. Кратко напомним некоторые фундаментальные определения и
теоремы линейной алгебры и выпуклого анализа, которые широко применяются при решении проблем
как линейного, так и нелинейного программирования.
Фундаментальным понятием линейной алгебры является линейное (вещественное) пространство.
Под ним подразумевается множество некоторых элементов (именуемых векторами или точками), для
которых заданы операции сложения и умножения на вещественное число (скаляр), причем элементы,
являющиеся результатом выполнения операций, также в соответствии с определением должны
принадлежать исходному пространству.
Частными случаями линейных пространств являются вещественная прямая, плоскость,
геометрическое трехмерное пространство.
Вектор ?1a¹ + ?2a² + …+ ?
m
a
m
называется линейной комбинацией векторов а¹
а²,..., а
m
с
коэффициентами ?1, ?
2,
?
m
,
Система векторов линейного пространства а¹
а²,..., а
m
называется линейно зависимой, если
существуют такие числа ?1, ?
2,
?
m
не равные одновременно нулю, что их линейная комбинация ?1a¹ +
?2a² + …+ ?
m
a
m
равняется нулевому вектору (вектору, все компоненты которого равны нулю). В
противном случае систему а¹,
а²,..., а
m
называют линейно независимой, т. е. линейная комбинация
данных векторов может быть равна нулевому вектору только при нулевых коэффициентах ?1, ?
2,
…, ?
m
Максимально возможное количество векторов, которые могут образовывать линейно независимую
систему в данном линейном пространстве, называют размерностью пространства, а любую систему
линейно независимых векторов в количестве, равном размерности, — базисом пространства.
Линейное пространство обычно обозначают как R
n
, где n — его размерность.
Любое подмножество данного линейного пространства, которое само обладает свойствами
линейного пространства, называется линейным подпространством. Множество Н, получаемое сдвигом
некоторого линейного подпространства
L ? R
n
на вектор
a ? R
n
: H=L+a, называется аффинным
множеством (пространством). Если фундаментальным свойством любого линейного пространства или
подпространства является принадлежность ему нулевого вектора, то для аффинного множества это не
всегда так. На плоскости примером подпространства является прямая, проходящая через начало
координат, а аффинного множества — любая прямая на плоскости. Характеристическим свойством
аффинного множества является принадлежность ему любой прямой, соединяющей две любые его
точки. Размерность аффинного множества совпадает с размерностью того линейного подпространства,
сдвигом которого оно получено.
Если рассматривается некоторое линейное пространство
R
n
, то принадлежащие ему аффинные
множества размерности 1 называются прямыми, а размерности (n-1)—гиперплоскостями. Так, обычная
плоскость является гиперплоскостью для трехмерного геометрического пространства R³, а прямая —
гиперплоскостью для плоскости R². Всякая гиперплоскость делит линейное пространство на два
полупространства.
Множество V векторов (точек) линейного пространства R
n
называется выпуклым, если оно содержит
отрезок прямой, соединяющей две его любые точки, или, другими словами, из того, что a ?V и b?V ,
следует, что х = (1- ?) х а+ ? х b ? V , где 0
?
??
1.