Ограничение (математика)

Условие задачи оптимизации, которому должно удовлетворять решение

В математике ограничение — это условие задачи оптимизации , которому должно удовлетворять решение. Существует несколько типов ограничений — в первую очередь ограничения равенства , ограничения неравенства и целочисленные ограничения . Набор возможных решений, удовлетворяющих всем ограничениям, называется допустимым набором . ^[1]

Пример

Ниже приведена простая задача оптимизации:

${\displaystyle \min f(\mathbf {x} )=x_{1}^{2}+x_{2}^{4}}$

при условии

${\displaystyle x_{1}\geq 1}$

и

${\displaystyle x_{2}=1,}$

где обозначает вектор ( x ₁ , x ₂ ). ${\displaystyle \mathbf {x} }$

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

Без ограничений решение было бы (0,0), где имеет наименьшее значение. Но это решение не удовлетворяет ограничениям. Решением задачи ограниченной оптимизации, указанной выше, является , что является точкой с наименьшим значением , удовлетворяющим двум ограничениям. ${\displaystyle f(\mathbf {x} )}$ ${\displaystyle \mathbf {x} =(1,1)}$ ${\displaystyle f(\mathbf {x} )}$

Терминология

• Если ограничение неравенства выполняется с равенством в оптимальной точке, то говорят, что ограничениесвязывание , поскольку точкане можетизменяться в направлении ограничения, даже если это улучшит значение целевой функции.
• Если ограничение-неравенство выполняется как строгое неравенство в оптимальной точке (то есть не выполняется при равенстве), то говорят, что ограничение выполняется.необязательный , так как точкаможетизменяться в направлении ограничения, хотя это не было бы оптимальным. При определенных условиях, например, в выпуклой оптимизации, если ограничение не является обязательным, задача оптимизации будет иметь то же самое решение даже при отсутствии этого ограничения.
• Если ограничение не выполняется в заданной точке, то эта точка считается невыполнимой .

Жесткие и мягкие ограничения

Если задача требует, чтобы ограничения были удовлетворены, как в приведенном выше обсуждении, то ограничения иногда называют жесткими ограничениями . Однако в некоторых задачах, называемых задачами удовлетворения гибких ограничений , предпочтительно, но не обязательно, чтобы определенные ограничения были удовлетворены; такие необязательные ограничения известны как мягкие ограничения . Мягкие ограничения возникают, например, при планировании на основе предпочтений . В задаче MAX-CSP допускается нарушение ряда ограничений, а качество решения измеряется количеством удовлетворенных ограничений.

Глобальные ограничения

Глобальные ограничения ^[2] — это ограничения, представляющие собой определенное отношение на ряде переменных, взятых вместе. Некоторые из них, такие как ограничение alldifferent, можно переписать как конъюнкцию атомарных ограничений на более простом языке: alldifferentограничение выполняется на n переменных и выполняется, если переменные принимают значения, которые попарно различны. Это семантически эквивалентно конъюнкции неравенств . Другие глобальные ограничения расширяют выразительность структуры ограничений. В этом случае они обычно охватывают типичную структуру комбинаторных задач. Например, ограничение выражает, что последовательность переменных принимается детерминированным конечным автоматом . ${\displaystyle x_{1}...x_{n}}$ ${\displaystyle x_{1}\neq x_{2},x_{1}\neq x_{3}...,x_{2}\neq x_{3},x_{2}\neq x_{4}...x_{n-1}\neq x_{n}}$regular

Глобальные ограничения используются ^[3] для упрощения моделирования проблем удовлетворения ограничений , для расширения выразительности языков ограничений, а также для улучшения разрешения ограничений : действительно, рассматривая переменные в целом, недопустимые ситуации можно увидеть раньше в процессе решения. Многие из глобальных ограничений ссылаются на онлайн-каталог.

Смотрите также

• Алгебра ограничений
• Условия Каруша-Куна-Таккера
• Множители Лагранжа
• Уровень установлен
• Линейное программирование
• Нелинейное программирование
• Ограничение
• Выполнимость по модулю теории

Ссылки

1. Такаяма, Акира (1985). Математическая экономика (2-е изд.). Нью-Йорк: Cambridge University Press. стр. 61. ISBN 0-521-31498-4.
2. Росси, Франческа; Ван Бик, Питер; Уолш, Тоби (2006). "7". Справочник по программированию в ограничениях (1-е изд.). Амстердам: Elsevier. ISBN 9780080463643. OCLC  162587579.
3. Росси, Франческа (2003). Принципы и практика программирования в ограничениях CP 2003 00 : 9-я международная конференция, CP 2003, Кинсейл, Ирландия, 29 сентября — 3 октября 2003 г. Труды . Берлин: Springer-Verlag Berlin Heidelberg. ISBN 9783540451938. OCLC  771185146.

Дальнейшее чтение

• Беверидж, Гордон СГ; Шехтер, Роберт С. (1970). "Основные черты оптимизации". Оптимизация: теория и практика . Нью-Йорк: McGraw-Hill. С. 5–8. ISBN 0-07-005128-3.

Внешние ссылки

• Часто задаваемые вопросы по нелинейному программированию Архивировано 30 октября 2019 г. на Wayback Machine
• Глоссарий математического программирования Архивировано 28.03.2010 на Wayback Machine