Surplusvariabelen

Surplusvariabelen zijn niet-negatieve variabelen die in lineaire programmering worden toegepast bij beperkingen van het type ≥. Het doel is om de ongelijkheid om te zetten naar een vergelijking, zodat het probleem kan worden geformuleerd in standaardvorm. Voor een beperking van de vorm a^T x ≥ b wordt deze doorgaans geschreven als a^T x − s = b, waarbij s ≥ 0 een surplusvariabele is.

Surplusvariabelen verschillen van slackvariabelen. Slackvariabelen worden toegevoegd aan ≤-beperkingen, zodat a^T x + s = b met s ≥ 0. De slackvariabele geeft aan hoeveel de linkerzijde onder de rechter zit, terwijl de surplusvariabele het overschot rechtzet zodat de vergelijking exact wordt. In beide gevallen geldt dat de variabele niet-negatief is en wordt gebruikt om ongelijkheden in gelijkheden om te zetten voor oplossingsmethoden zoals de simplex-methode.

Bij het oplossen van lineaire programmering kan het nodig zijn kunstmatige variabelen te introduceren om een beginwaardenoplossing te vinden, vooral bij beperkingen van het type ≥. In praktijk kan dit via een twee-fase-simplexmethode of de Big-M-methode, waarna de surplusvariabelen blijven bestaan in het model.

Voorbeeld: overweeg de beperking 3x1 + 2x2 ≥ 12 met x1, x2 ≥ 0. Introduceer een surplusvariabele s ≥ 0: 3x1 + 2x2 − s = 12. De surplusvariabele heft het overschot op zodat de vergelijking exact wordt. In de beginfase van de oplosprocedure is meestal een kunstmatige variabele nodig om een beginoplossing te vinden.