slack variable

Angol

Főnév

slack variable (tsz. slack variables)

(informatika) A slack variable (magyarul: tartalék változó, megengedett többlet) egy kulcsfontosságú fogalom a lineáris programozásban, különösen a szimplex algoritmus alkalmazása során. A slack változó lehetővé teszi, hogy az egyenlőtlenségi korlátokat (≤ típusú feltételeket) egyenlőségekké alakítsuk, így a probléma standard formáját elérjük, amely elengedhetetlen a szimplex módszer végrehajtásához.

1. A slack változó fogalma

Egy slack változó kifejezi, mennyivel kisebb a bal oldal, mint a jobb oldal egy „≤” típusú korlátnál.

Példa:

$2x+3y\leq 8$

Bevezetünk egy slack változót: ${\textstyle s\geq 0}$ , hogy:

$2x+3y+s=8$

Itt a ${\textstyle s}$ megmutatja a „szabad helyet” – azt a többletet, amit még felhasználhatnánk a korlát elérése előtt.

2. Miért van rá szükség?

A lineáris programozási problémákat a szimplex algoritmus csak akkor tudja megoldani, ha minden feltétel egyenlőségként van megadva.

A valós problémákban azonban gyakoriak az egyenlőtlenségek:

Erőforrás korlátok: „legfeljebb 100 egység”
Időkeretek: „nem haladhatja meg az 5 órát”
Kapacitás: „legfeljebb 200 kg”

Ezeket egyenlőséggé alakítjuk slack változók bevezetésével.

3. Átalakítás standard formára

A standard forma a szimplex módszerhez:

Cél: maximalizálás
Minden korlát: egyenlőség
Minden változó: nemnegatív

Egy „≤” típusú feltételhez egy pozitív slack változót adunk:

$a_{1}x_{1}+a_{2}x_{2}\leq b\quad \Rightarrow \quad a_{1}x_{1}+a_{2}x_{2}+s=b,\quad s\geq 0$

4. Példa teljes linearizálásra

Eredeti probléma:

Maximalizálandó:

$Z=3x+2y$

Feltételek:

$x+y\leq 42x+y\leq 5x,y\geq 0$

Slack változókkal:

$x+y+s_{1}=42x+y+s_{2}=5x,y,s_{1},s_{2}\geq 0$

Most már egy standard formában lévő lineáris programot kapunk, amely egyenlőségeket tartalmaz, és így alkalmazható rá a szimplex módszer.

5. Grafikus jelentés

Grafikusan a slack változó a távolság a pont és a korlát határvonala között.

Ha egy korlát:

$x+y\leq 4$

és az aktuális megoldás ${\textstyle x=1,y=2}$ , akkor:

$1+2=3\Rightarrow {\text{a korlát „nem teljesen kihasznált”}}\Rightarrow s_{1}=1$

Ha a megoldás pontosan a korlát határán van, pl. ${\textstyle x=2,y=2}$ , akkor:

$2+2=4\Rightarrow s_{1}=0\Rightarrow {\text{korlát teljesen kihasználva}}$

6. Értelmezés az optimalizálás után

A megoldásban:

Ha egy slack változó ${\textstyle s=0}$ : az adott korlát aktív, azaz szűk keresztmetszet
Ha ${\textstyle s>0}$ : a korlát nem aktív, még lenne „hely”

Ez fontos a dualitás és az árnyékárak (shadow prices) elemzésekor.

7. Slack vs. Surplus változó

Slack változó: „≤” típusú korlátnál, pozitív értéket ad hozzá
Surplus változó: „≥” típusú korlátnál, negatív irányban korrigál

Példa:

$x+y\geq 6\Rightarrow x+y-e=6,\quad e\geq 0$

Itt az ${\textstyle e}$ a surplus variable

8. C++ példa – slack változók bevezetése

Ez egy egyszerű struktúra, nem a teljes szimplex implementáció, csak a slack modellezése:

#include <iostream>
#include <vector>

struct Constraint {
    double a, b, rhs;
    char inequality; // '<' vagy '>'

    void standardize() {
        if (inequality == '<') {
            std::cout << a << "x + " << b << "y + s = " << rhs << "\n";
        } else if (inequality == '>') {
            std::cout << a << "x + " << b << "y - e = " << rhs << "\n";
        }
    }
};

int main() {
    Constraint c1 = {2, 3, 8, '<'};
    Constraint c2 = {1, 4, 10, '>'};

    std::cout << "Standard form:\n";
    c1.standardize();
    c2.standardize();

    return 0;
}

9. Slack változók szerepe a szimplex táblázatban

A slack változók kezdetben a bázisban vannak, azaz:

A rendszer azonnal kielégíti az egyenlőségeket, ha minden döntési változó nulla
Ez ad egy kezdeti megengedett sarokpontot
A szimplex ezt fogja tovább optimalizálni

10. Összefoglalás

A slack változó:

Segít átalakítani egyenlőtlenségi feltételeket egyenlőségekké
Lehetővé teszi a szimplex algoritmus alkalmazását
Jelentése: „mennyi maradék van még” egy korláton belül
Ha nulla → korlát éppen kihasznált
Ha pozitív → van „tartalék”, a korlát nem szoros

Gyakorlatban: Ha látod, hogy egy korláthoz tartozó slack változó 0, az azt jelzi, hogy az a korlát korlátozó tényező (binding constraint).

További információk

slack variable - Szótár.net (en-hu)
slack variable - Sztaki (en-hu)
slack variable - Merriam–Webster
slack variable - Cambridge
slack variable - WordNet
slack variable - Яндекс (en-ru)
slack variable - Google (en-hu)
slack variable - Wikidata
slack variable - Wikipédia (angol)