Базисные и опорные решения системы линейных уравнений

Введем понятие базисного решения системы линейных уравнений. Рассмотрим - мерные векторы, координаты которых равны коэффициентам при неизвестных и свободным членам уравнений системы (7):

; …; ; .

С помощью этих векторов систему (7) можно записать в виде

.

На основании полученного соотношения можно заключить, что решение системы уравнений (7) сводится к нахождению коэффициентов разложения вектора по векторам . В результате жордановых исключений расширенная матрица системы линейных уравнений (7)

примет следующий вид:

,

т.е. векторы преобразовались в единичные. Из этого следует, что векторы линейно независимы и составляют базис системы векторов . Систему уравнений, в которой столбцы коэффициентов при неизвестных являются единичными векторами, будем называть приведенной к единичному базису. Иногда систему в такой записи называют приведенной к разрешенному виду.

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

Если в общем решении (8) системы (7) свободным переменным придать нулевые значения, то полученное частное решение , или в векторной записи , называется базисным.

Так в примере 1 базисным будет решение: (3; 3; 0; 0).

Вообще говоря, из данной системы векторов можно выбрать максимально различных базисов, где

.

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

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

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

Рассмотрим способ отыскания опорных решений. Предположим, что в таблице 4 все элементы столбца свободных членов неотрицательны. Выясним, как сохранить неотрицательность свободных членов в процессе жордановых исключений.

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

(9)

будет неотрицательным, если , т.е. если разрешающий элемент положителен ( по предположению). Это первое требование к разрешающему элементу.

Таблица 9

	1	…		…
…	…	…	…	…
		…		…
…	…	…	…	…
		…		…
…	…	…	…	…

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

будет неотрицательным, если

. (10)

Так как , , , неравенство (10) справедливо при любом отрицательном .

Пусть теперь , тогда неравенство (10) можно переписать в виде

.

Этим неравенством выражается второе требование к разрешающему элементу: отношение свободного члена разрешающей строки к разрешающему элементу должно удовлетворять условию минимальности, т.е. оно должно быть наименьшим из всех отношений свободных членов к соответствующим элементам разрешающего столбца. Если такому требованию удовлетворяет сразу несколько отношений, то разрешающий элемент можно взять в любой строке, соответствующей одному из этих отношений.

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

Пример 2. Найти опорное решение системы

Решение: Запишем систему в виде таблицы 10, предварительно умножив третье уравнение на 1. В качестве разрешающего можно взять любой столбец, содержащий хотя бы один положительный элемент. Возьмем, например, третий столбец. Разрешающую строку выберем по наименьшему симплексному отношению: min(3/1;1/1)=1/1. Меньшее из этих отношений соответствует третьей строке. Она и будет разрешающей. На пересечении третьей строки и третьего столбца находится разрешающий элемент 1, с которым и выполняется шаг жорданового исключения.

Табл.10 Табл.11

0=		2 1 1 1
0=		2 1 0 1
0=		3 0 1 1

0=		5 1 2
0=		2 1 1
=		3 0 1

В результате еще двух шагов жордановых исключений получим таблицы 12 и13.

=	2/3
=	2/3
=	7/3

Табл.12 Табл.13

=	2/5	1/5 2/5
0=	6/5	3/5 9/5
=	11/5	3/5 1/5

Из таб.13 при =0 находим опорное решение системы:

(2/3; 0; 7/3; 2/3).