Классификация и характеристика методов решения задач

Оптимизации

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

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

В настоящее время для решения оптимальных задач применяют в основном следующие методы:

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

В последнее время разработан и успешно применяется для решения определенного класса задач метод геометрического программирования.

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

Часто методы решения нелинейных задач делят по признаку организации поиска экстремума: на методы слепого поиска и методы направленного поиска. К методам слепого поиска относятся метод сплошного перебора вариантов, метод пространственной сетки и метод статистических испытаний (метод Монте-Карло). К методам направленного поиска относятся градиентные методы: метод скорейшего спуска, метод покоординатного спуска и др.

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

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

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

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

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

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