slackvariabele

Een slackvariabele is een extra variabele die in lineaire programmering wordt ingevoerd om een ongelijkheid om te zetten in een gelijkheid, zodat standaardmethoden zoals de simplex-methode kunnen worden toegepast. Bij een programmeringsprobleem van de vorm: maximaliseer of minimaliseer c^T x onder de restricties A x ≤ b, x ≥ 0, kunnen de ongelijkheden worden geconverteerd door per ongelijkheid een slackvariabele s ≥ 0 toe te voegen, zodat A x + s = b. De slackvariabelen s geven de resterende of ongebruikte capaciteit aan bij elke restrictie.

De interpretatie is eenvoudig: elke s_i meet de hoeveelheid van hulpbron i die niet wordt gebruikt onder een gegeven oplossing. Als een oplossing de ongelijkheden precies vangt (geen resterende capaciteit), dan zijn de slackvariabelen nul.

Voorbeeld: bij de constraint 3x1 + 4x2 ≤ 12 voeg je een slackvariabele s1 ≥ 0 toe: 3x1 + 4x2 + s1 = 12. Wanneer x bepaalt wat er wordt geproduceerd en s1 positief is, blijft er nog capaciteit over.

Verschil met surplus- en artificiële variabelen: bij ≥-constraints wordt vaak een surplusvariabele gebruikt door A x − s = b, en soms is een artificiële variabele nodig om een beginpunt voor de methode te verkrijgen. Slackvariabelen maken samen met x de standaardvorm van het probleem en worden direct in de basis gebruikt in de beginoplossing.

Toepassingen liggen in resource allocation, productieplanning en algemene vormen van optimalisatie waarbij ongelijkheden voorkomen.