Тема 3. Линейное программирование

Решение систем методом Жордана–Гаусса

Задание 1. Решить систему линейных уравнений методом Жордана–Гаусса.

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

,

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

Все расчеты по методу Жордана–Гаусса будем проводить в таблице.

Алгоритм метода Жордана–Гаусса

1. В таблице записываем свободные члены, матрицу коэффициентов

при неизвестных. Дополняем таблицу контрольным столбцом, элементы

которого получены суммированием элементов строки, т.е. .

			…		…		…
			…		…		…
			…		…		…
…	…	…	…	…	…	…	…	…	…
			…		…		…
…	…	…	…	…	…	…	…	…	…
			…		…		…
…	…	…	…	…	…	…	…	…	…
			…		…		…

2. Во внутренней части таблицы выбираем отличный от нуля

разрешающий элемент, например .

3. Все элементы разрешающей строки (с номером p) делим на .

4. Остальные элементы разрешающего столбца (с номером )

заменяем нулями.

5. Все остальные элементы, включая и элементы контрольного

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

новые элементы контрольного столбца должны быть равны сумме всех элементов строки.

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

Замечание

1. Для удобства вычислений обычно выбирают .

2. Если в процессе решения какая-нибудь строка полностью

обнулится, то её вычеркиваем.

3. Если в процессе решения получим строку, у которой все

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

4. Если в разрешающей строке какой-либо элемент равен нулю,

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

5. Если в разрешающем столбце какой-либо элемент равен нулю,

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

Переменные, которым соответствуют единичные векторы, называют базисными.

Переменные, которые не входят в базис, называют свободными.

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

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

Теорема

1. Если число базисных переменных равно общему числу переменных системы, то система имеет единственное решение.

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

Пример. Решить систему методом Жордана–Гаусса

Решение.

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

базис       -1 1     -2               -2         -1       -6 -1     -3   -1 -1 -1   -3 -10       -2     -4           -5     -3       -2           -1

Записываем полученные данные в таблицу. Осуществляем контроль:

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

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

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

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

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

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

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

Поскольку все строки побывали разрешающими и система приведена к единичному базису, то выписываем ответ:

Ответ: .

Что делает отдел по эксплуатации и сопровождению ИС? Отвечает за сохранность данных (расписания копирования, копирование и пр.)...

ЧТО ПРОИСХОДИТ, КОГДА МЫ ССОРИМСЯ Не понимая различий, существующих между мужчинами и женщинами, очень легко довести дело до ссоры...

Система охраняемых территорий в США Изучение особо охраняемых природных территорий(ООПТ) США представляет особый интерес по многим причинам...

Что будет с Землей, если ось ее сместится на 6666 км? Что будет с Землей? - задался я вопросом...

Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте: