1.3. БАЗИСНЫЕ РЕШЕНИЯ И ВТОРАЯ ГЕОМЕТРИЧЕСКАЯ ИНТЕРПРЕТАЦИЯ ЗЛП

1.3.1. Векторная форма записи КЗЛП и ее применение. Рассмотрим каноническую задачу линейного программирования

Обозначим через аj столбцы матрицы А и будем рассматривать их как векторы пространства Rm.

Такое представление ограничений КЗЛП обычно называют векторной формой записи.

Векторы аj, j ( l:n будем называть векторами требований задачи (D, f), а вектор b — вектором ограничений. Множество всех неотрицательных линейных комбинаций столбцов аj с геометрической точки зрения может быть представлено как многогранный выпуклый конус, натянутый на систему векторов аj в пространстве Rm (рис. 1.3).

Соответственно, вопрос о существовании допустимого плана задачи (D, f) равнозначен вопросу о принадлежности вектора b данному конусу, а компоненты хj некоторого допустимого плана х ( D являются не чем иным, как коэффициентами разложения вектора ограничений задачи b по векторам, требований аj.

Такое представление КЗЛП получило название второй геометрической интерпретации.

В дальнейшем без ограничения общности можем предполагать, что число уравнений, задающих множество D, меньше или равно числу переменных задачи (m ? n). Действительно, если это не так, то либо система уравнений Ах = b несовместна (и, значит, множество D пустое), либо содержит избыточные (линейно зависимые) уравнения.

Если некоторые т столбцов аj1 ,аj2 ,...,аjm матрицы A являются линейно независимыми, то они образуют базис в пространстве Rm, и их, вообще говоря, будет достаточно для представления вектора b в виде линейной комбинации указанных столбцов. Это означает, что остальные столбцы войдут в данное разложение с нулевыми коэффициентами. Если к тому же коэффициенты линейной комбинации окажутся неотрицательными, то мы получаем так называемый базисный допустимый план х, у которого не более m компонентов отличны от нуля.

*

Пусть задана некоторая каноническая ЗЛП (D,f), А —матрица системы ограничений задачи, и ?= {аj1, аj2,..., аjm} —линейно независимая система столбцов матрицы А, образующая базис Rm. Обозначим множество номеров столбцов, входящих в систему b, через N (?) = {j1, j2,..., jm}. План х называется базисным планом задачи (D,f), если его компоненты, соответствующие базисным столбцам и называемые базисными компонентами, больше или равны нулю (хj ? 0, j ( N (?)}, а все остальные компоненты (небазисные) — равны нулю (xj = 0, j ? N (?)).

*

Базисный план х называется невырожденным, если все его базисные компоненты строго

положительны, и вырожденным в противном случае.

1.3.2. Свойства базисных планов. Следующая теорема трактует понятие базисного плана в терминах первой геометрической интерпретации ЗЛП.

Теорема 1.3. Каждый допустимый базисный план является угловой точкой множества допустимых планов D.

Доказательство.

Ради простоты положим, что базисными векторами являются первые m столбцов матрицы A, т. е. ?={al, a2,...,am}. Тогда утверждение теоремы 1.3 может быть переформулировано следующим образом:

Если существует такой n-мерный вектор

что x1 a1 +х2 а2 +...+xk ak =b, то х есть угловая точка множества D.

Проведем доказательство от противного, т. е. предположим, что рассматриваемый базисный план х не является угловой точкой множества D. Тогда ее можно представить в виде выпуклой комбинации некоторых двух различных допустимых планов х1 и х2:

x = ?x1+(1-?)x2, 0

В координатной форме последнее утверждение означает

Поскольку последние (n - k) компоненты вектора х по предположению равны 0, а числа хj1, xj2 ? 0 и ?, (1 -? )>0, то эти же компоненты в векторах x1 и х2 также равны 0.

Вычитая из (1.15) (1.16), получим

Так как векторы а1, а2,...,аk — линейно независимы, то коэффициенты х11 –х21 =0,..., х1k –х2k =0, из чего следует, что x1 =х2. Это противоречит предположению, что х1 и х2 являются различными угловыми точками множества D. Следовательно, х не может быть представлен в виде выпуклой комбинации двух точек D и по определению является угловой точкой данного множества. ?

Интересно отметить, что справедливо и обратное утверждение, которое приведем без доказательства:

Если х — угловая точка множества D, то она является допустимым базисным планом задачи (D, f).

В завершение параграфа необходимо отметить практическое значение установленной связи между угловыми точками и допустимыми базисными решениями: она позволяет формализовать (и тем самым существенно упростить) процесс перехода от одной угловой точки к другой.