Понятие ключевого уравнения и методы его решения

Линейное программирование — основные понятия с примерами решения

Содержание:

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

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

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

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

Построение математической модели экономической задачи включает следующие этапы:

1. выбор переменных задачи;
2. составление системы ограничений;
3. выбор целевой функции.

Переменными задачи называются величины

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

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

Общая задача математического программирования формулируется следующим образом: найти экстремум целевой функции: и соответствующие ему переменные при условии, что эти переменные удовлетворяют системе ограничений:

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

Данная запись означает следующее: найти экстремум целевой функции задачи и соответствующие ему переменные X = (). при условии, что эти переменные удовлетворяют системе ограничений и условиям неотрицательности.

Допустимым решением (планом) задачи линейного программирования называется любойX = (). удовлетворяющий системе ограничений и условиям неотрицательности. Множество допустимых решений (планов) задачи образует область допустимых решений.

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

Задача линейного программирования

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

Используя знак суммирования эту задачу можно записать следующим образом:

Каноническая задача линейного программирования в векторной форме имеет вид:

В данном случае введены векторы:

Здесь С — X — скалярное произведение векторов С и X.

Каноническая задача линейного программирования в матричной форме записи имеет вид:

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

Нередко используются задачи линейного программирования, называемые симметричными, которые в матричной форме записи имеют вид:

Приведение общей задачи линейного программирования к канонической форме

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

прибавляется величина такая, что переводит неравенство в равенство , где:

Неотрицательная переменная называется дополнительной переменной.

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

Теорема. Каждому решению неравенства соответствует единственное решение уравнения: и неравенства и, наоборот, каждому решению уравнения: и неравенства соответствует единственное решение неравенства:

Доказательство. Пусть — решение неравенства. Тогда:

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

Таким образом, решение удовлетворяет уравнению: и неравенству .

Доказана первая часть теоремы.

Пусть удовлетворяет уравнению и неравенству , т.е. . Отбрасывая в левой части равенства неотрицательную величину , получим:

т.е. удовлетворяет неравенству: что и требовалось доказать.

Если в левую часть неравенств системы ограничений вида

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

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

Дополнительные переменные вводятся в целевую функцию с нулевыми коэффициентами и поэтому не влияют на ее значения.

В реальных практических задачах дополнительные неизвестные имеют определенный смысл. Например, если левая часть ограничений задачи отражает расход ресурсов на производство продукции в объемах , а правые части — наличие производственных ресурсов, то числовые значения дополнительных неизвестных и означают объем неиспользованных ресурсов i-го вида.

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

Множества допустимых решений

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

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

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

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

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

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

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

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

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

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

Теорема. Любая тонка многоугольника является выпуклой линейной комбинацией его угловых точек.

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

Уравнение целевой функции при фиксированных значениях самой функции является уравнением прямой линии (плоскости, гиперплоскости и т.д.). Прямая, уравнение которой получено из целевой функции при равенстве ее постоянной величине, называется линией уровня.

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

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

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

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

Каноническая задача линейного программирования в векторной форме имеет вид:

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

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

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

Число отличных от нуля координат опорного решения не может превосходить ранга r системы векторов условий (т.е. числа линейно независимых уравнений системы ограничений).

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

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

Теорема. Любое опорное решение является угловой точкой области допустимых решений.

Теорема. Любая угловая точка области допустимых решений является опорным решением.

Пример:

Графический метод решения задачи линейной оптимизации рассмотрим на примере задачи производственного планирования при n = 2.

Предприятие изготавливает изделия двух видов А и В. Для производства изделий оно располагает сырьевыми ресурсами трех видов С, D и Е в объемах 600, 480 и 240 единиц соответственно. Нормы расхода ресурсов на единицу продукции каждого вида известны и представлены в табл. 14.1

Прибыль от реализации изделия А составляет 40 млн. руб., а изделия В — 50 млн.руб. Требуется найти объемы производства изделий А и В, обеспечивающие максимальную прибыль.

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

Тогда прибыль предприятия от реализации изделий А и изделий В составит:

Ограничения по ресурсам будут иметь вид:

Естественно, объемы производства должны быть неотрицательными

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

Каждое из записанных уравнений представляет собой прямую на плоскости, причем 4-я и 5-я прямые являются координатными осями.

Чтобы построить первую прямую, найдем точки ее пересечения с осями координат: а при .

Далее нас интересует, по какую сторону от прямой будет находиться полуплоскость, соответствующая первому неравенству. Чтобы определить искомую полуплоскость, возьмем точку O(0,0) подставив ее координаты в неравенство, видим, что оно удовлетворяется. Так как точка O(0,0) лежит левее первой прямой, то и полуплоскость будет находиться левее прямой

. На рис 14 , расположение полуплоскости относительно первой прямой отмечено стрелками.

Аналогично построены 2-я и 3-я прямые и найдены полуплоскости, соответствующие 2-му и 3-му неравенству. Точки, удовлетворяющие ограничениям , находятся в первом квадранте. Множество точек, удовлетворяющих всем ограничениям одновременно, является ОДР системы ограничений. Такой областью на графике (рис. 14.1) является многоугольник ОАВС.

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

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

имеет координаты

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

Решив эту систему, получаем, что

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

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

1. Строится область допустимых решений;
2. Строится вектор нормали к линии уровня с точкой приложении в начале координат;
3. Перпендикулярно вектору нормали проводится одна из линий уровня, проходящая через начало координат;
4. Линия уровня перемещается до положения опорной прямой. На этой прямой и будут находиться максимум или минимум функции.

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

На рис. 14.3 показан случай, когда прямая функции параллельна отрезку АВ, принадлежащему ОДР. Максимум функции Z достигается в точке А и в точке В, а, следовательно, и в любой точке отрезка АВ, т.к. эти точки могут быть выражены в виде линейной комбинации угловых точек А и В.

На рисунке 14.4 изображен случай, когда система ограничений образует неограниченное сверху множество. Функция Z в данном случае стремится к бесконечности, так как прямую функции можно передвигать в направлении вектора градиента как угодно далеко, а на рисунке 14.5 представлен случай несовместной системы ограничений.

Основные понятия симплексного метода решения задачи линейного программирования.

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

Симплекс-метод основан на следующих свойствах задачи линейного программирования:

• Не существует локального экстремума, отличного от глобального. Другими словами, если экстремум есть, то он единственный.
• Множество всех планов задачи линейного программирования выпукло.
• Целевая функция ЗЛП достигает своего максимального (минимального) значения в угловой точке многогранника решений (в его вершине). Если целевая функция принимает свое оптимальное значение более чем в одной угловой точке, то она достигает того же значения в любой точке, являющейся выпуклой линейной комбинацией этих точек.
• Каждой угловой точке многогранника решений отвечает опорный план ЗЛП.

Рассмотрим две разновидности симплексного метода: симплекс-метод с естественным базисом и симплекс-метод с искусственным базисом (или М-метод).

Симплекс-метод с естественным базисом

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

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

Проверка на оптимальность опорного плана проходит с помощью критерия оптимальности, переход к другому опорному плану — с помощью преобразований Жордана-Гаусса и с использованием критерия оптимальности.

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

Признак оптимальности заключается в следующих двух теоремах.

Теорема 1. Если для некоторого вектора, не входящего в базис, выполняется условие:

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

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

Теорема 2. Если для всех векторов выполняется условие то полученный план является оптимальным.

На основании признака оптимальности в базис вводится вектор Ак, давший минимальную отрицательную величину симплекс-разности:

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

Строка называется направляющей, столбец и элемент — направляющими (последний называют также разрешающим элементом).

Элементы вводимой строки, соответствующей направляющей строке, в новой симплекс-таблице вычисляются по формулам:

а элементы любой другой i-й строки пересчитываются по формулам:

Значения базисных переменных нового опорного плана (показатели графы «план») рассчитываются по формулам:

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

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

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

Симплексный метод с искусственным базисом (М-метод)

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

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

В полученной задаче первоначальный опорный план очевиден. При применении к этой задаче симплекс-метода оценки А, теперь будут зависеть от числа М. Для сравнения оценок нужно помнить, что М — достаточно большое положительное число, поэтому из базиса будут выводиться в первую очередь искусственные переменные.

В процессе решения M-задачи следует вычеркивать в симплекс-таблице искусственные векторы по мере их выхода из базиса. Если все искусственные векторы вышли из базиса, то получаем исходную задачу. Если оптимальное решение М-задачи содержит искусственные векторы или М-задача неразрешима, то исходная задача также неразрешима.

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

Теория двойственности

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

Любую задачу линейного программирования можно записать в виде:

Первоначальная задача называется исходной или прямой.

Модель двойственной задачи имеет вид:

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

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

Двойственная задача по отношению к исходной составляется согласно следующим правилам:

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

При копировании любых материалов с сайта evkova.org обязательна активная ссылка на сайт www.evkova.org

Сайт создан коллективом преподавателей на некоммерческой основе для дополнительного образования молодежи

Сайт пишется, поддерживается и управляется коллективом преподавателей

Whatsapp и логотип whatsapp являются товарными знаками корпорации WhatsApp LLC.

Cайт носит информационный характер и ни при каких условиях не является публичной офертой, которая определяется положениями статьи 437 Гражданского кодекса РФ. Анна Евкова не оказывает никаких услуг.

Лекция по теме «Уравнения высших степеней. Методы их решения». 9-й класс

Разделы: Математика

Класс: 9

1. Закрепить понятие целого рационального уравнения -й степени.
2. Сформулировать основные методы решения уравнений высших степеней (n > 3).
3. Обучить основным методам решения уравнений высших степеней.
4. Научить по виду уравнения определять наиболее эффективный способ его решения.

Формы, методы и педагогические приемы, которые используются учителем на уроке:

• Лекционно-семинарская система обучения (лекции – объяснение нового материала, семинары – решение задач).
• Информационно-коммуникационные технологии (фронтальный опрос, устная работа с классом).
• Дифференцированное обучение, групповые и индивидуальные формы.
• Использование исследовательского метода в обучении, направленного на развитие математического аппарата и мыслительных способностей каждого конкретного ученика.
• Печатный материал – индивидуальный краткий конспект урока (основные понятия, формулы, утверждения, материал лекций сжато в виде схем или таблиц).

1. Организационный момент.
   Цель этапа: включить учащихся в учебную деятельность, определить содержательные рамки урока.
2. Актуализация знаний учащихся.
   Цель этапа: актуализировать знания учащихся по изученным ранее смежным темам
3. Изучение новой темы (лекция). Цель этапа: сформулировать основные методы решения уравнений высших степеней (n > 3)
4. Подведение итогов.
   Цель этапа: еще раз выделить ключевые моменты в материале, изученном на уроке.
5. Домашнее задание.
   Цель этапа: сформулировать домашнее задание для учащихся.

1. Организационный момент.

Формулировка темы урока: “Уравнения высших степеней. Методы их решения”.

2. Актуализация знаний учащихся.

Теоретический опрос – беседа. Повторение некоторых ранее изученных сведений из теории. Учащиеся формулируют основные определения и дают формулировки необходимых теорем. Приводят примеры, демонстрируя уровень полученных ранее знаний.

• Понятие уравнения с одной переменной.
• Понятие корня уравнения, решения уравнения.
• Понятие линейного уравнения с одной переменной, понятие квадратного уравнения с одной переменной.
• Понятие равносильности уравнений, уравнения-следствия (понятие посторонних корней), переход не по следствию (случай потери корней).
• Понятие целого рационального выражения с одной переменной.
• Понятие целого рационального уравнения n-й степени. Стандартный вид целого рационального уравнения. Приведенное целое рациональное уравнение.
• Переход к совокупности уравнений более низких степеней путем разложения исходного уравнения на множители.
• Понятие многочлена n-й степени от x. Теорема Безу. Следствия из теоремы Безу. Теоремы о корнях (Z-корни и Q-корни) целого рационального уравнения с целыми коэффициентами (соответственно приведенного и неприведенного).
• Схема Горнера.

3. Изучение новой темы.

Будем рассматривать целое рациональное уравнение n-й степени стандартного вида с одной неизвестной переменной x : P_n(x) = 0 , где P_n(x) = a_nx n + a_n-1x n-1 + a₁x + a₀ – многочлен n-й степени от x, a_n ≠ 0 . Если a_n = 1 то такое уравнение называют приведенным целым рациональным уравнением n-й степени. Рассмотрим такие уравнения при различных значениях n и перечислим основные методы их решения.

n = 1 – линейное уравнение.

n = 2 – квадратное уравнение. Формула дискриминанта. Формула для вычисления корней. Теорема Виета. Выделение полного квадрата.

n = 3 – кубическое уравнение.

Пример: x 3 – 4x 2 – x + 4 = 0 (x – 4)(x 2 – 1) = 0 x₁ = 4 , x₂ = 1, x₃ = -1.

Возвратное кубическое уравнение вида ax 3 + bx 2 + bx + a = 0. Решаем, объединяя члены с одинаковыми коэффициентами.

Пример: x 3 – 5x 2 – 5x + 1 = 0 (x + 1)(x 2 – 6x + 1) = 0 x₁ = -1, x₂ = 3 + 2, x₃ = 3 – 2.

Уравнение с целыми коэффициентами. Подбор Z-корней на основании теоремы. Схема Горнера. При применении этого метода необходимо сделать акцент на том, что перебор в данном случае конечный, и корни мы подбираем по определенному алгоритму в соответствии с теоремой о Z-корнях приведенного целого рационального уравнения с целыми коэффициентами.

Пример: x 3 – 9x 2 + 23x – 15 = 0. Уравнение приведенное. Выпишем делители свободного члена <+1; +3; +5; +15>. Применим схему Горнера:

Получаем (x – 1)(x 2 – 8x + 15) = 0 x₁ = 1, x₂ = 3, x₃ = 5.

Уравнение с целыми коэффициентами. Подбор Q-корней на основании теоремы. Схема Горнера. При применении этого метода необходимо сделать акцент на том, что перебор в данном случае конечный и корни мы подбираем по определенному алгоритму в соответствии с теоремой о Q-корнях неприведенного целого рационального уравнения с целыми коэффициентами.

Пример: 9x 3 + 27x 2 – x – 3 = 0. Уравнение неприведенное. Выпишем делители свободного члена <+1; +3>. Выпишем делители коэффициента при старшей степени неизвестного. <+1; +3; +9> Следовательно, корни будем искать среди значений <+1; +; +; +3>. Применим схему Горнера:

x 3	x 2	x 1	x 0	вывод
9	27	-1	-3
1	9	1 x 9 + 27 = 36	1 x 36 – 1 = 35	1 x 35 – 3 = 32 ≠ 0	1 – не корень
-1	9	-1 x 9 + 27 = 18	-1 x 18 – 1 = -19	-1 x (-19) – 3 = 16 ≠ 0	-1 – не корень
	9	x 9 + 27 = 30	x 30 – 1 = 9	x 9 – 3 = 0	корень
x 2	x 1	x 0

Получаем (x – )(9x 2 + 30x + 9) = 0 x₁ = , x₂ = — , x₃ = -3.

Для удобства подсчета при подборе Q-корней бывает удобно сделать замену переменной, перейти к приведенному уравнению и подбирать Z-корни.

• Если можно воспользоваться заменой вида y = kx.

Формула Кардано. Существует универсальный метод решения кубических уравнений – это формула Кардано. Эту формулу связывают с именами итальянских математиков Джероламо Кардано (1501–1576), Николо Тарталья (1500–1557), Сципиона дель Ферро (1465–1526). Эта формула лежит за рамками нашего курса.

n = 4 – уравнение четвертой степени.

Пример: x 4 + 2x 3 + 5x 2 + 4x – 12 = 0 (x 4 + 2x 3 ) + (5x 2 + 10x) – (6x + 12 ) = 0 (x + 2)(x 3 + 5x – 6) = 0 (x + 2)(x – 1)(x 2 + x + 6) = 0 x₁ = -2, x₂ = 1.

Метод замены переменной.

• Возвратное уравнение четвертой степени вида ax 4 + bx 3 + cx 2 + bx + a = 0.

Решаем, объединяя члены с одинаковыми коэффициентами, путем замены вида

• Обобщенное возвратное уравнение четвертой степени вида ax 4 + bx 3 + cx 2 – bx + a = 0.

• Обобщенное возвратное уравнение четвертой степени вида ax 4 + bx 3 + cx 2 + kbx + k 2 a = 0.

• Замена общего вида. Некоторые стандартные замены.

Пример 3. Замена общего вида (вытекает из вида конкретного уравнения).

Уравнение с целыми коэффициентами. Подбор Z-корней на основании теоремы. Схема Горнера. Алгоритм аналогичен рассмотренному выше для n = 3.

Уравнение с целыми коэффициентами. Подбор Q-корней на основании теоремы. Схема Горнера. Алгоритм аналогичен рассмотренному выше для n = 3.

Формула общего вида. Существует универсальный метод решения уравнений четвертой степени. Эту формулу связывают с именем Людовико Феррари (1522–1565). Эта формула лежит за рамками нашего курса.

n > 5 – уравнения пятой и более высоких степеней.

Уравнение с целыми коэффициентами. Подбор Z-корней на основании теоремы. Схема Горнера. Алгоритм аналогичен рассмотренному выше для n = 3.

Уравнение с целыми коэффициентами. Подбор Q-корней на основании теоремы. Схема Горнера. Алгоритм аналогичен рассмотренному выше для n = 3.

Симметрические уравнения. Любое возвратное уравнение нечетной степени имеет корень x = -1 и после разложения его на множители получаем, что один сомножитель имеет вид (x + 1), а второй сомножитель – возвратное уравнение четной степени (его степень на единицу меньше, чем степень исходного уравнения). Любое возвратное уравнение четной степени вместе с корнем вида x = φ содержит и корень вида . Используя эти утверждения, решаем задачу, понижая степень исследуемого уравнения.

Метод замены переменной. Использование однородности.

Не существует формулы общего вида для решения целых уравнений пятой степени (это показали итальянский математик Паоло Руффини (1765–1822) и норвежский математик Нильс Хенрик Абель (1802–1829)) и более высоких степеней (это показал французский математик Эварист Галуа (1811–1832)).

• Напомним еще раз, что на практике возможно использование комбинации перечисленных выше методов. Удобно переходить к совокупности уравнений более низких степеней путем разложения исходного уравнения на множители.
• За рамками нашего сегодняшнего обсуждения остались широко используемые на практике графические методы решения уравнений и методы приближенного решения уравнений высших степеней.
• Бывают ситуации, когда у уравнения нет R-корней. Тогда решение сводится к тому, чтобы показать, что уравнение корней не имеет. Для доказательства анализируем поведение рассматриваемых функций на промежутках монотонности. Пример: уравнение x 8 – x 3 + 1 = 0 не имеет корней.
• Использование свойства монотонности функций. Бывают ситуации, когда использование различных свойств функций позволяет упростить поставленную задачу.
  Пример 1: уравнение x 5 + 3x – 4 = 0 имеет один корень x = 1. По свойству монотонности анализируемых функций других корней нет.
  Пример 2: уравнение x 4 + (x – 1) 4 = 97 имеет корни x₁ = -2 и x₂ = 3. Проанализировав поведение соответствующих функций на промежутках монотонности, заключаем, что других корней нет.

4. Подведение итогов.

Резюме: Теперь мы овладели основными методами решения различных уравнений высших степеней (для n > 3). Наша задача научиться эффективно использовать перечисленные выше алгоритмы. В зависимости от вида уравнения мы должны будем научиться определять, какой способ решения в данном случае является наиболее эффективным, а также правильно применять выбранный метод.

5. Домашнее задание.

[1]: п.7, стр. 164–174, №№ 33–36, 39–44, 46,47.

[4]: №№ 9.1–9.4, 9.6–9.8, 9.12, 9.14–9.16, 9.24–9.27.

Возможные темы докладов или рефератов по данной тематике:

• Формула Кардано
• Графический метод решения уравнений. Примеры решения.
• Методы приближенного решения уравнений.

Анализ усвоения материала и интереса учащихся к теме:

Опыт показывает, что интерес учащихся в первую очередь вызывает возможность подбора Z-корней и Q-корней уравнений при помощи достаточно простого алгоритма с использованием схемы Горнера. Также учащиеся интересуются различными стандартными типами замены переменных, которые позволяют существенно упрощать вид задачи. Особый интерес обычно вызывают графические методы решения. В этом случае дополнительно можно разобрать задачи на графический метод решения уравнений; обсудить общий вид графика для многочлена 3, 4, 5 степени; проанализировать, как связано число корней уравнений 3, 4, 5 степени с видом соответствующего графика. Ниже приведен список книг, в которых можно найти дополнительную информацию по данной тематике.

1. Виленкин Н.Я. и др. “Алгебра. Учебник для учащихся 9 классов с углубленным изучением математики” – М., Просвещение, 2007 – 367 с.
2. Виленкин Н.Я., Шибасов Л.П., Шибасова З.Ф. “За страницами учебника математики. Арифметика. Алгебра. 10-11 класс” – М., Просвещение, 2008 – 192 с.
3. Выгодский М.Я. “Справочник по математике” – М., АСТ, 2010 – 1055 с.
4. Галицкий М.Л. “Сборник задач по алгебре. Учебное пособие для 8-9 классов с углубленным изучением математики” – М., Просвещение, 2008 – 301 с.
5. Звавич Л.И. и др. “Алгебра и начала анализа. 8–11 кл. Пособие для школ и классов с углубленным изучением математики” – М., Дрофа, 1999 – 352 с.
6. Звавич Л.И., Аверьянов Д.И., Пигарев Б.П., Трушанина Т.Н. “Задания по математике для подготовки к письменному экзамену в 9 классе” – М., Просвещение, 2007 – 112 с.
7. Иванов А.А., Иванов А.П. “Тематические тесты для систематизации знаний по математике” ч.1 – М., Физматкнига, 2006 – 176 с.
8. Иванов А.А., Иванов А.П. “Тематические тесты для систематизации знаний по математике” ч.2 – М., Физматкнига, 2006 – 176 с.
9. Иванов А.П. “Тесты и контрольные работы по математике. Учебное пособие”. – М., Физматкнига, 2008 – 304 с.
10. Лейбсон К.Л. “Сборник практических заданий по математике. Часть 2–9 класс” – М., МЦНМО, 2009 – 184 с.
11. Макарычев Ю.Н., Миндюк Н.Г. “Алгебра. Дополнительные главы к школьному учебнику 9 класса. Учебное пособие для учащихся школ и классов с углубленным изучением математики.” – М., Просвещение, 2006 – 224 с.
12. Мордкович А.Г. “Алгебра. Углубленное изучение. 8 класс. Учебник” – М., Мнемозина, 2006 – 296 с.
13. Савин А.П. “Энциклопедический словарь юного математика” – М., Педагогика, 1985 – 352 с.
14. Сурвилло Г.С., Симонов А.С. “Дидактические материалы по алгебре для 9 класса с углубленным изучением математики” – М., Просвещение, 2006 – 95 с.
15. Чулков П.В. “Уравнения и неравенства в школьном курсе математик. Лекции 1–4” – М., Первое сентября, 2006 – 88 с.
16. Чулков П.В. “Уравнения и неравенства в школьном курсе математик. Лекции 5–8” – М., Первое сентября, 2009 – 84 с.

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

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

Понятия и обозначения

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

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

a11 * n 1 + a 12 * n 2 + …+a 1x n x = c 1.

a21 * n 1 + a 22 * n 2 + …+a 2x n x = c 2.

as1 * n 1 + a 12 * n 2 + …+a 1x n x = c s.

В этой записи s — это количество уравнений, x — число переменных, а n — переменная которую необходимо вычислить. Предполагается что a и b это известные свободные члены. Индексы обозначают порядковый номер уравнения. Первый символ — расположение строчки, а второй — позиция произведения переменной и свободного члена.

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

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

Существует четыре способа развязывания системы уравнений:

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

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

Алгебраическое сложение

Способ заключается в сложении или вычитании выражений. Это довольно простой способ и в то же время эффективный. Алгоритм нахождения ответа для равенств с двумя переменными n и m сводится к следующему:

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

То есть после выполнения арифметических действий с уравнениями должно получиться одно выражение с одним неизвестным. Затем находят значение этой переменной и в него подставляют полученный корень. Например, нужно узнать, какие корни системы, состоящей из двух строчек, превращают её в тождество:

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

Подставив поочерёдно в каждое равенство найденные корни можно найти второе неизвестное. Для корня n = – 5 ответом будет:

Соответственно, корнями будут числа два и минус два. Аналогичные действия необходимо выполнить и для корня другого знака n = 5. В итоге получится, что пары (− 5; − 2), (− 5; 2), (5; − 2), (5 ; 2) являются нужным ответом. При достаточном опыте подробно описывать решение не обязательно.

Существуют системы, требующие подготовительного этапа. Например, такого вида:

Исключить здесь сразу переменную не выйдет. Если умножить все члены первой строчки на тройку, а второй на четвёрку, получится запись:

9 * n – 12 * m = 15.

8 * n + 12 * m = 28.

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

Метод подстановки

Систему равенств возможно решить и способом подстановки. Используя любое из уравнений, можно выразить любую из неизвестных переменных, а затем подставить её в другое равенство. Алгоритм использования метода следующий:

• через n в одном из уравнений выражают m;
• подставляют полученное равенство вместо n в другое тождество;
• решают уравнение и находя m;
• поочерёдно подставляют найденные корни и получают ответ.

Например, нужно проверить, все ли целые корни могут быть у системы:

10 * n + 3 * m = 17.

Выразив m через n можно записать равенство: n = (8* m + 16) / 5. Так как n одинаково в обоих уравнениях, то следует подставить полученное тождество и записать: 10* n + 3*(8* n +16) / 5 = 17. Отсюда уже просто найти корень. Он будет равен дроби 1/2. Подставив его вместо n легко вычислить и второй корень: m = (8 * n + 16) / 5 = 4. Таким образом, у системы будет только один целый корень. При желании проверить ответ можно решить систему другим методом.

Использование матриц

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

Пусть дана система с тремя неизвестными х1, х2, х3. Нужно найти значения, при которых равенства станут верными. Для нахождения решений используют три матрицы:

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

Базисное решение строят на произведении первой и второй матрицы. В результате получают матрицу размером три на один. То есть вектор-столбец с тремя элементами. После выполнения действия получится, что системный вектор будет равен левой части системы и соответствовать третьей матрице. Таким образом, обозначив матрицы буквами А, Б, В, можно записать выражение А * Б = В и найти необходимую Б.

При умножении на А-1 (обратную матрицу) получают равенство: Е * Б = А-1 * В, где Е – единичная матрица получена из совместимости прямой и обратной. Так как при произведении с единичной матрицей значения не изменяются, то решением системы будет формула: Б = А-1 * В.

Способ Гаусса-Жордана

Частным случаем решения системы является Метод Гаусса — Жордана. Суть решения основана на составлении специальной таблицы. В первый столбец заносятся известные значения, то есть величины, расположенные после равно, а в три других коэффициенты, стоящие после неизвестных. Чтобы приступить к решению, необходимо выполнить три шага:

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

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

Этот метод используют только при выполнении условия совместности. Его ещё называют способом простой итерации. Он был доказан и оптимизирован Зейделем. С помощью итерационного метода можно посчитать систему А* Б = В с точностью “е”. Составляют n уравнение на сходимость, а затем на точность. Затем из первого уравнения выражают n1, второго n2, третьего n3 и так далее. Новые n с индексом i +1 считаются через старые i. Зейдель предложил расширить решение и добавить снова для счёта индекс i+1.

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

Теорема Кронекера — Капелли

Применяется она при проведении исследований без непосредственного решения. То есть для записи эквивалентной совокупности алгебраических уравнений с их минимальным числом. Теорема говорит о следующем: система уравнений А * Б = В имеет решение только тогда, когда ранг А равен (А, В), где последнее расширенная матрица, полученная из первого члена путём приписывания столбца В.

Это утверждение обобщает различные виды СЛАУ:

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

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

Решение Крамера

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

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

Как только все дискриминанты найдены, используют правило Крамера: n = Δn/ Δ. Подставляют значения, находят ответ. Стоит отметить, что много интернет-порталов, предлагающих услугу расчётов СЛАУ, используют для вычислений онлайн-метод Крамера.

Удобные онлайн-калькуляторы

В некоторых случаях решение СЛАУ онлайн будет хорошим подспорьем для того, чтобы разобраться в различных правилах, используемых при решениях. Из популярных интернет-сервисов, позволяющих найти корни систем, можно отметить: kontrolnaya-rabota, mathsolution, planetcalc, allcalc. Использовать эти сайты-решатели смогут даже слабо подготовленные пользователи, имеющие общее представление о методах решений.

Для выполнения расчёта необходимо ввести параметры системы и нажать кнопку «Рассчитать». При этом можно выбрать метод, на базе которого будут проводиться вычисления. Удобным является и то, что полученный расчёт сопровождается объяснениями.

На этих порталах также можно посмотреть примеры и правила решений. Некоторые калькуляторы могут построить и график системы. Например, kontrolnaya-rabota. Для этого на сайте нужно выбрать раздел «Графическое решение уравнений онлайн» и ввести исследуемую систему равенств.