Число базисных решений системы уравнений

Базисные (основные) и свободные (неосновные) переменные. Общее и базисное решения системы линейных алгебраических уравнений. Первая часть.

Что означает фраза «ранг матрицы равен $r$»? Она означает, что есть хотя бы один минор $r$-го порядка, который не равен нулю. Напомню, что такой минор называется базисным. Базисных миноров может быть несколько. При этом все миноры, порядок которых выше $r$, равны нулю или не существуют.

Выбрать $r$ базисных переменных в общем случае можно различными способами. В примерах я покажу наиболее часто используемый способ выбора.

Во всех изложенных ниже примерах матрицу системы будем обозначать буквой $A$, а расширенную матрицу системы – буквой $\widetilde$.

Решить СЛАУ $ \left \ < \begin& 3x_1-6x_2+9x_3+13x_4=9\\ & -x_1+2x_2+x_3+x_4=-11;\\ & x_1-2x_2+2x_3+3x_4=5. \end \right.$. Если система является неопределённой, указать базисное решение.

Итак, мы имеем СЛАУ, у которой 3 уравнения и 4 переменных: $x_1$, $x_2$, $x_3$, $x_4$. Так как количество переменных больше количества уравнений, то такая система не может иметь единственное решение (чуть позже мы строго докажем это предложение на основе теоремы Кронекера-Капелли). Найдём решения СЛАУ, используя метод Гаусса:

$$ \left( \begin 3 & -6 & 9 & 13 & 9 \\ -1 & 2 & 1 & 1 & -11 \\ 1 & -2 & 2 & 3 & 5 \end \right) \rightarrow \left|\begin & \text<поменяем местами первую и третью>\\ & \text<строки, чтобы первым элементом>\\ & \text <первой строки стала единица.>\end\right| \rightarrow \\ \rightarrow\left( \begin 1 & -2 & 2 & 3 & 5\\ -1 & 2 & 1 & 1 & -11 \\ 3 & -6 & 9 & 13 & 9 \end \right) \begin \phantom <0>\\ II+I\\ III-3\cdot I\end \rightarrow \left( \begin 1 & -2 & 2 & 3 & 5\\ 0 & 0 & 3 & 4 & -6 \\ 0 & 0 & 3 & 4 & -6 \end\right) \begin \phantom <0>\\ \phantom<0>\\ III-II\end \rightarrow \\ \rightarrow\left( \begin 1 & -2 & 2 & 3 & 5\\ 0 & 0 & 3 & 4 & -6 \\ 0 & 0 & 0 & 0 & 0 \end\right) $$

Мы завершили прямой ход метода Гаусса, приведя расширенную матрицу системы к ступенчатому виду. Слева от черты расположены элементы преобразованной матрицы системы, которую мы также привели к ступенчатому виду. Напомню, что если некая матрица приведена к ступенчатому виду, то её ранг равен количеству ненулевых строк.

И матрица системы, и расширенная матрица системы после эквивалентных преобразований приведены к ступенчатому виду; они содержат по две ненулевых строки. Вывод: $\rang A=\rang\widetilde = 2$.

Итак, заданная СЛАУ содержит 4 переменных (обозначим их количество как $n$, т.е. $n=4$). Кроме того, ранги матрицы системы и расширенной матрицы системы равны между собой и равны числу $r=2$. Так как $r < n$, то согласно следствию из теоремы Кронекера-Капелли СЛАУ является неопределённой (имеет бесконечное количество решений).

Найдём эти решения. Для начала выберем базисные переменные. Их количество должно равняться $r$, т.е. в нашем случае имеем две базисные переменные. Какие именно переменные (ведь у нас их 4 штуки) принять в качестве базисных? Обычно в качестве базисных переменных берут те переменные, которые расположены на первых местах в ненулевых строках преобразованной матрицы системы, т.е. на «ступеньках». Что это за «ступеньки» показано на рисунке:

На «ступеньках» стоят числа из столбцов №1 и №3. Первый столбец соответствует переменной $x_1$, а третий столбец соответствует переменной $x_3$. Именно переменные $x_1$ и $x_3$ примем в качестве базисных.

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

Почему можно принять переменные $x_1$ и $x_3$ в качестве базисных? Для ответа на этот вопрос давайте вспомним, что ранг матрицы системы равен числу $r=2$. Это говорит о том, что все миноры данной матрицы, порядок которых выше 2, либо равны нулю, либо не существуют. Ненулевые миноры есть только среди миноров второго порядка. Выберем какой-либо ненулевой минор второго порядка. Мы можем выбирать его как в исходной матрице системы $A$, т.е. в матрице $\left( \begin 3 & -6 & 9 & 13 \\ -1 & 2 & 1 & 1 \\ 1 & -2 & 2 & 3 \end \right)$, так и в преобразованной матрице системы, т.е. в $\left( \begin 1 & -2 & 2 & 3 \\ 0 & 0 & 3 & 4 \\ 0 & 0 & 0 & 0 \end\right)$. Так как в преобразованной матрице системы побольше нулей, то будем работать именно с нею.

Итак, давайте выберем минор второго порядка, элементы которого находятся на пересечении строк №1 и №2, и столбцов №1 и №2:

$$ M_<2>^<(1)>=\left| \begin 1 & -2 \\ 0 & 0 \end\right|=1\cdot 0-(-2)\cdot 0=0. $$

Вывод: выбранный нами минор второго порядка не является базисным, ибо он равен нулю. Так как элементы этого минора взяты из столбца №1 (он соответствует переменной $x_1$) и столбца №2 (он соответствует переменной $x_2$), то пара переменных $x_1$ и $x_2$ не могут быть базисными переменными.

Осуществим вторую попытку, взяв минор второго порядка, элементы которого лежат на пересечении строк №1, №2 и столбцов №3 и №4:

$$ M_<2>^<(2)>=\left| \begin 2 & 3\\ 3 & 4 \end\right|=2\cdot 4-3\cdot 3=-1. $$

Вывод: выбранный нами минор второго порядка является базисным, ибо он не равен нулю. Так как элементы этого минора взяты из столбца №3 (он соответствует переменной $x_3$) и столбца №4 (он соответствует переменной $x_4$), то пару переменных $x_3$ и $x_4$ можно принять в качестве базисных.

Сделаем и третью попытку, найдя значение минора, элементы которого расположены на пересечении строк №1, №2 и столбцов №1 и №3:

Вывод: выбранный нами минор второго порядка является базисным, ибо он не равен нулю. Так как элементы этого минора взяты из столбца №1 (он соответствует переменной $x_1$) и столбца №3 (он соответствует переменной $x_3$), то пару переменных $x_1$ и $x_3$ можно принять в качестве базисных.

Как видите, выбор базисных переменных не является однозначным. На самом деле количество вариантов выбора не превышает количество размещений из $n$ элементов по $r$, т.е. не больше чем $C_^$.

В рассматриваемом примере в качестве баисных были приняты переменные $x_1$ и $x_3$ – сугубо из соображений удобства дальнейшего решения. В чём это удобство состоит, будет видно чуток позже.

Базисные переменные выбраны: это $x_1$ и $x_3$. Остальные $n-r=2$ переменных (т.е. $x_2$ и $x_4$) являются свободными. Нам нужно выразить базисные переменные через свободные.

Я предпочитаю работать с системой в матричной форме записи. Для начала очистим полученную матрицу $\left( \begin 1 & -2 & 2 & 3 & 5\\ 0 & 0 & 3 & 4 & -6 \\ 0 & 0 & 0 & 0 & 0 \end\right)$ от нулевой строки:

$$ \left( \begin 1 & -2 & 2 & 3 & 5\\ 0 & 0 & 3 & 4 & -6 \end\right) $$

Свободным переменным, т.е. $x_2$ и $x_4$, соответствуют столбцы №2 и №4. Перенесём эти столбцы за черту. Знак всех элементов переносимых столбцов изменится на противоположный:

Почему меняются знаки? Что вообще значит это перенесение столбцов? показать\скрыть

Давайте обратимся к расширенной матрице системы, которая после преобразований имеет вид $\left( \begin 1 & -2 & 2 & 3 & 5\\ 0 & 0 & 3 & 4 & -6 \end\right)$. Перейдём от матрицы к уравнениям. Первая строка соответствует уравнению $x_1-2x_2+2x_3+3x_4=5$, а вторая строка соответствует уравнению $3x_3+4x_4=-6$. Теперь перенесём свободные переменные $x_2$ и $x_4$ в правые части уравнений. Естественно, что когда мы переносим выражение $4x_4$ в правую часть уравнения, то знак его изменится на противоположный, и в правой части появится $-4x_4$.

Если опять записать полученную систему в виде матрицы, то мы и получим матрицу с перенесёнными за черту столбцами.

А теперь продолжим решение обычным методом Гаусса. Наша цель: сделать матрицу до черты единичной. Для начала разделим вторую строку на 3, а потом продолжим преобразования обратного хода метода Гаусса:

$$ \left( \begin 1 & 2 & 5 & 2 & -3\\ 0 & 3 & -6 & 0 & -4 \end\right) \begin \phantom <0>\\ II:3 \end \rightarrow \left( \begin 1 & 2 & 5 & 2 & -3\\ 0 & 1 & -2 & 0 & -4/3 \end\right) \begin I-2\cdot II \\ \phantom <0>\end \rightarrow \\ \rightarrow \left(\begin 1 & 0 & 9 & 2 & -1/3\\ 0 & 1 & -2 & 0 & -4/3 \end\right). $$

Матрица до черты стала единичной, метод Гаусса завершён. Общее решение найдено, осталось лишь записать его. Если вспомнить, что четвёртый столбец соответствует переменной $x_2$, а пятый столбец – переменной $x_4$, то получим:

Нами получено общее решение заданной СЛАУ. Чтобы найти базисное решение, нужно все свободные переменные приравнять к нулю. Т.е. полагая $x_2=0$ и $x_4=0$, будем иметь:

Решение $x_1=9$, $x_2=0$, $x_3=-2$, $x_4=0$ и является базисным решением данной СЛАУ. В принципе, задавая свободным переменным иные значения, можно получить иные частные решения данной системы. Таких частных решений бесконечное количество. Например, принимая $x_2=-4$ и $x_4=1$, получим такое частное решение: $\left\ <\begin& x_1=\frac<2><3>;\\ & x_2=-4;\\ & x_3=-\frac<10><3>;\\ & x_4=1. \end\right.$. Базисное решение, которые мы нашли ранее – лишь одно из бесконечного множества частных решений заданной СЛАУ.

Если есть желание, то полученное решение можно проверить. Например, подставляя $x_1=9+2x_2-\frac<1><3>x_4$ и $x_3=-2-\frac<4><3>x_4$ в левую часть первого уравнения, получим:

$$ 3x_1-6x_2+9x_3+13x_4=3\cdot \left(9+2x_2-\frac<1><3>x_4\right)-6x_2+9\cdot \left(-2-\frac<4><3>x_4\right)+13x_4=9. $$

Проверка первого уравнения увенчалась успехом; точно так же можно проверить второе и третье уравнения.

Если система является неопределённой, указать базисное решение.

Похожий пример уже был решен в теме «метод Крамера» (пример №4). Переменные $x_4$ и $x_5$ были перенесены в правые части, а дальше применялись стандартные операции метода Крамера. Однако такой метод решения не гарантирует достижения результата. Например, мы переносим некие переменные в правую часть, а оставшийся определитель оказывается равным нулю, – что тогда? Решать перебором? 🙂 Поэтому гораздо удобнее применять преобразования метода Гаусса, как и в предыдущем примере.

$$ \left( \begin 1 & -2 & 4 & 0 & 2 & 0\\ 4 & -11 & 21 & -2 & 3 & -1\\ -3 & 5 & -13 & -4 & 1 & -2 \end \right) \begin \phantom <0>\\ II-4\cdot I\\ III+3\cdot I\end \rightarrow \left( \begin 1 & -2 & 4 & 0 & 2 & 0\\ 0 & -3 & 5 & -2 & -5 & -1\\ 0 & -1 & -1 & -4 & 7 & -2 \end \right) \rightarrow \\ \rightarrow \left|\begin & \text<поменяем местами вторую и третью>\\ & \text<строки, чтобы диагональным элементом>\\ & \text <второй строки стало число (-1).>\end\right|\rightarrow \left( \begin 1 & -2 & 4 & 0 & 2 & 0\\ 0 & -1 & -1 & -4 & 7 & -2\\ 0 & -3 & 5 & -2 & -5 & -1 \end \right) \begin \phantom <0>\\ \phantom<0>\\ III-3\cdot I\end \rightarrow \\ \rightarrow \left( \begin 1 & -2 & 4 & 0 & 2 & 0\\ 0 & -1 & -1 & -4 & 7 & -2\\ 0 & 0 & 8 & 10 & -26 & 5 \end \right). $$

Матрица системы и расширенная матрица системы приведены к трапециевидной форме. Ранги этих матриц равны между собой и равны числу 3, т.е. $\rang A=\rang\widetilde = 3$. Так как ранги равны между собой и меньше, чем количество переменных, то согласно следствию из теоремы Кронекера-Капелли данная система имеет бесконечное количество решений.

Количество неизвестных $n=5$, ранги обеих матриц $r=3$, поэтому нужно выбрать три базисных переменных и $n-r=2$ свободных переменных. Применяя тот же метод «ступенек», что и в предыдущем примере, выберем в качестве базисных переменных $x_1$, $x_2$, $x_3$, а в качестве свободных переменных – $x_4$ и $x_5$.

Столбцы №4 и №5, которые соответствуют свободным переменным, перенесём за черту. После этого разделим третью строку на 8 и продолжим решение методом Гаусса:

$$ \left( \begin 1 & -2 & 4 & 0 & 0 & -2\\ 0 & -1 & -1 & -2 & 4 & -7\\ 0 & 0 & 8 & 5 & -10 & 26 \end \right) \begin \phantom <0>\\ \phantom<0>\\ III:8\end \rightarrow \left( \begin 1 & -2 & 4 & 0 & 0 & -2\\ 0 & -1 & -1 & -2 & 4 & -7\\ 0 & 0 & 1 & 5/8 & -5/4 & 13/4 \end \right) \begin I-4\cdot III \\ II+III\\ \phantom<0>\end \rightarrow \\ \left( \begin 1 & -2 & 0 & -5/2 & 5 & -15\\ 0 & -1 & 0 & -11/8 & 11/4 & -15/4\\ 0 & 0 & 1 & 5/8 & -5/4 & 13/4 \end \right) \begin \phantom <0>\\ II\cdot (-1)\\ \phantom<0>\end \rightarrow \left( \begin 1 & -2 & 0 & -5/2 & 5 & -15\\ 0 & 1 & 0 & 11/8 & -11/4 & 15/4\\ 0 & 0 & 1 & 5/8 & -5/4 & 13/4 \end \right) \begin I+2\cdot II \\ \phantom<0>\\ \phantom<0>\end \rightarrow\\ \rightarrow\left( \begin 1 & 0 & 0 & 1/4 & -1/2 & -15/2\\ 0 & 1 & 0 & 11/8 & -11/4 & 15/4\\ 0 & 0 & 1 & 5/8 & -5/4 & 13/4 \end \right) $$

Продолжение этой темы рассмотрим во второй части, где разберём ещё два примера с нахождением общего решения.

Метод Жордана-Гаусса онлайн

Данный онлайн калькулятор находит общее решение системы линейных уравнений методом Жордана-Гаусса. Дается подробное решение. Для вычисления выбирайте количество уравнений и количество переменных. Затем введите данные в ячейки и нажимайте на кнопку «Вычислить.» Теоретическую часть нахождения решения системы линейных уравнений методом Жордана-Гаусса смотрите ниже.

Предупреждение

Инструкция ввода данных. Числа вводятся в виде целых чисел (примеры: 487, 5, -7623 и т.д.), десятичных чисел (напр. 67., 102.54 и т.д.) или дробей. Дробь нужно набирать в виде a/b, где a и b (b>0) целые или десятичные числа. Примеры 45/5, 6.6/76.4, -7/6.7 и т.д.

Метод Жордана-Гаусса

Метод Жордана-Гаусса − это метод для решения систем линейных уравнений а также метод нахождения обратной матрицы. Данный метод является модификацией метода Гаусса.

Первый этап метода Жордана-Гаусса аналогична методу Гаусса (прямой ход Гаусса), который подробно можно посмотреть на странице «Метод Гаусса онлайн». Второй этап (обратный ход) метода Жордана-Гаусса заключается в обнулении всех элементов матрицы коэффициентов системы линейных уравнений, выше ведущих элементов. Отметим, что мы здесь рассматриваем произвольную систему линейных уравнений, где число переменных может быть не равным числу ограничений.

Рассмотрим следующую систему линейных уравнений:

(1)

Запишем систему (1) в матричном виде:

(3)

A-называется матрица коэффициентов системы, b − правая часть ограничений, x− вектор переменных, которую нужно найти. Пусть rang(A)=p.

Построим расшренную матрицу системы:

(4)

После прямого хода Гаусса (подробнее о прямом ходе Гаусса посмотрите на странице «Метод Гаусса онлайн») получим следующую расширенную матрицу:

(5)

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

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

Итак, обнуляем все элементы, стоящие в столбце p, выше элемента . Так как ≠0, то сложим строки 1,2. p−1 со строкой p, умноженной на соответственно.

Расширенная матрица примет следующий вид:

Аналогичным методом обнуляем элементы столбцов p−1, p−2, . 2 выше ведущих элементов .

Расширенная матрица примет следующий вид:

Делим каждую строку на соответствующий ведущий элемент (если ведущий элемент существует):

Тогда решение можно записать так:

где − произвольные вещественные числа.

Отметим, что при m=n и rangA=n система линейных уравнений (2) имеет единственное решение.

Рассмотрим численные примеры.

Примеры решения системы линейных уравнений методом Жордана-Гаусса

Пример 1. Найти решение системы линейных уравнений методом Жордана-Гаусса:

Матричный вид записи: Ax=b, где

.

Для решения системы, построим расширенную матрицу:

.

Обозначим через a_ij элементы i-ой строки и j-ого столбца.

Первый этап. Прямой ход Гаусса

Исключим элементы 1-го столбца матрицы ниже элемента a₁₁. Для этого сложим строки 2,3 со строкой 1, умноженной на 1/2,-3/2 соответственно:

.

Исключим элементы 2-го столбца матрицы ниже элемента a2 2. Для этого сложим строку 3 со строкой 2, умноженной на 1/5:

.

Второй этап. Обратный ход Гаусса

Исключим элементы 3-го столбца матрицы выше элемента a₃₃. Для этого сложим строки 1, 2 со строкой 3, умноженной на -3/2, -5/4 соответственно:

.

Исключим элементы 2-го столбца матрицы выше элемента a₂₂. Для этого сложим строку 1 со строкой 2, умноженной на -2/5:

.

Делим каждую строку матрицы на соответствующий ведущий элемент (если ведущий элемент существует):

.

.

Векторный вариант решения:

.

Пример 2. Найти решение системы линейных уравнений методом Жордана-Гаусса:

Матричный вид записи: Ax=b, где

Для решения системы, построим расширенную матрицу:

Обозначим через a_ij элементы i-ой строки и j-ого столбца.

Первый этап. Прямой ход Гаусса.

Исключим элементы 1-го столбца матрицы ниже элемента a₁₁. Для этого сложим строки 2,3 со строкой 1, умноженной на 4/3, 5/3 соответственно:

Исключим элементы 2-го столбца матрицы ниже элемента a2 2. Для этого сложим строку 3 со строкой 2, умноженной на -2:

Второй этап. Обратный ход Гаусса

Исключим элементы 2-го столбца матрицы выше элемента a₂₂. Для этого сложим строку 1 со строкой 2, умноженной на -3/10:

Делим каждую строку матрицы на соответствующий ведущий элемент (если ведущий элемент существует):

Выразим переменные x₁, x₂ относительно остальных переменных.

x₃− произвольное действительное число.

Векторный вариант решения:

Запишем вышеизложенное решение, представив свободные переменные в виде тождеств:

Тогда векторное решение можно представить так:

,

x₃− произвольное действительное число.

Число базисных решений системы уравнений

Решение произвольных систем

Пусть дана система m линейных уравнений с n неизвестными:

(1)

В матричной форме система (1) имеет вид

где А = — матрица коэффициентов системы;

Х = — матрица-столбец переменных;

В = — матрица-столбец свободных членов.

Решением системы (1) называется всякий вектор , координаты которого обращают каждое уравнение системы в верное равенство.

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

Система уравнений называется определенной, если она имеет единственное решение, и неопределенной, если она имеет более одного решения.

Две системы называются эквивалентными, если множества их решений совпадают.

Теорема 1. (теорема Кронекера — Капелли ). Система (1) совместна тогда и только тогда, когда ранг матрицы системы равен рангу расширенной матрицы системы:

.

Теорема 2 . Если ранг матрицы совместной системы равен числу неизвестных, то система имеет единственное решение. Если ранг матрицы совместной системы меньше числа неизвестных, то система имеет бесконечно много решений.

Пусть ранг матрицы r ( A )= r n . Переменные называются базисными (основными), если определитель матрицы коэффициентов при них (базисный минор) отличен от нуля. Количество базисных переменных равно r . Другие n — r переменных называются свободными ( неосновными ). Выражение базисных переменных через свободные называется общим решением системы. Из него можно получить бесконечное множество частных решений, придавая свободным переменным произвольные значения.

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

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

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

Элементарными преобразованиями системы являются:

— умножение уравнения на число, отличное от нуля;

— сложение уравнения, умноженного на любое число, с другим уравнением;

— отбрасывание уравнения 0 = 0.

Если при выполнении элементарных преобразований получено уравнение вида 0 = k (где k 0), то система несовместна.

Перейдем теперь к решению систем с различным количеством неизвестных и уравнений. Пусть дана система m линейных уравнений с n неизвестными. Если такая система совместна, то при r n она имеет бесконечное множество решений, каждое из которых может быть получено из общего решения системы.

Для нахождения общего решения нам необходимо выбрать, какие неизвестные мы будем считать основными (базисными). Это могут быть любые r переменных, коэффициенты при которых составляют определитель, отличный от нуля. Затем выбранные основные переменные нужно выразить через свободные. Для этого с помощью элементарных преобразований необходимо расширенную матрицу системы привести к такому виду, чтобы коэффициенты при базисных переменных образовали так называемые базисные столбцы — столбцы, состоящие из нулей и одной единицы.

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

Левый столбец таблицы содержит информацию об исключенных (базисных) переменных. Остальные столбцы содержат коэффициенты при неизвестных и свободные члены уравнений.

В исходную таблицу записывают расширенную матрицу системы. Далее приступают к выполнению очередной итерации:

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

2. Элементы ключевой строки делят на ключевой элемент.

3. Ключевой столбец заполняют нулями.

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

Переход к другому базису

Перейти от одного базиса системы к другому позволяет преобразование однократного замещения: вместо одной из основных переменных в базис вводят одну из свободных переменных. Для этого в столбце свободной переменной выбирают ключевой элемент и выполняют преобразования по указанному выше алгоритму, начиная с п. 2.

Нахождение опорных решений

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

Опорные решения системы находят методом Гаусса при выполнении следующих условий.

1. В исходной системе все свободные члены должны быть неотрицательны: .

2. В число базисных может быть введена только та переменная, в столбце коэффициентов при которой есть хотя бы один положительный элемент.

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

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

Замечание 2 . Если в столбцах коэффициентов при свободных переменных нет ни одного положительного элемента, то переход к новому опорному решению невозможен.