Методы исследования функций численного анализа

Линейное программирование представляет собой математический аппарат, разработанный для решения оптимальных задач с линейными выражениями для критерия оптимальности и линейными ограничениями на область изменения переменных. Такие задачи обычно встречаются при решении во­просов оптимального планирования производства с ограниченным количеством ресурсов, при определении оптимального плана пе­ревозок (транспортные задачи) и т. д. Для решения большого круга задач линейного программирова­ния имеется практически универсальный алгоритм — симплексный метод, позволяющий за конечное число итераций находить опти­мальное решение подавляющего большинства задач. Тип исполь­зуемых ограничений (равенства или неравенства) не сказывается на возможности применения указанного алгоритма. Дополнитель­ной проверки на оптимальность для получаемых решений не тре­буется. Как правило, практические задачи линейного программиро­вания отличаются весьма значительным числом независимых пере­менных. Поэтому для их решения обычно используют вычислитель­ные машины, необходимая мощность которых определяется раз­мерностью решаемой задачи.

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

Методы нелинейного программирования приме­няют для решения оптимальных задач с нелинейными функциями цели. На независимые переменные могут быть наложены ограни­чения также в виде нелинейных соотношений, имеющих вид ра­венств или неравенств. По существу методы нелинейного програм­мирования используют, если ни один из перечисленных выше ме­тодов не позволяет сколько-нибудь продвинуться в решении оптимальной задачи. Поэтому указанные методы иногда называют также прямыми методами решения оптимальных задач. Для получения численных результатов важное место отводится нелинейному программированию и в решении оптимальных задач такими методами, как динамическое программирование, принцип, максимума и т. п. на определенных этапах их применения. Названием «методы нелинейного программирования» объеди­няется большая группа численных методов, многие из которых при­способлены для решения оптимальных задач соответствующего класса. Выбор того или иного метода обусловлен сложностью вы­числения критерия оптимальности и сложностью ограничивающих условий, необходимой точностью решения, мощностью имеющейся вычислительной машины и т. д. Ряд методов нелинейного програм­мирования практически постоянно используется в сочетании с дру­гими методами оптимизации, как, например, метод сканирования в динамическом программировании. Кро­ме того, эти методы служат основой построения систем автомати­ческой оптимизации — оптимизаторов, непосредственно при­меняющихся для управления производственными процессами.

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

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

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

Поиск по сайту: