Что такое базисные переменные

Что такое базисные переменные

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

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

(1)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Источник

Большая Энциклопедия Нефти и Газа

Базисные переменные

Базисные переменные обеих задач выражены через соответствующие небазисные переменные. [1]

Базисные переменные всегда положительны. Принятие этого предположения невырожденности весьма целесообразно, так как при этом т наибольших компонент х могут быть приняты за базисные. [2]

Базисные переменные для условий (9.14) будут представлены в специальном виде, в котором переменные и всегда будут в числе базисных, тогда как переменные х и К могут входить в число базисных и выходить из них. Вводится также предположение невырожденности, требующее, чтобы все базисные переменные были отличны от нуля. Так как размер таблицы равен ( т п) X ( 2п т), то алгоритм всегда будет вырабатывать п т ненулевых базисных переменных. Согласно предположению невырожденности никакая нулевая переменная не может входить в число базисных. [3]

Базисные переменные будут разделены, если мы сможем заменить матрицу В единичной матрицей. [4]

Выразим базисные переменные через свободную переменную, для чего умножим первое ограничительное уравнение на 22 / 012 и вычтем второе ограничительное уравнение. [6]

Поскольку базисные переменные хг и х2 имеют ненулевые коэффициенты в г-строке, эту строку следует преобразовать. [7]

Если положить базисные переменные равными числам из 0-го столбца, то получим допустимое решение. [8]

Последовательно приравнивая базисные переменные нулю, получим уравнения прямых. [9]

Тогда можно выразить базисные переменные через оставшиеся и свести решение задачи к задаче меньшей размерности, в которой принимают участие лишь небазисные переменные. [10]

Следовательно, две базисные переменные можно выразить линейно через другие две свободные. [11]

В таком ее виде базисные переменные легко спутать с другими и поэтому первый шаг заключается в том, чтобы оставить по одной базисной переменной в каждой строке, после чего станет легко принимать решения. Тогда первые т столбцов матрицы Л образуют квадратную матрицу В ( базисную матрицу для этого угла) и оставшиеся п столбцов дают матрицу F размера тхп. Основной момент состоит в том, что в этом углу xF0 и уравнение Ах Ь превращается в Вхв Ь, откуда находятся базисные переменные хв. Таким образом, стоимость равняется сх свхв. [12]

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

Условие ( б) утверждает, что базисные переменные исключены из целевой функции. Условие ( в) означает, что в этой форме постоянные члены уравнений неотрицательны. [15]

Источник

Содержание:

Базисные и свободные переменные:

Пусть задана система

Элементарными преобразованиями системы линейных уравнений называются следующие преобразования:

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

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

Предположим, что в системе (6.1.1). Если это не так, то переставим уравнения системы так, чтобы .

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

(6.1.2)

в которой коэффициенты вычислены по формулам:

На втором шаге метода Гаусса исключим неизвестное из всех уравнений системы (6.1.2) начиная с третьего, предполагая, что (в противном случае, переставим уравнения системы (6.1.2)

чтобы это условие было выполнено). Для исключения неизвестного последовательно умножим второе уравнение системы (6.1.2) на множетели и вычтем последовательно преобразованные уравнения из третьего, четвёртого, последнего. уравнения системы (6.1.2). В результате получим эквивалентную систему:

в которой коэффициенты вычислены по формулам:

Продолжая аналогичные преобразования, систему (6.1.1) можно привести к одному из видов:

Совокупность элементарных преобразований, приводящих систему (6.1.1) к виду (6.1.4) или (6.1.5) называется прямым ходом метода Гаусса.

Отметим, что если на каком-то шаге прямого хода метода Гаусса получим уравнение вида:

, то это означает, что система (6.1.1) несовместна.

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

Если же в результате прямого хода метода Гаусса мы получим систему (6.1.5), которая называется системой ступенчатого вида, то из последнего уравнения этой системы находим значение неизвсстного которое выражается через неизвестные . Найденное выражение подставляем в предпоследнее уравнение системы (6.1.5) и выражаем неизвестное через неизвестные и т.д. Двигаясь снизу вверх в системе (6.1.5) находим выражения неизвестных через неизвестные При этом неизвестные называются базисными неизвестными, а неизвестные — свободными. Так как свободным неизвестным можно придавать любые значения и получать соответствующие значения базисных неизвестных, то система (6.1.5), а, следовательно, и система (6.1.1) в этом случае имеет бесконечное множество решений. Полученные выражения базисных неизвестных через свободные неизвестные называются общим решением системы уравнений (6.1.1).

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

Формализовать метод Гаусса можно при помощи следующего алгоритма.

Алгоритм решения системы m линейных уравнений с n неизвестными методом Гаусса

1. Составьте расширенную матрицу коэффициентов системы уравнений так, чтобы было не равно нулю:

2. Выполните первый шаг метода Гаусса: в первом столбце начиная со второй строки, запишите нули, а все другие элементы вычислите по формуле

Матрица после первого шага примет вид

3. Выполните второй шаг метода Гаусса, предполагая, что : во втором столбце начиная с третьей строки, запишите нули, а все другие элементы вычислите по формуле

После второго шага матрица примет вид

4. Продолжая аналогичные преобразования, придёте к одному из двух случаев:

а) либо в ходе преобразований получим уравнение вида

тогда данная система несовместна;

б) либо придём к матрице вида:

где . Возможное уменьшение числа строк

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

5. Использовав конечную матрицу, составьте систему, при этом возможны два случая:

5.2. :

Система имеет в этом случае бесконечное множество решений.

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

Последующие шаги выполняем по правилам:

1) выбирается разрешающий элемент (диагональный элемент матрицы);

2) элементы разрешающей строки оставляем без изменения;

3) все элементы разрешающего столбца, кроме разрешающего элемента, заменяем нулями; • •

4) все другие элементы матрицы пересчитываем по правилу прямоугольника.

На последнем шаге делим элементы строк на диагональные элементы матрицы, записанные слева от вертикальной черты, и получаем решение системы.

Пример:

Решить систему уравнений:

Решение:

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

Из последней матрицы находим следующее решение системы

уравнении:

Ответ:

Пример:

Решить систему уравнений:

Решение:

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

Система привелась к ступенчатому виду (трапециевидной форме):

в которой неизвестные — базисные, а — свободные. Из второго уравнения системы (6.1.6) находим выражение через . Из первого уравнений найдём выражение через и . Система имеет бесконечное множество решений. Общее решение системы имеет вид:

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

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

Ответ: система имеет бесконечное множество решений, общее решение которой записывается в виде:

Пример:

Решить систему уравнений:

Решение:

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

Ответ: система несовместна.

Замечание 1. Если дана система уравнений (6.1.1), в которой число уравнений m равно числу неизвестных n (m=n) и определитель этой системы не равен нулю , то система имеет единственное решение, которое можно найти по формулам Крамера: , где определитель получен из определи-теля заменой j-ro столбца столбцом свободных членов.

Если же такую систему (m-n) записать в матричной форме AX=F, то её решение можно найти по формуле и оно является единственным.

Пример:

Найти обратную матрицу для матрицы:

Решение:

то обратная матрица существует. Составим расширенную мат-рицу и применим алгоритм полного исключения:

Покажем, что

ответ

Исследование совместности и определённости системы. Теорема Кронекера-Капелли

Рассмотрим систему (6.1.1) m линейных уравнений с n неизвестными при любых m и n (случай m=n не исключается). Вопрос о совместности системы решается следующим критерием.

Теорема 6.2.1. (критерий Кронкера-Капелли). Для того, чтобы система линейных уравнений(6.1.1) была совместна, необходимо и достаточно, чтобы ранг матрицы А системы был равен рангу расширенной матрицы .

Доказательство и Необходимость:

Предположим, что система (6.1.1) совместна и — какое-либо её решение (возможно единственное). По определению решения системы получаем:

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

.

Достаточность. Пусть . Рассмотрим r базисных

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

где — коэффициенты линейных комбинаций. А это означает, что — решение системы (6.1.1), следовательно,

эта система совместна.

Совместная система линейных уравнений (6.1.1) может быть либо определенной, либо неопределенной.

Следующая теорема даст критерий определенности.

Теорема 6.2.2. Совместная система линейных уравнений имеет единственное решение тогда и только тогда, когда ранг матрицы А системы равен числу п ее неизвестных.

Таким образом, если число уравнений m системы (6.1.1) меньше числа ее неизвестных n и система совместна, то ранг матрицы системы . Значит система неопределенная.

В случае по теореме 6.2.2 получаем, что система имеет единственное решение. Так как , то определитель и квадратная матрица А имеет обратную x матрицу и её решение можно найти по формуле: , где Х- столбец неизвестных, F— столбец свободных членов, или по формулам Крамера.

Следует отметить, что, решая систему (6.1.1) методом Гаусса, мы определяем и совместность, и определённость системы.

Пример:

Исследовать на совместность и определённость следующую систему линейных уравнений:

Решение:

Составим расширенную матрицу заданной системы. Определяя её ранг, находим тем самым и ранг матрицы системы. Для нахождения ранга матрицы применим алгоритм метода Гаусса.

Из последней матрицы следует, что ранг расширенной матрицы не может быть больше ранга матрицы А системы. Так как

, то заданная система совместная и неопределённая.

Однородные системы линейных уравнений

Система линейных уравнений (6.1.1) называется однородной, если все свободные члены равны нулю, то есть система имеет следующий вид:

Эта система всегда совместна, так как очевидно, что она имеет нулевое решение

Для однородной системы важно установить, имеет ли она ненулевые решения. Этот факт устанавливается следующей теоремой.

Теорема 6.3.1. Для того, чтобы однородная система имела ненулевые решения, необходимо и достаточно, чтобы ранг г матрицы А системы был меньше числа неизвестных n (rn).

Доказательство. Необходимость. Пусть система (6.3.1) имеет ненулевое решение. Тогда она неопределённая, т.к. имеет еще и нулевое решение. В силу теоремы 6.2.2 ранг матрицы неопределённой системы не может равняться n потому что при r(А)=n система определённая. Следовательно, и так как он не может быль больше n то .

Достаточность. Если , то в силу теоремы 6.2.2 система (6.3.1) имеет бесчисленное множество решений. А так как только одно решение является нулевым, то все остальные решения ненулевые.

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

Доказательство. Действительно, ранг матрицы системы (6.3.1) не может превышать m. Но так как по условию, то и . Следовательно, в силу теоремы 6.3.1 система имеет ненулевые решения.

Следствие 2. Для того, чтобы однородная система с квадрат-ной матрицей имела ненулевые решения, необходимо и достаточно, чтобы её определитель равнялся нулю.

Доказательство. Рассмотрим однородную систему с квадратной матрицей:

(6.3.2)

Если определитель матрицы системы , то ранг матрицы , тогда в силу теоремы 6.3.1 система (6.3.2) имеет ненулевое решение, так как условие является необходимым и достаточным условием для существования ненулевого решения. Заметим, что если определитель матрицы системы (6.3.2) не равен нулю, то в силу теоремы 6.3.1 она имеет только нулевое решение.

Пример:

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

Решение:

Составим матицу системы и применим алгоритм полного исключения:

Из последней матрицы следует, что и система имеет бесчисленное множество решений.

Используя последнюю матрицу, последовательно находим общее решение:

Неизвестные — базисные, — свободная неизвестная, .

Фундаментальная система решений. Общее решение неоднородной системы линейных уравнений

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

(6.4.1)

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

1) сумма двух решений также является решением системы, т.е.

если — решения системы

(6.4.1), то и — решение системы (6.4.1);

2) произведение решенийна любое число есть решение системы, т.е. — решение системы.

Из приведенных свойств следует, что

3) линейная комбинация решений системы (6.4.1) является решением этой системы.

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

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

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

Теорема 6.4.1. Если ранг матрицы однородной системы уравнений (6.4.1) меньше числа неизвестных (r(А)n), то система (6.4.1) имеет бесконечное множество фундаментальных систем решений, причём каждая из них состоит из n-r решений и любые n-r линейно независимые решения составляют фундаментальную систему.

Сформулируем алгоритм построения фундаментальной системы решений:

Меняя произвольно определитель , можно получать всевозможные фундаментальные системы решений.

Пример:

Найти общее решение и фундаментальную систему решений для однородной системы уравнений:

Решение:

Составим матрицу системы и применим алгоритм полного исключения.

Для последней матрицы составляем систему:

,

, из которой находим общее решение:

в котором — базисные неизвестные, а — свободные неизвестные.

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

Если ранг матрицы системы однородных линейных уравнений (6.4.1) на единицу меньше числа неизвестных: то , и значит, фундаментальная система состоит из одного решения. Следовательно, любое ненулевое решение образует фундаментальную систему. В этом случае любые два решения различаются между собой лишь числовыми множителями.

Рассмотрим теперь неоднородную систему m линейных уравнений с n неизвестными (6.1.1). Если в системе (6.1.1) положить , то полученная однородная система называется приведенной для системы (6.1.1).

Решения системы (6.1.1) и её приведенной системы удовлетворяют свойствам:

Из этих свойств следует теорема.

Теорема 6.4.2. Общее решение неоднородной системы (6.1.1.) определяется суммой любого частного решения этой системы и общего решения её приведенной системы.

Пример:

Найти общее решение системы:

Решение:

Составим расширенную матрицу (A|F) заданной системы и применим алгоритм полного исключения:

,

Преобразованной матрице соответствует система уравнений:

из которой находим общее решение системы:

, где — базисные неизвестные, а — свободные неизвестные.

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

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

Очевидно, что общее решение приведенной системы имеет вид:

Суммируя частное решение заданной системы и общее решение приведенной системы, получим общее решение (6.4.2) исходной системы.

Отметим, что общее решение системы (6.1.1) можно представить в векторном виде:

где — • некоторое решение (вектор-строка) системы (6.1.1);

— фундаментальная система решений системы (6.4.1);

— любые действительные числа.

Формула (6.4.4) называется общим решением системы (6.1.1) в векторной форме.

Запишем общее решение системы примера 6.4.1 в векторной форме. Для этого определим фундаментальную систему решений приведенной системы. Возьмём определитель и придадим поочерёдно свободным неизвестным значения, равные элементам строк. Пусть тогда из общего решения (6.4.3) приведенной системы находим ; если же , то . Следовательно, фундаментальную систему решений образуют решения: и . Тогда общее решение заданной системы в векторной форме имеет вид: , где — частное решение заданной системы; .

Определение метода Гаусса

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

Пример:

Решить систему уравнений методом Гаусса:

Решение:

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

а) из ее второй и третьей строк вычтем первую, умноженную соответственно на 3 и 2:

б) третью строку умножим на (-5) и прибавим к ней вторую:

В результате всех этих преобразований данная система приводится к треугольному виду:

Из последнего уравнения находим Подставляя это значение во второе уравнение, имеем Далее из первого уравнения получим

Вычисление метода Гаусса

Этот метод основан на следующей теореме.

Теорема:

Элементарные преобразования не изменяют ранга матрицы.

К элементарным преобразованиям матрицы относят:

Путем элементарных преобразований исходную матрицу можно привести к трапециевидной форме

где все диагональные элементы отличны от нуля. Тогда ранг полученной матрицы равен рангу исходной матрицы и равен k.

Пример:

Найти ранг матрицы

1) методом окаймляющих миноров;

Указать один из базисных миноров.

Решение:

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

Существуют два минора третьего порядка, окаймляющих минор

Т.к. миноры третьего порядка равны нулю, ранг матрицы равен двум. Базисным минором является, например, минор

2. Найдем ранг матрицы методом Гаусса. Производя последовательно элементарные преобразования, получим:

Последняя матрица имеет трапециевидную форму и ее ранг равен двум. Следовательно, ранг исходной матрицы также равен двум.

При копировании любых материалов с сайта evkova.org обязательна активная ссылка на сайт www.evkova.org

Сайт создан коллективом преподавателей на некоммерческой основе для дополнительного образования молодежи

Сайт пишется, поддерживается и управляется коллективом преподавателей

Whatsapp и логотип whatsapp являются товарными знаками корпорации WhatsApp LLC.

Cайт носит информационный характер и ни при каких условиях не является публичной офертой, которая определяется положениями статьи 437 Гражданского кодекса РФ. Анна Евкова не оказывает никаких услуг.

Источник