Вычисляют главный определитель системы:
Вычисляют все дополнительные определители системы:
Если главный определитель системы не равен нулю, то выполняют пункт 5. Иначе рассматривают вопрос о разрешимости данной системы (имеет бесчисленное множество решений или не имеет решений).Находят значения всех неизвестных по формулам Крамера для решения системы n линейных уравнений с n неизвестными, которые имеют вид: Пример 1Решить по методу Крамера систему из трех уравнений с тремя неизвестными:
Решение
Запишем главный и побочные определители системы:
Вычислим эти определители:Δ = 3*4*(-4)+7*(-3)*5+(-2)*(-8)*5−5*4*5−3*(-3)*(-8)-7*(-2)*(-4) = 48−105+80−100−72−56 = 128−333 = -205.Δ1 = -112+(-45)+(-192)-(-240)-24−168 = -112−45−192+240−24−168 = 240−541 = -301.Δ2 = -36−420−280−75+196−288 = 196−1099 = -903.Δ3 = -144−147−30−140+27−168 = -629+27 = -602.Главный определитель системы не равен нулю. Находим неизвестные по формулам Крамера. Подставим найденные значения определителей в формулы Крамера: x1 = Δ1/Δ = -301/(-205) = 1,468 292 682 927 ≈ 1,47;x2 = Δ2/Δ = -903/(-205) = 4,40 487 804 878 ≈ 4,4;x3 = Δ3/Δ = -602/(-205) = 2,936 585 365 854 ≈ 2,93.Вывод.При решении систем линейных уравнений по методу Крамера используются формулы, в которых участвуют как главный, так и дополнительные определители системы:
Напомним, что главным определителем системы называется определитель главной матрицы системы, составленной из коэффициентов при неизвестных:
Если в главном определителе системы заменить поочередно столбцы коэффициентов при x1, x2,…xn на столбец свободных членов, то получим n дополнительных определителей (для каждого из n неизвестных):При этом важен вопрос о разрешимости данной системы, который решается сравнением главного и дополнительных определителей системы с нулем:
2.2. 3Метод Гаусса — прямой и обратный ход. Рассмотрим метод Гаусса. Например, пусть дана расширенная матрица некоторой системы m линейных уравнений c n неизвестными:
Будем считать, что a11 ≠ 0 (если это не так, то достаточно переставить первую и некоторую другую строку расширенной матрицы местами). Проведем следующие элементарные преобразования: C2-(a21/a11)*C1,…Cm-(am1/a11)*C1,т.е. Ci-(ai1/a11)*C1, i = 2, 3, …, m.Т. е. от каждой строки расширенной матрицы (кроме первой) отнимаем первую строку, умноженную на частное от деления первого элемента этой строки на диагональный элемент а11. В результате получим матрицу:
Т. е. первая строка осталась без изменений, а в столбце под, а 11 на всех местах оказались нули. Обратим внимание, что преобразования коснулись всех элементов строк, начиная со второй, всей расширенной матрицы системы. Теперь наша задача состоит в том, чтобы получить нули подо всеми диагональными элементами матрицы, А — aij, где I = j. Повторим наши элементарные преобразования, но уже для элемента α22. C 1-(a12/α22)*C2,…Cm-(αm2/α22)*C2,т.е. Ci-(αi2/α22)*C2, i = 3, …, m.Т. е. от каждой строки расширенной матрицы (теперь кроме первой и второй) отнимаем вторую строку, умноженную на частное от деления первого элемента этой (текущей) строки на диагональный элемент α 22. Такие преобразования продолжаются до тех пор, пока матрица не приведется к верхнее — треугольному виду.
Т. е. под главной диагональю не окажутся все нули:
Вспомнив, что каждая строка представляет собой одно из уравнений линейной системы уравнений, легко заметить, что последнее m-ое уравнение принимает вид:γmn*xn = δm.Отсюда легко можно найти значение первого корня — xn = δm/γmn.Подставив это значение в предыдущее m-1-е уравнение, легко получим значение xn-1-ого корня. Таким образом, поднимаясь до самого верха обратным ходом метода Гаусса, мы последовательно найдем все корни системы уравнений. Пример 1Рассмотрим систему уравнений:
Главный определитель данной системы:Δ = [1*(-4)*(-2)+2*2*1+(-1)*(-1)*(-1)]-[1*(-4)*(-1)+2*(-1)*(-2)+2*(-1)*1] = [8+4−1]-[4+4−2] = 11−6 =5,т. е. Δ ≠ 0.Т. е. система определена и разрешима. Решим ее по методу Гаусса. Проведем прямой ход метода Гаусса, выписав предварительно расширенную матрицу системы:
Получим нули под главной диагональю в первом столбце расширенной матрицы. Для получения нуля в элементе a21 (т. е. под диагональю во второй строке матрицы) вторую строку матрицы преобразуем по формуле C 2-(a21/a11)*C1 = C2-(2/1)*C1 = C2−2*C1:Аналогично поступаем и с элементом а31 (т. е. под диагональю в третьей строке матрицы). Третью строку матрицы преобразуем по формуле C3-(a31/a11)*C1 = C3-(-1/1)*C1 = C3+C1:Таким образом, мы получили нули под главной диагональю в первом столбце расширенной матрицы.
Осталось получить нуль под главной диагональю во втором столбце матрицы, т. е. на месте элемента, а 32. Для этого третью строку матрицы преобразуем по формуле C3-(a32/a22)*C2 = C3-(1/-2)*C2 = C3+½C2:Таким образом, проведя прямой ход метода Гаусса, мы получили расширенную матрицу системы, приведенную к верхне-треугольному виду:
Эта матрица эквивалентна системе:
Обратным ходом метода Гаусса найдем корни системы. Из последнего уравнения найдем корень х3:-5/2×3 = 3/2,x3 = (3/2):(-5/2) = 3/2*(-2/5) = -3/5.Корень x3 = -3/5 найден. Подставим его в верхнее (второе) уравнение системы (-2×2−3×3 = 1):-2×2−3(-3/5) = 1,-2×2+9/5 = 1,-2×2 = 1−9/5,-2×2 = -4/5,x2 = (-4/5):(-2) = (-4/5)*(-½) = 2/5.Корень x2 = 2/5 найден. Подставим его и корень х3 в верхнее (первое) уравнение системы (x1-x2+x3 = 0):x1−2/5+(-3/5) = 0, x1−5/5 = 0, x1 = 5/5 = 1. Проверка:
т. е.т. е. и т. д.Вывод.Итак, метод Гаусса (или, иначе, метод последовательного исключения неизвестных) состоит в следующем:
Путем элементарных преобразований систему уравнений приводят к эквивалентной ей системе с верхне-треугольной матрицей. Эти действия называют прямым ходом. Из полученной треугольной системы переменные находят с помощью последовательных подстановок (обратный ход).При этом все преобразования проводятся над так называемой расширенной матрицей системы, которую и приводят к верхнее — треугольному виду в прямом ходе метода.
2.2. 4 Метод Гаусса — Жордана
Метод Гаусса — Жордана используется для решения квадратных систем линейных алгебраических уравнений, нахождения обратной матрицы, нахождения координат вектора в заданном базисе, отыскания ранга матрицы. Метод является модификацией метода Гаусса. Назван в честь К. Ф. Гаусса и немецкого геодезиста и математика Вильгельма Йордана. Алгоритм:
Выбирают первую колонку слева, в которой есть хоть одно отличное от нуля значение. Если самое верхнее число в этой колонке есть нуль, то меняют всю первую строку матрицы с другой строкой матрицы, где в этой колонке нет нуля. Все элементы первой строки делят на верхний элемент выбранной колонки. Из оставшихся строк вычитают первую строку, умноженную на первый элемент соответствующей строки, с целью получить первым элементом каждой строки (кроме первой) нуль. Далее проводят такую же процедуру с матрицей, получающейся из исходной матрицы после вычёркивания первой строки и первого столбца. После повторения этой процедуры n − 1 раз получают верхнюю треугольную матрицу
Вычитаем из предпоследней строки последнюю строку, умноженную на соответствующий коэффициент, с тем, чтобы в предпоследней строке осталась только 1 на главной диагонали. Повторяют предыдущий шаг для последующих строк. В итоге получают единичную матрицу и решение на месте свободного вектора (с ним необходимо проводить все те же преобразования).Чтобы получить обратную матрицу, нужно применить все операции в том же порядке к единичной матрице.
2.2. 5Геометрическая интерпретация задач линейного программирования
Пусть на плоскости x10×2задана совместная система неравенств, где Геометрически каждое неравенство определяет полуплоскость с граничной линией: ai1x1+ ai2x2=bi, i= 1,2,…, m. Условия не отрицательности переменных величин определяют полуплоскости с граничными линиями x1 = 0, x2 = 0. Так как система неравенств по условию задачи совместна, то полуплоскости, пересекаясь, дадут некоторую общую часть, состоящую из точек, координаты которых удовлетворяют всем неравенствам системы. Эта общая часть называется областью допустимых решений или многоугольником решений. В частных случаях это может быть точка, отрезок прямой ой, луч, треуольник, многоугольник и неограниченная многоугольная область. Если в системе ограничений n = 3, то имеет место трехмерное пространство, и кроме рассматриваемых случаев область допустимых решений может быть частью плоскости, многогранником и неограниченной многогранной областью. В общем случае имеет место n — мерное пространство и многогранник решений. Таким образом, геометрически решение задачи линейного программирования заключается в нахождении такой точки многогранника решений, координаты которой доставляют целевой функции экстремальное значение.
Список литературы
Архипова З.В., Пархомов В. А. Информационные технологии в экономике: Учеб. пособие. — Иркутск: Изд-во БГУЭП, 2003 — 184 с. Буторин В., Ткаченко А., Шипилов С. Прикладной системный анализ: концептуальный подход. «КузбасевузиздатАСТШ». Кемерово — Москва, 2006
Вагнер Г. Основы исследования операций. Т.1−2 / Г. Вагнер — М.: Мир, 1971.
— 335 с. Вентцель Е. С. Исследование операций / Е. С. Вентцель — М.: Советское радио, 1972. — 552 с. Гиляревский Р. Основы информатики. Курс лекций. М., «Экзамен», 2004
Информатика /под ред. Проф. Н. В. Макаровой. — М.: Финансы и статистика, 1997.
— 768 с.: ил.Информатика. Базовый курс/Симонович С.В. и др. — Спб.: издательство «Питер», 2000.
— 640 с.: ил. Исследование операций в экономике / Под ред. Н. Ш. Кремера М.:Юнити, 1997. — 407 с. Кузнецов А. В., Сакович В. А., Холод Н. И. Высшая математика. Математическое программирование. Минск: Высш. шк,
1994.- 286 с. Кузнецов Ю. Н. Математическое программирование / Ю. Н. Кузнецов, В. И. Кузубов, А. Б. Волощенко — М.: Высшая школа, 1986. — 352 с. Материалы сайта
http://ruseti.ru/evm/Островский В. А. Информатика: учеб. для вузов. М.: Высшая школа, 2000. —511 с.: ил. Прикладная информатика, статьи по информатике, имена в Интернете. — [Режим доступа] ;
http://priinfo.net/publ/9−1-0−4.Прикладная информатика, статьи по информатике, электронная почта. — [Режим доступа] ;
http://priinfo.net/publ/9−1-0−9.
