Как делается интерполяция. Как сделать интерполяцию. Постановка задачи интерполяции

. Алгоритм симплекс-метода

Пример 5.1. Решить следующую задачу линейного программирования симплекс-методом:

Решение:

I итерация:

х3 , х4 , х5 , х6 х1 ,х2 . Выразим базисные переменные через свободные:

Приведем целевую функциюк следующему виду:

На основе полученной задачи сформируем исходную симплекс-таблицу:

Таблица 5.3

Исходная симплекс-таблица

				Оценочные отношения

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

3 этап: проверка совместности системы ограничений ЗЛП.

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

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

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

6 этап: проверка оптимальности.

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

Так как найденное базисное решение допустимое, то поиск разрешающей колонки будем производить по следующей схеме: определяем колонки с отрицательными элементами в строке целевой функции (кроме колонки свободных чисел). Согласно таблице 5.3, таких колонок две: колонка «х1 » и колонка «х2 ». Из таких колонок выбирается та, которая содержит наименьший элемент в строке целевой функции. Она и будет разрешающей. Колонка «х2 » содержит наименьший элемент (–3) в сравнении с колонкой «х1

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

Таблица 5.4

Исходная симплекс-таблица

В таблице 5.4 наименьшее положительное оценочное отношение соответствует строке «х5 », следовательно, она будет разрешающей.

Элемент, расположенный на пересечение разрешающей колонки и разрешающей строки, принимается в качестве разрешающего. В нашем примере – это элемент , который расположен на пересечении строки «х5 » и колонки «х2 ».

Разрешающий элемент показывает одну базисную и одну свободную переменные, которые необходимо поменять местами в симплекс-таблице, для перехода к новому «улучшенному» базисному решению. В данном случае это переменные х5 и х2 , в новой симплекс-таблице (таблице 5.5) их меняем местами.

9.1. Преобразование разрешающего элемента.

Разрешающий элемент таблицы 5.4 преобразовывается следующим образом:

Полученный результат вписываем в аналогичную клетку таблицы 5.5.

9.2. Преобразование разрешающей строки.

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

9.3. Преобразование разрешающей колонки.

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

9.4. Преобразование остальных элементов симплекс-таблицы.

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

К примеру, рассмотрим преобразование элемента, расположенного на пересечении строки «х3 » и колонки «», условно обозначим его «х3 ». В таблице 5.4 мысленно вычерчиваем прямоугольник, одна вершина которого располагается в клетке, значение которой преобразуем (т.е. в клетке «х3 »), а другая (диагональная вершина) – в клетке с разрешающим элементом. Две другие вершины (второй диагонали) определяются однозначно. Тогда преобразованное значение клетки «х3 » будет равно прежнему значению данной клетки минус дробь, в знаменателе которой разрешающий элемент (из таблицы 5.4), а в числителе произведение двух других неиспользованных вершин, т.е.:

«х3 »: .

Аналогично преобразуются значения других клеток:

«х3 х1 »: ;

«х4 »: ;

«х4 х1 »: ;

«х6 »: ;

«х6 х1 »: ;

«»: ;

«х1 »: .

В результате данных преобразований получили новую симплекс- таблицу (таблица 5.5).

II итерация:

1 этап: составление симплекс-таблицы.

Таблица 5.5

Симплекс-таблица II итерации

				Оценочные отношения

2 этап: определение базисного решения.

В результате проведенных симплекс-преобразований получили новое базисное решение (таблица 5.5):

Как видно, при данном базисном решении значение целевой функции =15, что больше чем при предыдущем базисном решении.

Не совместность системы ограничений в соответствии с признаком 1 в таблице 5.5 не выявлена.

4 этап: проверка ограниченности целевой функции.

Неограниченность целевой функции в соответствии с признаком 2 в таблице 5.5 не выявлена.

5 этап: проверка допустимости найденного базисного решения.

Найденное базисное решение в соответствии с признаком 4 не оптимальное, так как в строке целевой функции симплекс-таблицы (таблица 5.5) содержится отрицательный элемент: –2 (свободное число данной строки при рассмотрении данного признака не учитывается). Следовательно, переходим к 8 этапу.

8 этап: определение разрешающего элемента.

8.1. Определение разрешающей колонки.

Найденное базисное решение допустимое, определяем колонки с отрицательными элементами в строке целевой функции (кроме колонки свободных чисел). Согласно таблице 5.5, такой колонкой является только одна колонка: «х1 ». Следовательно, ее принимаем в качестве разрешенной.

8.2. Определение разрешающей строки.

Согласно полученным значениям положительных оценочных отношений в таблице 5.6, минимальным является отношение, соответствующее строке «х3 ». Следовательно, ее принимаем в качестве разрешенной.

Таблица 5.6

Симплекс-таблица II итерации

				Оценочные отношения
				3/1=3 – min

9 этап: преобразование симплекс-таблицы.

Преобразования симплекс-таблицы (таблицы 5.6) выполняются аналогично, как и в предыдущей итерации. Результаты преобразований элементов симплекс-таблицы приведены в таблице 5.7.

III итерация

По результатам симплекс-преобразований предыдущей итерации составляем новую симплекс-таблицу:

Таблица 5.7

Симплекс-таблица III итерации

				Оценочные отношения

2 этап: определение базисного решения.

В результате проведенных симплекс-преобразований получили новое базисное решение (таблица 5.7):

3 этап: проверка совместности системы ограничений.

Не совместность системы ограничений в соответствии с признаком 1 в таблице 5.7 не выявлена.

4 этап: проверка ограниченности целевой функции.

Неограниченность целевой функции в соответствии с признаком 2 в таблице 5.7 не выявлена.

5 этап: проверка допустимости найденного базисного решения.

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

6 этап: проверка оптимальности найденного базисного решения.

Найденное базисное решение в соответствии с признаком 4 не оптимальное, так как в строке целевой функции симплекс-таблицы (таблица 5.7) содержится отрицательный элемент: –3 (свободное число данной строки при рассмотрении данного признака не учитывается). Следовательно, переходим к 8 этапу.

8 этап: определение разрешающего элемента.

8.1. Определение разрешающей колонки.

Найденное базисное решение допустимое, определяем колонки с отрицательными элементами в строке целевой функции (кроме колонки свободных чисел). Согласно таблице 5.7, такой колонкой является только одна колонка: «х5 ». Следовательно, ее принимаем в качестве разрешенной.

8.2. Определение разрешающей строки.

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

Таблица 5.8

Симплекс-таблица III итерации

				Оценочные отношения
				5/5=1 – min

9 этап: преобразование симплекс-таблицы.

Преобразования симплекс-таблицы (таблицы 5.8) выполняются аналогично, как и в предыдущей итерации. Результаты преобразований элементов симплекс-таблицы приведены в таблице 5.9.

IV итерация

1 этап: построение новой симплекс-таблицы.

По результатам симплекс-преобразований предыдущей итерации составляем новую симплекс-таблицу:

Таблица 5.9

Симплекс-таблица IV итерации

				Оценочные отношения
			–(–3/5)=3/5
			–(1/5)=–1/5
			–(9/5)=–9/5
			–(–3/5)=3/5

2 этап: определение базисного решения.

В результате проведенных симплекс-преобразований получили новое базисное решение, согласно таблице 5.9 решение следующее:

3 этап: проверка совместности системы ограничений.

Не совместность системы ограничений в соответствии с признаком 1 в таблице 5.9 не выявлена.

4 этап: проверка ограниченности целевой функции.

Неограниченность целевой функции в соответствии с признаком 2 в таблице 5.9 не выявлена.

5 этап: проверка допустимости найденного базисного решения.

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

6 этап: проверка оптимальности найденного базисного решения.

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

7 этап: проверка альтернативности решения.

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

Ответ: оптимальное значение целевой функции рассматриваемой задачи =24, которое достигается при.

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

Решение:

I итерация:

1 этап: формирование исходной симплекс-таблицы.

Исходная задача линейного программирования задана в стандартной форме. Приведем ее к каноническому виду путем введения в каждое из ограничений-неравенств дополнительной неотрицательной переменной, т.е.

В полученной системе уравнений примем в качестве разрешенных (базисных) переменные х3 , х4 , х5 , х6 , тогда свободными переменными будут х1 ,х2 . Выразим базисные переменные через свободные.

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

В симплекс-таблице выделяются следующие блоки:

Запишем решение задачи примера из раздела 3.3 в симплекс-таблицах:

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

В последнюю строку первой симплекс-таблицы заносим критерий в неявной форме

Исключаем из этого критерия базисную переменную x 4 , приводя критерий к виду

Для оптимальности решения все оценки должны быть неотрицательны

Решение не оптимальное, т.к. есть отрицательные оценки.

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

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

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

Решение не оптимальное, т.к. есть отрицательная оценка -2.

Решение оптимальное, т.к. все оценки больше нуля. Очевидно, что увеличить нельзя.

Правила построения симплекс-таблиц

Симплекс-таблица строится для какого-либо опорного решения.

Пусть опорное решение. Симплекс-таблица для этого решения имеет вид

Базисная матрица B = (A 1 , A 2 , … A m)

· при базисных переменных текущая матрица единичная.

• · любой столбец.
• · вектор правых частей ограничений.
• · оценки при свободных переменных не нулевые

· в правой нижней клетке - значение критерия

Этапы симплекс-метода

• 1. Проверка признака оптимальности ()
• 2. Если есть, то решение не оптимальное. Тогда выбираем столбец с минимальной оценкой. Его назовем разрешающим.
• 3. Разрешающая строка выбирается по минимальному отношению свободных членов к положительным коэффициентам разрешающего столбца. Базисная переменная, выражающаяся из этой строки, выходит из списка базисных переменных. Т.е. x k выходит, а x s входит.

• 4. Текущая симплекс-таблица преобразуется по следующему правилу:
  • · разрешающая строка делится на разрешающий элемент:

• · разрешающий столбец заменяется единичным.
• · все остальные элементы симплекс-таблицы могут быть пересчитаны по правилу четырехугольника:

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

Или новое значение элемента равно произведению элементов на главной диагонали минус произведение элементов на противоположной диагонали, и все это деленное на разрешающий элемент.

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

Метод Гаусса-Жордана предназначен для решения систем линейных алгебраических уравнений (СЛАУ). Он является модификацией метода Гаусса . Если метод Гаусса осуществляется в два этапа (прямой ход и обратный) то метод Гаусса-Жордана позволяет решить систему в один этап. Подробности и непосредственная схема применения метода Гаусса-Жордана описаны в примерах.

Во всех примерах $A$ обозначает матрицу системы, $\widetilde{A}$ - расширенную матрицу системы. О матричной форме записи СЛАУ можно прочесть .

Пример №1

Решить СЛАУ $ \left\{ \begin{aligned} & 4x_1-7x_2+8x_3=-23;\\ & 2x_1-4x_2+5x_3=-13;\\ & -3x_1+11x_2+x_3=16. \end{aligned} \right.$ методом Гаусса-Жордана.

Давайте перейдём от последней полученной нами матрице к системе:

$$ \left\{ \begin{aligned} & 0\cdot x_1+1\cdot x_2+0\cdot x_3=1;\\ & 1\cdot x_1+0\cdot x_2+0\cdot x_3=-2;\\ & 0\cdot x_1+0\cdot x_2+1\cdot x_3=-1. \end{aligned} \right. $$

Упрощая полученную систему, имеем:

$$ \left\{ \begin{aligned} & x_2=1;\\ & x_1=-2;\\ & x_3=-1. \end{aligned} \right. $$

Полное решение без пояснений выглядит так:

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

Выбор разрешающих элементов на главной диагонали матрицы системы.

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

Первый шаг

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

$$ \left(\begin{array} {ccc|c} 4 & -7 & 8 & -23\\ 2 & -4& 5 & -13 \\ -3 & 11 & 1 & 16 \end{array} \right)\rightarrow \left(\begin{array} {ccc|c} 2 & -4& 5 & -13\\ 4 & -7 & 8 & -23 \\ -3 & 11 & 1 & 16 \end{array} \right) $$

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

$$ \left(\begin{array} {ccc|c} 2 & -4& 5 & -13\\ 4 & -7 & 8 & -23 \\ -3 & 11 & 1 & 16 \end{array} \right) \begin{array} {l} I:2 \\\phantom{0} \\ \phantom{0} \end{array} \rightarrow \left(\begin{array} {ccc|c} 1 & -2& 5/2 & -13/2 \\4 & -7 & 8 & -23\\ -3 & 11 & 1 & 16 \end{array} \right) \begin{array} {l} \phantom{0} \\ II-4\cdot I\\ III+3\cdot I \end{array} \rightarrow \left(\begin{array} {ccc|c} 1 & -2& 5/2 & -13/2\\0 & 1 & -2 & 3\\ 0 & 5 & 17/2 & -7/2 \end{array} \right). $$

Второй шаг

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

$$ \left(\begin{array} {ccc|c} 1 & -2& 5/2 & -13/2\\0 & 1 & -2 & 3\\ 0 & 5 & 17/2 & -7/2 \end{array} \right) \begin{array} {l} I+2\cdot II \\ \phantom{0}\\ III-5\cdot II \end{array} \rightarrow \left(\begin{array} {ccc|c} 1 & 0 & -3/2 & -1/2 \\ 0 & 1 & -2 & 3\\ 0 & 0 & 37/2 & -37/2 \end{array} \right). $$

Второй шаг окончен. Переходим к третьему шагу.

Третий шаг

На третьем шаге требуется обнулить элементы третьего столбца. В качестве разрешающего элемента выбираем элемент третьей строки, т.е. 37/2. Разделим элементы третьей строки на 37/2 (чтобы разрешающий элемент стал равен 1), а затем обнулим соответствующие элементы третьего столбца:

$$ \left(\begin{array} {ccc|c} 1 & 0 & -3/2 & -1/2 \\ 0 & 1 & -2 & 3\\ 0 & 0 & 37/2 & -37/2 \end{array} \right) \begin{array} {l} \phantom{0}\\ \phantom{0}\\ III:\frac{37}{2} \end{array} \rightarrow \left(\begin{array} {ccc|c} 1 & 0 & -3/2 & -1/2 \\ 0 & 1 & -2 & 3\\ 0 & 0 & 1 & -1 \end{array} \right) \begin{array} {l} I+2\cdot III\\II+3/2\cdot III\\ \phantom{0} \end{array} \rightarrow \left(\begin{array} {ccc|c} 1 & 0 & 0 & -2 \\ 0 & 1 & 0 & 1\\ 0 & 0 & 1 & -1 \end{array} \right). $$

Ответ получен: $x_1=-2$, $x_2=1$, $x_3=-1$. Полное решение без пояснений выглядит так:

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

Ответ : $x_1=-2$, $x_2=1$, $x_3=-1$.

Пример №2

Решить СЛАУ $ \left\{ \begin{aligned} & 3x_1+x_2+2x_3+5x_4=-6;\\ & 3x_1+x_2+2x_4=-10;\\ & 6x_1+4x_2+11x_3+11x_4=-27;\\ & -3x_1-2x_2-2x_3-10x_4=1. \end{aligned} \right.$ методом Гаусса-Жордана.

Запишем расширенную матрицу данной системы : $\widetilde{A}=\left(\begin{array} {cccc|c} 3 & 1 & 2 & 5 & -6\\ 3 & 1& 0 & 2 & -10 \\ 6 & 4 & 11 & 11 & -27 \\ -3 & -2 & -2 & -10 & 1 \end{array} \right)$.

В качестве разрешающих элементов станем выбирать диагональные элементы матрицы системы: на первом шаге возьмём элемент первой строки, на втором шаге элемент второй строки и так далее.

Первый шаг

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

$$ \left(\begin{array}{cccc|c} 3 & 1 & 2 & 5 & -6\\ 3 & 1 & 0 & 2 & -10\\ 6 & 4 & 11 & 11 & -27\\ -3 & -2 & -2 & -10 & 1\end{array}\right) \begin{array} {l} I:3\\ \phantom{0}\\\phantom{0}\\\phantom{0}\end{array} \rightarrow \left(\begin{array}{cccc|c} 1 & 1/3 & 2/3 & 5/3 & -2\\ 3 & 1 & 0 & 2 & -10\\ 6 & 4 & 11 & 11 & -27\\ -3 & -2 & -2 & -10 & 1\end{array}\right) \begin{array} {l} \phantom{0}\\ II-3\cdot I\\III-6\cdot I\\IV+3\cdot I\end{array} \rightarrow\\ \rightarrow\left(\begin{array}{cccc|c} 1 & 1/3 & 2/3 & 5/3 & -2\\ 0 & 0 & -2 & -3 & -4\\ 0 & 2 & 7 & 1 & -15\\ 0 & -1 & 0 & -5 & -5\end{array}\right). $$

Второй шаг

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

$$ \left(\begin{array}{cccc|c} 1 & 1/3 & 2/3 & 5/3 & -2\\ 0 & 0 & -2 & -3 & -4\\ 0 & 2 & 7 & 1 & -15\\ 0 & -1 & 0 & -5 & -5\end{array}\right)\rightarrow \left(\begin{array}{cccc|c} 1 & 1/3 & 2/3 & 5/3 & -2\\ 0 & -1 & 0 & -5 & -5\\ 0 & 2 & 7 & 1 & -15\\ 0 & 0 & -2 & -3 & -4\end{array}\right) $$

Вот теперь всё в норме: разрешающий элемент равен (-1). Бывает, кстати, что смена мест строк невозможна, но это обговорим в следующем примере №3. А пока что делим вторую строку на (-1), а затем обнуляем элементы второго столбца. Обратите внимание, что во втором столбце элемент, расположенный в четвёртой строке, уже равен нулю, поэтому четвёртую строку трогать не будем.

$$ \left(\begin{array}{cccc|c} 1 & 1/3 & 2/3 & 5/3 & -2\\ 0 & -1 & 0 & -5 & -5\\ 0 & 2 & 7 & 1 & -15\\ 0 & 0 & -2 & -3 & -4\end{array}\right) \begin{array} {l} \phantom{0}\\II:(-1) \\\phantom{0}\\\phantom{0}\end{array} \rightarrow \left(\begin{array}{cccc|c} 1 & 1/3 & 2/3 & 5/3 & -2\\ 0 & 1 & 0 & 5 & 5\\ 0 & 2 & 7 & 1 & -15\\ 0 & 0 & -2 & -3 & -4\end{array}\right) \begin{array} {l} I-1/3\cdot II\\ \phantom{0} \\III-2\cdot II\\\phantom{0}\end{array} \rightarrow\\ \rightarrow\left(\begin{array}{cccc|c} 1 & 0 & 2/3 & 0 & -11/3\\ 0 & 1 & 0 & 5 & 5\\ 0 & 0 & 7 & -9 & -25\\ 0 & 0 & -2 & -3 & -4\end{array}\right). $$

Третий шаг

Приступаем к обработке третьего столбца. В качестве разрешающего элемента мы условились брать диагональные элементы матрицы системы. Для третьего шага это означает выбор элемента, расположенного в третьей строке. Однако если мы просто возьмём элемент 7 в качестве разрешающего, то всю третью строку придётся делить на 7. Мне кажется, что разделить на (-2) попроще. Поэтому поменяем местами третью и четвёртую строки, и тогда разрешающим элементом станет (-2):

$$ \left(\begin{array}{cccc|c} 1 & 0 & 2/3 & 0 & -11/3\\ 0 & 1 & 0 & 5 & 5\\ 0 & 0 & 7 & -9 & -25\\ 0 & 0 & -2 & -3 & -4\end{array}\right) \rightarrow \left(\begin{array}{cccc|c} 1 & 0 & 2/3 & 0 & -11/3\\ 0 & 1 & 0 & 5 & 5\\ 0 & 0 & -2 & -3 & -4\\ 0 & 0 & 7 & -9 & -25\end{array}\right) $$

Разрешающий элемент - (-2). Делим третью строку на (-2) и обнуляем соответствующие элементы третьего столбца:

$$ \left(\begin{array}{cccc|c} 1 & 0 & 2/3 & 0 & -11/3\\ 0 & 1 & 0 & 5 & 5\\ 0 & 0 & -2 & -3 & -4\\ 0 & 0 & 7 & -9 & -25\end{array}\right) \begin{array} {l} \phantom{0}\\ \phantom{0} \\III:(-2)\\\phantom{0}\end{array}\rightarrow \left(\begin{array}{cccc|c} 1 & 0 & 2/3 & 0 & -11/3\\ 0 & 1 & 0 & 5 & 5\\ 0 & 0 & 1 & 3/2 & 2\\ 0 & 0 & 7 & -9 & -25\end{array}\right) \begin{array} {l} I-2/3\cdot III\\ \phantom{0} \\ \phantom{0}\\IV-7\cdot III\end{array}\rightarrow\\ \rightarrow\left(\begin{array}{cccc|c} 1 & 0 & 0 & -1 & -5\\ 0 & 1 & 0 & 5 & 5\\ 0 & 0 & 1 & 3/2 & 2\\ 0 & 0 & 0 & -39/2 & -39\end{array}\right). $$

Четвёртый шаг

Переходим к обнулению четвёртого столбца. Разрешающий элемент расположен в четвёртой строке и равен числу $-\frac{39}{2}$.

$$ \left(\begin{array}{cccc|c} 1 & 0 & 0 & -1 & -5\\ 0 & 1 & 0 & 5 & 5\\ 0 & 0 & 1 & 3/2 & 2\\ 0 & 0 & 0 & -39/2 & -39\end{array}\right) \begin{array} {l} \phantom{0}\\ \phantom{0} \\ \phantom{0}\\IV:\left(-\frac{39}{2}\right) \end{array}\rightarrow \left(\begin{array}{cccc|c} 1 & 0 & 0 & -1 & -5\\ 0 & 1 & 0 & 5 & 5\\ 0 & 0 & 1 & 3/2 & 2\\ 0 & 0 & 0 & 1 & 2\end{array}\right) \begin{array} {l} I+IV\\ II-5\cdot IV \\ III-3/2\cdot IV \\ \phantom{0} \end{array}\rightarrow\\ \rightarrow\left(\begin{array}{cccc|c} 1 & 0 & 0 & 0 & -3\\ 0 & 1 & 0 & 0 & -5\\ 0 & 0 & 1 & 0 & -1\\ 0 & 0 & 0 & 1 & 2\end{array}\right). $$

Решение окончено. Ответ таков: $x_1=-3$, $x_2=-5$, $x_3=-1$, $x_4=2$. Полное решение без пояснений:

Ответ : $x_1=-3$, $x_2=-5$, $x_3=-1$, $x_4=2$.

Пример №3

Решить СЛАУ $\left\{\begin{aligned} & x_1-2x_2+3x_3+4x_5=-5;\\ & 2x_1+x_2+5x_3+2x_4+9x_5=-3;\\ & 3x_1+4x_2+7x_3+4x_4+14x_5=-1;\\ & 2x_1-4x_2+6x_3+11x_5=2;\\ & -2x_1+14x_2-8x_3+4x_4-7x_5=20;\\ & -4x_1-7x_2-9x_3-6x_4-21x_5=-9. \end{aligned}\right.$ методом Гаусса-Жордана. Если система является неопределённой, указать базисное решение.

Подобные примеры разбираются в теме "Общее и базисное решения СЛАУ" . Во второй части упомянутой темы данный пример решён с помощью метод Гаусса . Мы же решим его с помощью метода Гаусса-Жордана. Пошагово разбивать решение не станем, так как это уже было сделано в предыдущих примерах.

$$ \left(\begin{array}{ccccc|c} 1 & -2 & 3 & 0 & 4 & -5\\ 2 & 1 & 5 & 2 & 9 & -3\\ 3 & 4 & 7 & 4 & 14 & -1\\ 2 & -4 & 6 & 0 & 11 & 2\\ -2 & 14 & -8 & 4 & -7 & 20\\ -4 & -7 & -9 & -6 & -21 & -9 \end{array}\right) \begin{array} {l} \phantom{0} \\ II-2\cdot I\\ III-3\cdot I\\ IV-2\cdot I\\ V+2\cdot I\\VI+4\cdot I \end{array} \rightarrow \left(\begin{array}{ccccc|c} 1 & -2 & 3 & 0 & 4 & -5\\ 0 & 5 & -1 & 2 & 1 & 7\\ 0 & 10 & -2 & 4 & 2 & 14\\ 0 & 0 & 0 & 0 & 3 & 12\\ 0 & 10 & -2 & 4 & 1 & 10\\ 0 & -15 & 3 & -6 & -5 & -29 \end{array}\right) \begin{array} {l} \phantom{0} \\ II:5 \\ \phantom{0}\\ \phantom{0}\\ \phantom{0} \\ \phantom{0}\end{array} \rightarrow \\ \left(\begin{array}{ccccc|c} 1 & -2 & 3 & 0 & 4 & -5\\ 0 & 1 & -1/5 & 2/5 & 1/5 & 7/5\\ 0 & 10 & -2 & 4 & 2 & 14\\ 0 & 0 & 0 & 0 & 3 & 12\\ 0 & 10 & -2 & 4 & 1 & 10\\ 0 & -15 & 3 & -6 & -5 & -29 \end{array}\right) \begin{array} {l} I+2\cdot II \\ \phantom{0}\\ III-10\cdot II\\ IV:3\\ V-10\cdot II\\VI+15\cdot II \end{array} \rightarrow \left(\begin{array}{ccccc|c} 1 & 0 & 13/5 & 4/5 & 22/5 & -11/5\\ 0 & 1 & -1/5 & 2/5 & 1/5 & 7/5\\ 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 1 & 4\\ 0 & 0 & 0 & 0 & -1 & -4\\ 0 & 0 & 0 & 0 & -2 & -8 \end{array}\right). $$

Полагаю, что одно из сделанных преобразований всё-таки требует пояснения: $IV:3$. Все элементы четвёртой строки нацело делились на три, поэтому сугубо из соображений упрощения мы разделили все элементы этой строки на три. Третья строка в преобразованной матрице стала нулевой. Вычеркнем нулевую строку:

$$ \left(\begin{array}{ccccc|c} 1 & 0 & 13/5 & 4/5 & 22/5 & -11/5\\ 0 & 1 & -1/5 & 2/5 & 1/5 & 7/5\\ 0 & 0 & 0 & 0 & 1 & 4\\ 0 & 0 & 0 & 0 & -1 & -4\\ 0 & 0 & 0 & 0 & -2 & -8 \end{array}\right) $$

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

В этой ситуации проблема решается крайне незамысловато. Мы не можем обработать третий столбец? Хорошо, перейдём к четвёртому. Может, в четвёртом столбце элемент третьей строки будет не равен нулю. Однако четвёртый столбец "болеет" той же проблемой, что и третий. Элемент третьей строки в четвёртом столбце равен нулю. И смена мест строк опять-таки ничего не даст. Четвёртый столбец тоже не можем обработать? Ладно, перейдём к пятому. А вот в пятом столбце элемент третьей строки очень даже не равен нулю. Он равен единице, что довольно-таки хорошо. Итак, разрешающий элемент в пятом столбце равен 1. Разрешающий элемент выбран, поэтому осуществим дальшейшие преобразования метода Гаусса-Жордана:

$$ \left(\begin{array}{ccccc|c} 1 & 0 & 13/5 & 4/5 & 22/5 & -11/5\\ 0 & 1 & -1/5 & 2/5 & 1/5 & 7/5\\ 0 & 0 & 0 & 0 & 1 & 4\\ 0 & 0 & 0 & 0 & -1 & -4\\ 0 & 0 & 0 & 0 & -2 & -8 \end{array}\right) \begin{array} {l} I-22/5\cdot III \\ II-1/5\cdot III \\ \phantom{0}\\ IV+III\\ V+2\cdot III \end{array} \rightarrow \left(\begin{array}{ccccc|c} 1 & 0 & 13/5 & 4/5 & 0 & -99/5\\ 0 & 1 & -1/5 & 2/5 & 0 & 3/5\\ 0 & 0 & 0 & 0 & 1 & 4\\ 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 \end{array}\right) \rightarrow \\ \rightarrow\left|\text{Удаляем нулевые строки}\right|\rightarrow \left(\begin{array}{ccccc|c} 1 & 0 & 13/5 & 4/5 & 0 & -99/5\\ 0 & 1 & -1/5 & 2/5 & 0 & 3/5\\ 0 & 0 & 0 & 0 & 1 & 4 \end{array}\right)$$

Мы привели матрицу системы и расширенную матрицу системы к ступенчатому виду. Ранги обеих матриц равны $r=3$, т.е. надо выбрать 3 базисных переменных. Количество неизвестных $n=5$, поэтому нужно выбрать $n-r=2$ свободных переменных. Так как $r < n$, то согласно следствию из теоремы Кронекера-Капелли данная система является неопределённой (т.е. имеет бесконечное количество решений). Для нахождения решений системы составим "ступеньки":

На "ступеньках" стоят элементы из столбцов №1, №2, №5. Следовательно, базисными будут переменные $x_1$, $x_2$, $x_5$. Свободными переменными, соответственно, будут $x_3$, $x_4$. Столбцы №3 и №4, соответствующие свободным переменным, перенесём за черту, при этом, конечно, не забыв сменить им знаки.

$$ \left(\begin{array}{ccccc|c} 1 & 0 & 13/5 & 4/5 & 0 & -99/5\\ 0 & 1 & -1/5 & 2/5 & 0 & 3/5\\ 0 & 0 & 0 & 0 & 1 & 4 \end{array}\right)\rightarrow \left(\begin{array}{ccc|ccc} 1 & 0 & 0 & -99/5 & -13/5 & -4/5\\ 0 & 1 & 0 & 3/5 & 1/5 & -2/5\\ 0 & 0 & 1 & 4 & 0 & 0\end{array}\right). $$

Из последней матрицы получим общее решение: $\left\{\begin{aligned} & x_1=-\frac{99}{5}-\frac{13}{5}x_3-\frac{4}{5}x_4;\\ & x_2=\frac{3}{5}+\frac{1}{5}x_3-\frac{2}{5}x_4;\\ & x_3 \in R;\\ & x_4\in R;\\ & x_5=4. \end{aligned}\right.$. Базисное решение найдём, приняв свободные переменные равными нулю, т.е. $x_3=0$, $x_4=0$:

$$ \left\{\begin{aligned} & x_1=-\frac{99}{5};\\ & x_2=\frac{3}{5};\\ & x_3=0;\\ & x_4=0;\\ & x_5=4. \end{aligned}\right. $$

Задача решена, осталось лишь записать ответ.

Ответ : Общее решение: $\left\{\begin{aligned} & x_1=-\frac{99}{5}-\frac{13}{5}x_3-\frac{4}{5}x_4;\\ & x_2=\frac{3}{5}+\frac{1}{5}x_3-\frac{2}{5}x_4;\\ & x_3 \in R;\\ & x_4\in R;\\ & x_5=4. \end{aligned}\right.$, базисное решение: $\left\{\begin{aligned} & x_1=-\frac{99}{5};\\ & x_2=\frac{3}{5};\\ & x_3=0;\\ & x_4=0;\\ & x_5=4. \end{aligned}\right.$.