Симплекс-метод. Метод Жордана-Гаусса

Пусть имеем систему линейных уравнений.

Метод Жордана-Гаусса заключается в приведении системы (1) к виду. Суть преобразования состоит в следующем:в первом уравнении системы (1) выбирается ненулевой коэффициент при какой-либо переменной , далее это уравнение будем умножать на коэффициент , где и складываем преобразованное (1) равенство с равенством под номером N. Таким образом, переменная останется только в 1 равенстве, а во всех остальных коэффициент при этой переменной будет равен 0.

Повторяя те же действия для всех остальных строчек системы (1), получим что: 1) либо система несовместна (когда все коэффициенты очередного уравнения =0, а свободный член ) 2) выявляются и отбрасываются уравнения, в которых все коэффициенты =0 и свободный член =0. (в этом случае уменьшается ранг матрицы).

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

-базисная переменная

В результате получаем следующую систему уравнений:

(2)

- это список базисных переменных.

-множество небазисных переменных.

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

Задавая небазисным переменным произвольные значения, будем получать по (3) различные значения базиса.

Одним из таких решений будет вектор с координатами

При и 0 при

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

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

Применим метод Гаусса к системе (5) переменная войдет в состав базисных переменных.

можно представить как

Подставим в равенство выражение (3) для базисных переменных.

(6)

Для вектора равенство (6) будет иметь вид:

Далее обозначим как и тогда для системы линейных уравнений и целевой функции приведенная система будет иметь вид: