Базисные решения ОЗЛП

Напомним, что в системе ограничений ОЗЛП число уравнений (m) предполагается меньшим числа неизвестных (n), вследствие чего ранг матрицы не может оказаться больше m. Всюду в дальнейшем будем считать, что ранг матрицы A равен m. Последнее, в частности, означает, что среди столбцов матрицы A имеется по крайней мере один набор из m линейно независимых столбцов.

Определение. Набор из m линейно независимых столбцов матрицы A будем называть базисом матрицы A.

Замечание. Очевидно, каждая фиксированная матрица A имеет конечное число базисов (не более ), причем каждый базис матрицы A есть также базис векторного пространства R^m (m ¾ число строк матрицы A).

Определение. Решение системы называется ее базисным решением с базисными переменными если столбцы матрицы A образуют базис матрицы, а значения всех небазисных компонент вектора равны нулю (то есть при ).

Представим систему в векторной форме

(4)

Пусть столбцы матрицы образуют ее базис. Тогда для отыскания базисного решения системы (4), соответствующего базису , достаточно положить в (4) небазисные переменные равными нулю и решить систему из которой значения базисных переменных определяются однозначно.

Определение. Базисное решение называется вырожденным, если значения одной или нескольких базисных переменных равны нулю. Базисное решение называется невырожденным, если значения всех базисных переменных отличны от нуля.

Определение. Базисное решение системы , удовлетворяющее условию называется допустимым базисным решением (ДБР) ОЗЛП.

Очевидно, что положительными компонентами ДБР ОЗЛП могут быть только значения базисных переменных. Невырожденное ДБР имеет ровно m положительных компонент, а количество положительных компонент вырожденного ДБР меньше m.

Пример. Пусть система ограничений ОЗЛП имеет вид

или где Таким образом, Базисами матрицы могут служить следующие наборы векторов: и Базис определяет невырожденное ДБР (1; 1; 0; 0) ^T с базисными переменными . Базисам и соответствует одно и то же вырожденное базисное решение не являющееся ДБР. Базисам и соответствует одно и тоже вырожденное ДБР (0; 0; 0; 5) ^T; при этом базисными переменными можно считать либо x ₁ и x ₄, либо x ₂ и x ₄. Пример допустимого решения, не являющегося базисным: (0; 0; 5; 15) ^T.

В дальнейшем любой базис матрицы A, порождающий ДБР, будем называть также базисом этого решения. При этом базис невырожденного ДБР определяется единственным образом. Базис вырожденного ДБР может быть определен неоднозначно.

Теорема (о существовании ДБР). Если задача линейного программирования имеет хотя бы одно допустимое решение, то она имеет и ДБР.

Доказательство. Пусть – допустимое решение ОЗЛП, причем при . Если при этом векторы (столбцы матрицы А) линейно независимы, то – ДБР, его базисом является любая совокупность т линейно независимых столбцов матрицы А, включающая в себя . Предположим, что линейно зависимы. Тогда существуют числа , не все равные нулю и такие, что

. (5)

Можно считать, что среди , есть хотя бы одно положительное число, так как в противном случае равенство (5) можно умножить на –1.

Далее, так как – допустимое решение, то

. (6)

Умножая (5) на некоторое положительное число λ и вычитая полученное равенство из (6), будем иметь

. (7)

Выберем . Допустим , . Тогда при и .

Рассмотрим теперь вектор с координатами при и при . Этот вектор является допустимым решением ОЗЛП в силу равенства (7) и выбора λ. Количество положительных компонент вектора не более . Если соответствующие этим положительным компонентам векторы-столбцы матрицы А линейно независимы, то – ДБР и теорема доказана. Если же векторы-столбцы матрицы А, соответствующие положительным компонентам решения , связаны линейной зависимостью, то можно получить новое допустимое решение , которое имеет не более положительных компонент, и так далее, пока не придем к ДБР. Теорема доказана.

Дата добавления: 2015-07-14