Povolená proměnná - Slack variable

V optimalizační problém, a volná proměnná je proměnná, která je přidána k omezení nerovnosti transformovat to do rovnosti. Zavedení proměnné slack nahradí omezení nerovnosti omezením rovnosti a omezením negativity na proměnné slack.^[1]^:131

Uvolněné proměnné se používají zejména v lineární programování. Stejně jako u ostatních proměnných v rozšířených omezeních, proměnná slack nemůže mít záporné hodnoty jako simplexní algoritmus vyžaduje, aby byly kladné nebo nulové.^[2]

Pokud je proměnná uvolnění spojená s omezením nula konkrétně kandidátní řešení, omezení je vazba protože omezení omezuje možné změny od tohoto bodu.
Pokud je proměnná ochabnutí pozitivní u konkrétního kandidátského řešení je omezení nezávazný tam, protože omezení neomezuje možné změny od tohoto bodu.
Pokud je proměnná ochabnutí negativní v určitém okamžiku jde o to nemožné (není povoleno), protože nesplňuje omezení.

Příklad

Zavedením proměnné slack ${displaystyle mathbf {y} geq mathbf {0}}$ nerovnost ${displaystyle mathbf {A} mathbf {x} leq mathbf {b}}$ lze převést na rovnici ${displaystyle mathbf {A} mathbf {x} + mathbf {y} = mathbf {b}}$ .

Vkládání do orthantu

Slack proměnné dávají vložení a polytop ${displaystyle Phookrightarrow (mathbf {R} _ {geq 0}) ^ {f}}$ do standardu F-orthant, kde F je počet omezení (fazet mnohostěnu). Tato mapa je one-to-one (slack proměnné jsou jednoznačně určeny), ale ne na (ne všechny kombinace mohou být realizovány), a je vyjádřena v podmínkách omezení (lineární funkcionálové, vektory).

Slabé proměnné jsou dvojí na zobecněné barycentrické souřadnice, a duálně na zobecněné barycentrické souřadnice (které nejsou jedinečné, ale lze je realizovat všechny), jsou jednoznačně určeny, ale nelze je všechny realizovat.

Zobecněné barycentrické souřadnice vyjadřují polytop s n vrcholy (duální na fazety), bez ohledu na rozměr, jako obraz normy ${displaystyle (n-1)}$ -simplex, který má n vrcholy - mapa je na: ${displaystyle Delta ^ {n-1} woheadrightarrow P,}$ a vyjadřuje body ve smyslu vrcholy (body, vektory). Mapa je jedna k jedné právě tehdy, je-li mnohostěn simplexní, v takovém případě je mapa izomorfismem; to odpovídá bodu, který nemá unikátní zobecněné barycentrické souřadnice.

Reference

^ Boyd, Stephen P .; Vandenberghe, Lieven (2004). Konvexní optimalizace (pdf). Cambridge University Press. ISBN 978-0-521-83378-3. Citováno 15. října 2011.CS1 maint: ref = harv (odkaz)
^ Gärtner, Bernd; Matoušek, Jiří (2006). Porozumění a používání lineárního programování. Berlín: Springer. ISBN 3-540-30697-8.^:42

externí odkazy

Slack Variable Tutorial - Vyřešte problémy s proměnlivou rezervou online

[1] Boyd, Stephen P .; Vandenberghe, Lieven (2004). Konvexní optimalizace (pdf). Cambridge University Press. ISBN 978-0-521-83378-3. Citováno 15. října 2011.CS1 maint: ref = harv (odkaz)

[2] Gärtner, Bernd; Matoušek, Jiří (2006). Porozumění a používání lineárního programování. Berlín: Springer. ISBN 3-540-30697-8.^:42

[1]

[2]