П.1. Базисные и опорные решения

Рассмотрим линейную систему из m уравнений с n переменными

(2.1)

В дальнейшем будет интересен случай, когда n > m.

Будем полагать, что в системе (2.1) все уравнения являются независимыми, что в свою очередь означает r = m, где r – ранг матрицы системы
A = (a_ij).

Рассмотрим одну из таких систем

Составим расширенную матрицу системы и проведем несложные преобразования

В данном случае r = 2, число переменных n = 3. Очевидно, что такая система имеет бесконечно много решений.

Перейдем от последней матрицы к системе уравнений

Выразим переменные х₁ и х₃ через переменную х₂

Рассмотрим столбцы перед переменными х₁ и х₃, как векторы и . Данные векторы образуют базис в двумерном пространстве. Отсюда название переменных х₁ и х₃ – базисные переменные.

В общем случае базисных переменных в системе из m независимых уравнений с n переменными будет m.

Определение 2.1. Базисными переменными системы m линейных уравнений с n переменными (m < n) называется любой набор из m переменных, если определитель матрицы коэффициентов при них отличен от нуля.

Оставшиеся n – m переменных называются свободными. В рассматриваемом примере свободной является переменная х₂. Придавая переменной х₂ различные значения можно получить множество частных решений: Х₁ ; Х₂ и т.д.

Решение Х₁ получается, если свободную переменную приравнять к нулю.

Определение 2.2. Если в общем решении системы m линейных уравнений с n переменными (n – m) свободных переменных равны нулю, то такое решение называется базисным.

Число базисных решений равно количеству неупорядоченных подмножеств из n элементов (число неизвестных) по m (число базисных неизвестных), т.е. это число равно

,

где n! = n × (n – 1) × …× 3 × 2 × 1; m! = m × (m – 1) × …× 2 × 1.

В данном примере число базисных решений определяется следующим образом

.

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

Обратимся к примерам 1.1 и 1.2, рассмотренным в предыдущем параграфе. В системе ограничений одной и другой задачи присутствует требование неотрицательности переменных х₁, …, х_n. Это требование не является случайным, поскольку в экономических моделях, связанных с решением систем линейных уравнений, неизвестные величины соответствуют некоторым конкретным экономическим показателям, которые могут быть только неотрицательными. Неотрицательные базисные решения назовем опорными *.

Рассмотрим отыскание опорных решений на примере.

П р и м е р 2.1. Найти все опорные решения системы линейных уравнений:

Решение. Столбец свободных переменных не содержит отрицательных компонент. Если бы в каком-то уравнении были отрицательные свободные члены, нужно было бы умножением обеих частей уравнения на (– 1) сделать свободный член соответствующего уравнения положительным. Составим расширенную матрицу системы

и определим первый разрешающий элемент так, чтобы в последнем столбце в результате элементарных преобразований не появились отрицательные компоненты. Очевидно, разрешающий элемент должен быть положительным. В первом столбце все компоненты положительные. Какой из них можно взять в качестве разрешающего? Составим отношения (j = 1, 2, 3). Если за разрешающий элемент выбрать тот из элементов первого столбца, которому соответствует минимальное отношение, то в столбце свободных членов после преобразований не будет отрицательных компонент – это элемент а₃₁ = 1. Получим

~ .

Во втором столбце первоначальной матрицы за разрешающий можно взять только элемент а₂₂ = 1 (он единственный положительный элемент этого столбца)

~ .

В третьем столбце за разрешающий можно взять а₃₃ = 11, т. к. :

~ .

В четвертом столбце все элементы отрицательные и разрешающий элемент выбрать нельзя.

Остановимся на первом варианте и продолжим процесс далее

~ ~ ~ .

Очевидно, ранг матрицы равен 2, базисные неизвестные – х₁ и х₄; свободные – х₂ и х₃. Общее решение: (7 – 11х₂ + 34 х₃; х₂; х₃; 1 – 3х₂ + 9х₃).

Базисное решение (7; 0; 0; 1) является опорным.

В данном случае существует базисных решений, соответствующих базисным переменным: х₁х₂; х₁х₃; х₁х₄; х₂х₃; х₂х₄; х₃х₄. Вариант х₁х₄ уже был рассмотрен.

Вернемся к матрице системы, полученной после преобразований:

.

Варианты х₁х₃; х₂х₃; х₃х₄ невозможны, т.к. в столбце, соответствующем х₃, нет положительных компонент, и х₃ не может войти в базис. Введем в базис х₂: , значит разрешающий элемент а₁₂ = 3. Получим

~ .

Базисное решение - опорное.

Проверим последний вариант х₂х₄: в четвертом столбце последней матрицы разрешающим может быть только элемент а₁₂ = 1/3 > 0, но тогда из базиса уйдет неизвестная х₂ и получим базисные переменные х₁х₄, что уже было рассмотрено.

Итак, опорные решения: (7; 0; 0; 1) и .

Сформулируем общее правило выбора разрешающего элемента при отыскании опорного решения для определенного столбца j.

1. Приводим систему уравнений к виду, когда в столбце свободных членов нет отрицательных чисел.

2. В выбранном столбце j в «конкурсе» на звание «разрешающий элемент» участвуют только положительные элементы.

3. Каждый элемент в столбце свободных членов, делим на соответствующий ему элемент столбца j.

4. Выбираем из полученных соотношений наименьшее (Q_j).

5. Элемент, для которого отношение, полученное в пункте 3, наименьшее, является разрешающим элементом.

 

12345678Следующая ⇒

Поделиться: