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