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

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

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

Пример [ править ]

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

{\ Displaystyle \ мин е (\ 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 е (\ mathbf {х})}$ ${\ Displaystyle \ mathbf {x} = (1,1)}$ ${\ Displaystyle е (\ mathbf {х})}$

Терминология [ править ]

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

Жесткие и мягкие ограничения [ править ]

Если проблема требует, чтобы ограничения были удовлетворены, как в вышеупомянутом обсуждении, ограничения иногда называют жесткими ограничениями . Однако в некоторых задачах, называемых проблемами удовлетворения гибких ограничений , предпочтительно, но не требуется, чтобы выполнялись определенные ограничения; такие необязательные ограничения известны как мягкие ограничения . Мягкие ограничения возникают, например, при планировании на основе предпочтений . В задаче 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], чтобы упростить моделирование проблем удовлетворения ограничений , расширить выразительность языков ограничений, а также улучшить разрешение ограничений : действительно, рассматривая все переменные в целом, недопустимые ситуации можно увидеть раньше в процессе решения . Многие из глобальных ограничений указаны в онлайн-каталоге.

См. Также [ править ]

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

Ссылки [ править ]

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

Дальнейшее чтение [ править ]

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

Внешние ссылки [ править ]

FAQ по нелинейному программированию
Глоссарий математического программирования

[1] Такаяма, Акира (1985). Математическая экономика (2-е изд.). Нью-Йорк: Издательство Кембриджского университета. п. 61 . ISBN 0-521-31498-4.

[2] Росси, Франческа; Ван Бик, Питер; Уолш, Тоби (2006). «7». Справочник по программированию в ограничениях (1-е изд.). Амстердам: Эльзевир. ISBN 9780080463643. OCLC 162587579 .

[3] Росси, Франческа (2003). Принципы и практика программирования ограничений CP 2003 00: 9-я Международная конференция, CP 2003, Кинсейл, Ирландия, 29 сентября 3 октября 2003 г. Протоколы . Берлин: Springer-Verlag Berlin Heidelberg. ISBN 9783540451938. OCLC 771185146 .

[1]