Классификация оптимизационных задач
ВГТУ
2024-12-03
Задача оптимизации
Задача оптимизации – задача возникающая, когда из некоторой совокупности возможных вариантов поведения или принятия решения в какой-либо области деятельности необходимо выбрать один вариант путем сравнения этих вариантов на основе их количественной оценки.
Варианты решения задачи оптимизации называют альтернативами.
Задача оптимизации
По содержанию задачи оптимизации весьма разнообразны. Они могут быть связаны с проектированием технических устройств и технологических процессов, с распределением ограниченных ресурсов и планированием работы предприятий, наконец, с решением проблем, возникающих в повседневной жизни человека.
Всевозможные устройства, процессы и ситуации, применительно к которым предстоит решать задачу оптимизации, объединим общим названием объект оптимизации.
Задача оптимизации
Задача оптимизации - те признаки и предпочтения, по которым следует провести сравнительную оценку альтернатив и выбрать среди них наилучшую с точки зрения поставленной цели оптимизации.
Цель оптимизации
Целью оптимизации может быть повышение производительности или срока службы технического устройства, снижение массы конструкции или затрат на его производство и т.п.
Математическая модель объекта оптимизации
Математическая модель объекта оптимизации описывает объект при помощи соотношений между величинами, характеризующими его свойства. Обычно хотя бы часть этих величин можно изменять в некоторых пределах, что и порождает множество альтернатив, среди которых и предстоит выбрать наилучшую.
Математическая модель объекта оптимизации
Изменяемые при оптимизации величины, входящие в математическую модель объекта оптимизации, называют параметрами оптимизации, а соотношения, устанавливающие пределы возможного изменения этих параметров, — ограничениями.
Эти ограничения могут быть заданы в форме равенств или неравенств. Их называют соответственно ограничениями типа равенства или ограничениями типа неравенства.
Математическая модель объекта оптимизации
Если множество параметров оптимизации является подмножеством конечномерного линейного пространства, то говорят о конечномерной задаче оптимизации в отличие от бесконечномерных задач, которые рассматривают в вариационном исчислении и оптимальном управлении.
Критерий оптимальности
Критерием оптимальности может быть требование достижения наибольшего или наименьшего значения одной или несколькими действительными \(скалярными\) функциями параметров оптимизации, выражающими количественно меру достижения цели оптимизации рассматриваемого объекта. Каждую из таких функций принято называть целевой.
Критерий оптимальности
Если целевая функция единственная, то задачу конечномерной оптимизации называют задачей математического программирования, а в противном случае — задачей многокритериальной (векторной) оптимизации.
Задача линейного программирования
Если целевая функция и ограничения являются линейными относительно параметров оптимизации, то говорят о задаче линейного программирования.
Одну из первых таких задач сформулировал и решил Л.В. Канторович. Задача Канторовича была связана с выбором оптимальной производственной программы, что и объясняет появление в названии этого класса задач слова «программирование».
При нелинейной зависимости целевой функции или ограничений от параметров оптимизации говорят о задаче нелинейного программирования.
Задачи оптимального проектирования
При создании технического устройства различного назначения обычно часть его параметров можно изменять в определенных пределах. Это приводит к тому, что при проектировании появляется некоторое множество вариантов создаваемого устройства.
В результате возникает проблема выбора из этого множества альтернатив наилучшей альтернативы с точки зрения критерия оптимальности. Соответствующие такому выбору задачи оптимизации часто называют задачами оптимального проектирования.
Экономические задачи
Задачи математического программирования часто возникают в экономике, при планировании производственных процессов и количественной оценке альтернатив, связанных с принятием управленческих решений.
Постановка этих задач обычно основана на анализе и сопоставлении расходуемых ресурсов и полученного результата. Такой подход принято называть методом «затраты — эффективность».
Экономические задачи
Применение этого подхода приводит, как правило, к двум связанным между собой типам задач:
максимизировать эффективность при ограниченных затратах
обеспечивать эффективность не ниже заданной при минимальных затратах
Таким образом, критерием оптимальности может быть количественное выражение затрат или эффективности.
Математические модели
Одна и та же прикладная задача может приводить к разным задачам оптимизации в зависимости от того, какая математическая модель используется при рассмотрении реального объекта оптимизации.
Желательно применять более простые модели, но в то же время достаточно полно отражающие свойства объекта, существенные с точки зрения поставленной цели, выраженной в критерии оптимальности.
Параметры оптимизации
Пусть \(f_0(x)\) — целевая функция, количественно выражающая некоторый критерий оптимальности и зависящая от координат \(x_j\),
\[x_j,\ j=\overline{1,n}\quad \text{точки}\quad x\in \mathbb{R}^n\]
Эти координаты являются параметрами оптимизации (иногда их называют также переменными задачи оптимизации или просто переменными задачи).
Минимизация
При математической формулировке задачи оптимизации целевую функцию выбирают с таким знаком, чтобы решение задачи соответствовало поиску минимума этой функции. Поэтому формулировку общей задачи математического программирования обычно записывают так: \[f_0(x)\rightarrow min,\quad x\in\Omega \]где \(\Omega \subset \mathbb{R}^n\)— множество возможных альтернатив, рассматриваемых при поиске решения задачи.
Допустимые решения
Любую точку \(x\in\Omega\) называют допустимым решением задачи математического программирования, а само множество — множеством допустимых решений или, короче, допустимым множеством.
Точку \(x^*\in\Omega\), в которой функция \(f_0(x)\) достигает своего наименьшего значения, называют оптимальным решением задачи.
Допустимые решения
При отсутствии ограничений множество \(\Omega\) совпадает с областью определения \(D(f_0)\subset\mathbb{R}^n\) целевой функции. Если же рассматриваемые альтернативы должны удовлетворять некоторым ограничениям, то множество допустимых решений сужается.
Задача минимизации
Задачу \[f_0(x)\rightarrow min, \ x\in\Omega\]в дальнейшем будем называть задачей минимизации целевой функции на множестве \(\Omega\), понимая под этим нахождение наименьшего значения функции \(f_0(x)\) на \(\Omega\) и точек \(x\in \Omega\), в которых оно достигается. Но целевая функция может и не достигать на \(\Omega\) наименьшего значения. Тогда говорят о точной нижней грани \(\underset{x\in\Omega}\inf {f_0(x)}\) функции \(f_0(x)\) на этом множестве и используют запись \[ f_0(x)\rightarrow\inf, \quad x\in\Omega\]
Линейная целевая функция
Если \(f_0(x)\) — линейная функция, то ее область определения совпадает c \(\mathbb{R}^n\). B \(\mathbb{R}^n\) такую функцию с помощью стандартного скалярного произведения можно представить в виде \(f_0(x)=(c,x)\), где \(c=(c_1, \dots , c_n)\in\mathbb{R}^n\) — известный вектор. \[f_0(x)=(c,x)=\sum_{j=1}^n c_jx_j\]
Требование наличия ограничений
Ясно, что указанная целевая функция может достигать наименьшего значения на множестве \(\Omega\) лишь в точках границы \(\partial \Omega\) этого множества. Если в задаче нет ограничений, то точная нижняя грань линейной функции равна \(-\infty\). Поэтому в случае линейной целевой функции задача оптимизации имеет смысл лишь при наличии ограничений.
Стандартная задача линейного программирования
В частном случае, когда заданы линейные ограничения типа равенства
\[Bx=d, \quad x\in\mathbb{R}^n,\]
где \(d\in\mathbb{R}^k\), \(В\) — матрица размера \(k\times n\), а параметры оптимизации могут принимать лишь неотрицательные значения, т.е. \[x_j\ge0,\quad j=\overline{1,n},\] эти соотношения составляют стандартную задачу линейного программирования, или задачу линейного программирования в стандартной форме (каноническую задачу линейного программирования, или задачу линейного программирования в канонической форме).
Общая задача линейного программирования
Если добавить ограничении типа неравенства \[\sum_{j=1}^n a_{ij}x_j\le b_m,\] Где \(a_{ij}\in\mathbb{R},\ i=\overline{1,m}\), то формулируется общая задача линейного программирования.
При отсутствии ограничений типа равенства образуется формулировка основной задачи линейного программирования (иногда ее называют естественной задачей линейного программирования).
Выпуклые функции
Среди целевых функций достаточно широкий класс составляют выпуклые функции. Во многих прикладных задачах оптимизации область допустимых значений параметров оптимизации оказывается выпуклым множеством . В такой области целевая функция может сохранять одно и то же направление выпуклости, т.е. выпукла либо вниз (выпукла), либо вверх (вогнута).
Выпуклое программирование
Любую вогнутую целевую функцию, изменив знак, можно сделать выпуклой. Задачи оптимизации, в которых необходимо найти наименьшее значение выпуклой целевой функции, рассматриваемой на выпуклом множестве, относят к задачам выпуклого программирования. Частными случаями таких задач являются задачи квадратичного и линейного программирования.
Дискретное программирование
Если множество \(\Omega\) допустимых решений оказывается конечным множеством, то мы имеем задачу дискретного программирования, а если к тому же координаты этих точек — целые числа, то — задачу целочисленного программирования.
