Стандартные формы задач оптимизации
В стандартных формах задач объектом оптимизации является непрерывная функция
вещественных переменных
, допустимая область
задается конечной системой равенств
и неравенств с непрерывными левыми частями
и
. Если при этом область
ограничена, то в ней обязательно существует по крайней мере одна точка абсолютного максимума и одна точка абсолютного минимума функции
. Поскольку перемена знака у левых частей неравенств
и
меняет знаки этих неравенств на противоположные, можно ограничиться одним из двух типов неравенств. Обычно при максимизации используются неравенства вида
, а при минимизации - неравенства вида
. Таким образом, возникают две стандартные формы постановки задач оптимизации.
;
. (4.2)
Ограничения типа неравенств легко заменить ограничениями типа равенств и простыми координатными неравенствами, вводя дополнительные (вещественные) переменные
. При этом ограничения вида
заменятся парой ограничений
,
, а ограничения
- парой ограничений
,
. Этот прием будет в дальнейшем именоваться приемом элиминации нетривиальных неравенств. Его особенно удобно применять в тех случаях, когда по смыслу задачи все точки допустимой области имеют неотрицательные координаты. В результате его применения в таких условиях возникает третья стандартная форма постановки задачи оптимизации:
. (4.3)
Во всех перечисленных постановках может присутствовать дополнительное требование о том, чтобы все координаты точки оптимума были целыми числами (или числами некоторого заданного ряда). Это требование превращает задачу непрерывной оптимизации в задачу целочисленной оптимизации. В случае, когда допустимая область
ограничена, в ней может находиться лишь конечное множество точек с целочисленными координатами. Поэтому задача целочисленной оптимизации в ограниченной области в принципе может быть решена методом перебора, то есть путем вычисления значения целевой функции во всех допустимых точках и выбора из них точки (или точек) с оптимальными значениями критерия.
Содержание раздела
