ПОИСК Статьи Рисунки Таблицы Основные задачи прикладной математики из "Моделирование процессов автоматизированного химико - технологического проектирования" Решение системы линейных уравнений широко применяется ш инженерных расчетах. Существуют точные и приближенные методы решения [2, 4]. [c.26] Точные методы — это методы, которые за конечное число шагов, зависящее только от числа уравнений в сист(вме, дают (если игнорировать ошибки округления) точное решение системы. Наиболее известным и удобным для реализации на ЭВМ является метод Гаусса метод последовательного исключения). Число элементарных алгебраических операций при решении системы по методу Гаусса имеет порядок и , где п—число уравнений. Метод заключается в последовательном исключении неизвестных в уравнениях, в результате чего истема приводится к виду, в котором она разрешима. В настоящее время соответствующая стандартная программа имеется в любой библиотеке стандартных программ ЭВМ. [c.26] Если практические системы уравнений имеют большой порядок, то элементы их матрицы, как правило, почти все — нули. Например, система состоит из 500 уравнений, но в каждое из них входит не более 10 переменных. Матрица такой системы состоит из 250 ООО чисел, при этом только 5000 чисел не нули. Таким образом, чтобы поместить такую систему в память ЭВМ, достаточно запомнить не все 250 ООО чисел что невозможно, а немногим более 15 000 (сами ненулевые числа и их номера в матрице). Для таких систем метод Гаусса крайне неудобен, так как он многие нулевые элементы переводит в ненулевые, которые должны запоминаться. [c.26] Приближенные методы позволяют за конечное число шагов найти лишь некоторое приближение к решению системы, которое тем точнее, чем больше шагов сделано. Достоинством этих методов является то, что в памяти ЭВМ можно хранить исходную матрицу системы. Однако каждый из этих методов может быть применен только к системам специального вида, на которых этот метод, как говорят, сходится . Для каждого метода имеется свой класс таких систем. Кроме того, возникают вопросы, связанные со скоростью сходимости. Всё это привело к возникновению большого количества приближенных методов. Перечислим наиболее важные из них. [c.26] Методы полной релаксации. Эти методы в различной модификации основаны на следующем принципе. Оценивается сверху расстояние между имеющимся приближением и решением системы, а затем на каждом шаге изменяется одна (или несколько, в случае групповой релаксации) компонента вектора предыдущего приближения так, чтобы уменьшить имеющуюся оценку. [c.26] Метод наискорейшего спуска. Этот метод относится к группе так называемых градиентных методов. Он но существу применяется не непосредственно к системе линейных уравнений, а к эквивалентной ей задаче оптимизации. По этой нрйчине мы рассмотрим его позднее. Ёолее подробное описание этих и других методов содержится в работе [4]. [c.27] В методе Ньютона выбирается начальное приближение затем в окрестности этого приближения нелинейная задача апнроксими-руется соответствующей линейной. Решение этой задачи дает приращение для Жд и в сумме нолзгчается следующее приближение и т. д. Этот метод является точным обобщением на случай п переменных ньютоновского метода нахождения нулей вещественной функции одного переменного. [c.27] Оптюшзация на непрерывном множестве. Нахождение экстремумов непрерывной функции, рассматриваемой на некотором непрерывном множестве, в самом общем виде может быть записана следующим образом. [c.27] Условия (И-1) называют ограничениями, а (11-2) — функцией цели. Это общая задача математического программирования. Наиболее простой и изученный- ее вариант — задача линейного программирования. В этой задаче все ограничения и функция цели — линейны. Такая задача может быть точно решена за конечное число шагов с помощью так называемого симплекс-метода [5]. [c.28] Следующая по сложности — задача квадратичного программирования. При этом ограничения остаются линейными, но функция цели — квадратна. Эта задача уже не может быть решена точно, однако во многих случаях имеются простые алгоритмы приближенного решения. [c.28] Одним из основных методов, применяемых к общей задаче математического программирования, является градиентный метод. Он имеет множество модификаций, но в основе всех их лежит следующий процесс. [c.28] Находясь в точке (ж ,. . ., ж ), мы с помощью некоторой процедуры, связанной с нахождением градиента-функции в этой точке (отсюда и название метода), ищем направление, па которому ата функция убывает (в случае задачи на минимум) или возрастает (в случае задачи на максимум). Перемещаясь по этому направлению на некоторое расстояние, мы попадаем в точку х[,. . аг ), в которой значение функции цели меньше (больше), чем в предыдущей, и т. д. [c.28] Недостатком метода является его локальность, в силу которой мы можем вместо абсолютного экстремума функции получить в конечном результате локальный экстремум. [c.28] Вариационные задачи. Среди оптимизационных задач особый класс составляют задачи, в которых требуется найти некоторую функцию, оптимизирующую данньЁй функционал. Эти задачи называются вариационными. Для их решения обычно применяют два общих метода. Метод Эйлера заключается в переходе от задачи минимизации функционала к задаче решения некоторого дифференциального уравнения. Метод Лагранжа основан на обобщении соответствующих свойств экстремальных точек функций, в результате чего решение вариационной задачи сводится к отысканию корней нужным образом определенного дифференциала функционала. [c.28] Прежде всего следует отметить метод ветвей и границ. Это метода который реализует точный перебор, но придает ему некоторую правильную форму, в результате чего на конкретных задачах он может достаточно быстро привести к решению. Метод заключается в построении дерева логических возможностей, пути которого моделируют всевозможные варианты решения задачи. Так, если мы хотим найти кратчайший цикл в графе (решить задачу коммивояжера), то соответствующее дерево строится следующим образом (рис. П-2). [c.29] Введем фиктивную н у левую вершину — нулевой ярус. Выбору каждого ребра из п возможных ребер сопоставим вершину 1-го яруса. Для каждой вершины 1-го яруса построим 2-й ярус вершин, где каждой вершине отвечает выбор некоторого ребра графа (с учетом соответствующих ограничений выбранное ранее ребро не берется, цикл не замыкается преждевременно и т. п.). [c.29] В дереве логических возможностей рассматривают всевозможные пути от нулевого яруса до последнего. При этом (и в этом сущность метода) предполагается известным некоторый функционал от пройденного пути, который обычно позволяет не проходить этот путь до конца, если он не оптимален. Так, на рис. П-5 таким функционалом является для каждого отрезка пути по дереву длина соответствующих этому пути ребер графа. Пройдя какой-либо путь до конца, получим некоторый цикл на графе. Затем пойдем по другому пути на дереве. [c.29] Для каждого отрезка получающейся цепи оценим минимальную длину цикла, в который она входит. Для этого, если длина отрезка 5, добавим к длине цепи длины п — 8 кратчайших ребер, не включенных в цепь. Если полученное число больше, чем длина наименьшего из построенных уже циклов, то этот путь (со всеми дальнейшими разветвлениями) не рассматривается далее. Действуя таким образом и понижая за счет вновь полученных циклов оценку сверху, получим искомое решение. [c.30] Таков упорядоченный алгоритм полного перебора. В некоторых случаях перебор при решении задачи можно уменьшить. Так, если каждой точке области определения задачи можно сопоставить некоторое небольшое множество точек (называемое окрестностью данной точки), обладающее тем свойством, что в рассматриваемой точке наша функция принимает экстремальное значение но сравнению со значениями во всех точках окрестности, то имеется глобальный экстремум. Ясно, что в подобных задачах перебор можно вести только внутри окрестностей и спуск возможен но значениям функции. Простейшим примером такого рода является ситуация, когда задачу можно включить в схему линейного программирования. В этом случае окрестность точки уже определена — это все соседние с ней вершины многогранника, ограничивающего допустимую область определения. Именно на переборе по таким окрестностям и основан уже упоминавшийся симплекс-метод. [c.30] Вернуться к основной статье