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

Математическое программирование предполагает построение алгоритмов решения задач оптимизации (задач оптимального планирования). В зависимости от свойств целевой функции и ограничений математическое программирование подразделяестся на: линейное; нелинейное (нелинейное при линейных ограничениях: выпуклое; сепарабельное; квадратичное; геометрическое). Это разделение неслучайно. Оно определяется отсутствием универсальных методов решения задач нелинейного программи­рования, для которого разработаны лишь эффективные методы решения отдельных классов задач. Задачи оптимизации связаны с вопросами эффективного использования или распределения ограниченных ресурсов для достижения желаемых целей. Характерной чертой задач оптимизации является большое число реше­ний, удовлетворяющих условиям задачи. Выбор конкретного решения, как "наилучшего", зависит от функции цели (показатель качества, критерий оптимальности, функция качества, критерий эффективности и т.д. - си­нонимы). Задача, допускающая лишь одно решение_, не требует оптимиза­ции.

В общем плане, существующие методы математического программирова­ния подразделяются на аналитические и численные

Аналитические методы включают в себя классические методы дифференциального и вариационного исчисления. Эти методы за­ключаются

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

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

Решение задач оптимизации численными методами представляет собой два этапа:

Первый этап - сбор информации об объекте;

Алгоритм сбора информации должен быть

1) прост;

2) должен обеспечивать процедуру решения наиболее полной информацией об объекте;

3) должен учитывать априорную информацию, полученную ранее, т.е. иметь возможность самообучаться.

На втором этапе строится процедура решения на базе проанали­зированной информации.

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

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

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