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

Ограничение (на английски: constraint) в математиката е условие в оптимизационна задача, което решението на задачата трябва да удовлетвори. Обикновено това е релация във вида на неравенство или равенство, но по-общо може да бъде всякакъв вид ограничително условие, което променливите на решението трябва да изпълнят (например, че решението трябва да е целочислено). Някои ограничения могат да са формулирани като логически преходи от вида if ... then ... else.

Множеството от кандидат-решения, които удовлетворяват всички ограничения на задачата, съставляват множество (област) от допустимите стойности.

„Твърди“ и „меки“ ограничения

Ако задачата изисква ограниченията да бъдат изцяло удовлетворени, в литературата се среща терминът „твърди ограничения“ (hard constraints). В някои задачи, наречени „гъвкави задачи за удовлетворяване на ограниченията“, за определени ограничения има препоръка, но не и изискване, да бъдат удовлетворени; такива незадължителни ограничения са известни като „меки ограничения“ (soft constraints).

Примери за задачи с меки ограничения са следните:

MAX-CSP (CSP от constraint satisfaction problem), са задачи за удовлетворяване на ограничения, където до определен брой ограничения се позволява да не бъдат изпълнени. Качеството на крайното решение се измерва по броя ограничения, които са изпълнени.
Претеглените задачи за удовлетворяване на ограниченията са задачи, в които спазването или неспазването на определено ограничение се претегля спрямо предварително дефинирани предпочитания (тегла). Крайното решение се определя по предварително определените предпочитания (тегла) на удовлетворените ограничения.
Размитите задачи за удовлетворяване на ограничения дефинират ограниченията като размити релации, и удовлетворяването на ограничение е непрекъсната функция, чиито стойности могат да варират от „напълно неудовлетворено ограничение“ (стойността „0“) до „напълно удовлетворено ограничение“ (стойността „1“).

Пример

Нека е дадена следната тривиална оптимизационна задача: Да се открият решенията, за които:

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

при условията

Неуспех при разбора (SVG (MathML може да се активира чрез браузърен плъгин): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/bg.wikipedia.org/v1/":): {\displaystyle x_1 \ge 1}

и

x_{2}=1,

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

Първият ред в примера дефинира функцията, която следва да бъде минимизирана (наричана целева функция, в някои задачи за математическа оптимизация – фитнес функция). Вторият и третият редове дефинират двете ограничения, първото от които във вид на неравенство, а вторият – във вид на равенство. И двете ограничения са „твърди“, т.е. трябва задължително да бъдат удовлетворени и те дефинират множеството от допустимите стойности за кандидат-решенията.

Без тези ограничения, решението би било векторът $\mathbf {x} =(0,0)$ , при който решението $f(\mathbf {x} )$ би било минимално възможното, 0. Това минимално решение обаче не удовлетворява двете дефинирания ограничения. Решението на задачата е векторът $\mathbf {x} =(1,1)$ , при който се получава минималната стойност на целевата функция $f(\mathbf {x} )$ при удовлетворени и двете ограничения.

Тази страница частично или изцяло представлява превод на страницата Constraint (mathematics) в Уикипедия на английски. Оригиналният текст, както и този превод, са защитени от Лиценза „Криейтив Комънс – Признание – Споделяне на споделеното“, а за съдържание, създадено преди юни 2009 година – от Лиценза за свободна документация на ГНУ. Прегледайте историята на редакциите на оригиналната страница, както и на преводната страница, за да видите списъка на съавторите.

ВАЖНО: Този шаблон се отнася единствено до авторските права върху съдържанието на статията. Добавянето му не отменя изискването да се посочват конкретни източници на твърденията, които да бъдат благонадеждни.