Онлайн решение как найти базис - AvtoShod.ru - решение различных проблем

Инструкция. Для получения решения необходимо выбрать

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

Система линейных уравнений:
2x₁ + x₂ — x₃ + 3x₄ — 2x₅ = 2
x₁ — x₂ + x₄ = 0
x₁ — x₃ + x₄ — 2x₅ = -1
Запишем ее через матрицу.

Решение системы линейных уравнений называется базисным, если свободные переменные (m>n) обращаются в ноль.

Пример №1. Найти три базисных решения системы линейных уравнений методом Жордана-Гаусса, указать среди них опорные.
Решение. Запишем систему в виде:

Пример №2. Используя метод Жордана-Гаусса, привести систему к единичному базису. Найти одно из: а) базисных решений, б) опорных решений системы.
Запишем систему в виде:

Последовательно будем выбирать разрешающий элемент РЭ, который лежит на главной диагонали матрицы.
Разрешающий элемент равен (1).
На месте разрешающего элемента получаем 1, а в самом столбце записываем нули.
Все остальные элементы матрицы, включая элементы столбца B, определяются по правилу прямоугольника.
Для этого выбираем четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
НЭ = СЭ — (А*В)/РЭ
РЭ — разрешающий элемент (1), А и В — элементы матрицы, образующие прямоугольник с элементами СТЭ и РЭ.
Представим расчет каждого элемента в виде таблицы:

Источник

Онлайн калькулятор. Проверить образуют ли вектора базис.

Этот онлайн калькулятор позволит вам очень просто проверить образует ли заданый набор векторов базис (проверить линейную независимость векторов).

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

Калькулятор для проверки образуют ли вектора базис (проверить линейную независимость векторов)

Выберите размерность пространства

Количество координат в векторе:

Введите значение векторов:

Инструкция использования калькулятора для проверки образуют ли вектора базис (проверки линейной независимости векторов)

Для того чтобы проверить образуют ли вектора базис (проверить линейную независимость векторов) онлайн:
выберите необходимую вам размерность пространства;
введите значение векторов;
Нажмите кнопку «Проверить образуют ли вектора базис» и вы получите детальное решение задачи.

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

В онлайн калькулятор вводить можно числа или дроби. Более подробно читайте в правилах ввода чисел.

Дополнительные возможности калькулятора проверки образуют ли вектора базис (проверить линейную независимость векторов)

Между полями для ввода можно перемещаться нажимая клавиши «влево» и «вправо» на клавиатуре.

Вводить можно числа или дроби (-2.4, 5/7, . ). Более подробно читайте в правилах ввода чисел.

Векторное пространство: размерность и базис, разложение вектора по базису

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

Введем некоторые определения.

Размерность векторного пространства – число, соответствующее максимальному количеству линейно независимых векторов в этом пространстве.

Базис векторного пространства – совокупность линейно независимых векторов, упорядоченная и в своей численности равная размерности пространства.

Рассмотрим некое пространство n -векторов. Размерность его соответственно равна n . Возьмем систему из n -единичных векторов:

e ( 1 ) = ( 1 , 0 , . . . , 0 ) e ( 2 ) = ( 0 , 1 , . . . , 0 ) e ( n ) = ( 0 , 0 , . . . , 1 )

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

Так как число векторов в системе равно n , то размерность пространства n -мерных векторов равна n , а единичные векторы e ( 1 ) , e ( 2 ) , . . . , e ( n ) являются базисом указанного пространства.

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

Если мы поменяем местами первый и второй вектор, получим систему векторов e ( 2 ) , e ( 1 ) , . . . , e ( n ) . Она также будет являться базисом n -мерного векторного пространства. Составим матрицу, взяв за ее строки векторы полученной системы. Матрица может быть получена из единичной матрицы перестановкой местами первых двух строк, ранг ее будет равен n . Система e ( 2 ) , e ( 1 ) , . . . , e ( n ) линейно независима и является базисом n -мерного векторного пространства.

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

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

Векторное пространство с размерностью n имеет столько базисов, сколько существует линейно независимых систем из n -мерных векторов числом n.

Плоскость является двумерным пространством – ее базисом будут два любых неколлинеарных вектора. Базисом трехмерного пространства послужат три любых некомпланарных вектора.

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

Исходные данные: векторы

a = ( 3 , — 2 , 1 ) b = ( 2 , 1 , 2 ) c = ( 3 , — 1 , — 2 )

Необходимо определить, являются ли указанные векторы базисом трехмерного векторного пространства.

Решение

Для решения поставленной задачи исследуем заданную систему векторов на линейную зависимость. Составим матрицу, где строки – координаты векторов. Определим ранг матрицы.

A = 3 2 3 — 2 1 — 1 1 2 — 2 A = 3 — 2 1 2 1 2 3 — 1 — 2 = 3 · 1 · ( — 2 ) + ( — 2 ) · 2 · 3 + 1 · 2 · ( — 1 ) — 1 · 1 · 3 — ( — 2 ) · 2 · ( — 2 ) — 3 · 2 · ( — 1 ) = = — 25 ≠ 0 ⇒ R a n k ( A ) = 3

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

Ответ: указанные векторы являются базисом векторного пространства.

Исходные данные: векторы

a = ( 3 , — 2 , 1 ) b = ( 2 , 1 , 2 ) c = ( 3 , — 1 , — 2 ) d = ( 0 , 1 , 2 )

Необходимо определить, может ли указанная система векторов являться базисом трехмерного пространства.

Решение

Указанная в условии задачи система векторов является линейно зависимой, т.к. максимальное число линейно независимых векторов равно 3. Таким образом, указанная система векторов не может служить базисом трехмерного векторного пространства. Но стоит отметить, что подсистема исходной системы a = ( 3 , — 2 , 1 ) , b = ( 2 , 1 , 2 ) , c = ( 3 , — 1 , — 2 ) является базисом.

Ответ: указанная система векторов не является базисом.

Исходные данные: векторы

a = ( 1 , 2 , 3 , 3 ) b = ( 2 , 5 , 6 , 8 ) c = ( 1 , 3 , 2 , 4 ) d = ( 2 , 5 , 4 , 7 )

Могут ли они являться базисом четырехмерного пространства?

Решение

Cоставим матрицу, используя в качестве строк координаты заданных векторов

A = 1 2 3 3 2 5 6 8 1 3 2 4 2 5 4 7

По методу Гаусса определим ранг матрицы:

A = 1 2 3 3 2 5 6 8 1 3 2 4 2 5 4 7

1 2 3 3 0 1 0 2 0 1 — 1 1 0 1 — 2 1

1 2 3 3 0 1 0 2 0 0 — 1 — 1 0 0 — 2 — 1

1 2 3 3 0 1 0 2 0 0 — 1 — 1 0 0 0 1 ⇒ ⇒ R a n k ( A ) = 4

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

Ответ: заданные векторы являются базисом четырехмерного пространства.

Исходные данные: векторы

a ( 1 ) = ( 1 , 2 , — 1 , — 2 ) a ( 2 ) = ( 0 , 2 , 1 , — 3 ) a ( 3 ) = ( 1 , 0 , 0 , 5 )

Составляют ли они базис пространства размерностью 4?

Решение

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

Ответ: нет, не составляют.

Разложение вектора по базису

Примем, что произвольные векторы e ( 1 ) , e ( 2 ) , . . . , e ( n ) являются базисом векторного n-мерного пространства. Добавим к ним некий n -мерный вектор x → : полученная система векторов станет линейно зависимой. Свойства линейной зависимости гласят, что хотя бы один из векторов такой системы может линейно выражаться через остальные. Переформулируя это утверждение, можно говорить о том, что хотя бы один из векторов линейно зависимой системы может раскладываться по остальным векторам.

Таким образом, мы пришли к формулировке важнейшей теоремы:

Любой вектор n -мерного векторного пространства единственным образом раскладывается по базису.

Докажем эту теорему:

зададим базис n -мерного векторного пространства — e ( 1 ) , e ( 2 ) , . . . , e ( n ) . Сделаем систему линейно зависимой, добавив к ней n -мерный вектор x → . Этот вектор может быть линейно выражен через исходные векторы e :

x = x 1 · e ( 1 ) + x 2 · e ( 2 ) + . . . + x n · e ( n ) , где x 1 , x 2 , . . . , x n — некоторые числа.

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

Отнимем от левой и правой частей этого равенства соответственно левую и правую части равенства x = x 1 · e ( 1 ) + x 2 · e ( 2 ) + . . . + x n · e ( n ) . Получим:

1 — x 1 ) · e ( 1 ) + ( x

2 — x 2 ) · e ( 2 ) + . . . ( x

Система базисных векторов e ( 1 ) , e ( 2 ) , . . . , e ( n ) линейно независима; по определению линейной независимости системы векторов равенство выше возможно только тогда, когда все коэффициенты ( x

2 — x 2 ) , . . . , ( x

n — x n ) будут равны нулю. Из чего справедливым будет: x 1 = x

n . И это доказывает единственный вариант разложения вектора по базису.

При этом коэффициенты x 1 , x 2 , . . . , x n называются координатами вектора x → в базисе e ( 1 ) , e ( 2 ) , . . . , e ( n ) .

Доказанная теория делает понятным выражение «задан n -мерный вектор x = ( x 1 , x 2 , . . . , x n ) »: рассматривается вектор x → n -мерного векторного пространства, и его координаты заданы в некотором базисе. При этом также понятно, что этот же вектор в другом базисе n -мерного пространства будет иметь другие координаты.

Рассмотрим следующий пример: допустим, что в некотором базисе n -мерного векторного пространства задана система из n линейно независимых векторов

e ( 1 ) = ( e 1 ( 1 ) , e 2 ( 1 ) , . . . , e n ( 1 ) ) e ( 2 ) = ( e 1 ( 2 ) , e 2 ( 2 ) , . . . , e n ( 2 ) ) ⋮ e ( n ) = ( e 1 ( n ) , e 2 ( n ) , . . . , e n ( n ) )

а также задан вектор x = ( x 1 , x 2 , . . . , x n ) .

Векторы e 1 ( 1 ) , e 2 ( 2 ) , . . . , e n ( n ) в этом случае также являются базисом этого векторного пространства.

Предположим, что необходимо определить координаты вектора x → в базисе e 1 ( 1 ) , e 2 ( 2 ) , . . . , e n ( n ) , обозначаемые как x

Вектор x → будет представлен следующим образом:

2 · e ( 2 ) + . . . + x

Запишем это выражение в координатной форме:

( x 1 , x 2 , . . . , x n ) = x

1 · ( e ( 1 ) 1 , e ( 1 ) 2 , . . . , e ( 1 ) n ) + x

2 · ( e ( 2 ) 1 , e ( 2 ) 2 , . . . , e ( 2 ) n ) + . . . + + x

n · ( e ( n ) 1 , e ( n ) 2 , . . . , e ( n ) n ) = = ( x

2 e 1 ( 2 ) + . . . + x

2 e 2 ( 2 ) + + . . . + x

n e 2 ( n ) , . . . , x

2 e n ( 2 ) + . . . + x

Полученное равенство равносильно системе из n линейных алгебраических выражений с n неизвестными линейными переменными x

n e 2 n ⋮ x n = x

Матрица этой системы будет иметь следующий вид:

e 1 ( 1 ) e 1 ( 2 ) ⋯ e 1 ( n ) e 2 ( 1 ) e 2 ( 2 ) ⋯ e 2 ( n ) ⋮ ⋮ ⋮ ⋮ e n ( 1 ) e n ( 2 ) ⋯ e n ( n )

Пусть это будет матрица A , и ее столбцы – векторы линейно независимой системы векторов e 1 ( 1 ) , e 2 ( 2 ) , . . . , e n ( n ) . Ранг матрицы – n , и ее определитель отличен от нуля. Это свидетельствует о том, что система уравнений имеет единственное решение, определяемое любым удобным способом: к примеру, методом Крамера или матричным методом. Таким образом мы сможем определить координаты x

n вектора x → в базисе e 1 ( 1 ) , e 2 ( 2 ) , . . . , e n ( n ) .

Применим рассмотренную теорию на конкретном примере.

Исходные данные: в базисе трехмерного пространства заданы векторы

e ( 1 ) = ( 1 , — 1 , 1 ) e ( 2 ) = ( 3 , 2 , — 5 ) e ( 3 ) = ( 2 , 1 , — 3 ) x = ( 6 , 2 , — 7 )

Необходимо подтвердить факт, что система векторов e ( 1 ) , e ( 2 ) , e ( 3 ) также служит базисом заданного пространства, а также определить координаты вектора х в заданном базисе.

Решение

Система векторов e ( 1 ) , e ( 2 ) , e ( 3 ) будет являться базисом трехмерного пространства, если она линейно независима. Выясним эту возможность, определив ранг матрицы A , строки которой – заданные векторы e ( 1 ) , e ( 2 ) , e ( 3 ) .

Используем метод Гаусса:

A = 1 — 1 1 3 2 — 5 2 1 — 3

1 — 1 1 0 5 — 8 0 3 — 5

1 — 1 1 0 5 — 8 0 0 — 1 5

R a n k ( A ) = 3 . Таким образом, система векторов e ( 1 ) , e ( 2 ) , e ( 3 ) линейно независима и является базисом.

Пусть в базисе вектор x → имеет координаты x

3 . Связь этих координат определяется уравнением:

3 e 1 ( 3 ) x 2 = x

3 e 2 ( 3 ) x 3 = x

Применим значения согласно условиям задачи:

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

∆ = 1 3 2 — 1 2 1 1 — 5 — 3 = — 1 ∆ x

1 = 6 3 2 2 2 1 — 7 — 5 — 3 = — 1 , x

1 ∆ = — 1 — 1 = 1 ∆ x

2 = 1 6 2 — 1 2 1 1 — 7 — 3 = — 1 , x

2 ∆ = — 1 — 1 = 1 ∆ x

3 = 1 3 6 — 1 2 2 1 — 5 — 7 = — 1 , x

Так, вектор x → в базисе e ( 1 ) , e ( 2 ) , e ( 3 ) имеет координаты x

Ответ: x = ( 1 , 1 , 1 )

Связь между базисами

Предположим, что в некотором базисе n-мерного векторного пространства даны две линейно независимые системы векторов:

c ( 1 ) = ( c 1 ( 1 ) , c 2 ( 1 ) , . . . , c n ( 1 ) ) c ( 2 ) = ( c 1 ( 2 ) , c 2 ( 2 ) , . . . , c n ( 2 ) ) ⋮ c ( n ) = ( c 1 ( n ) , e 2 ( n ) , . . . , c n ( n ) )

e ( 1 ) = ( e 1 ( 1 ) , e 2 ( 1 ) , . . . , e n ( 1 ) ) e ( 2 ) = ( e 1 ( 2 ) , e 2 ( 2 ) , . . . , e n ( 2 ) ) ⋮ e ( n ) = ( e 1 ( n ) , e 2 ( n ) , . . . , e n ( n ) )

Указанные системы являются также базисами заданного пространства.

n ( 1 ) — координаты вектора c ( 1 ) в базисе e ( 1 ) , e ( 2 ) , . . . , e ( 3 ) , тогда связь координат будет задаваться системой линейных уравнений:

1 ( 1 ) e 1 ( 1 ) + c

2 ( 1 ) e 1 ( 2 ) + . . . + c

n ( 1 ) e 1 ( n ) с 2 ( 1 ) = c

1 ( 1 ) e 2 ( 1 ) + c

2 ( 1 ) e 2 ( 2 ) + . . . + c

n ( 1 ) e 2 ( n ) ⋮ с n ( 1 ) = c

1 ( 1 ) e n ( 1 ) + c

2 ( 1 ) e n ( 2 ) + . . . + c

В виде матрицы систему можно отобразить так:

( c 1 ( 1 ) , c 2 ( 1 ) , . . . , c n ( 1 ) ) = ( c

n ( 1 ) ) · e 1 ( 1 ) e 2 ( 1 ) … e n ( 1 ) e 1 ( 2 ) e 2 ( 2 ) … e n ( 2 ) ⋮ ⋮ ⋮ ⋮ e 1 ( n ) e 2 ( n ) … e n ( n )

Сделаем по аналогии такую же запись для вектора c ( 2 ) :

( c 1 ( 2 ) , c 2 ( 2 ) , . . . , c n ( 2 ) ) = ( c

n ( 2 ) ) · e 1 ( 1 ) e 2 ( 1 ) … e n ( 1 ) e 1 ( 2 ) e 2 ( 2 ) … e n ( 2 ) ⋮ ⋮ ⋮ ⋮ e 1 ( n ) e 2 ( n ) … e n ( n )

И, далее действуя по тому же принципу, получаем:

( c 1 ( n ) , c 2 ( n ) , . . . , c n ( n ) ) = ( c

n ( n ) ) · e 1 ( 1 ) e 2 ( 1 ) … e n ( 1 ) e 1 ( 2 ) e 2 ( 2 ) … e n ( 2 ) ⋮ ⋮ ⋮ ⋮ e 1 ( n ) e 2 ( n ) … e n ( n )

Матричные равенства объединим в одно выражение:

c 1 ( 1 ) c 2 ( 1 ) ⋯ c n ( 1 ) c 1 ( 2 ) c 2 ( 2 ) ⋯ c n ( 2 ) ⋮ ⋮ ⋮ ⋮ c 1 ( n ) c 2 ( n ) ⋯ c n ( n ) = c

n ( n ) · e 1 ( 1 ) e 2 ( 1 ) ⋯ e n ( 1 ) e 1 ( 2 ) e 2 ( 2 ) ⋯ e n ( 2 ) ⋮ ⋮ ⋮ ⋮ e 1 ( n ) e 2 ( n ) ⋯ e n ( n )

Оно и будет определять связь векторов двух различных базисов.

Используя тот же принцип, возможно выразить все векторы базиса e ( 1 ) , e ( 2 ) , . . . , e ( 3 ) через базис c ( 1 ) , c ( 2 ) , . . . , c ( n ) :

e 1 ( 1 ) e 2 ( 1 ) ⋯ e n ( 1 ) e 1 ( 2 ) e 2 ( 2 ) ⋯ e n ( 2 ) ⋮ ⋮ ⋮ ⋮ e 1 ( n ) e 2 ( n ) ⋯ e n ( n ) = e

n ( n ) · c 1 ( 1 ) c 2 ( 1 ) ⋯ c n ( 1 ) c 1 ( 2 ) c 2 ( 2 ) ⋯ c n ( 2 ) ⋮ ⋮ ⋮ ⋮ c 1 ( n ) c 2 ( n ) ⋯ c n ( n )

Дадим следующие определения:

n ( n ) является матрицей перехода от базиса e ( 1 ) , e ( 2 ) , . . . , e ( 3 )

к базису c ( 1 ) , c ( 2 ) , . . . , c ( n ) .

n ( n ) является матрицей перехода от базиса c ( 1 ) , c ( 2 ) , . . . , c ( n )

к базису e ( 1 ) , e ( 2 ) , . . . , e ( 3 ) .

Проверить образуют ли вектора базис онлайн калькулятор

Базисом в -мерном пространстве называется упорядоченная система из линейно-независимых векторов.

Введём также некоторые дополнительные понятия, необходимые для дальнейшего изложения.

, где − некоторые числа и называется линейной комбинацией векторов .

Если существуют такие числа из которых хотя бы одно не равно нулю (например ) и при этом выполняется равенство:

, то система векторов − является линейно-зависимой.

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

Базис может образовывать только линейно-независимая система векторов. Понятие линейной зависимости/независимости системы векторов, тесно связано с понятием ранга матрицы .

Наш онлайн калькулятор позволяет проверить образует ли система векторов базис. При этом калькулятор выдаёт подробное решение на русском языке.

источники:

http://zaochnik.com/spravochnik/matematika/vektory/vektornoe-prostranstvo/

http://mathforyou.net/online/vectors/basis/

Источник

Калькулятор симплекс-метода

Количество переменных:

Количество ограничений:

Очистить

Решить

В двойственную

Выполнено действий:

Как пользоваться калькулятором

Задайте количество переменных и ограничений
Введите коэффициенты целевой функции
Введите коэффициенты ограничений и выберите условия (≤, = или ≥)
Выберите тип решения
Нажмите кнопку «Решить»

Что умеет калькулятор симплекс-метода

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

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

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

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

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

Целевая функция — функция, максимум (или минимум) которой нужно найти. Представляет собой сумму произведений коэффициентов на значения переменных: F = c₁·x₁ + c₂·x₂ + … + c_n·x_n

Ограничение — условие вида a₁·x₁ + a₂·x₂ + … + a_n·x_n v b, где вместо v ставится один из знаков: ≤, = или ≥

План — произвольный набор значений переменных x₁ … x_n.

Алгоритм решения основной задачи ЛП симплекс-методом

Пусть в задаче есть m ограничений, а целевая функция заивисит от n основных переменных. Первым делом необходимо привести все ограничения к каноническому виду — виду, в котором все условия задаются равенствами. Для этого предварительно все неравенства с ≥ умножаются на -1, для получения неравенств с ≤.

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

Пример 1

Привести к каноническому виду ограничения:
2·x₁ + 3·x₂ + 6·x₃ ≤ 240
4·x₁ + 2·x₂ + 4·x₃ = 200
4·x₁ + 6·x₂ + 8·x₃ ≥ 160
Меняем знаки у ограничений с ≥, путём умножения на -1 и добавляем дополнительные переменные к ограничениям с неравенством:
2·x₁ + 3·x₂ + 6·x₃ + x₄ = 240
4·x₁ + 2·x₂ + 4·x₃ = 200
-4·x₁ — 6·x₂ — 8·x₃ + x₅ = -160

Формирование начального базиса

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

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

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

Пример 2

9·x₁ + 5·x₂ + 4·x₃ + 3·x₄ + 2·x₅ → max
x₁ — 2·x₂ + 2·x₃ ≤ 6
x₁ + 2·x₂ + x₃ + x₄ = 24
2·x₁ + x₂ — 4·x₃ + 2·x₅ = 30
Для ограничения с неравенством добавляем дополнительную переменную x₆.
Перепишем ограничения в каноническом виде:
x₁ — 2·x₂ + 2·x₃ + x₆ = 6
x₁ + 2·x₂ + x₃ + x₄ = 24
2·x₁ + x₂ — 4·x₃ + 2·x₅ = 30

Ищем начальное базисное решение:
Ограничение 1 содержит неравенство, базисной будет добавленная дополнительная переменная x₆
Столбец 4 является частью единичной матрицы. Переменная x₄ входит в начальный базис
В пятом столбце все значения кроме третьего равны нулю. Поэтому в качестве третьей базисной переменной берём x₅, предварительно разделив третью строку на 2.
Симплекс-таблица

базис	x₁	x₂	x₃	x₄	x₅	x₆	b
x₆	1	-2	2	0	0	1	6
x₄	1	2	1	1	0	0	24
?	2	1	-4	0	2	0	30

После преобразования получаем следующую таблицу:

базис	x₁	x₂	x₃	x₄	x₅	x₆	b
x₆	1	-2	2	0	0	1	6
x₄	1	2	1	1	0	0	24
x₅	1	1 2	-2	0	1	0	15

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

Пример 3

4·x₁ + 5·x₂ + 4·x₃ → max
2·x₁ + 3·x₂ + 6·x₃ ≤ 240
4·x₁ + 2·x₂ + 4·x₃ = 160
4·x₁ + 6·x₂ + 8·x₃ ≤ 200
Для каждого ограничения с неравенством добавляем дополнительные переменные x₄ и x₅.
Перепишем ограничения в каноническом виде:
2·x₁ + 3·x₂ + 6·x₃ + x₄ = 240
4·x₁ + 2·x₂ + 4·x₃ = 160
4·x₁ + 6·x₂ + 8·x₃ + x₅ = 200

Ищем начальное базисное решение:
Ограничение 1 содержит неравенство, базисной будет добавленная дополнительная переменная x₄
Ограничение 3 содержит неравенство, базисной будет добавленная дополнительная переменная x₅

Начальная симплекс-таблица

базис	x₁	x₂	x₃	x₄	x₅	b
x₄	2	3	6	1	0	240
?	4	2	4	0	0	160
x₅	4	6	8	0	1	200

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

базис	x₁	x₂	x₃	x₄	x₅	b
x₄	2	3	6	1	0	240
x₁	4	2	4	0	0	160
x₅	4	6	8	0	1	200

После исключения получаем следующую таблицу:

базис	x₁	x₂	x₃	x₄	x₅	b
x₄	0	2	4	1	0	160
x₁	1	1 2	1	0	0	40
x₅	0	4	4	0	1	40

После того как базис сформирован, нужно построить начальную симплекс-таблицу. Она строится следующим образом:

Для удобства в первой строке можно записать коэффициенты C_i целевой функции (для дополнительных переменных эти коэффициенты равны нулю)
Вторая строка формирует шапку таблицы. В ней первый столбец называется базис, а остальные перечисляют основные переменные x₁..x_n и дополнительные x_n+1..x_n+k
Затем построчно перечисляются базисные переменные и коэффициенты ограничений

Схематично начальная таблица будет выглядеть примерно так:

C	с₁	c₂	…	c_n	0	0	…	0	0
базис	x₁	x₂	…	x_n	x_n+1	x_n+2	…	x_n+k	b
x_e₁	a₁₁	a₁₂	…	a_1n	a_1n+1	a_1n+2	…	a_1n+k	b₁
x_e₂	a₂₁	a₂₂	…	a_2n	a_2n+1	a_2n+2	…	a_2n+k	b₂
…	…	…	…	…	…	…	…	…	…
x_{e_m}	a_m1	a_m2	…	a_mn	a_mn+1	a_mn+2	…	a_mn+k	b_m

Избавляемся от отрицательных свободных коэффициентов

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

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

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

Пример 4

20·x₁ + 20·x₂ + 10·x₃ → min
4·x₁ + 3·x₂ + 2·x₃ ≥ 33
3·x₁ + 2·x₂ + x₃ ≥ 23
x₁ + x₂ + 2·x₃ ≥ 12

Меняем знаки у ограничений с ≥, путём умножения на -1:
-4·x₁ — 3·x₂ — 2·x₃ ≤ -33
— 3·x₁ — 2·x₂ — x₃ ≤ -23
— x₁ — x₂ — 2·x₃ ≤ -12

Для каждого ограничения с неравенством добавляем дополнительные переменные x₄..x₆.
Перепишем ограничения в каноническом виде:
— 4·x₁ — 3·x₂ — 2·x₃ + x₄ = -33
— 3·x₁ — 2·x₂ — x₃ + x₅ = -23
— x₁ — x₂ — 2·x₃ + x₆ = -12

Ищем начальное базисное решение:
Ограничение 1 содержит неравенство, базисной будет добавленная дополнительная переменная x₄
Ограничение 2 содержит неравенство, базисной будет добавленная дополнительная переменная x₅
Ограничение 3 содержит неравенство, базисной будет добавленная дополнительная переменная x₆

Начальная симплекс-таблица

базис	x₁	x₂	x₃	x₄	x₅	x₆	b
C	20	20	10	0	0	0	0
x₄	-4	-3	-2	1	0	0	-33
x₅	-3	-2	-1	0	1	0	-23
x₆	-1	-1	-2	0	0	1	-12

В столбце b присутствуют отрицательные значения.
Максимальное по модулю |b|_max = |-33| находится в первой строке.
Максимальный по модулю элемент в первой строке = -4 находится в первом столбце.
В качестве базисной переменной x₄ берём x₁.
Делим первую строку на -4. Из второй и третьей строк вычитаем первую, умноженную на соответствующий элемент в первом столбце.

Обновлённая таблица:

базис	x₁	x₂	x₃	x₄	x₅	x₆	b
C	20	20	10	0	0	0	0
x₁	1	3 4	1 2	— 1 4	0	0	33 4
x₅	0	1 4	1 2	— 3 4	1	0	7 4
x₆	0	— 1 4	— 3 2	— 1 4	0	1	— 15 4

В столбце b присутствуют отрицательные значения.
Максимальное по модулю |b|_max = |-

| находится в третьей строке.
Максимальный по модулю элемент в третьей строке = —

находится в третьем столбце.
В качестве базисной переменной x₆ берём x₃.
Делим третью строку на —

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

Обновлённая таблица:

базис	x₁	x₂	x₃	x₄	x₅	x₆	b
C	20	20	10	0	0	0	0
x₁	1	2 3	0	— 1 3	0	1 3	7
x₅	0	1 6	0	— 5 6	1	1 3	1 2
x₃	0	1 6	1	1 6	0	— 2 3	5 2

Расчёт дельт

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

Для расчёта дельт используется следующая формула: Δ_i = c_e₁·a_1i + c_e₂·a_2i + … + c_{e_m}·a_mi — c_i. Проще говоря, чтобы вычислить дельту по заданной i-ой переменной, нужно перемножить коэффициенты условий в i-ом столбце на коэффициенты целевой функции при соответствующих базисных переменных, сложить эти произведения и вычесть из полученной суммы коэффициент целевой функции столбца i.

Пример 5

Таблица:

базис	x₁	x₂	x₃	x₄	x₅	x₆	b
C	3	0	2	0	0	-6	0
x₂	2	1	-3	0	0	6	18
x₄	-3	0	2	1	0	-2	24
x₅	1 5	0	3 5	0	1	— 4 5	36 5

Вычисляем дельты: Δ_i = C₂·a_1i + C₄·a_2i + C₅·a_3i — C_i

Симплекс-таблица с дельтами

базис	x₁	x₂	x₃	x₄	x₅	x₆	b
C	3	0	2	0	0	-6	0
x₂	2	1	-3	0	0	6	18
x₄	-3	0	2	1	0	-2	24
x₅	1 5	0	3 5	0	1	— 4 5	36 5
Δ	-3	0	-2	0	0	6	0

Проверка плана на оптимальность

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

Пример 6

9·x₁ + 5·x₂ + 4·x₃ + 3·x₄ + 2·x₅ → max
x₁ — 2·x₂ + 2·x₃ ≤ 6
x₁ + 2·x₂ + x₃ + x₄ = 24
2·x₁ + x₂ — 4·x₃ + x₅ = 30
Симплекс-таблица с дельтами

базис	x₁	x₂	x₃	x₄	x₅	x₆	b
C	9	5	4	3	2	0	0
x₆	1	-2	2	0	0	1	6
x₄	1	2	1	1	0	0	24
x₅	2	1	-4	0	1	0	30
Δ	-2	3	-9	0	0	0	132

Критерий оптимальности: план оптимален, если в таблице отсутствуют отрицательные дельты.
План не оптимален, так как ищется максимум функции, а Δ₁ = -2 отрицательна.

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

Переход к более оптимальному решению

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

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

Пример 7

Симплекс-таблица с дельтами

базис	x₁	x₂	x₃	x₄	x₅	x₆	b
C	2	1	-2	0	0	0	0
x₁	1	-5	0	-3	0	-1	25
x₅	0	-16	0	-7	1	-3	57
x₃	0	-6	1	-2	0	-1	17
Δ	0	1	0	-2	0	0	16

Проверяем план на оптимальность: план не оптимален, так как ищется минимум функции, а Δ₂ = 1 положительна.
Определяем разрешающий столбец — столбец, в котором находится максимальная дельта: 2, Δ₂: 1
Находим симплекс-отношения Q, путём деления коэффициентов b на соответствующие значения второго столбца

базис	x₁	x₂	x₃	x₄	x₅	x₆	b	Q
C	2	1	-2	0	0	0	0
x₁	1	-5	0	-3	0	-1	25	—
x₅	0	-16	0	-7	1	-3	57	—
x₃	0	-6	1	-2	0	-1	17	—
Δ	0	1	0	-2	0	0	16

Все значения второго столбца отрицательны. Функция не ограничена. Оптимальное решение отсутствует.

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

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

Пример 8

Симплекс-таблица с дельтами

базис	x₁	x₂	x₃	x₄	x₅	x₆	b
C	9	5	4	3	2	0	0
x₆	1	-2	2	0	0	1	6
x₄	1	2	1	1	0	0	24
x₅	2	1	-4	0	1	0	30
Δ	-2	3	-9	0	0	0	132

Проверяем план на оптимальность: план не оптимален, так как Δ₁ = -2 отрицательна.

Итерация 1

Определяем разрешающий столбец — столбец, в котором находится минимальная дельта: 3, Δ₃: -9
Находим симплекс-отношения Q, путём деления коэффициентов b на соответствующие значения третьего столбца
В найденном столбце ищем строку с наименьшим значением Q: Q_min = 3, строка 1.
На пересечении найденных строки и столбца находится разрешающий элемент: 2
В качестве базисной переменной x₆ берём x₃.

базис	x₁	x₂	x₃	x₄	x₅	x₆	b	Q
C	9	5	4	3	2	0	0
x₃	1	-2	2	0	0	1	6	6 / 2 = 3
x₄	1	2	1	1	0	0	24	24 / 1 = 24
x₅	2	1	-4	0	1	0	30	—
Δ	-2	3	-9	0	0	0	132

Делим первую строку на 2. Из второй и третьей строк вычитаем первую, умноженную на соответствующий элемент в третьем столбце.
Вычисляем новые дельты: Δ_i = C₃·a_1i + C₄·a_2i + C₅·a_3i — C_i

базис	x₁	x₂	x₃	x₄	x₅	x₆	b	Q
C	9	5	4	3	2	0	0
x₃	1 2	-1	1	0	0	1 2	3	3
x₄	1 2	3	0	1	0	— 1 2	21	24
x₅	4	-3	0	0	1	2	42	—
Δ	5 2	-6	0	0	0	9 2	159

Текущий план X: [ 0, 0, 3, 21, 42, 0 ]
Целевая функция F: 9·0 + 5·0 + 4·3 + 3·21 + 2·42 + 0·0 = 159
Проверяем план на оптимальность: план не оптимален, так как Δ₂ = -6 отрицательна.

Итерация 2

Определяем разрешающий столбец — столбец, в котором находится минимальная дельта: 2, Δ₂: -6
Находим симплекс-отношения Q, путём деления коэффициентов b на соответствующие значения второго столбца
В найденном столбце ищем строку с наименьшим значением Q: Q_min = 7, строка 2.
На пересечении найденных строки и столбца находится разрешающий элемент: 3
В качестве базисной переменной x₄ берём x₂.

базис	x₁	x₂	x₃	x₄	x₅	x₆	b	Q
C	9	5	4	3	2	0	0
x₃	1 2	-1	1	0	0	1 2	3	—
x₂	1 2	3	0	1	0	— 1 2	21	21 / 3 = 7
x₅	4	-3	0	0	1	2	42	—
Δ	5 2	-6	0	0	0	9 2	159

Делим вторую строку на 3. Из первой и третьей строк вычитаем вторую, умноженную на соответствующий элемент во втором столбце.
Вычисляем новые дельты: Δ_i = C₃·a_1i + C₂·a_2i + C₅·a_3i — C_i

базис	x₁	x₂	x₃	x₄	x₅	x₆	b	Q
C	9	5	4	3	2	0	0
x₃	2 3	0	1	1 3	0	1 3	10	—
x₂	1 6	1	0	1 3	0	— 1 6	7	7
x₅	9 2	0	0	1	1	3 2	63	—
Δ	7 2	0	0	2	0	7 2	201

Текущий план X: [ 0, 7, 10, 0, 63, 0 ]
Целевая функция F: 9·0 + 5·7 + 4·10 + 3·0 + 2·63 + 0·0 = 201
Проверяем план на оптимальность: отрицательные дельты отсутствуют, следовательно план оптимален.
Ответ: x₁ = 0, x₂ = 7, x₃ = 10, x₄ = 0, x₅ = 63, F = 201

Метод искусственного базиса

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

Подготовительный этап

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

Пример 9

3·x₁ + 2·x₂ + 3·x₃ → min
-2·x₁ — x₂ — x₃ ≥ -2
3·x₁ + 8·x₂ + 2·x₃ ≥ 8
2·x₁ + x₃ = 1
Меняем знаки у ограничений с отрицательными свободными коэффициентами, путём умножения на -1:
2·x₁ + x₂ + x₃ ≤ 2
3·x₁ + 8·x₂ + 2·x₃ ≥ 8
2·x₁ + x₃ = 1

Для каждого ограничения с неравенством добавляем дополнительные переменные x₄ и x₅.
Ограничение 1 содержит неравенство, базисной будет добавленная дополнительная переменная x₄
Ограничение 2 содержит неравенство с ≥. Базисная переменная для этого ограничения будет определена позднее.
Ограничение 3 содержит равенство. Базисная переменная для этого ограничения будет определена позднее.

Начальная симплекс-таблица

базис	x₁	x₂	x₃	x₄	x₅	b
C	3	2	3	0	0	0
x₄	2	1	1	1	0	2
?₁	3	8	2	0	-1	8
?₂	2	0	1	0	0	1

Формирование начального базиса

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

Пример 10

x₁ — x₂ → min
2·x₁ + x₂ = 1
x₁ — 3·x₂ + x₃ = 3
x₁ + 11·x₂ = 11
Ограничение 1 содержит равенство. Базисная переменная для этого ограничения будет определена позднее.
Столбец 3 является частью единичной матрицы. Переменная x₃ входит в начальный базис
Ограничение 3 содержит равенство. Базисная переменная для этого ограничения будет определена позднее.

Начальная симплекс-таблица

базис	x₁	x₂	x₃	b
C	1	-1	0	0
?₁	2	1	0	1
x₃	1	-3	1	3
?₃	1	11	0	11

Для ограничения 1 добавляем искусственную переменную u₁ и делаем её базисной.
Для ограничения 3 добавляем искусственную переменную u₂ и делаем её базисной.
В целевую функцию добавляем искусственные пременные с коэффициентом M, где M — очень большое число.

Таблица с искусственными переменными

базис	x₁	x₂	x₃	u₁	u₂	b
C	1	-1	0	M	M	0
u₁	2	1	0	1	0	1
x₃	1	-3	1	0	0	3
u₂	1	11	0	0	1	11

Перепишем условие задачи с учётом добавленных искусственных переменных:
F = 1x₁ -1x₂ + Mu₁ + Mu₂ → min
2·x₁ + x₂ + u₁ = 1
x₁ — 3·x₂ + x₃ = 3
x₁ + 11·x₂ + u₂ = 11

Расчёт дельт и проверка плана на оптимальность

После того, как начальный базис сформирован необходимо вычислить дельты. Дельты вычисляются полностью аналогично базовому методу: Δ_i = c_e₁·a_1i + c_e₂·a_2i + … + c_{e_m}·a_mi — c_i. Единственным отличием будет тот факт, что результат может содержать значения с M. Когда дельты будут получены необходимо проверить текущий опорный план на оптимальность (см. проверку плана на оптимальность в базовом симплекс-методе). Если план оптимален, то алгоритм завершает свою работу, иначе формирует более оптимальное решение и повторяет процесс.

Пример 11

Таблица с искусственными переменными

базис	x₁	x₂	x₃	x₄	x₅	x₆	u₁	u₂	b
C	3	2	3	0	0	0	M	M	0
x₄	2	1	1	1	0	0	0	0	2
u₁	3	0	2	0	-1	0	1	0	3
u₂	0	0	1	0	0	-1	0	1	1

Вычисляем дельты: Δ_i = C₄·a_1i + C₇·a_2i + C₈·a_3i — C_i

Δ₁ = C₄·a₁₁ + C₇·a₂₁ + C₈·a₃₁ — C₁ = 0·2 + M·3 + M·0 — 3 = -3 + 3M
Δ₂ = C₄·a₁₂ + C₇·a₂₂ + C₈·a₃₂ — C₂ = 0·1 + M·0 + M·0 — 2 = -2
Δ₃ = C₄·a₁₃ + C₇·a₂₃ + C₈·a₃₃ — C₃ = 0·1 + M·2 + M·1 — 3 = -3 + 3M
Δ₄ = C₄·a₁₄ + C₇·a₂₄ + C₈·a₃₄ — C₄ = 0·1 + M·0 + M·0 — 0 = 0
Δ₅ = C₄·a₁₅ + C₇·a₂₅ + C₈·a₃₅ — C₅ = 0·0 + M·(-1) + M·0 — 0 = -M
Δ₆ = C₄·a₁₆ + C₇·a₂₆ + C₈·a₃₆ — C₆ = 0·0 + M·0 + M·(-1) — 0 = -M
Δ₇ = C₄·a₁₇ + C₇·a₂₇ + C₈·a₃₇ — C₇ = 0·0 + M·1 + M·0 — M = 0
Δ₈ = C₄·a₁₈ + C₇·a₂₈ + C₈·a₃₈ — C₈ = 0·0 + M·0 + M·1 — M = 0
Δ_b = C₄·b₁ + C₇·b₂ + C₈·b₃ — C₉ = 0·2 + M·3 + M·1 — 0 = 4M

Симплекс-таблица с дельтами

базис	x₁	x₂	x₃	x₄	x₅	x₆	u₁	u₂	b
C	3	2	3	0	0	0	M	M	0
x₄	2	1	1	1	0	0	0	0	2
u₁	3	0	2	0	-1	0	1	0	3
u₂	0	0	1	0	0	-1	0	1	1
Δ	-3 + 3M	-2	-3 + 3M	0	-M	-M	0	0	4M

Текущий план X: [ 0, 0, 0, 2, 0, 0, 3, 1 ]
Целевая функция F: 3·0 + 2·0 + 3·0 + 0·2 + 0·0 + 0·0 + M·3 + M·1 = 4M
Проверяем план на оптимальность: план не оптимален, так как Δ₁ = -3 + 3M положительна.

Источник

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

Если Вы хотите связаться со мной, имеете вопросы, предложения или хотите помочь развивать сайт OnlineMSchool пишите мне support@onlinemschool.com

Источник

Калькулятор онлайн.
Решение систем линейных алгебраических уравнений (СЛАУ)
Метод Гаусса, матричный метод, метод Крамера, исследование на совместность (теорема Кронекера-Капелли),
определение количества решений, нахождение нормальной фундаментальной системы решений.

С помощью данной математической программы вы можете решить и исследовать систему линейных алгебраических уравнений (СЛАУ).

Программа не только даёт ответ задачи, но и приводит подробное решение с пояснениями шагов решения.

Данная программа может быть полезна учащимся старших классов общеобразовательных школ при подготовке к контрольным работам и
экзаменам, при проверке знаний перед ЕГЭ, родителям для контроля решения многих задач по математике и алгебре.
А может быть вам слишком накладно нанимать репетитора или покупать новые учебники? Или вы просто хотите как можно быстрее
сделать домашнее задание по математике или алгебре? В этом случае вы также можете воспользоваться нашими программами с подробным
решением.

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

Правила ввода чисел

Числа можно вводить целые и дробные.

Дробные числа можно вводить в 3-х различных видах:

в виде десятичных дробей,
в виде обыкновенных дробей,
в виде периодических десятичных дробей.

Ввод дробного числа в виде десятичной дроби.
При вводе десятичной дроби, целую часть от дробной части можно отделять точкой или запятой :
Ввод: -2.34
Результат: ( -2{,}34 )

Ввод: -1,15
Результат: ( -1{,}15 )

Ввод дробного числа в виде обыкновенной дроби.

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

При вводе числовой дроби числитель отделяется от знаменателя знаком деления: /
Ввод: -2/3
Результат: $$ -frac{2}{3} $$

Целая часть отделяется от дроби знаком амперсанд: &
Ввод: 5&8/3
Результат: $$ 5frac{8}{3} $$
Помните, что на ноль делить нельзя!

Ввод дробного числа в виде периодической десятичной дроби.
В периодических десятичных дробях период заключается в скобки.
Ввод: 0,(72)
Результат: $$ frac{8}{11} $$

Ввод: -2,3(4)
Результат: $$ -2frac{31}{90} $$

Наши игры, головоломки, эмуляторы:

Немного теории.

Системы линейных алгебраических уравнений

Основные определения

Система (m) линейных алгебраических уравнений с (n) неизвестными (сокращенно СЛАУ) представляет собой систему вида

( left{ begin{array}{l}
a_{11}x_1 + a_{12}x_2 + cdots + a_{1n}x_n = b_1 \
a_{21}x_1 + a_{22}x_2 + cdots + a_{2n}x_n = b_2 \
cdots \
a_{m1}x_1 + a_{m2}x_2 + cdots + a_{mn}x_n = b_m
end{array} right. tag{1} )

Уравнения системы называют алгебраическими потому, что левая часть каждого из них есть многочлен от (n) переменных
( x_1 , ldots x_n ), а линейными потому, что эти многочлены имеют первую степень.

Числа (a_{ij} in mathbb{R} ) называют коэффициентами СЛАУ. Их нумеруют двумя индексами: номером уравнения (i) и номером
неизвестного (j). Действительные числа ( b_1 , ldots b_m ) называют свободными членами уравнений.

СЛАУ называют однородной, если ( b_1 = b_2 = ldots = b_m = 0 ). Иначе её называют неоднородной.

Решением СЛАУ, да и вообще всякой системы уравнений, называют такой набор значений неизвестных ( x_1^circ, ldots , x_n^circ ),
при подстановке которых каждое уравнение системы превращается в тождество. Любое конкретное решение СЛАУ также называют её частным решением.

Решить СЛАУ — значит решить две задачи:
— выяснить, имеет ли СЛАУ решения;
— найти все решения, если они существуют.

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

Если СЛАУ (1) имеет решение, и притом единственное, то её называют определенной, а если решение неединственное — то неопределенной.
При (m=n), т.е. когда количество уравнений совпадает с количеством неизвестных, СЛАУ называют квадратной.

Формы записи СЛАУ

Кроме координатной формы (1) записи СЛАУ часто используют и другие её представления.

Рассматривая коэффициенты (a_{ij}) СЛАУ при одном неизвестном (x_j) как элементы столбца, а (x_j) как коэффициент, на который умножается
столбец, из (1) получаем новую форму записи СЛАУ:
( begin{pmatrix}
a_{11} \
a_{21} \
vdots \
a_{m1}
end{pmatrix} x_1 + begin{pmatrix}
a_{12} \
a_{22} \
vdots \
a_{m2}
end{pmatrix} x_2 + ldots + begin{pmatrix}
a_{1n} \
a_{2n} \
vdots \
a_{mn}
end{pmatrix} x_n = begin{pmatrix}
b_1 \
b_2 \
vdots \
b_m
end{pmatrix} )

или, обозначая столбцы соответственно ( a_1 , ldots , a_n , b ),
( x_1 a_1 + x_2 a_2 + ldots + x_n a_n = b tag{2} )

Таким образом, решение СЛАУ (1) можно трактовать как представление столбца (b) в виде линейной комбинации столбцов ( a_1, ldots, a_n ).
Соотношение (2) называют векторной записью СЛАУ.

Обратим внимание на то, что слева в каждом уравнении системы (1) стоит сумма попарных произведений — так же, как и в произведении двух матриц.
Если взять за основу произведение матриц, то СЛАУ (1) можно записать так :
( begin{pmatrix}
a_{11} & a_{12} & cdots & a_{1n} \
a_{21} & a_{22} & cdots & a_{2n} \
vdots & vdots & ddots & vdots \
a_{m1} & a_{m2} & cdots & a_{mn}
end{pmatrix} begin{pmatrix}
x_1 \
x_2 \
vdots \
x_n
end{pmatrix} = begin{pmatrix}
b_1 \
b_2 \
vdots \
b_m
end{pmatrix} )

или (Ax=b), где (A) — матрица размера (m times n); (x) — столбец неизвестных; (b) — столбец свободных членов:
( A = begin{pmatrix}
a_{11} & a_{12} & cdots & a_{1n} \
a_{21} & a_{22} & cdots & a_{2n} \
vdots & vdots & ddots & vdots \
a_{m1} & a_{m2} & cdots & a_{mn}
end{pmatrix} ,; )
( X = begin{pmatrix}
x_1 \
x_2 \
vdots\
x_n
end{pmatrix} ,; )
( B = begin{pmatrix}
b_1 \
b_2 \
vdots \
b_m
end{pmatrix} )

Поскольку (A ;,; X) и (B) являются матрицами, то запись СЛАУ (1) в виде (AX=B) называют матричной. Если (B=0), то СЛАУ
является однородной и в матричной записи имеет вид (AX=0).

Приведенные рассуждения показывают, что задачи :
а) решения СЛАУ (1)
б) представления столбца в виде линейной комбинации данных столбцов
в) решения матричных уравнений вида (AX=B)
являются просто различной формой записи одной и той же задачи.

Критерий совместности СЛАУ

«Триединство» форм записи СЛАУ позволяет легко получить критерий совместности СЛАУ. Напомним, что содержательный смысл это понятие имеет
для неоднородных СЛАУ (однородные СЛАУ всегда совместны).

Матрицу
( A = begin{pmatrix}
a_{11} & a_{12} & cdots & a_{1n} \
a_{21} & a_{22} & cdots & a_{2n} \
vdots & vdots & ddots & vdots \
a_{m1} & a_{m2} & cdots & a_{mn}
end{pmatrix} )
называют матрицей (коэффициентов) СЛАУ (1), а матрицу
( (A|B) = left( begin{array}{cccc|c}
a_{11} & a_{12} & cdots & a_{1n} & b_1 \
a_{21} & a_{22} & cdots & a_{2n} & b_2 \
vdots & vdots & ddots & vdots & vdots \
a_{m1} & a_{m2} & cdots & a_{mn} & b_m
end{array} right) )

расширенной матрицей СЛАУ (1). Расширенная матрица полностью характеризует СЛАУ. Это означает, что по этой матрице однозначно
(если сохранить обозначения для неизвестных) восстанавливается сама СЛАУ.

Теорема Кронекера-Капелли. Для совместности СЛАУ (AX=B) необходимо и достаточно, чтобы ранг её матрицы (A) был равен рангу
её расширенной матрицы ( (A|B) ).

Формулы Крамера

Теорема. СЛАУ с квадратной невырожденной матрицей имеет решение, и притом единственное, которое определяется по
формулам Крамера :

$$ x_i = frac{Delta_i}{|A|} ;,quad i=overline{1,n} tag{3} $$

где (Delta_i) — определитель матрицы, получающейся из матрицы (A) заменой (i)-го столбца на столбец свободных членов.

Следствие. Однородная СЛАУ с квадратной невырожденной матрицей имеет единственное решение — нулевое.

Если матрица СЛАУ не является квадратной невырожденной, то формулы Крамера не работают и приходится использовать другие методы
нахождения решений.

Однородные системы

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

Теорема. Если столбцы ( X^{(1)}, X^{(2)}, ldots , X^{(s)} ) — решения однородной СЛАУ (AX=0), то любая их линейная комбинация
также является решением этой системы.

Следствие. Если однородная СЛАУ имеет ненулевое решение, то она имеет бесконечно много решений.

Естественно попытаться найти такие решения ( X^{(1)}, ldots , X^{(s)} ) системы (AX=0), чтобы любое другое решение этой системы
представлялось в виде их линейной комбинации и притом единственным образом. Оказывается, что это всегда возможно и приводит к следующему определению.

Определение. Любой набор из (k=n-r) линейно независимых столбцов, являющихся решениями однородной СЛАУ (AX=0), где
(n) — количество неизвестных в системе, а (r) — ранг её матрицы (A), называют фундаментальной системой решений этой однородной СЛАУ.

При исследовании и решении однородных систем линейных алгебраических уравнений будем использовать следующую терминологию. Если в матрице
(A) однородной СЛАУ (AX=0) фиксировать базисный минор, то ему соответствуют базисные столбцы и, следовательно, набор неизвестных, отвечающих
этим столбцам. Указанные неизвестные называют базисными, или зависимыми, а остальные неизвестные — свободными, или
независимыми.

Теорема. Пусть дана однородная СЛАУ (AX=0) с (n) неизвестными и ( text{rang}A = r ). Тогда существует набор из (k=n-r)
решений ( X^{(1)}, ldots , X^{(k)} ) этой СЛАУ, образующих фундаментальную систему решений.

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

Следствие. С помощью нормальной фундаментальной системы решений однородной СЛАУ множество всех решений можно описать формулой :
$$ X = c_1X^{(1)} + ldots + c_kX^{(k)} $$
где постоянные ( c_i ;, quad i=overline{1,k} ), принимают произвольные значения.

Следствие. Для существования ненулевого решения у однородной квадратной СЛАУ необходимо и достаточно, чтобы её матрица была вырождена.

Неоднородные системы

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

Теорема. Пусть столбец (X^circ) — некоторое решение СЛАУ (AX=B). Произвольный столбец (X) является решением этой СЛАУ тогда и
только тогда, когда он имеет представление (X = X^circ + Y ), где (Y) — решение соответствующей однородной СЛАУ (AY=0).

Следствие. Пусть (X’) и (X») — решения неоднородной системы (AX=B). Тогда их разность ( Y = X’ — X» ) является
решением соответствующей однородной системы (AY=0).

Эта теорема сводит проблему решения СЛАУ к случаю однородной системы: чтобы описать все решения неоднородной СЛАУ, достаточно энать одно
её решение (частное решение) и все решения соответствующей однородной СЛАУ.

Чтобы решить неоднородную систему, надо, во-первых, убедиться, что она совместна (например, по теореме Кронекера-Капелли), а во-вторых,
найти частное решение (X^circ) этой системы, чтобы свести её к однородной системе.

Теорема о структуре общего решения СЛАУ. Пусть (X^circ) — частное решение СЛАУ (AX=B) и известна фундаментальная система
решений ( X^{(1)}, ldots , X^{(k)} ) соответствующей однородной системы (AX=0). Тогда любое решение СЛАУ (AX=B) можно представить в виде
$$ X = X^circ + c_1 X^{(1)} + c_2 X^{(2)} + ldots + c_k X^{(k)} $$
где ( c_i in mathbb{R} ;, quad i=overline{1,k} ).

Эту формулу называют общим решением СЛАУ.

Источник

Онлайн калькулятор. Проверить образуют ли вектора базис.

Калькулятор для проверки образуют ли вектора базис (проверить линейную независимость векторов)

Инструкция использования калькулятора для проверки образуют ли вектора базис (проверки линейной независимости векторов)

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

Дополнительные возможности калькулятора проверки образуют ли вектора базис (проверить линейную независимость векторов)

Векторное пространство: размерность и базис, разложение вектора по базису

Разложение вектора по базису

Связь между базисами

Проверить образуют ли вектора базис онлайн калькулятор

Калькулятор симплекс-метода

Как пользоваться калькулятором

Что умеет калькулятор симплекс-метода

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

Алгоритм решения основной задачи ЛП симплекс-методом

Формирование начального базиса

Избавляемся от отрицательных свободных коэффициентов

Расчёт дельт

Проверка плана на оптимальность

Переход к более оптимальному решению

Итерация 1

Итерация 2

Метод искусственного базиса

Подготовительный этап

Формирование начального базиса

Расчёт дельт и проверка плана на оптимальность

Немного теории.

Не пропустите также: