Добро пожаловать на наш портал !

Методы компьютерного моделирования экономических процессов

Свойства базисных планов

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

Теорема 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<λ<1.

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

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

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

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

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

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

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