Статические задачи оптимизации

Статические задачи оптимизации называются также задачами математического программирования.

Задача математического программирования формулируется следующим образом. Найти вектор Статические задачи оптимизации - student2.ru с компонентами Статические задачи оптимизации - student2.ru из некоторого допустимого множества Статические задачи оптимизации - student2.ru , задаваемого в виде ограничений

Статические задачи оптимизации - student2.ru Статические задачи оптимизации - student2.ru , (1.1)

который минимизирует (или максимизирует) целевую функцию

Статические задачи оптимизации - student2.ru ,

т.е.

Статические задачи оптимизации - student2.ru или Статические задачи оптимизации - student2.ru . (1.2)

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

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

Задачи линейного программирования характеризуются тем, что функции Статические задачи оптимизации - student2.ru и Статические задачи оптимизации - student2.ru являются линейными по Статические задачи оптимизации - student2.ru .Требуется найти вектор Статические задачи оптимизации - student2.ru с компонентами Статические задачи оптимизации - student2.ru , обеспечивающий минимум (или максимум) функции

Статические задачи оптимизации - student2.ru (1.3)

при условиях Статические задачи оптимизации - student2.ru Статические задачи оптимизации - student2.ru , Статические задачи оптимизации - student2.ru Статические задачи оптимизации - student2.ru .

В основе большинства методов решения задач линейного программирования лежит симплекс-метод [10,12].

К задачам нелинейного программирования относятся все задачи с нелинейной целевой функцией или нелинейными ограничениями. Частным случаем являются задачи квадратичного программирования, которые характеризуются квадратичной зависимостью целевой функции Статические задачи оптимизации - student2.ru и линейной зависимостью функций Статические задачи оптимизации - student2.ru . Методы решения задач этого типа в основном базируются на теореме Куна-Таккера [4].

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

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

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

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

Наши рекомендации