Slack variabel

I ett optimeringsproblem är en slack-variabel en variabel som läggs till en ojämlikhetsbegränsning för att omvandla den till en jämlikhet. Införande av en slack-variabel ersätter en ojämlikhetsrestriktion med en likhetsrestriktion och en icke-negativitetsrestriktion på slack-variabeln.

Slack-variabler används särskilt vid linjär programmering . Liksom med de andra variablerna i de utökade begränsningarna kan slack-variabeln inte anta negativa värden, eftersom simplexalgoritmen kräver att de är positiva eller noll.

• Om en slack-variabel associerad med en begränsning är noll vid en viss kandidatlösning , är begränsningen bindande där, eftersom begränsningen begränsar de möjliga ändringarna från den punkten .
• Om en slack-variabel är positiv vid en viss kandidatlösning, är begränsningen icke-bindande där, eftersom begränsningen inte begränsar de möjliga ändringarna från den punkten.
• Om en slack-variabel är negativ någon gång, är punkten omöjlig (inte tillåten), eftersom den inte uppfyller begränsningen.

Slack-variabler används också i Big M-metoden .

Exempel

Genom att introducera slackvariabeln $\mathbf {s} \geq \mathbf {0}$ , olikheten $\mathbf {A} \mathbf {x} \leq \mathbf {b}$ kan konverteras till ekvationen $\mathbf {A} \mathbf {x} +\mathbf {s} =\mathbf {b}$ .

Inbäddning i orthant

Ytterligare information: Orthant och generaliserade barycentriska koordinater

Slackvariabler ger en inbäddning av en polytop $P\hookrightarrow (\mathbf {R} _{\geq 0})^{f}$ i standarden f - orthant , där ${\ displaystyle f}$ är antalet begränsningar (facetter av polytopen). Denna karta är en-till-en (slack-variabler bestäms unikt) men inte på (inte alla kombinationer kan realiseras) och uttrycks i termer av begränsningarna ( linjära funktionaler, kovektorer).

Slack-variabler är dubbla till generaliserade barycentriska koordinater , och dubbelt till generaliserade barycentriska koordinater (som inte är unika men alla kan realiseras) är unikt bestämda, men kan inte alla realiseras.

Dubbelt uttrycker generaliserade barycentriska koordinater en polytop med $n$ hörn (dual to facetter), oavsett dimension, som bilden av standarden $(n-1)$ -simplex, som har $n$ hörn – kartan är på: $\Delta ^{n-1}\twoheadrightarrow P,$ och uttrycker punkter i termer av hörn (punkter, vektorer) . Kartan är en-till-en om och endast om polytopen är en simplex, i vilket fall kartan är en isomorfism; detta motsvarar en punkt som inte har unika generaliserade barycentriska koordinater.

externa länkar

• Slack Variable Tutorial - Lös slack variabel problem online