В задачах выпуклого программирования целевая функция является выпуклой (при минимизации) или вогнутой (при максимизации), а ограничения задают выпуклое множество допустимых решений.
З а м е ч а н и е 4.5. Ряд авторов задачи НП с вогнутыми функциями выделяют в отдельный класс задач вогнутого программирования.
З а м е ч а н и е 4.6. В силу того, что линейная функция является одновременно и выпуклой и вогнутой, задача ЛП может рассматриваться как частный случай задачи выпуклого программирования.
Невыпуклое программирование охватывает все остальные задачи, не обладающие особенностями задач выпуклого программирования.
Существенной особенностью выпуклого программирования является совпадение локального и глобального экстремумов. Отсюда следует, что при решении задач выпуклого программирования достаточно найти только локальный экстремум. Такой экстремум будет одновременно и глобальным. Рассмотренная особенность значительно упрощает решение задач выпуклого программирования.
В выпуклом программировании выделяют несколько классов задач, имеющих специальные методы решения.
Так, выделяется класс задач квадратичного программирования. В таких задачах целевая функция представляет собой в общем случае многочлен второй степени (сумму линейной и квадратичной функций) [5,6, 47]. Краткая характеристика таких задач будет дана в ниже в п.4.3
Выделяется также класс задач геометрического программирования. В таких задачах ЦФ и функциональные ограничения имеют вид так называемых позиномов, представляющих собой сумму произведений степенных функций всех переменных оптимизации. Краткая характеристика таких задач будет дана в ниже в п.4.3
Рассмотрим далее общие методы решения задач ПН.
4.2. Методы безусловной оптимизации в НП
Напомним, что задачей безусловной оптимизации называется задача, в постановке которой отсутствуют ограничения на оптимизируемые переменные.
З а м е ч а н и е 4.7. Некоторые авторы считают, что задачу нахождения экстремума нелинейной ЦФ при отсутствии ограничений нельзя считать задачей МП, предполагающей по определению наличие ограничений. Другие авторы считают такие задачи частным случаем задач НП.
Отсутствие ограничений в задаче безусловной оптимизации приводит к тому, что значение каждой из n переменных оптимизации может быть любым действительным числом. На теоретико-множественном языке это записывается в виде: X Î Rn , где Rn – n-мерное евклидово пространство.
Методы безусловной оптимизации нелинейных функций делятся на аналитические и численные.
4.2.2. Аналитические методы безусловной оптимизации НП
Будем называть аналитическими методами безусловной оптимизации НП методы, предусматривающие получение аналитических соотношений, позволяющих найти точку экстремума. Получение таких соотношений предусматривает выполнение трех этапов: 1) выполнение операций дифференцирования, 2) решение системы уравнений , 3) проверку некоторых условий (так называемых достаточных условий экстремума).
Задачи безусловной оптимизации функции одной или нескольких переменных обычно рассматриваются в рамках математического анализа. В таких задачах предполагается известной аналитическая зависимость функции от аргументов, а также существование обычных или частных производных до второго порядка включительно. В рамках НП такую задачу оптимизации обычно называют классической.
При аналитическом решении такой задачи используют необходимые и достаточные условия экстремума функции.
Напомним, что необходимоеусловие существования экстремума функции одной переменной в некоторой точке состоит в том, чтобы ее первая производная в этой точке была равна нулю. То же условие для функции n переменных состоит в том, чтобы в некоторой точке частные производные первого порядка были равны нулю (или, по крайней мере, одна из частных производных не существует или бесконечна).
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.