Omezení (matematika) - Constraint (mathematics)
![]() | Tento článek obsahuje a seznam doporučení, související čtení nebo externí odkazy, ale jeho zdroje zůstávají nejasné, protože mu chybí vložené citace.Září 2016) (Zjistěte, jak a kdy odstranit tuto zprávu šablony) ( |
v matematika, a omezení je podmínkou optimalizace problém, který musí řešení uspokojit. Existuje několik typů omezení - především rovnost omezení, nerovnost omezení a celočíselná omezení. Sada kandidátní řešení které splňují všechna omezení, se nazývá proveditelná sada.[1]
Příklad
Následuje jednoduchý problém s optimalizací:
podléhá
a
kde označuje vektor (x1, X2).
V tomto příkladu první řádek definuje funkci, která má být minimalizována (nazývá se Objektivní funkce, ztrátová funkce nebo nákladová funkce). Druhý a třetí řádek definují dvě omezení, z nichž první je omezení nerovnosti a druhé je omezení rovnosti. Tato dvě omezení jsou tvrdá omezení, což znamená, že je nutné, aby byli spokojeni; definují proveditelnou sadu kandidátských řešení.
Bez omezení by řešení bylo (0,0), kde má nejnižší hodnotu. Ale toto řešení neuspokojuje omezení. Řešení omezená optimalizace výše uvedený problém je , což je bod s nejmenší hodnotou který splňuje dvě omezení.
Terminologie
- Pokud platí omezení nerovnosti s rovnost v optimálním bodě se omezení říká vazba, jako bod nemůže měnit ve směru omezení, i když by to zlepšilo hodnotu objektivní funkce.
- Pokud omezení nerovnosti platí jako a přísná nerovnost v optimálním bodě (tj. nedrží se rovnosti) se omezení říká nezávazný, jako bod mohl se může měnit ve směru omezení, i když by to nebylo optimální. Za určitých podmínek, jako například v konvexní optimalizaci, pokud je omezení nezávazné, měl by problém s optimalizací stejné řešení i v případě, že by toto omezení neexistovalo.
- Pokud není omezení v daném bodě splněno, říká se, že bod je nemožné.
Tvrdá a měkká omezení
Pokud problém vyžaduje splnění omezení, jako ve výše uvedené diskusi, jsou omezení někdy označována jako tvrdá omezení. V některých problémech však tzv problémy s uspokojením flexibilních omezení, je upřednostňováno, ale není požadováno, aby byla splněna určitá omezení; taková nepovinná omezení jsou známá jako měkká omezení. Měkká omezení vznikají například v plánování založené na preferencích. V MAX-CSP problému může být porušeno několik omezení a kvalita řešení se měří počtem uspokojených omezení.
Globální omezení
Globální omezení[2] jsou omezení představující konkrétní vztah k celé řadě proměnných. Některé z nich, například úplně jiný
omezení, lze přepsat jako spojení atomových omezení v jednodušším jazyce: úplně jiný
omezení vydrží n proměnné , a je spokojen, pokud proměnné nabývají hodnot, které se párově liší. Je sémanticky ekvivalentní konjunkci nerovností . Další globální omezení rozšiřují expresivitu rámce omezení. V tomto případě obvykle zachycují typickou strukturu kombinatorických problémů. Například pravidelný
omezení vyjadřuje, že posloupnost proměnných je přijímána a deterministický konečný automat.
Používají se globální omezení[3] zjednodušit modelování problémy s uspokojením omezení, rozšířit expresivitu omezujících jazyků a také vylepšit rozlišení omezení: skutečně, když vezmeme v úvahu proměnné úplně, je možné v procesu řešení vidět nerealizovatelné situace dříve. Mnoho globálních omezení je odkazováno na online katalog.
Viz také
Reference
- ^ Takayama, Akira (1985). Matematická ekonomie (2. vyd.). New York: Cambridge University Press. p.61. ISBN 0-521-31498-4.
- ^ Rossi, Francesca; Van Beek, Peter; Walsh, Toby (2006). „7“. Příručka programování omezení (1. vyd.). Amsterdam: Elsevier. ISBN 9780080463643. OCLC 162587579.
- ^ Rossi, Francesca (2003). Principy a praxe programování omezení CP 2003 00: 9. mezinárodní konference, CP 2003, Kinsale, Irsko, 29. září, 3. října 2003. Sborník. Berlín: Springer-Verlag Berlin Heidelberg. ISBN 9783540451938. OCLC 771185146.
Další čtení
- Beveridge, Gordon S. G .; Schechter, Robert S. (1970). „Základní funkce v optimalizaci“. Optimalizace: Teorie a praxe. New York: McGraw-Hill. str. 5–8. ISBN 0-07-005128-3.