 |
 |
 |
 |
|
 |
 |
16
линейная комбинация столбцов а
j
, равная столбцу b? R
m
:
Такое представление ограничений КЗЛП обычно называют векторной формой записи.
Векторы а
j
, j ? l:n
будем называть векторами требований задачи (D, f), а вектор b
—
вектором
ограничений. Множество всех неотрицательных линейных комбинаций столбцов а
j
с геометрической
точки зрения может быть представлено как многогранный выпуклый конус, натянутый на систему
векторов а
j
в пространстве R
m
(рис. 1.3).
Соответственно, вопрос о существовании допустимого плана задачи (D, f) равнозначен вопросу о
принадлежности вектора b данному конусу, а компоненты х
j
некоторого допустимого
плана х
?
D
являются не чем иным, как коэффициентами разложения вектора ограничений задачи b по векторам,
требований а
j
.
Такое представление КЗЛП получило название второй геометрической интерпретации.
В дальнейшем без ограничения общности можем предполагать, что число уравнений, задающих
множество D, меньше или равно числу переменных задачи (m
? n
). Действительно, если это не так, то
либо система уравнений Ах = b несовместна (и, значит, множество D пустое), либо содержит
избыточные (линейно зависимые) уравнения.
Если некоторые т столбцов а
j1
,а
j2
,...,а
jm
матрицы A являются линейно независимыми, то они
образуют базис в пространстве R
m
, и их, вообще говоря, будет достаточно для представления вектора b
в виде линейной комбинации указанных столбцов. Это означает, что остальные столбцы войдут в
данное разложение с нулевыми коэффициентами. Если к тому же коэффициенты линейной комбинации
окажутся неотрицательными, то мы получаем так называемый базисный допустимый план х, у которого
не более m компонентов отличны от нуля. Сформулируем определение базисного плана более строго,
так как это одно из фундаментальных понятий теории линейного пpогpаммиpования.
Пусть задана некоторая каноническая ЗЛП (D,f), А —матрица системы ограничений задачи, и
?=
{а
j1
, аj2,..., а
jm
} —линейно независимая система столбцов матрицы А, образующая базис R
m
.
Обозначим множество номеров столбцов, входящих в систему b, через N (?) = {j1, j2,..., j
m
}. План х
называется базисным планом задачи (D,f),
если его компоненты, соответствующие базисным
столбцам и называемые базисными компонентами, больше или равны нулю (х
j
?
0, j ? N (?)}, а все
остальные компоненты (небазисные) — равны нулю (x
j
= 0, j
N (?)).
Базисный план х называется невырожденным, если все его базисные компоненты строго
положительны, и вырожденным в противном случае.
1.3.2. Свойства базисных планов. Следующая теорема трактует понятие базисного плана в
терминах первой геометрической интерпретации ЗЛП.
Теорема 1.3. Каждый допустимый базисный план является угловой точкой множества
допустимых планов D.