1. Математическое описание и классификация задач оптимизации
Решение задачи оптимизации начинается с формирования математической оптимизационной модели. Обобщенно оптимизационная модель может быть записана следующим образом:
(1)
Здесь
– вектор варьируемых параметров объекта;
– целевая функция (критерий оптимальности),
т. е. функция, характеризующая наиболее
важные и существенные свойства объекта
и являющаяся критерием оценки качества
каждого из вариантов. На основании
вычисления значений целевой функции
f(X)
анализируются и сравниваются между
собой различные варианты объектов.
В процессе оптимизации объект должен
удовлетворять различным требованиям
(конструктивным, техническим,
экономическим), которые формализуются
в виде системы ограничений. Ограничения
на варьируемые параметры
называют прямыми ограничениями. Здесь
и
– нижние и верхние допустимые значения
для управляемого параметра
,
которые зависят от решаемой оптимизационной
задачи.
Ограничения вида
,
называют функциональными ограничениями.
Функциональные ограничения являются
какими-либо функциями от варьируемых
параметров и формулируются в виде
системы равенств и неравенств.
Совокупность функциональных и прямых ограничений образует допустимую область или область допустимых решений задачи D.
Таким образом, решение задачи оптимизации сводится к определению значений варьируемых параметров , обеспечивающих оптимальное значение (максимум или минимум) целевой функции f(X) и удовлетворяющих системе ограничений. Рассмотренная математическая оптимизационная модель является обобщенной и конкретизируется при решении практических задач оптимизации. При этом в зависимости от вида оптимизационной модели задачи оптимизации и методы их решения делятся на следующие классы:
1. В зависимости от числа управляемых параметров различают задачи одномерной и многомерной оптимизации. В задачах одномерной оптимизации имеется один варьируемый параметр, а в задачах многомерной оптимизации – несколько параметров.
2. По характеру искомого оптимума различают задачи локальной и глобальной оптимизации (унимодальные и многоэкстремальные задачи).
3. В зависимости от наличия ограничений выделяют задачи безусловной и условной оптимизации. В задачах безусловной оптимизации ограничения отсутствуют, и варьируемые параметры могут изменяться в любых пределах.
4. В зависимости от количества критериев оптимальности различают задачи однокритериальной (скалярной) и многокритериальной (векторной) оптимизации. В задачах многокритериальной оптимизации имеется несколько критериев оптимальности.
5. По виду целевой функции и ограничений различают задачи линейной и нелинейной оптимизации. В задачах линейной оптимизации целевая функция и все функции-ограничения линейны. Если хотя бы одна из функций является нелинейной, задача относится к классу задач нелинейной оптимизации.
6. По характеру изменения варьируемых параметров различают задачи непрерывной и дискретной оптимизации. В задачах непрерывной оптимизации параметры изменяются непрерывно в пределах, установленных функциональными ограничениями. В задачах дискретной оптимизации варьируемые параметры принимают дискретные значения.
Частными случаями задач дискретной
оптимизации являются задачи целочисленной
и булевой оптимизации. В задачах
целочисленной оптимизации варьируемые
параметры могут принимать только
целочисленные значения. В задачах
булевой оптимизации
.
Если D – дискретное
конечное множество точек, то такая
дискретная задача называется комбинаторной.
Если при оптимизации часть параметров
дискретна, а часть имеет непрерывный
характер, то рассматривается задача
частично дискретной (непрерывно-дискретной)
оптимизации.
Необходимо заметить, что одна и та же оптимизационная задача может относиться к нескольким типам (например, являться однокритериальной, линейной и непрерывной). Для различных типов оптимизационных задач разработаны соответствующие методы их решения, классификация которых является аналогичной. При этом данные методы, как правило, инвариантны к предметной области их приложения.