Лекция: Пространство оптимизации

S = Rn — задача оптимизации с непрерывными переменными

S = Zn — задача целочисленной оптимизации

S = Bn — задача булевой оптимизация (частный случай задачи целочисленной оптимизации, при которой переменные могут принимать только два значения — ноль и единица). Если при этом f(X) принимает значения из Rn, то — задача псевдобулевой оптимизации

Если значение целевой функции зависит от некоторых комбинаций объектов из конечного набора, их размещения или способа упорядочения, то такие задачи называются задачами комбинаторной оптимизации

Задачи целочисленной и комбинаторной оптимизации объединяются понятием задач дискретной оптимизации

В задачах смешанной оптимизации могут одновременно присутствовать переменные нескольких или даже всех типов (наиболее известный частный случай — задачи смешанного целочисленного программирования с целочисленными и непрерывными переменными)

Свойства функций, входящих в постановку задачи оптимизации

Целевая функция имеет более одного локального экстремума — задача глобальной или многоэкстремальной оптимизации (если требуется найти все локальные экстремумы или наилучший из них)

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

Целевая функция и/или функции, описывающие ограничения, заданы не аналитически (в виде компьютерных программ, имитационных моделей, человеко-машинных процедур или как выход реальной системы) — задачи оптимизации с неявными функциями (поисковые задачи оптимизации)

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

Общая формулировка задачи математического программирования:

f(X) ® ,

при ограничениях

hi(X) = 0, i = 1,..., m,

gi(X) ³ 0, i = m+1,..., p.

Все функции, входящие в постановку, являются непрерывно дифференцируемыми — задача дифференцируемой оптимизации, иначе – задача недифференцируемой оптимизации

Целевая функция выпукла, функции-ограниче-ния образуют выпуклую допустимую область — задача выпуклой оптимизации

Целевая функция сепарабельна, ограничения линейны — задача сепарабельного программирования

Целевая функция квадратичная, ограничения – линейны — задача квадратичного программирования

Все функции общего вида — общая задача нелинейного программирования

Целевая функция и функции-ограничения являются линейными относительно независимых переменных — задача линейного программирования

Более узкие постановки задачи линейного программирования — транспортная задача, задача о назначениях, задача целочисленного линейного программирования и т.п.