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

 

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

Некоторые сделали бы так.

Заметим, что прибавив к левой части второго уравнения левую часть первого, а к правой части - правую, можно избавиться от неизвестных переменных x₂ и x₃ и сразу найти x₁:

Подставляем найденное значение x₁=1 в первое и третье уравнение системы:

Если умножить обе части третьего уравнения системы на -1 и прибавить их к соответствующим частям первого уравнения, то мы избавимся от неизвестной переменной x₃ и сможем найти x₂:

Подставляем полученное значение x₂=2 в третье уравнение и находим оставшуюся неизвестную переменную x₃:

Другие поступили бы иначе.

Разрешим первое уравнение системы относительно неизвестной переменной x₁ и подставим полученное выражение во второе и третье уравнение системы, чтобы исключить из них эту переменную:

Теперь разрешим второе уравнение системы относительно x₂ и подставим полученный результат в третье уравнение, чтобы исключить из него неизвестную переменную x₂:

Из третьего уравнения системы видно, что x₃=3. Из второго уравнения находим , а из первого уравнения получаем .

Знакомые способы решения, не правда ли?

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

Следует заметить, что когда мы выражаем x₁ через x₂ и x₃ в первом уравнении, а затем подставляем полученное выражение во второе и третье уравнения, то к такому же результату приводят следующие действия:

· к левой и правой частям второго уравнения прибавляем соответствующие части первого уравнения, умноженные на ,

· к левой и правой частям третьего уравнения прибавляем соответствующие части первого уравнения, умноженные на .

Действительно, такая процедура также позволяет исключить неизвестную переменную x₁ из второго и третьего уравнений системы:

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

Например, в СЛАУ в первом уравнении отсутствует неизвестная переменная x₁ (иными словами, коэффициент перед ней равен нулю). Поэтому мы не можем разрешить первое уравнение системы относительно x₁, чтобы исключить эту неизвестную переменную из остальных уравнений. Выходом из этой ситуации является перестановка местами уравнений системы. Так как мы рассматриваем системы линейных уравнений, определители основных матриц которых отличны от нуля, то всегда существует уравнение, в котором присутствует нужная нам переменная, и мы это уравнение можем переставить на нужную нам позицию. Для нашего примера достаточно поменять местами первое и второе уравнения системы , дальше можно разрешить первое уравнение относительно x₁ и исключить ее из остальных уравнений системы (хотя во втором уравнении x₁ уже отсутствует).

Надеемся, что суть Вы уловили.

Опишем алгоритм метода Гаусса.

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

Будем считать, что , так как мы всегда можем этого добиться перестановкой местами уравнений системы. Исключим неизвестную переменную x₁ из всех уравнений системы, начиная со второго. Для этого ко второму уравнению системы прибавим первое, умноженное на , к третьему уравнению прибавим первое, умноженное на , и так далее, к n-ому уравнению прибавим первое, умноженное на . Система уравнений после таких преобразований примет вид

где , а .

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

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

Будем считать, что (в противном случае мы переставим местами вторую строку с k-ой, где ). Приступаем к исключению неизвестной переменной x₂ из всех уравнений, начиная с третьего.

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

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

Далее приступаем к исключению неизвестной x₃, при этом действуем аналогично с отмеченной на рисунке частью системы

Так продолжаем прямой ход метода Гаусса пока система не примет вид

С этого момента начинаем обратный ход метода Гаусса: вычисляем x_n из последнего уравнения как , с помощью полученного значения x_n находим x_n-1 из предпоследнего уравнения, и так далее, находим x₁ из первого уравнения.

ГЛАВА 3.ПРИМЕРЫ РЕШЕНИЯ

Предприятие производит 3 вида продукции: А1, А2, А3, используя сырьё двух типов. Известны затраты сырья каждого типа на единицу продукции, запасы сырья на планируемый период, а также прибыль от единицы продукции каждого вида.

Таблица 3.5.

Сырье	Затраты сырья на единицу продукции	Запас сырья
А1	А2	А3
I	3,5		4,2
II
Прибыль от ед.прод.

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

Составим математическую модель задачи. Пусть x1, х2, х3 соответственно – количество единиц продукции А1, А2, А3, которую производит предприятие. По смыслу задачи эти переменные неотрицательны.

Тогда f(x1, x2, x3) = x1 + 3 x2 + 3 x3 – совокупная прибыль от продажи произведенной продукции, которую требуется максимизировать.

Подсчитаем затраты сырья:

Сырье 1-го типа: 3,5 х1 + 7 х2 + 4,2 х3, по условию затраты не превосходят 1400,

Сырье 2-го типа: 4 х1 + 5 х2 + 8 х3, по условию затраты не превосходят 2000.

Пришли к задаче линейного программирования:

f(x1, x2, x3) = x1 + 3 x2 + 3 x3 → max,

3,5 х1 + 7 х2 + 4,2 х3 ≤ 1400,

4 х1 + 5 х2 + 8 х3 ≤ 2000,

x1 ≥ 0, x2 ≥ 0, x3 ≥ 0.

Преобразуем первое ограничение:

3,5 х1 + 7 х2 + 4,2 х3 ≤ 1400, (поделим на 7)

0,5 х1 + 1 х2 + 0,6 х3 ≤ 200, (умножим на 10)

5 х1 + 10 х2 + 6 х3 ≤ 2000.

Получили задачу:

f(x1, x2, x3) = x1 + 3 x2 + 3 x3 → max,

5 х1 + 10 х2 + 6 х3 ≤ 2000,

4 х1 + 5 х2 + 8 х3 ≤ 2000,

x1 ≥ 0, x2 ≥ 0, x3 ≥ 0.

Решим данную задачу симплекс-методом. Введем дополнительные переменные х4, х5 для приведения задачи к каноническому виду:

f(x1, x2, x3) = x1 + 3 x2 + 3 x3 → max,

5 х1 + 10 х2 + 6 х3 + х4 = 2000,

4 х1 + 5 х2 + 8 х3 + х5 = 2000,

x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0, x5 ≥ 0.

В качестве опорного плана выберем Х=(0, 0, 0, 2000, 2000). Составим симплекс-таблицу:

Таблица 3.6.

Базис	План	х1	х2	х3	х4	х5	δ ij
х4
х5
f		-1	-3	-3

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

Таблица 3.7.

Базис	План	х1	х2	х3	х4	х5	δ ij
х2		1/2		3/5	1/10		1000/3
х5		3/2			-1/2		1000/5
f		1/2		-6/5	3/10

Таблица 3.8.

Базис	План	х1	х2	х3	х4	х5	δ ij
х4		8/25			4/25	-3/25
х3		3/10			-1/10	1/5
f		43/50			9/50	6/25

В последнем плане строка f не содержит отрицательных значений, план x1 = 0, x2 = 80, x3 = 200оптимален, целевая функция принимает максимальное значение 840(совокупная прибыль).

Дадим экономическую интерпретацию оптимального плана. Согласно этому плану необходимо произвести 0 единиц продукции типа А1, 80 единиц продукции типа А2, 200 единиц продукции типа А3.

В строке f оптимального плана в столбцах дополнительных переменных y*=(9/50, 6/25).

Двойственные оценки определяют дефицитность сырья. Так как y1*=9/50>0, y2*=6/25>0, то, согласно второй теореме двойственности сырье и 1го, и 2го типов полностью используется в оптимальном плане и является дефицитным сырьем.

Кроме того, значения двойственных оценок показывают, насколько возрастает доход предприятия при увеличении дефицитного сырья на единицу (соответственно, на 9/50 и на 6/25).

 

Заключение

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

Если в процессе прямого хода метода Гаусса одно или несколько уравнений принимают вид , где - некоторое число, отличное от нуля, то система несовместна.

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

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

 

 

Литература

1. Кремер Н.Ш.; Путко Б.А.; Тришин И.М., "Математика для экономистов: от Арифметики до Эконометрики", Москва, 2007.

2. Применение факторного анализа при исследовании экономических процессов. Невидомская И.А., Якубова А.М. // Современные наукоемкие технологии. 2013. № 6.

3. Матричный метод линеаризации уравнений движения управляемого объекта. /Литвин Д.Б., Гулай Т.А., Долгополова А.Ф., Виселов Г.И.// Информационные системы и технологии как фактор развития экономики региона.,2013.

4. В.С. Решение задач интернетмаркетинга матричным методом экспертного оценивания // Экономика и управление, 2008, № 3.

5. Солодовников А.С., Бабайцев В.А., Браилов А.В. Математика в экономике: Учебник: в 3 частях., 2008.

6.Басыров Р.Р., Григорьева Д.Р. «Глобальный научный потенциал». СПб., — 2014 — № 7. — С. 61—63.

7.Высшая математика для экономистов: учебник / под ред. Н.Ш. Кремера. М.: ЮНИТИ-ДАНА, 2010.

8.Козак А.В., Пилиди В.С. Линейная алгебра. М.: Вузовская книга, 2005.

9.Кремер Н.Ш.; Путко Б.А.; Тришин И.М., «Математика для экономистов: от Арифметики до Эконометрики», М., 2007.

10.Морозова О.В., Долгополова А.Ф., Долгих Е.В. Экономико-математические методы: теория и практика. Ставрополь: СтГАУ «АГРУС», 2006.

11.Сирл С., Госман У. Матричная алгебра в экономике. М.: Статистика, 1974.

12.Шевцов Г.С. Линейная алгебра: теория и прикладные аспекты. М.: Финансы и статистика, 2003.

13. http://www.cleverstudents.ru/systems/solving_systems_Gauss_method.html

14. http://fb.ru/article/268087/zadacha-s-resheniem-po-ekonomike-formulyi-po-ekonomike-dlya-resheniya-zadach

15. http://www.bestreferat.ru/referat-257733.html