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

редактировать

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

Содержание

1 Пример
2 Терминология
3 Жесткие и мягкие ограничения
4 Глобальные ограничения
5 См. также
6 Ссылки
7 Дополнительная литература
8 Внешние ссылки

Пример

Следующая простая задача оптимизации:

min f (x) знак равно x 1 2 + x 2 4 {\ displaystyle \ min f (\ mathbf {x}) = x_ {1} ^ {2} + x_ {2} ^ {4}}

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

с учетом

x 1 ≥ 1 {\ displaystyle x_ {1} \ geq 1}

{\ displaystyle x_ {1} \ geq 1}

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

{\ displaystyle x_ {2} = 1,}

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

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

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

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

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

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

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

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

Глобальные ограничения - это ограничения, представляющие конкретное отношение для ряда переменных, взятых вместе. Некоторые из них, такие как ограничение alldifferent, можно переписать как соединение атомарных ограничений на более простом языке: ограничение alldifferentвыполняется для n переменных $х 1... x n {\ displaystyle x_ {1}... x_ {n}}$ ${\ displaystyle x_ {1}... x_ {n}}$ , и выполняется, если переменные принимают значения, которые попарно различны. Он семантически эквивалентен конъюнкции неравенств $x 1 ≠ x 2, x 1 ≠ x 3..., Икс 2 ≠ Икс 3, Икс 2 ≠ Икс 4... xn - 1 ≠ xn {\ 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}}$ ${\ 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 выражает, что последовательность переменных принимается детерминированным конечным автоматом.

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

См. Также

Ссылки

Дополнительная литература

Beveridge, Gordon SG; Шехтер, Роберт С. (1970). «Основные возможности оптимизации». Оптимизация: теория и практика. Нью-Йорк: Макгроу-Хилл. С. 5–8. ISBN 0-07-005128-3.

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