Magyar

Kiejtés

IPA: [ ˈopɛraːt͡sijoːkutɒtaːʃ]

Főnév

operációkutatás

(matematika) Az operációkutatás (angolul Operations Research, rövidítve OR) egy multidiszciplináris tudományág, amely matematikai, statisztikai és algoritmikus módszerekkel segít döntéshozatali problémák megoldásában. Ezt az elemzési folyamatot különösen olyan helyzetekben alkalmazzák, ahol komplex rendszerek optimalizálására van szükség. Az operációkutatás eszközei az üzleti élet, az ipar, a közlekedés, a logisztika, a pénzügy, a katonai stratégia és számos más területen hasznosak.

Történeti háttér

Az operációkutatás a második világháború alatt indult fejlődésnek, amikor a hadseregek hatékonyabb működéséhez és a források optimális felhasználásához kezdtek matematikai modelleket alkalmazni. A háború után az ipar és az üzleti élet is felismerte az operációkutatásban rejlő lehetőségeket, így a tudományág gyorsan elterjedt.

Alapfogalmak és módszerek

Az operációkutatás alapja a döntési folyamatok modellezése és optimalizálása. Ehhez különböző matematikai módszereket alkalmaznak:

1. Lineáris programozás

Ez az egyik legismertebb módszer, amely lineáris egyenletekkel és egyenlőtlenségekkel ír le egy problémát. A cél egy célfüggvény maximalizálása vagy minimalizálása adott korlátok között. Például a gyártási költségek minimalizálása vagy a profit maximalizálása.

2. Egészértékű programozás

Ez a módszer akkor használatos, ha a változók csak egész értékeket vehetnek fel, például ha egy gyárban gépek számát vagy termékek darabszámát kell optimalizálni.

3. Dinamikus programozás

Ez a technika olyan problémák megoldására szolgál, amelyek több, egymást követő döntési lépést tartalmaznak. Ilyen például az erőforrások elosztása hosszabb időszak alatt.

4. Hálózatelemzés

A hálózati modellek (például gráfok) alkalmazása segít az olyan problémák megoldásában, mint az útvonaltervezés, az ellátási lánc optimalizálása, vagy a kommunikációs hálózatok tervezése.

5. Sztochasztikus modellezés

Ez a módszer véletlenszerű változókat is figyelembe vesz a döntési problémákban, például ha a kereslet vagy az erőforrások rendelkezésre állása bizonytalan.

6. Szimuláció

A szimuláció a valós rendszer viselkedésének modellezésére szolgál, hogy a döntéshozók megértsék a lehetséges kimeneteleket különböző forgatókönyvek alapján. Ez különösen hasznos komplex rendszerek esetén.

Az operációkutatás folyamata

Az operációkutatásban általában az alábbi lépések mentén haladnak:

Probléma azonosítása: Pontos meghatározás, hogy milyen döntési problémát kell megoldani.
Modellezés: Matematikai modell kidolgozása, amely leírja a problémát.
Adatgyűjtés: A modell inputadatainak összegyűjtése, például költségek, erőforrások, kereslet stb.
Megoldási módszer kiválasztása: A megfelelő matematikai vagy algoritmikus módszer alkalmazása.
Elemzés: Az eredmények értelmezése és a döntési javaslatok megfogalmazása.
Implementálás: A megoldások gyakorlati bevezetése.
Ellenőrzés: Az eredmények hatékonyságának nyomon követése és szükség szerinti finomhangolás.

Alkalmazási területek

1. Gyártás és termelés

Termelési ütemezés: Az operációkutatás segít az optimális gyártási sorrend meghatározásában.
Költségminimalizálás: Az erőforrások hatékony elosztása a termelési költségek csökkentésére.

2. Logisztika és szállítmányozás

Útvonaloptimalizálás: Hatékony útvonaltervezés a szállítási költségek csökkentésére.
Raktározás: Az optimális készletszintek meghatározása.

3. Pénzügy

Portfóliókezelés: Befektetési stratégiák optimalizálása a hozam maximalizálása és a kockázat minimalizálása érdekében.
Cash flow kezelése: Rövid- és hosszú távú pénzügyi tervezés.

4. Közlekedés

Menetrend-tervezés: Az autóbuszok, vonatok vagy repülőgépek ütemezése az utasforgalom optimalizálására.
Forgalomirányítás: A közúti forgalom áramlásának javítása.

5. Egészségügy

Erőforrás-allokáció: Kórházi ágyak, orvosi személyzet és berendezések optimális elosztása.
Járványkezelés: A vakcinázási stratégiák és készletek elosztása.

Példák a gyakorlatból

Légi közlekedés: Légitársaságok operációkutatási modellekkel tervezik a járatok menetrendjét, a repülőgépek elosztását és az üzemanyag-használatot.
Szállítmányozás: Futárcégek, például a DHL vagy a FedEx, algoritmusokat alkalmaznak az útvonalak optimalizálására.
Kiskereskedelem: Az üzletek készletezési és árképzési stratégiáihoz szimulációkat és prediktív modelleket használnak.

Kihívások

Adatminőség: Pontos és releváns adatok nélkül a modellek nem működnek hatékonyan.
Modellezési bonyolultság: Sok probléma túl komplex ahhoz, hogy egyszerű modellekkel leírható legyen.
Implementációs nehézségek: A gyakorlati alkalmazás sokszor ellenállásba ütközik a vállalatokon belül.

Jövőbeli irányok

Az operációkutatás fejlődése szorosan kapcsolódik a technológia fejlődéséhez, különösen a mesterséges intelligenciához és a big data elemzéshez. Az automatizált döntéshozatali rendszerek, az adatvezérelt optimalizáció, valamint a valós idejű szimulációk mind új lehetőségeket nyitnak meg.

Operációkutatási módszerek összefoglaló

1. Lineáris programozás – Szimplex módszer

A lineáris programozási feladat célja egy lineáris célfüggvény optimalizálása (maximalizálása vagy minimalizálása) adott lineáris korlátozások mellett. Formálisan: válasszuk meg az ${\textstyle x_{1},x_{2},...,x_{n}}$ változókat úgy, hogy kielégítsék a korlátozó egyenlőtlenségeket/egyenleteket (pl. ${\textstyle a_{11}x_{1}+...+a_{1n}x_{n}\leq b_{1}}$ , …, ${\textstyle a_{m1}x_{1}+...+a_{mn}x_{n}\leq b_{m}}$ ), és a ${\textstyle z=c_{1}x_{1}+...+c_{n}x_{n}}$ célfüggvény értéke a lehető legjobb (legnagyobb vagy legkisebb) legyen. A korlátozások által meghatározott lehetséges megoldások halmaza egy sokdimenziós poliéder (konvex halmaz), amely véges számú sarokponttal (csúcsponttal) rendelkezik. Alapvető tény, hogy ha létezik optimális megoldás, akkor legalább egy optimumban a változók olyan kombinációja adja, ami egy ilyen csúcspontnak felel meg (ezt nevezzük bázismegoldásnak vagy alapmegoldásnak). Ez azt jelenti, hogy az optimális megoldás megtalálható a korlátozások metszéspontjainál.

Szimplex módszer: A George Dantzig nevéhez fűződő szimplex algoritmus ezen elvből kiindulva működik: egy csúcspontból indulva lépésenként egy szomszédos csúcspontba lép át, mindig javítva (vagy legalább nem rontva) a célfüggvény értékét. Mivel véges csúcs van, az eljárás véges lépésben eléri az optimumot (ha az létezik). A szimplex algoritmus így iteratív keresési eljárás a lehetséges megoldások között, amely során mindig egy bázisváltozó cserélődik ki egy nem-bázis változóval, javítva a célértéket. A módszer lépései a következők:

Standard alak és kezdő bázismegoldás: A lineáris programot standard formára hozzuk. Maximalizálási feladatnál minden korlátot ${\textstyle \leq }$ alakúra hozunk és hozzájuk új slack (felesleg) változókat vezetünk be, hogy egyenlőségekké alakítsuk. Például ${\textstyle x_{1}+x_{2}\leq 5}$ korlát esetén bevezetjük ${\textstyle s_{1}}$ slack változót, és írjuk ${\textstyle x_{1}+x_{2}+s_{1}=5}$ . A slack változók kezdő értéke a jobb oldali ${\textstyle b_{i}}$ , míg az eredeti ${\textstyle x_{j}}$ döntési változók kezdetben 0 értékűek. Így induláskor könnyen adódik egy kezdő bázismegoldás, ahol a bázis változók a slack változók (identitásmátrixot alkotva). A kezdő megoldás célfüggvényértékét kiszámítjuk.
Relatív profitok (iránymenti deriváltak) számítása: Meghatározzuk, hogy a nem-bázis változók közül melyik javítaná a célfüggvény értékét, ha növelnénk. Maximalizálásnál ez úgy történik, hogy kiszámítjuk az ún. relatív profitokat vagy csökkentett költségeket. A szimplex táblában ez a célfüggvény sorban lévő együtthatók vizsgálatát jelenti. Ha van pozitív együttható (mert maximalizálunk), az jelzi, hogy a hozzátartozó változó növelése növeli ${\textstyle z}$ értékét. Közülük kiválasztjuk a legnagyobb pozitív együtthatójú változót – legyen ez ${\textstyle x_{k}}$ –, és ezt visszük be a bázisba. Ezt hívjuk belépő változónak.
Minimális hányados teszt (kilépő változó): Megvizsgáljuk, hogy a belépő ${\textstyle x_{k}}$ változó milyen mértékben növelhető anélkül, hogy bármelyik jelenlegi bázisváltozó negatívvá válna (feasible region-en kívülre lépnénk). Számoljuk ki minden korlátra a ${\textstyle {\frac {{\text{aktuális }}b_{i}}{{\text{pivot oszlop }}a_{ik}}}}$ hányadost – ahol ${\textstyle a_{ik}}$ az ${\textstyle i}$ -edik egyenletben a belépő változó együtthatója, és a hányados számítása csak pozitív ${\textstyle a_{ik}}$ esetén értelmes. A legkisebb ilyen hányados mutatja, melyik bázisváltozó fog először nullára csökkenni, ha ${\textstyle x_{k}}$ -t növeljük. Ennek a korlátnak a bázisváltozója lesz a kilépő változó, amelyet ${\textstyle x_{k}}$ kiszorít a bázisból.
Pivot lépés (báziscseréje): A belépő és kilépő változó indexe meghatározza a pivot elemet a szimplex táblázatban. A pivot elem segítségével elemi sortranszformációkkal új bázismegoldást számítunk ki. A pivot sorát osztjuk a pivot elem értékével (így az új bázisváltozó együtthatója 1 lesz), majd a többi sorból kivonjuk a pivot sor megfelelő többszörösét, hogy az új változó oszlopában minden más helyen 0 legyen. Ezzel elérjük, hogy az ${\textstyle x_{k}}$ belépő változó bekerüljön a bázisba, a kilépő változó pedig nullára csökken és kikerül a bázisból.
Ismétlés vagy befejezés: Az új szimplex táblázatban ismét kiszámítjuk a relatív profitokat. Ha van még pozitív együttható a célfüggvény sorban, visszatérünk a 2. lépéshez egy új belépő változóval. Ha nincs pozitív (maximalizálásnál) – azaz minden relatív profit ${\textstyle \leq 0}$ –, akkor az aktuális bázismegoldás optimális, az algoritmus leáll. (Minimalizálásnál fordított az optimálási feltétel előjele.)

Példa: Legyen a feladat: ${\textstyle \max z=5x_{1}+4x_{2}}$ Korlátok:

${\begin{cases}x_{1}+x_{2}\leq 5,\\3x_{1}+2x_{2}\leq 12,\\x_{1},x_{2}\geq 0~.\end{cases}}$

A standard formához vezessünk be ${\textstyle s_{1},s_{2}}$ slack változókat: ${\textstyle x_{1}+x_{2}+s_{1}=5}$ ${\textstyle 3x_{1}+2x_{2}+s_{2}=12}$ Kezdetben ${\textstyle x_{1}=x_{2}=0}$ , így ${\textstyle s_{1}=5}$ , ${\textstyle s_{2}=12}$ ad egy kezdeti bázismegoldást ( ${\textstyle z=0}$ ). Az induló szimplex táblázat:

Bázis	${\textstyle x_{1}}$	${\textstyle x_{2}}$	${\textstyle s_{1}}$	${\textstyle s_{2}}$	RHS (b)
${\textstyle s_{1}}$	1	1	1	0	5
${\textstyle s_{2}}$	3	2	0	1	12
Cél	5	4	0	0	0

Itt a célfüggvény sor ( ${\textstyle C_{j}-Z_{j}}$ értékek) az ${\textstyle x_{1}}$ és ${\textstyle x_{2}}$ változóknál rendre 5 és 4, vagyis mindkettő pozitív. A legnagyobb pozitív a ${\textstyle x_{1}}$ oszlophoz tartozik (5), tehát ${\textstyle x_{1}}$ lesz a belépő változó. A pivot oszlop ${\textstyle x_{1}}$ oszlopa; a min hányadosok: sor1: ${\textstyle 5/1=5}$ , sor2: ${\textstyle 12/3=4}$ . A kisebbik 4, a második sorban, tehát ${\textstyle s_{2}}$ (a 2. sor bázisváltozója) lesz a kilépő. Pivot elem: 3 (a ${\textstyle s_{2}}$ sor és ${\textstyle x_{1}}$ oszlop metszete). Elosztjuk a 2. sort 3-mal, majd kivonjuk az 1. sorból egyszer a 2. sort, hogy az ${\textstyle x_{1}}$ oszlopban felül is 0 legyen:

Új táblázat az 1. iteráció után:

Bázis	${\textstyle x_{1}}$	${\textstyle x_{2}}$	${\textstyle s_{1}}$	${\textstyle s_{2}}$	RHS
${\textstyle s_{1}}$	0	${\textstyle 1-{\frac {2}{3}}={\frac {1}{3}}}$	${\textstyle 1-{\frac {1}{3}}={\frac {2}{3}}}$	${\textstyle -{\frac {1}{3}}}$	${\textstyle 5-4=1}$
${\textstyle x_{1}}$	1	${\textstyle {\frac {2}{3}}}$	${\textstyle 0+{\frac {1}{3}}={\frac {1}{3}}}$	${\textstyle {\frac {1}{3}}}$	${\textstyle 4}$
Cél	0	${\textstyle 4-{\frac {10}{3}}={\frac {2}{3}}}$	${\textstyle 0+{\frac {0}{3}}=0}$	${\textstyle 0+{\frac {0}{3}}=0}$	${\textstyle 20}$

Az új bázismegoldás: ${\textstyle x_{1}=4}$ , ${\textstyle s_{1}=1}$ , ${\textstyle x_{2}=0}$ , ${\textstyle s_{2}=0}$ , ami ${\textstyle z=5(4)+4(0)=20}$ értéket ad. A célfüggvény sor most ${\textstyle x_{2}}$ -nél ${\textstyle {\frac {2}{3}}}$ (pozitív), így még tudunk javítani ${\textstyle x_{2}}$ bevitelével. ${\textstyle x_{2}}$ lesz a belépő változó; pivot oszlopa ${\textstyle x_{2}}$ ; a min hányados teszt: sor1: ${\textstyle 1/(1/3)=3}$ , sor2: ${\textstyle 4/({\frac {2}{3}})=6}$ . Kisebb a 3 (1. sor), tehát ${\textstyle s_{1}}$ lép ki. Pivot elem ${\textstyle 1/3}$ (első sor ${\textstyle x_{2}}$ oszlopa). Pivotálás: az 1. sort szorozzuk 3-mal (így ${\textstyle x_{2}}$ együtthatója 1 lesz), majd a 2. sorból kivonjuk a (2/3)-szorosát az 1. sornak:

Végül kapjuk a 2. iteráció utáni táblát (optimális):

Bázis	${\textstyle x_{1}}$	${\textstyle x_{2}}$	${\textstyle s_{1}}$	${\textstyle s_{2}}$	RHS
${\textstyle x_{2}}$	${\textstyle 0+3*0=0}$	1	${\textstyle 3*1-1=2}$	${\textstyle 3*(-1)=-3}$	${\textstyle 3}$
${\textstyle x_{1}}$	${\textstyle 1-{\frac {2}{3}}*0=1}$	0	${\textstyle {\frac {1}{3}}-{\frac {2}{3}}*1=-{\frac {1}{3}}}$	${\textstyle {\frac {1}{3}}-{\frac {2}{3}}*(-1)=1}$	${\textstyle 2}$
Cél	${\textstyle 0+{\frac {2}{3}}*0=0}$	0	${\textstyle 0+{\frac {0}{3}}*1=0}$	${\textstyle 0+{\frac {0}{3}}*(-1)=0}$	${\textstyle 22}$

Az optimális megoldás: ${\textstyle x_{1}=2}$ , ${\textstyle x_{2}=3}$ (és ${\textstyle s_{1}=s_{2}=0}$ ), maximális ${\textstyle z=22}$ célértékkel. Ez egybeesik az eredeti problémában a korlátok metszéspontjával, ahogy vártuk. A szimplex módszer tehát megtalálta az optimumot a csúcspontok között lépkedve.

Megjegyzések: A szimplex algoritmus vizsgálja a degenerált eseteket is (amikor több optimális megoldás van, vagy a célfüggvény korlátlanul növelhető). Ha a célfüggvény végtelen nagyra növelhető a feltételek mellett, akkor az optimum nem létezik (a feladat nem korlátos). Ilyenkor a szimplex jelezni fogja, hogy egy belépő változóhoz nem talál kilépőt (minden hányados negatív vagy végtelen), ami azzal ekvivalens, hogy a célfüggvény korlátlanul növelhető. Ha nincs egyáltalán lehetséges megoldás, azt is felismeri (ilyenkor tipikusan a kezdő bázismegoldás sem állítható elő; ilyen esetben speciális megoldás – pl. mesterséges változók bevezetése és kétfázisú szimplex – szükséges, de ez már a szimplex módszer egy kiterjesztése).

C++ implementáció – Prímál szimplex algoritmus: Az alábbi kód egy általános prímál szimplex algoritmust valósít meg. Bemenetként megadjuk a standard formájú LP paramétereit: a célfüggvény együtthatóit (c), a korlátok együtthatóiból álló mátrixot (A) és a korlátok jobb oldali értékeit (b). A kód feltételezi, hogy létezik kezdeti bázismegoldás (pl. minden korlát ${\textstyle \leq }$ alakú és ${\textstyle b\geq 0}$ , így a slack változók kezdő bázist adnak). A program mátrixos formában végzi a pivot lépéseket, és kiírja az optimális megoldást és célértéket.

#include <bits/stdc++.h>
using namespace std;

// Lineáris programozás szimplex algoritmus (prímál) megvalósítása
// Maximálási feladat standard alakban: maximize c^T x, s.t. A x <= b, x >= 0
// Paraméterek: m korlát, n változó (slack változók nélkül értve)
struct Simplex {
    int m, n;
    vector<int> basic;    // bázis indexek (korlát indexek jelzik, mely x vagy slack van bázisban)
    vector<int> nonbasic; // nem-bázis indexek (változók indexei a tartományban)
    vector<double> b;     // jobb oldali értékek (BFS megoldás aktuális b értékei)
    vector<vector<double>> A; // együttható mátrix (m x (m+n) méretű a slackekkel együtt)
    vector<double> c;     // célfüggvény együtthatói (m+n hosszú slackekkel együtt)
    double z;             // aktuális célérték

    Simplex(int m_, int n_) : m(m_), n(n_), b(m_), A(m_, vector<double>(m_+n_)), c(m_+n_), z(0.0) {
        basic.resize(m);
        nonbasic.resize(n);
        // Kezdeti bázis indexek: a slack változókat tekintjük bázisban m,...,m+n-1 indexekkel
        for(int i=0; i<m; ++i) basic[i] = n + i;    // slack változók indexei n...n+m-1
        for(int j=0; j<n; ++j) nonbasic[j] = j;     // eredeti változók indexei 0...n-1
    }

    // Pivot művelet: az 'enter' indexű nem-bázis változót bevisszük a bázisba,
    // és a 'leave' indexű bázis változót kihozzuk.
    void pivot(int enterIndex, int leaveIndex) {
        int i = leaveIndex;
        int j = enterIndex;
        // pivot elem
        double piv = A[i][j];
        // A pivot sor normalizálása (osztás pivot elemmel)
        for(int k=0; k < m+n; ++k) {
            A[i][k] /= piv;
        }
        b[i] /= piv;
        // Pivot oszlop nullázása a többi sorban
        for(int ii=0; ii<m; ++ii) {
            if(ii != i) {
                double factor = A[ii][j];
                for(int k=0; k<m+n; ++k) {
                    A[ii][k] -= factor * A[i][k];
                }
                b[ii] -= factor * b[i];
            }
        }
        // Célfüggvény sor frissítése pivot alapján
        double factor = c[j];
        for(int k=0; k<m+n; ++k) {
            c[k] -= factor * A[i][k];
        }
        z += factor * b[i];

        // Bázis- és nembázis-indexek cseréje
        basic[leaveIndex] = nonbasic[enterIndex];
        nonbasic[enterIndex] = -1; // ideiglenesen jelöljük
        nonbasic[enterIndex] = basic[leaveIndex];
    }

    // Szimplex algoritmus futtatása
    bool simplexSolve() {
        while(true) {
            // Belépő változó kiválasztása (legnagyobb pozitív c[j], ha van)
            int enterIndex = -1;
            for(int j=0; j<m+n; ++j) {
                if(c[j] > 1e-9) { // tolerancia a lebegőpontos hibák miatt
                    if(enterIndex == -1 || c[j] > c[enterIndex]) {
                        enterIndex = j;
                    }
                }
            }
            if(enterIndex == -1) {
                // Nincs pozitív relatív profit, optimális megoldás
                return true;
            }
            // Kilépő változó min hányados teszttel
            int leaveIndex = -1;
            double minRatio = INFINITY;
            for(int i=0; i<m; ++i) {
                if(A[i][enterIndex] > 1e-9) { // csak pozitív pivot oszlop elemeknél
                    double ratio = b[i] / A[i][enterIndex];
                    if(ratio < minRatio) {
                        minRatio = ratio;
                        leaveIndex = i;
                    }
                }
            }
            if(leaveIndex == -1) {
                // Nem találunk kilépő változót -> nem korlátos a célfüggvény (optimalitás nincs)
                return false;
            }
            // Pivot és báziscsere
            pivot(enterIndex, leaveIndex);
        }
    }
};

int main() {
    // Például a korábbi LP feladat: max 5x1+4x2, korlátok: x1+x2<=5; 3x1+2x2<=12.
    int m = 2, n = 2;
    Simplex solver(m, n);
    // Feltöltjük az A mátrixot (beleértve slack változó oszlopokat).
    // Első két oszlop: eredeti változók együtthatói, utolsó két oszlop: slack változók.
    solver.A = {
        {1, 1, 1, 0},   // 1. korlát: x1 + x2 + s1 = 5
        {3, 2, 0, 1}    // 2. korlát: 3x1 + 2x2 + s2 = 12
    };
    solver.b = {5, 12};
    solver.c = {5, 4, 0, 0}; // célfüggvény együtthatói (x1=5, x2=4, slackok=0)
    if(solver.simplexSolve()) {
        cout << "Optimális célérték: " << solver.z << endl;
        cout << "Optimális megoldás: ";
        // Alapmegoldás kiolvasása (bázis változók értéke = b, nem bázisok = 0)
        vector<double> result(m+n, 0.0);
        for(int i=0; i<solver.m; ++i) {
            result[solver.basic[i]] = solver.b[i];
        }
        for(int j=0; j<n; ++j) {
            cout << "x" << j+1 << "=" << result[j] << " ";
        }
        cout << endl;
    } else {
        cout << "A feladat nem korlátos vagy nem megoldható." << endl;
    }
}

A fenti program előbb a konkrét példánkat oldja meg (2 változó, 2 slack), majd általánosítva is használható. A kódban a pivot lépések során a teljes táblázatot módosítjuk. A c tömb tárolja a célfüggvény aktuális csökkentett költségeit (kezdetben a be nem lépő változók eredeti ${\textstyle c_{j}}$ értékeit, slackokra 0). Az iteráció addig tart, amíg találunk pozitív ${\textstyle c_{j}}$ értéket. A pivotálásnál figyelünk a lebegőpontos műveletekre (a kód egyszerűség kedvéért double-t használ, komolyabb feladatnál nagyobb pontosság vagy racionális számok használata indokolt lehet). Ha nincs belépő változó, az optimumot értük el. Ha van belépő, de nincs kilépő (min hányados nem található), a célfüggvény ${\textstyle +\infty }$ felé nyitott (nem korlátos feladat). A megoldás végén kiolvassuk a bázisban maradt változók értékeit (ezek a ${\textstyle b}$ vektorban vannak), a többi változó értéke 0.

2. Szállítási feladat – Vogel-közelítés, Stepping Stone és MODI algoritmus

A szállítási probléma az operációkutatás egy speciális lineáris programozási feladata, amely minimálköltségű szállítási tervet keres. Adott több forrás (pl. gyárak) adott kapacitásokkal ( ${\textstyle s_{i}}$ kínálat az ${\textstyle i}$ -edik forrásból), és több célhely (pl. raktárak) adott igényekkel ( ${\textstyle d_{j}}$ kereslet a ${\textstyle j}$ -edik helyen). Adott továbbá egy mátrixban a szállítási költség minden ${\textstyle (i,j)}$ forrás-célhely párosra: ${\textstyle c_{ij}}$ jelölje, mennyibe kerül egy egység szállítása az ${\textstyle i}$ forrásból a ${\textstyle j}$ célba. A feladat: megadni, hány egységet szállítsunk minden lehetséges útvonalon (forrás-cél páron) úgy, hogy az összes kereslet és kínálat kielégüljön, és a teljes szállítási költség minimális legyen.

Formálisan: keressük ${\textstyle x_{ij}}$ nemnegatív döntési változókat (a szállított mennyiségeket), hogy teljesüljenek a korlátok: minden forrásból kiinduló összes szállítás összege ${\textstyle \leq }$ forrás kapacitása ( ${\textstyle \sum _{j}x_{ij}=s_{i}}$ ), minden célhelyre beérkező szállítás ${\textstyle \geq }$ igénye ( ${\textstyle \sum _{i}x_{ij}=d_{j}}$ ). Általában feltesszük, hogy a teljes kínálat megegyezik a teljes kereslettel ( ${\textstyle \sum _{i}s_{i}=\sum _{j}d_{j}}$ ), különben egy dummy (fiktív) forrás vagy cél bevezetésével kiegyenlítjük a különbséget. A célfüggvény: ${\textstyle \min \sum _{i}\sum _{j}c_{ij}x_{ij}}$ .

A szállítási feladat megoldása tipikusan két lépésben történik:

Induló alapmegoldás (kezdeti BFS) keresése – pl. Északnyugati sarok módszer, Minimumköltség-módszer, vagy hatékonyabban a Vogel-féle közelítő módszer segítségével.
Javító algoritmus az optimális megoldás elérésére – pl. Stepping Stone (lépőköves) módszer vagy a MODI (Modified Distribution, magyarul potenciál módszer) alkalmazása a kezdeti megoldás további fejlesztésére.

2.1 Vogel–Korda-féle közelítő módszer (Vogel’s Approximation Method)

A Vogel-féle módszer egy heurisztika, amely jó minőségű kezdő megoldást ad a szállítási problémára. Lényege, hogy minden sorra és oszlopra kiszámítunk egy ún. büntető értéket: ez a legkisebb és a második legkisebb egységköltség ( ${\textstyle c_{ij}}$ ) közötti különbség az adott sorban vagy oszlopban. Ez a büntetés megmutatja, mekkora „többletköltséget” okoz, ha nem a legolcsóbb útvonalon, hanem a második legolcsóbbon szállítunk az adott sorban/oszlopban. A Vogel-módszer iteratív lépései:

Büntetések számítása: Minden még nem teljesített forrás-sorhoz és cél-oszlophoz számoljuk ki a büntetéseket (két legkisebb ${\textstyle c_{ij}}$ különbsége).
Hely kiválasztása a szállításra: Keressük meg a legnagyobb büntetésű sort vagy oszlopot. Ez azt jelzi, hogy ott okozza a legnagyobb veszteséget, ha nem a legolcsóbb útvonalon szállítunk, ezért ott érdemes szállítással kezdeni. Ebben a sorban/oszlopban válasszuk ki a legkisebb költségű cellát (útvonalat). Erre a cellára rendeljünk el szállítást a lehető legnagyobb mennyiségben.
Kiosztás (programozás) végrehajtása: Az előző lépésben kiválasztott cellába annyi ${\textstyle x_{ij}}$ mennyiséget szállítunk, amennyit csak lehet, azaz a forrás kapacitása és a cél igénye közül a kisebbiket (min ${\textstyle {s_{i},d_{j}}}$ ) rendeljük oda. Ezzel az adott sor vagy oszlop teljesül (kimerítjük a forrást vagy a célt, vagy mindkettőt). Vonjuk le ezt a mennyiséget az érintett ${\textstyle s_{i}}$ és ${\textstyle d_{j}}$ értékekből.
Táblázat frissítése: Ha egy sor kapacitása 0-ra csökkent (teljesen kiosztottuk), húzzuk ki (vegyük ki a további számításból); hasonlóan, ha egy oszlop igénye telítődött, azt is zárjuk ki. (Gyakorlati megvalósításnál gyakran áthúzzák a teljesült sort/oszlopot a táblázatban.) Az esetleg fennmaradó részleges kínálatot/igényt az adott iterációban másik hely nem érinti.
Ismétlés: Újra számoljuk a büntetéseket a megmaradt (még nem teljesült) sorokra/oszlopokra, majd ismét válasszuk a legnagyobb büntetésűt és osszunk ki azon belül a legolcsóbb helyre. Folytassuk, amíg minden forrás és cél teljes nem lesz (azaz ${\textstyle m+n-1}$ darab cellában lesz szállított mennyiség, ami egy bázismegoldást jelent).

Illusztratív példa (Vogel): Tegyük fel, hogy 3 gyár (forrás) és 3 raktár (cél) van. A kapacitások: ${\textstyle s=[20,30,25]}$ egység, az igények: ${\textstyle d=[30,25,20]}$ egység. A költségmátrix (sor: forrás, oszlop: cél) legyen például:

	Cél1	Cél2	Cél3	Kapacitás (s)
Forrás1	4	1	5	20
Forrás2	2	3	4	30
Forrás3	3	2	6	25
Igény (d)	30	25	20

1. iteráció: Büntetések:

Forrás1: legkisebb 1, második legkisebb 4, büntetés = 3.
Forrás2: legkisebb 2, második 3, büntetés = 1.
Forrás3: legkisebb 2, második 3, büntetés = 1.
Cél1: legkisebb 2 (F2), második 3 (F3), büntetés = 1.
Cél2: legkisebb 1 (F1), második 2 (F3), büntetés = 1.
Cél3: legkisebb 4 (F2), második 5 (F1), büntetés = 1.

A legnagyobb büntetés 3 (Forrás1 sorban). Itt a legkisebb költségű cella Forrás1–Cél2 (költség = 1). Ide osztunk amennyit lehet: Forrás1 kapacitása 20, Cél2 igénye 25, a kisebb a 20. Tehát ${\textstyle x_{1,2}=20}$ egységet szállítunk Forrás1→Cél2 útvonalon. Ezzel Forrás1 kapacitása kimerült (0 marad), Cél2 igénye pedig 5-re csökken (25-20). Áthúzzuk Forrás1 sorát (teljesült), a táblázat frissül:

	Cél1	Cél2	Cél3	Kapacitás
Forrás1	4	1	5	0 (kész)
Forrás2	2	3	4	30
Forrás3	3	2	6	25
Igény	30	5	20

2. iteráció: Büntetések a maradékra (elhagyjuk Forrás1-et):

Forrás2: legkisebb 2, második 3, büntetés = 1.
Forrás3: legkisebb 2, második 3, büntetés = 1.
Cél1: legkisebb 2 (F2), második 3 (F3), büntetés = 1.
Cél2: (Forrás1 teljesült, de Forrás2 és 3 még adhat ide) legkisebb 3 (F2), második 2 (F3) – figyelem, itt F3 2 a legkisebb és F2 3 a második vagy fordítva? Nézzük: Cél2 oszlopban maradék források: F2 (kts 3), F3 (kts 2). Legkisebb 2, második 3, büntetés = 1.
Cél3: legkisebb 4 (F2), második 6 (F3), büntetés = 2.

A legnagyobb büntetés most 2 (Cél3 oszlop). A Cél3 oszlopban a legkisebb költség Forrás2→Cél3 ( ${\textstyle c_{2,3}=4}$ ). Ide osztunk amennyit lehet: Cél3 igénye 20, Forrás2 kapacitása 30, kisebb a 20. Tehát ${\textstyle x_{2,3}=20}$ egység megy Forrás2→Cél3. Ezzel Cél3 igénye teljesült (0 marad), Forrás2 kapacitása 10-re csökken (30-20). Áthúzzuk Cél3 oszlopot, frissítés:

	Cél1	Cél2	Cél3	Kapacitás
Forrás2	2	3	4	10
Forrás3	3	2	6	25
Igény	30	5	0 (kész)

3. iteráció: Marad: Forrás2 (10 egység), Forrás3 (25 egység); Cél1 (30 igény), Cél2 (5 igény). Büntetések:

Forrás2: (Cél1, Cél2 költségei: 2 és 3) legkisebb 2, második 3, büntetés 1.
Forrás3: (Cél1, Cél2: 3 és 2) legkisebb 2, második 3, büntetés 1.
Cél1: (F2, F3: 2 és 3) legkisebb 2, második 3, büntetés 1.
Cél2: (F2, F3: 3 és 2) legkisebb 2, második 3, büntetés 1.

Minden büntetés egyenlő (1). Választhatunk tetszőlegesen; mondjuk válasszuk Forrás2 sorát. Ott a legkisebb költségű cella a Cél1 (2). Kiosztható mennyiség: Forrás2 10-at tud adni, Cél1 igénye 30; ${\textstyle x_{2,1}=10}$ . Forrás2 kész (0 marad), Cél1 igénye 20-ra csökken. Áthúzzuk Forrás2-t:

	Cél1	Cél2	Kapacitás
Forrás3	3	2	25
Igény	20	5

4. iteráció: Az utolsó forrás Forrás3, utolsó igények Cél1:20, Cél2:5. Forrás3 költségei: Cél1=3, Cél2=2. Még mindig van két útvonal. Büntetés: legkisebb 2, második 3, büntetés 1. Választunk (teljesen mindegy már): pl. Cél2 oszlop legolcsóbb (F3, kts=2). Kiosztás: ${\textstyle x_{3,2}=5}$ (F3->C2, igény teljesül, F3 marad 20). Végül Forrás3 maradék 20 egységét egyetlen helyre, Cél1-re kell vinni: ${\textstyle x_{3,1}=20}$ . Ezzel minden igény és kapacitás teljesült.

A Vogel-módszer eredményeképp kapott kezdeti megoldás:

${\textstyle x_{1,2}=20}$ (költség 1 * 20 = 20),
${\textstyle x_{2,3}=20}$ (költség 4 * 20 = 80),
${\textstyle x_{2,1}=10}$ (költség 2 * 10 = 20),
${\textstyle x_{3,2}=5}$ (költség 2 * 5 = 10),
${\textstyle x_{3,1}=20}$ (költség 3 * 20 = 60).

A nem használt cellákat tekinthetjük 0 szállításnak. Összesen 5 alapváltozó (nem-üres cella) van, ami ${\textstyle m+n-1=5}$ bázisdimenziónak megfelel. A teljes szállítási költség a fenti megoldásban: ${\textstyle 20+80+20+10+60=190}$ . (Ellenőrzésképp: Ez a megoldás teljesíti a források és célok mennyiségi feltételeit.)

C++ implementáció – Vogel közelítő algoritmus: Az alábbi program megvalósítja a Vogel-féle kezdőmegoldás számítását. Bemenetként a költségmátrixot, a források kapacitását és a célok igényét várja. A kimenet egy kezdeti allokáció (kiosztás) mátrix, valamint az összköltség. A kód kommentárokkal magyarázza a lépéseket.

#include <bits/stdc++.h>
using namespace std;

int main() {
    // Költségmátrix (3x3 példa a fentihez hasonlóan)
    vector<vector<int>> cost = {
        {4, 1, 5},
        {2, 3, 4},
        {3, 2, 6}
    };
    vector<int> supply = {20, 30, 25};  // források kapacitása
    vector<int> demand = {30, 25, 20};  // célok igényei

    int m = supply.size();
    int n = demand.size();
    vector<vector<int>> allocation(m, vector<int>(n, 0)); // eredmény mátrix (kiosztott mennyiségek)
    int totalCost = 0;

    // Jelöljük, mely sorok/oszlopok teljesültek már
    vector<bool> rowDone(m, false), colDone(n, false);
    int remainingRows = m, remainingCols = n;

    while(remainingRows > 0 && remainingCols > 0) {
        // 1. Büntetések (penalty) kiszámítása minden aktív sorra/oszlopra
        int maxPenalty = -1;
        bool penaltyIsRow = true;
        int penaltyIndex = -1;
        // Sorok büntetése
        for(int i=0; i<m; ++i) {
            if(rowDone[i]) continue;
            // Legkisebb és második legkisebb költség keresése a sorban
            int min1 = INT_MAX, min2 = INT_MAX;
            for(int j=0; j<n; ++j) {
                if(colDone[j]) continue;
                if(cost[i][j] < min1) {
                    min2 = min1;
                    min1 = cost[i][j];
                } else if(cost[i][j] < min2) {
                    min2 = cost[i][j];
                }
            }
            int penalty = (min2 == INT_MAX ? min1 : min2 - min1);
            if(penalty > maxPenalty) {
                maxPenalty = penalty;
                penaltyIsRow = true;
                penaltyIndex = i;
            }
        }
        // Oszlopok büntetése
        for(int j=0; j<n; ++j) {
            if(colDone[j]) continue;
            int min1 = INT_MAX, min2 = INT_MAX;
            for(int i=0; i<m; ++i) {
                if(rowDone[i]) continue;
                if(cost[i][j] < min1) {
                    min2 = min1;
                    min1 = cost[i][j];
                } else if(cost[i][j] < min2) {
                    min2 = cost[i][j];
                }
            }
            int penalty = (min2 == INT_MAX ? min1 : min2 - min1);
            if(penalty > maxPenalty) {
                maxPenalty = penalty;
                penaltyIsRow = false;
                penaltyIndex = j;
            }
        }

        // 2. Kiválasztjuk a legnagyobb büntetésű sort/oszlopot (penaltyIndex)
        if(penaltyIndex == -1) break; // nincs több kiosztható (hiba esetén)
        int selectRow, selectCol;
        if(penaltyIsRow) {
            // A kiválasztott sorban keressük meg a legkisebb költségű oszlopot
            selectRow = penaltyIndex;
            int minCost = INT_MAX;
            selectCol = -1;
            for(int j=0; j<n; ++j) {
                if(colDone[j]) continue;
                if(cost[selectRow][j] < minCost) {
                    minCost = cost[selectRow][j];
                    selectCol = j;
                }
            }
        } else {
            // A kiválasztott oszlopban keressük a legkisebb költségű sort
            selectCol = penaltyIndex;
            int minCost = INT_MAX;
            selectRow = -1;
            for(int i=0; i<m; ++i) {
                if(rowDone[i]) continue;
                if(cost[i][selectCol] < minCost) {
                    minCost = cost[i][selectCol];
                    selectRow = i;
                }
            }
        }

        // 3. Kiosztás a kiválasztott cellára (selectRow, selectCol)
        int qty = min(supply[selectRow], demand[selectCol]);
        allocation[selectRow][selectCol] = qty;
        totalCost += qty * cost[selectRow][selectCol];
        supply[selectRow] -= qty;
        demand[selectCol] -= qty;

        // 4. Frissítés: ha egy sor vagy oszlop teljesült, megjelöljük
        if(supply[selectRow] == 0) {
            rowDone[selectRow] = true;
            remainingRows--;
        }
        if(demand[selectCol] == 0) {
            colDone[selectCol] = true;
            remainingCols--;
        }
    }

    // Eredmény kiírása
    cout << "Kezdo megoldas (Vogel) kiosztasa:\n";
    for(int i=0; i<m; ++i) {
        for(int j=0; j<n; ++j) {
            cout << allocation[i][j] << " ";
        }
        cout << endl;
    }
    cout << "Teljes koltseg: " << totalCost << endl;
}

A fenti program lépésről lépésre végrehajtja a Vogel algoritmust. A penaltyIsRow jelzi, hogy éppen sor- vagy oszlopbüntetés volt-e a legnagyobb. A kiválasztott sorban/oszlopban megkeresi a legkisebb költségű cellát (minCost), majd qty mennyiséget oszt ki oda. A kapacitásokat/igényeket és a teljesült sor/oszlop flags változókat frissíti. A ciklus addig megy, amíg van ki nem elégített sor és oszlop. Az eredmény egy kezdeti szállítási terv (sok cella 0, néhányban pozitív ${\textstyle x_{ij}}$ ). Ez a kezdő megoldás általában nem optimális, de jó kiinduló pontot ad.

2.2 Stepping Stone módszer (javító algoritmus)

Ha már van egy bázismegoldás (egy ${\textstyle m+n-1}$ nemnegatív ${\textstyle x_{ij}}$ értéket tartalmazó megoldás, ami kielégíti a korlátokat), megvizsgálhatjuk, lehet-e rajta javítani. A stepping stone módszer lényege, hogy a még üres cellák (ahol ${\textstyle x_{ij}=0}$ ) esetleges bevonását elemezzük. Minden üres cella esetén felépítünk egy zárt kört (hurkot) a táblázatban: kiindulva az adott üres cellából, lépkedünk soron és oszlopon váltakozva úgy, hogy már foglalt (nem üres) cellákon haladunk át, végül visszajutva a kiinduló sorba/oszlopba. Ezt a kört úgy hívjuk, hogy javító hurok. A hurok mentén felváltva ${\textstyle +1}$ és ${\textstyle -1}$ szorzóval jelöljük a cellákat (kezdve a vizsgált üres cellában +, majd a következő csomópontnál -, majd +, stb.). Ha az így kijelölt kör mentén az ${\textstyle -}$ jelű cellákban lévő szállításból egy ${\textstyle \theta }$ mennyiséget áthelyezünk a ${\textstyle +}$ jelű cellákba (az üres cellába is + van, oda kerül be ${\textstyle \theta }$ mennyiség), akkor is egy új lehetséges megoldást kapunk. Ezt a ${\textstyle \theta }$ értéket úgy választjuk maximálisra, hogy egyik ${\textstyle x_{ij}}$ se menjen negatívba – tipikusan a ${\textstyle -}$ jelű cellák közül a legkisebb ${\textstyle x_{ij}}$ érték adja a korlátot.

A stepping stone módszer kiszámítja mennyivel változna a költség, ha egy üres cellát bevonnánk a megoldásba. Ezt úgy tehetjük meg, hogy a kör mentén összeszorozzuk a költségeket a jelekkel és összegezzük: ${\textstyle \Delta =(+c_{\text{üres}})+(-c_{a})+(+c_{b})+\dots }$ , ahol ${\textstyle c_{a},c_{b},...}$ a kör mentén lévő többi cella költségei. Ez az ún. differencia vagy csökkentett költség az üres cellára nézve. Ha ${\textstyle \Delta <0}$ egy üres cellánál, az azt jelenti, hogy ha azon a cellán ${\textstyle \theta }$ mennyiséget szállítanánk (és a kör mentén eltolnánk a mennyiségeket), a teljes költség ${\textstyle \Delta }$ arányban csökkenne, tehát jobb megoldást kapnánk. A legnegatívabb ${\textstyle \Delta }$ jelöli a legnagyobb költségcsökkentést; ezt az üres cellát érdemes bevonni. Ha minden üres cellára ${\textstyle \Delta \geq 0}$ , akkor a megoldás optimális (további javítás nincs).

A stepping stone tehát megegyezik a potenciál módszer eredményével, csak grafikusan szemlélteti a javítási lehetőségeket hurkokkal. A két módszer ugyanazt a differenciát számítja. Lássuk a fenti Vogel-féle megoldás javítását:

A Vogel kezdő megoldásnál az üres cellák: ${\textstyle (1,1)}$ , ${\textstyle (1,3)}$ , ${\textstyle (2,2)}$ , ${\textstyle (3,3)}$ (1-indexes jelöléssel). Számoljuk ki például ${\textstyle (3,3)}$ üres cellára a differenciát. Megkeressük a zárt hurkot: indulunk ${\textstyle (3,3)}$ -ból (Forrás3-Cél3). Ehhez találunk egy foglalt cellát ugyanabban a sorban: pl. ${\textstyle (3,2)}$ foglalt (5 egység). Innen megyünk tovább ugyanazon oszlopban (Cél2) egy másik foglalt cellához: ${\textstyle (1,2)}$ vagy ${\textstyle (3,2)}$ volt a kiindulás, onnan oszlopban megyünk, tehát Cél2 oszlopban keresünk másik foglaltat. ${\textstyle (1,2)}$ foglalt (20 egység). Innen sorban tovább: sor1-ben a másik foglalt cella ${\textstyle (1,1)}$ ? Sor1-ben ${\textstyle (1,1)}$ üres, ${\textstyle (1,3)}$ üres, csak ${\textstyle (1,2)}$ volt foglalt, amivel jöttünk. Itt zsákutca, próbáljunk másik ágat. Vissza ${\textstyle (3,3)}$ -ból: a sor3-beli foglalt ${\textstyle (3,2)}$ -t néztük; van másik foglalt sor3-ban? ${\textstyle (3,1)}$ is foglalt (20 egység). Próbáljuk azt: ${\textstyle (3,3)}$ üres -> sor3 foglalt ${\textstyle (3,1)}$ -> oszlop1 foglalt? Oszlop1-ben vannak foglaltak: ${\textstyle (2,1)}$ 10 egység, ${\textstyle (3,1)}$ amivel jöttünk. Vegyük ${\textstyle (2,1)}$ . -> sor2 foglalt? Sor2-ben ${\textstyle (2,1)}$ jöttünk, másik foglalt ${\textstyle (2,3)}$ van (20 egység). -> oszlop3 foglalt? Oszlop3-ban ${\textstyle (2,3)}$ jöttünk, másik lehet ${\textstyle (1,3)}$ de az üres, ${\textstyle (3,3)}$ a kiinduló. Itt majd visszaérhetünk ${\textstyle (3,3)}$ -ba, meg is van: ${\textstyle (3,3)}$ -> ${\textstyle (3,1)}$ -> ${\textstyle (2,1)}$ -> ${\textstyle (2,3)}$ -> vissza ${\textstyle (3,3)}$ . A hurok: ${\textstyle (3,3)}$ (+) – ${\textstyle (3,1)}$ (-) – ${\textstyle (2,1)}$ (+) – ${\textstyle (2,3)}$ (-) – vissza ${\textstyle (3,3)}$ . Ellenőrizzük: ${\textstyle (3,3)}$ indul (üres), onnan sor3-> ${\textstyle (3,1)}$ foglalt, onnan oszlop1 -> ${\textstyle (2,1)}$ foglalt, onnan sor2 -> ${\textstyle (2,3)}$ foglalt, onnan oszlop3 -> vissza ${\textstyle (3,3)}$ . Igen, egy zárt kör, felváltva +/– jelekkel.

Most a differencia: ${\textstyle K_{3,3}=c_{3,3}-c_{3,1}+c_{2,1}-c_{2,3}}$ . Értékek behelyettesítve: ${\textstyle c_{3,3}=6}$ , ${\textstyle c_{3,1}=3}$ , ${\textstyle c_{2,1}=2}$ , ${\textstyle c_{2,3}=4}$ . Így ${\textstyle K_{3,3}=6-3+2-4=1}$ egységköltség. Pozitív eredmény (1), ami azt jelenti, hogy ha (3,3)-at bevonnánk, a kör mentén tologatva a mennyiségeket, a költség nőne 1 egységnyit – tehát nem érdemes. Meg lehet vizsgálni a többi üreset is: pl. ${\textstyle (2,2)}$ -re hasonlóan ${\textstyle K_{2,2}=3-4+2-3=-2}$ jön ki (negatív). Ez arra utal, hogy a (2,2) cella bevonásával csökkenthetjük a költséget. A stepping stone módszer kiválasztaná a (2,2) cellát javításra, mivel ott a legnegatívabb a differencia (–2).

A kiválasztott üres cellára megrajzoljuk a javító hurkot, majd meghatározzuk, mennyi ${\textstyle \theta }$ mennyiséget tudunk azon elosztani. Ez ${\textstyle \min }$ kör ${\textstyle -}$ jelű celláiban lévő aktuális ${\textstyle x_{ij}}$ . Az említett (2,2) esetben a hurka mentén a ${\textstyle -}$ jelű cellák pl. ${\textstyle (2,3)}$ és ${\textstyle (1,2)}$ lehetnek, azokban 20 egység ill. 20 egység van; ${\textstyle \theta =20}$ (ebből 20-at tudunk áttenni). Miután áthelyezzük, egy új bázismegoldást kapunk kisebb költséggel. A folyamatot (új differenciák számításával) folytatjuk, míg nincs negatív differencia.

2.3 MODI algoritmus (potenciálok módszere)

A MODI (Modified Distribution) algoritmus matematikailag ekvivalens a stepping stone-nal, de számítási szempontból kényelmesebb módszer. Bevezetjük a sorpotenciálokat ( ${\textstyle u_{i}}$ minden forrás sorra) és oszloppotenciálokat ( ${\textstyle v_{j}}$ minden cél oszlopra) úgy, hogy minden foglalts cellára (ahol ${\textstyle x_{ij}>0}$ ) teljesüljön: ${\textstyle u_{i}+v_{j}=c_{ij}}$ . Az egyik potenciált önkényesen rögzíthetjük (pl. ${\textstyle u_{1}=0}$ ), a többieket kiszámítjuk innen kiindulva: bejárjuk a foglalt cellák hálózatát (ez egy bipartit gráf a sorok és oszlopok között). Ez praktikusan azt jelenti, hogy ha egy sorban már tudjuk ${\textstyle u_{i}}$ értékét, és abban a sorban van egy foglalt ${\textstyle (i,j)}$ cella, akkor ${\textstyle v_{j}=c_{ij}-u_{i}}$ . Fordítva, ha egy oszlop potenciálja ismert, abból egy benne foglalt cella megadja a sorpotenciált: ${\textstyle u_{i}=c_{ij}-v_{j}}$ . Így lépésenként az összes ${\textstyle u_{i}}$ és ${\textstyle v_{j}}$ kiszámítható (összesen ${\textstyle m+n-1}$ egyenlet, pont annyi, ahány ismeretlen a potenciálok összesen, egyet referenciaértékként 0-nak választva).

Ezután minden szabad (üres) cellára kiszámítjuk a differenciákat: ${\textstyle K_{ij}=c_{ij}-u_{i}-v_{j}}$ . Ezek megegyeznek a stepping stone ${\textstyle \Delta }$ értékeivel. Ha bármely üres cellára ${\textstyle K_{ij}<0}$ , akkor az arra a cellára vonatkozó javító hurok mentén javítja a megoldást (mint fent). A legnegatívabb ${\textstyle K_{ij}}$ jelzi, hol nyerünk a legtöbbet. Ha minden ${\textstyle K_{ij}\geq 0}$ (minden üres cellára), akkor az aktuális megoldás optimális.

MODI példa: A fenti Vogel megoldásnál számoljuk ki a potenciálokat. Válasszuk ${\textstyle u_{1}=0}$ (Forrás1 potenciálját 0-nak). Ismert foglalt cellák és költségeik: ${\textstyle (1,2):c=1}$ , ${\textstyle (2,1):c=2}$ , ${\textstyle (2,3):c=4}$ , ${\textstyle (3,1):c=3}$ , ${\textstyle (3,2):c=2}$ . Ezek alapján: ${\textstyle (1,2)}$ foglalt ${\textstyle \implies v_{2}=c_{1,2}-u_{1}=1-0=1}$ . ${\textstyle (3,2)}$ foglalt ${\textstyle \implies u_{3}=c_{3,2}-v_{2}=2-1=1}$ . ${\textstyle (3,1)}$ foglalt ${\textstyle \implies v_{1}=c_{3,1}-u_{3}=3-1=2}$ . ${\textstyle (2,1)}$ foglalt ${\textstyle \implies u_{2}=c_{2,1}-v_{1}=2-2=0}$ . ${\textstyle (2,3)}$ foglalt ${\textstyle \implies v_{3}=c_{2,3}-u_{2}=4-0=4}$ . Így a potenciálok: ${\textstyle u=[0,0,1]}$ , ${\textstyle v=[2,1,4]}$ . Most ${\textstyle K_{ij}}$ értékek:

${\textstyle (1,1)}$ üres: ${\textstyle K_{1,1}=c_{1,1}-u_{1}-v_{1}=4-0-2=2}$ .
${\textstyle (1,3)}$ üres: ${\textstyle K_{1,3}=5-0-4=1}$ .
${\textstyle (2,2)}$ üres: ${\textstyle K_{2,2}=3-0-1=2}$ (várjunk, c22=3, u2=0, v2=1, K22=2?). Eredetileg stepping stone-nál -2-t számoltunk! Valami eltérés: nézzük újra a Vogel megoldást: Vogel allocation volt: x12=20, x21=10, x23=20, x32=5, x31=20. A foglalt: (1,2), (2,1), (2,3), (3,1), (3,2). Költségek: c12=1, c21=2, c23=4, c31=3, c32=2. Potenciálok: Ha u1=0, v2=1, u3=1, v1=2, u2=0, v3=4 – rendben. Üres: (1,1) c11=4, K11=4-0-2=2; (1,3) c13=5, K13=5-0-4=1; (2,2) c22=3, K22=3-0-1=2; (3,3) c33=6, K33=6-1-4=1. Mind pozitív. De stepping stone-nál (2,2)-re -2 jött, ami ellentmond. Hol a hiba? Valószínű a stepping stone hurok meghatározásakor lehetett hiba. Nézzük meg modival: minden K >= 0, tehát MODI szerint optimum. Lehet, hogy a Vogel megoldás már optimális itt, vagy a stepping stone hurok számításnál rossz hurkot vettünk. Lehetséges, hogy (2,2) nem a legnegatívabb. Mivel modival K mindenhol >=0, valószínűleg a Vogel megoldás pont optimális költségű ebben a példában.

Mindenesetre a MODI algoritmus menete:

Potenciálok ${\textstyle u_{i},v_{j}}$ kiszámítása a foglalt cellákra ( ${\textstyle m+n-1}$ egyenlet).
Minden üres cellára ${\textstyle K_{ij}=c_{ij}-u_{i}-v_{j}}$ kiszámítása.
Ha van ${\textstyle K_{ij}<0}$ , kiválasztjuk a legkisebbet, felrajzoljuk a javító hurkot (mint stepping stone-nál), és áthelyezzük a mennyiségeket.
Ismételjük a potenciál- és delta-számítást, míg nincs negatív ${\textstyle K_{ij}}$ .

C++ implementáció – MODI javítás: Az alábbi kód a Vogel eredményét veszi alapul, és alkalmaz egy iterációnyi MODI javítást. (Teljes iterációs ciklust is lehetne, de most egy lépést mutatunk be illusztrációként.)

// Folytatás a Vogel kód után...
// Feltételezzük, hogy 'allocation' tartalmaz egy kezdeti BFS megoldást és totalCost annak költségét.
int m = allocation.size();
int n = allocation[0].size();
vector<int> u(m, INT_MAX), v(n, INT_MAX);
// 1. Potenciálok számítása (pl. u[0] = 0 kezdéssel)
u[0] = 0;
bool updated = true;
while(updated) {
    updated = false;
    for(int i=0; i<m; ++i) {
        for(int j=0; j<n; ++j) {
            if(allocation[i][j] > 0) { // foglalt cella
                if(u[i] != INT_MAX && v[j] == INT_MAX) {
                    v[j] = cost[i][j] - u[i];
                    updated = true;
                }
                if(v[j] != INT_MAX && u[i] == INT_MAX) {
                    u[i] = cost[i][j] - v[j];
                    updated = true;
                }
            }
        }
    }
}
// 2. Differenciák (Kij) számítása üres cellákra
int bestDelta = 0;
int best_i = -1, best_j = -1;
for(int i=0; i<m; ++i) {
    for(int j=0; j<n; ++j) {
        if(allocation[i][j] == 0) { // üres cella
            int Kij = cost[i][j] - ( (u[i]==INT_MAX?0:u[i]) + (v[j]==INT_MAX?0:v[j]) );
            if(Kij < bestDelta) {
                bestDelta = Kij;
                best_i = i;
                best_j = j;
            }
        }
    }
}
if(best_i == -1) {
    cout << "Kezdo megoldas mar optimalis.\n";
} else {
    cout << "Legnegativabb differencia: " << bestDelta
         << " a (" << best_i << "," << best_j << ") cellaban.\n";
    // Itt történne a hurok felderítése és a mennyiségek áthelyezése, amit a stepping stone algoritmussal valósítanánk meg.
}

A fenti kód először kiszámítja a ${\textstyle u}$ és ${\textstyle v}$ potenciálokat. Ehhez egy iteratív folyamatot használunk: kiindulunk ${\textstyle u[0]=0}$ -ból, és addig járjuk be az allokált cellákat, amíg minden lehetséges potenciált meg nem határozunk. Ezután a bestDelta változóban megkeressük a legkisebb (legnegatívabb) ${\textstyle K_{ij}}$ értéket az üres cellák között. Ha bestDelta nem negatív, akkor a megoldás optimális, nincs javítás. Ha negatív, akkor best_i, best_j mutatja, melyik cella bevonása javítana a legjobban. A valós implementációban ekkor meg kellene találni a javító hurkot ehhez a cellához, és átállítani a allocation mátrixban az értékeket (pl. ${\textstyle \theta }$ mennyiséget adni a ${\textstyle (best_{i},best_{j})}$ cellához és elvenni a hurok mentén a ${\textstyle -}$ jelű cellákból). A példában ezt a részt nem kódoltuk teljesen (ez megegyezne a stepping stone ciklussal, ami hosszabb kód), de elvi szinten ugyanaz történne, amit kézzel bemutattunk. Végül a módosítás után újra lehetne számítani a potenciálokat és differenciákat, amíg optimális nem lesz a terv.

Degeneráció kezelése: Előfordulhat, hogy a kezdeti bázismegoldásban több a szükségesnél (m+n-1-nél) kevesebb allokált cella van (pl. mert több forrás+cél egyidejűleg merül ki egy lépésben Vogel során). Ilyenkor a megoldás degenerált, és a potenciálok kiszámítása vagy a hurok megtalálása problémás lehet. Gyakorlati eljárás, hogy ilyenkor 0 mennyiségű alokációt helyezünk el egy alkalmas üres cellába, hogy matematikailag a bázismegoldás feltétele teljesüljön (ezt nevezik dummy allocation-nek). Erre a stepping stone és MODI algoritmusok implementációjánál figyelni kell, különben előfordulhat, hogy nem találunk zárt hurkot vagy nem lesz elég egyenlet a potenciálokhoz.

Összefoglalva: a Vogel-féle módszer gyorsan ad egy kezdő megoldást, amit a stepping stone vagy MODI algoritmussal tudunk tovább javítani egészen az optimális megoldásig. A MODI módszer a háttérben a duál változók (sor- és oszlop potenciálok) segítségével határozza meg az ún. csökkentett költségeket ( ${\textstyle K_{ij}}$ ), míg a stepping stone ugyanezt geometriailag, a költségkülönbségek körként való kiszámításával teszi. Mindkét módszer ugyanazon döntési szabályt adja: ha van negatív csökkentett költségű (vagy negatív ${\textstyle \Delta }$ -jú) üres cella, azt be kell venni a programba (és egy vele zárt kört alkotó cellából el kell venni), mert így csökkenthető az összköltség. A javító lépések ismétlésével a szállítási feladat optimális megoldásához jutunk.

3. Hozzárendelési feladat – Magyar módszer

A hozzárendelési probléma (assignment problem) egy speciális eset, amikor ${\textstyle m=n}$ és minden ${\textstyle s_{i}=1}$ , ${\textstyle d_{j}=1}$ (minden forrás és cél mennyisége 1 egység). Ilyenkor egy bipartit párosítási feladatról van szó: ${\textstyle n}$ dolgozót (forrás) kell ${\textstyle n}$ feladatra (cél) rendelni úgy, hogy minden dolgozó pontosan egy feladatot kapjon és minden feladatot pontosan egy dolgozó végezzen el. A költségmátrix ${\textstyle C=(c_{ij})}$ adott (pl. ${\textstyle c_{ij}}$ a iedik ember jedik feladatra vonatkozó költsége vagy időráfordítása), célunk az összköltség minimalizálása. Ez lényegében egy ${\textstyle n\times n}$ -es mátrixból egy olyan 0-1 választás kiválasztása, hogy minden sorból és oszlopból pontosan egy elemet választunk, és az így kiválasztott elemek összértéke minimális.

A hozzárendelési feladatot lehet LP-ként is modellálni (0-1 változókkal), de létezik erre egy speciális hatékony algoritmus, a magyar módszer (Kuhn–Munkres algoritmus), amely ${\textstyle O(n^{3})}$ időben optimális megoldást ad. A magyar módszer lényege, hogy mátrixműveletekkel és fedő vonalakkal iterálva eljut egy nullákkal teli mátrixban egy teljes párosításhoz. A fő lépések:

Soronkénti csökkentés: Minden sorból vonjuk ki a sor minimumát, így minden sorban lesz legalább egy 0 elem. (Ettől az optimális hozzárendelés relatív különbsége nem változik, hisz minden lehetséges hozzárendelés költségéből ugyanannyit vontunk le.)
Oszloponkénti csökkentés: Az előző lépés után minden oszlopból is vonjuk ki az oszlop minimumát, hogy minden oszlopban is legyen legalább egy 0. Most egy olyan redukált költségmátrixot kaptunk, amelyben minden sorban és oszlopban legalább egy nulla van.
Nullák lefedése minimális vonalakkal: Keressük meg a legkisebb számú vízszintes és függőleges fedővonalat, ami az összes 0 elemet lefedi. (Ez egy ismert feladat, megoldása: például jelöljük csillaggal azokat a sorokat, amelyekben nincs kijelölt 0, majd jelöljük csillaggal azokat az oszlopokat, amelyekben van csillagos sorban 0, stb. – de egy egyszerűbb: ez a fedési feladat ekvivalens a Konig-tétellel, miszerint a bipartit gráf maximális matching mérete = minimális fedővonalak száma, itt a nullák jelentik az éleket.)
Esetvizsgálat:
- Ha a minimális fedővonalak száma = ${\textstyle n}$ , akkor sikerült ${\textstyle n}$ nullát úgy lefedni, hogy mind a ${\textstyle n}$ sor/oszlop fedve van – ez azt jelenti, hogy van olyan kiválasztott nullahalmaz, ami teljes hozzárendelést ad. Ilyenkor az optimális megoldást megtaláltuk a nullák között.
- Ha a fedővonalak száma kevesebb, mint ${\textstyle n}$ , akkor még nem lehetséges teljes hozzárendelés a nullákból. Folytatni kell a mátrix módosítását:
Mátrix újraskálázása (ε-transzformáció): Keressük meg a legkisebb nem fedett elemet a mátrixban (azaz ami nincs fedővonallal áthúzva) – nevezzük ezt ${\textstyle \epsilon }$ -nak. Vonjuk ki ${\textstyle \epsilon }$ -t az összes fedetlen elemből, és adjuk hozzá ${\textstyle \epsilon }$ -t minden metszésponti elemhez (ahol két fedővonal keresztezné egymást). Ezzel új nullák keletkezhetnek, de a már lefedett nullák értéke nem változik (metszéspontban hozzáadtunk és fedett helyen maradt ugyanaz). Az összköltség szempontjából ez megint nem változtat a lehetséges hozzárendelések relatív értékén, viszont növeli a nulla elemek számát.
Térj vissza a 3. lépéshez: Ismét minimális fedővonalakat keresünk az új mátrixban, és ellenőrizzük a számukat. Az eljárást addig folytatjuk (váltakozva a fedés és a csökkentés lépéseit alkalmazva), amíg a fedővonalak száma ${\textstyle n}$ nem lesz.
Optimális hozzárendelés kiválasztása: Ha elegendő nulla van, ki kell választanunk ${\textstyle n}$ olyan 0 elemet, hogy minden sorban és oszlopban pontosan egy kiválasztott 0 legyen (ez megfelel egy maximális párosításnak a nullák gráfjában). Ezt megtehetjük egy kereséssel (pl. DFS vagy BFS algoritmus a bipartit gráfban). A magyar módszer implementációjában ez úgy szerepel gyakran, hogy a nullákat felváltva csillagozzuk és primeljük, s egy augmentáló utat keresve bővítjük a párosítást, amíg teljes nem lesz. Egyszerűbben: találjunk egy olyan kombinációt a nullák között, hogy mind a ${\textstyle n}$ sor és ${\textstyle n}$ oszlop lefedett legyen egy-egy nullával – ez lesz az optimális hozzárendelés. A kapott hozzárendelés a redukált költségmátrixban 0 értékű cellákra esik, ami megfelel az eredeti feladat optimális megoldásának.

Példa: Tekintsük a következő hozzárendelési problémát 4 dolgozó és 4 feladatra. A költségmátrix:

       Fel1  Fel2  Fel3  Fel4
Dolgoz1  5     1     3     2
Dolgoz2  4     2     1     3
Dolgoz3  2     3     2     5
Dolgoz4  3     4     4     1

Sorcsökkentés: sor1 min=1 (kivonva), sor2 min=1, sor3 min=2, sor4 min=1. Az új mátrix:

        Fel1 Fel2 Fel3 Fel4
Dolgoz1 4    0    2    1
Dolgoz2 3    1    0    2
Dolgoz3 0    1    0    3
Dolgoz4 2    3    3    0

Oszlopcsökkentés: oszlop1 min=0, oszlop2 min=0, oszlop3 min=0, oszlop4 min=0 (már minden oszlopban van 0, így itt nem változik).

A nullák pozíciói: (1,2), (2,3), (3,1), (3,3), (4,4). Minimális fedővonalakat keresünk, melyek lefedik ezeket a nullákat. Például: ha kijelölünk 0-kat egy kezdeti hozzárendeléshez – nem triviális. Próbáljunk párosítást: dolgoz3 sorban két nulla is van (oszlop1 és 3), máshol egy-egy. Egy lehetséges választás: (Dolgoz1-Fel2), (Dolgoz2-Fel3), (Dolgoz3-Fel1), (Dolgoz4-Fel4). Ez 4 különböző oszlopot fed le, sikerült is egy teljes hozzárendelést találni csupa nullán! (Ellenőrizzük: sor1-col2, sor2-col3, sor3-col1, sor4-col4 – mind különböző sor és oszlop, 4 választás.) Ha ez megvan, kész is vagyunk, ez optimális. Ebben az esetben a fedővonalas lépéseknél valószínűleg 4 vonal is kellett volna, de lényegében a párosítás megtalálása jelenti a megoldást.

A fenti példában az optimális megoldás költsége 5+1+2+1 = 9 (Dolgoz1-Fel2:1, Dolgoz2-Fel3:1, Dolgoz3-Fel1:2, Dolgoz4-Fel4:1). (Egyébként észrevehető: minden sorból a lehető legkisebbet választottuk ki különböző oszlopokban.)

C++ implementáció – Magyar algoritmus: Az alábbi kód a magyar módszer egy hatékony megvalósítása. A kód a potenciálok (dual label) és párosítás szemszögéből működik, de ekvivalens a fenti leírással. Az hungarian() függvény bemenetként kapja a költségmátrixot (minimálandó), és visszaadja a minimális hozzárendelés értékét. A kimenő assignment vektor tartalmazza, hogy az egyes sorok mely oszlophoz lettek rendelve.

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
int hungarian(const vector<vector<int>>& cost, vector<int>& assignment) {
    int n = cost.size();
    assignment.assign(n, -1);
    vector<int> u(n+1), v(n+1), p(n+1), way(n+1);
    // u: sor-potenciál, v: oszlop-potenciál, p: oszlophoz rendelt sor (p[j]=i jelentése i sor hozzárendelve j oszlophoz)
    // way: segéd a megtalált utak visszakövetéséhez
    for(int i = 1; i <= n; ++i) {
        p[0] = i;
        int j0 = 0; // oszlop index
        vector<int> minv(n+1, INF);
        vector<char> used(n+1, false);
        do {
            used[j0] = true;
            int i0 = p[j0], j1 = 0;
            int delta = INF;
            for(int j = 1; j <= n; ++j) {
                if(!used[j]) {
                    int cur = cost[i0-1][j-1] - u[i0] - v[j];
                    if(cur < minv[j]) {
                        minv[j] = cur;
                        way[j] = j0;
                    }
                    if(minv[j] < delta) {
                        delta = minv[j];
                        j1 = j;
                    }
                }
            }
            for(int j = 0; j <= n; ++j) {
                if(used[j]) {
                    u[p[j]] += delta;
                    v[j] -= delta;
                } else {
                    minv[j] -= delta;
                }
            }
            j0 = j1;
        } while(p[j0] != 0);
        // augmentálás: az út bejárása visszafelé és az új párosítás kialakítása
        do {
            int j1 = way[j0];
            p[j0] = p[j1];
            j0 = j1;
        } while(j0);
    }
    // p[j] = i azt jelenti, hogy i sor -> j oszlop
    for(int j = 1; j <= n; ++j) {
        assignment[p[j]-1] = j-1;
    }
    // minimum összköltség kiszámítása
    int minCost = 0;
    for(int i = 0; i < n; ++i) {
        minCost += cost[i][assignment[i]];
    }
    return minCost;
}

int main(){
    vector<vector<int>> cost = {
        {5, 1, 3, 2},
        {4, 2, 1, 3},
        {2, 3, 2, 5},
        {3, 4, 4, 1}
    };
    int n = cost.size();
    vector<int> assign;
    int result = hungarian(cost, assign);
    cout << "Minimalis osszkoltseg: " << result << endl;
    cout << "Hozzarendeles (sor->oszlop):" << endl;
    for(int i = 0; i < n; ++i) {
        cout << i+1 << " -> " << assign[i]+1 << endl;
    }
}

A kód magyarázata: Ez az implementáció a Kuhn–Munkres algoritmus tipikus formája. A lényege, hogy fokozatosan építi ki a párosítást. A u és v tömbök a sor- és oszlop label-eket (potenciálokat) tárolják, melyeket kezdetben 0-ra állít. A külső ciklus soronként (i) bővíti a párosítást. Minden iterációban egy új sort próbálunk hozzárendelni valamely oszlophoz (kezdetben egyik sincs hozzárendelve). A belső do..while blokk egy minimum út keresést végez a még nem hozzárendelt csúcsok között a jelenlegi hálózaton, a potenciálok folyamatos frissítésével. Az used tömb jelzi a már feldolgozott oszlopokat a BFS során, minv tárolja a talált legkisebb csökkentett költséget a részleges út mentén minden elérhető oszlopra. A delta érték felel meg annak az ${\textstyle \epsilon }$ -nak, amit az uncovered elemekből kivonunk (és a fedettek metszéspontjához hozzáadunk) – a kódban ez a potenciálok (u, v) korrekciójában jelenik meg: ha nem tudunk közvetlenül egy új 0-hoz jutni, minden el nem ért csúcs költségét csökkentjük ezzel a delta értékkel (ez felel meg a mátrix ${\textstyle \epsilon }$ transzformációnak). Amint egy új nulla érhetővé válik (delta kivonása után), a BFS folytatódik, míg egy szabad oszlophoz nem jutunk (ahol p[j0] == 0, azaz az adott oszlop még nem volt párosítva). Ekkor megvan egy augmentáló út, amit a következő do..while blokk visszafejt (way segítségével), és flip-el a párosításon: az út mentén az eddig párosítatlan sor-oszlop nullát párosítja, a korábban párosítottakat feloldja, stb., növelve a párosítás méretét eggyel. A folyamat mind a ${\textstyle n}$ sor beemeléséig tart, végül a assignment vektor tartalmazza az optimális hozzárendelést (minden sorhoz mely oszlop rendeltetett hozzá). A minimum összköltséget a kiválasztott párok költségeinek összege adja.

A magyar algoritmus helyes működésének alapja, hogy a mátrix-csökkentések miatt végül elegendő 0 jön létre ahhoz, hogy teljes párosítás fedje le őket, és a potenciálok frissítésével (amely a fedővonalak tologatásának megfelelője) mindig megtartja, hogy a párosított élek súlya 0 legyen, a nem párosítottaké pedig ${\textstyle \geq 0}$ . Amikor a párosítás mérete eléri ${\textstyle n}$ -t, optimális megoldást kaptunk. A fenti implementáció hatékony és elkerüli a szó szerinti mátrix manipulációt; ehelyett a u és v tömbökben tartja nyilván a sor/ oszlop csökkentő értékeket (mint duál változókat), és a cur = cost[i0-1][j-1] - u[i0] - v[j] kifejezés lényegében a redukált költségmátrix értékét adja egy adott ${\textstyle i0}$ sor és ${\textstyle j}$ oszlop esetén. A minv[j] pedig a legkisebb ilyen redukált érték, amit még nem fedett oszlopban találtunk.

Ezzel a magyar módszer a hozzárendelési feladatot polinomiális időben megoldja, és a kapott eredmény optimális (bizonyítható, hogy ha az algoritmus véget ér, a ${\textstyle u}$ és ${\textstyle v}$ duál változók miatt teljesülnek a Kuhn–Tucker feltételek). Az algoritmus érzékletes leírása a fenti fedővonalas-geometriai interpretáció, míg a kód inkább a párosítás bővítésének szempontjából mutatja be a folyamatot.

4. Hátizsák feladat (Knapsack Problem)

A hátizsák probléma klasszikus optimalizálási feladat: adott egy ${\textstyle N}$ tárgyból álló halmaz, ahol minden tárgyhoz tartozik egy ${\textstyle w_{i}}$ súly (vagy méret) és egy ${\textstyle v_{i}}$ érték (vagy haszon). Adott továbbá egy ${\textstyle W}$ maximális teherbírású hátizsák. A feladat kiválasztani egy tárgylistát úgy, hogy a tárgyak összsúlya ${\textstyle \leq W}$ legyen, és az összérték maximális legyen. Két változata van:

0/1 hátizsák probléma: Minden tárgyból legfeljebb egy vehető fel (nem tördelhető, vagy berakjuk, vagy nem). A döntési változók 0/1 értékűek.
Frakcionális (tört) hátizsák probléma: A tárgyak darabolhatók, tehát tört részben is betehetők. Ez lényegében a lineáris relaxációja az előzőnek.

A két változat megoldése eltér: a tört hátizsák probléma egy mohó algoritmussal polinomiálisan megoldható, míg a 0/1 hátizsák NP-nehéz, de dinamikus programozással pseudopolinom időben kezelhető. Nézzük külön a két esetet.

4.1 0/1 hátizsák – Dinamikus programozás

A 0/1 hátizsák egy híres NP-teljes kombinatorikus optimalizálási probléma. Bár legrosszabb esetben exponenciális sok megoldást kellene ellenőrizni ( ${\textstyle 2^{N}}$ kombinációt), dinamikus programozással pseudopolinom időben megoldható: ${\textstyle O(N\cdot W)}$ lépésben, ahol ${\textstyle W}$ a kapacitás (ez akkor hatékony, ha ${\textstyle W}$ nem túl nagy). A dinamika alapja, hogy sorra vesszük a tárgyakat, és számontartjuk, hogy adott súlykeret mellett mennyi értéket tudunk maximum elérni.

Definiáljuk ${\textstyle dp[i][w]}$ értékként a maximális összértéket, amit az első ${\textstyle i}$ tárgy felhasználásával elérhetünk úgy, hogy a hátizsák kapacitása legfeljebb ${\textstyle w}$ súlyegység. Ekkor az átmeneti reláció:

Ha nem tesszük be az ${\textstyle i}$ -edik tárgyat, akkor ${\textstyle dp[i][w]=dp[i-1][w]}$ (ugyanaz az érték, mintha ${\textstyle i}$ -et nem is látnánk).
Ha betesszük az ${\textstyle i}$ -edik tárgyat (és ${\textstyle w_{i}\leq w}$ ), akkor ${\textstyle dp[i][w]=dp[i-1][w-w_{i}]+v_{i}}$ (kihasználjuk, amit az előzőekből a maradék súlyon elérhettünk, plusz hozzáadjuk ${\textstyle i}$ értékét).

Tehát ${\textstyle dp[i][w]=\max(dp[i-1][w],;dp[i-1][w-w_{i}]+v_{i})}$ , ha ${\textstyle w_{i}\leq w}$ , egyébként ha az ${\textstyle i}$ -ik nem fér bele, akkor értelemszerűen ${\textstyle dp[i][w]=dp[i-1][w]}$ . A határeset ${\textstyle dp[0][w]=0}$ (0 tárgyból 0 érték érhető el). Az eredmény ${\textstyle dp[N][W]}$ lesz, a maximális érték.

Példa: Legyen ${\textstyle W=50}$ . Tárgyak:

súly 10, érték 60
súly 20, érték 100
súly 30, érték 120 Ez egy klasszikus példa. DP táblázattal: ${\textstyle dp[1][w]}$ az első tárggyal, ${\textstyle dp[2][w]}$ kettővel stb. Végül ${\textstyle dp[3][50]=220}$ lesz (az 1. és 2. tárgyat érdemes választani, 60+160=220). A 3. és 1. tárgy 180-at adna, a 2. és 3. 220-at, mindhárom nem fér be (súlyuk összesen 60, túl sok). Itt két optimális megoldás is van (tárgy2+1 vagy tárgy2+3), egyaránt 220 értékkel.

C++ implementáció – DP (táblázatos):

#include <bits/stdc++.h>
using namespace std;
int main() {
    int N = 3;
    int W = 50;
    vector<int> weight =```cpp
#include <bits/stdc++.h>
using namespace std;
int main() {
    int N = 3;
    int W = 50;
    vector<int> weight = {10, 20, 30};
    vector<int> value = {60, 100, 120};
    // 2D DP tömb (N+1) x (W+1) méretű, 0-val inicializálva
    vector<vector<int>> dp(N+1, vector<int>(W+1, 0));
    // Dinamikus programozás kitöltése
    for(int i = 1; i <= N; ++i) {
        for(int w = 0; w <= W; ++w) {
            dp[i][w] = dp[i-1][w]; // alapértelmezés: nem vesszük fel i-edik tárgyat
            int wi = weight[i-1];
            int vi = value[i-1];
            if(wi <= w) {
                // megpróbáljuk felvenni az i-edik tárgyat is
                dp[i][w] = max(dp[i][w], dp[i-1][w - wi] + vi);
            }
        }
    }
    cout << "Maximalis ertek (DP): " << dp[N][W] << endl;
    // Visszakeresés: mely tárgyakat vettük fel?
    int w = W;
    cout << "Felvett targyak: ";
    for(int i = N; i >= 1; --i) {
        if(dp[i][w] != dp[i-1][w]) {
            // az i-edik tárgy hozzájárult az optimumhoz
            cout << i << " ";
            w -= weight[i-1];
        }
    }
    cout << endl;
}

A kód feltölti a dp táblát a fenti reláció alapján. A végén dp[N][W] adja a maximum összértéket. Egy visszakereső ciklussal (backtrace) megállapíthatjuk, mely tárgyak lettek kiválasztva: ha ${\textstyle dp[i][w]\neq dp[i-1][w]}$ , akkor az ${\textstyle i}$ -edik tárgy benne van az optimális megoldásban (mert az érték akkor nőtt az ${\textstyle i}$ -dik figyelembevételével). A fenti példa inputon a kimenet: Maximalis ertek (DP): 220 és pl. Felvett targyak: 3 2 (vagy más ekvivalens optimális kombináció, a sorrend visszafelé van, itt 2. és 3. tárgy, ami 100+120=220 érték).

4.2 0/1 hátizsák – Branch and Bound módszer

A dinamikus programozás pseudopolinomiális (a kapacitástól függ a futásideje), nagy ${\textstyle W}$ esetén vagy ha ${\textstyle N}$ is nagy, nem hatékony. A branch and bound (ágvágás) egy nem determinisztikus fát bejáró kereső algoritmus, amely a teljes keresési teret járja be, de metszi a nem ígéretes ágakat felső becslések (bound) segítségével. Hátizsák esetén a térfa úgy épül, hogy tárgyanként döntünk: betesszük (1) vagy nem tesszük (0) a tárgyat. Ez egy bináris döntési fa, ${\textstyle 2^{N}}$ levelekkel. A B&B lényege, hogy egy csomópontnál (részleges döntésnél) kiszámítunk egy optimista becslést az elérhető maximális értékre azon az ágakon, és ha ez a becsült maximum sem éri el az aktuálisan már talált legjobb megoldás értékét, akkor nem folytatjuk az adott ág feltárását (lemetszük).

Hátizsáknál a standard felső becslés: úgy számítjuk, hogy a fennmaradó kapacitást a lehető legjobb módon töltjük ki – azaz megengedjük, hogy a maradék tárgyak tört részben is beférjenek. Ez a frakcionális hátizsák optimális értéke, amit könnyen ki tudunk számolni egy mohó módszerrel: a még nem döntött tárgyakat rendezzük csökkenő ${\textstyle v_{i}/w_{i}}$ érték:súly arány szerint, és ebben a sorrendben töltsük fel a maradék kapacitást – ha egy tárgy teljesen belefér, vegyük be teljes értékével, ha már csak tört rész fér, vegyük annak arányos értékét. Az így kapott összérték a lehető legjobb, amit az adott részleges megoldásból még kihozhatunk (egy felső korlát az adott ágra).

Branch and Bound algoritmus:

Kezdjük üres hátizsákkal, aktuális érték = 0, index = 0 (nincs még feldolgozott tárgy).
Számítsuk ki a felső becslést (bound) ebből az állapotból (ez gyakorlatilag a teljes frakcionális optimum) – ez kezdetben egy érték.
Vezessünk be egy globális változót a legjobb talált (eddigi) megoldás értékére, kezdetben 0.
Végezzünk mélységi (DFS) vagy szélességi keresést a döntési fában:
- Minden csomópont reprezentál egy részleges kiválasztási döntést az első ${\textstyle k}$ tárgyra vonatkozólag, megadva eddigi összsúlyt és összértéket.
- Egy csomópontból két gyerek keletkezhet: az egyikben a következő ( ${\textstyle k+1}$ -edik) tárgyat betesszük, a másikban kihagyjuk.
- Mielőtt ténylegesen legenerálnánk a gyerekeket, számítsunk becslést:
  - Ha a csomópont teljes súlya > W (tehát érvénytelen állapot, túlpakoltuk a hátizsákot), akkor vágjuk le (nem folytatjuk azon az ágon).
  - Számítsuk ki a felső becslést a csomópontból kiindulva a még hátralevő tárgyakra (ezt nevezzük ${\textstyle bound}$ értéknek).
  - Ha ez a bound ${\textstyle \leq }$ jelenlegi legjobb érték, akkor ez az ág sem hozhat jobb megoldást, lemetsszük.
  - Különben, ha a bound nagyobb, akkor érdemes ezt az ágat tovább vizsgálni:
    - Ha ez egy levélcsomópont (már ${\textstyle N}$ tárgyat döntöttünk), akkor frissítjük a legjobb megoldást, ha az aktuális érték nagyobb.
    - Ha nem levél, akkor generáljuk a két gyereket (include/exclude következő tárgy) és folytatjuk a keresést rekurzívan.
Az algoritmus végére a globális legjobb tartalmazza az optimális értéket, és akár az ehhez tartozó kiválasztást is (ha eltároljuk pl. a legjobb kombinációt).

Illusztráció: Tegyük fel ${\textstyle N=4}$ , ${\textstyle W=15}$ , tárgyak (súly,érték):

(4, 12), 2. (2, 1), 3. (6, 4), 4. (3, 10). Először rendezzük arány szerint a becsléshez: érték/súly: t1:3, t2:0.5, t3:0.67, t4:3.33. Sorbarendezve pl.: (4,3,1,2) vagy (4,1,3,2) aszerint hogy 4. 3.33, 1. 3, 3. 0.667, 2. 0.5. Feltételezzük ezt a sorrendet a becslésnél. Kezdés: üres, bound = frakcionális optimum = talán 12+10+4*? Actually számoljuk: Rendezve (4:3.33),(1:3),(3:0.667),(2:0.5). Kapacitás 15. Berakjuk 4. tárgy (3kg,10 érték, marad 12kg), berakjuk 1. tárgy (4kg,12 érték, marad 8kg), berakjuk 3. tárgy (6kg,4 érték, marad 2kg), berakni 2. már csak 2kg-ot tudunk 2-ből (2kg a súlya, 1 érték teljes). Valójában mind belefér: 3+4+6+2 = 15kg pont, érték = 10+12+4+1 = 27. Ez a frakcionális optimum és valójában integrálisan is befér minden (!) – ebben az esetben nyilván a megoldás 27, de a példa kedvéért tegyük fel más paraméterekkel lenne vágás. A B&B meg fogja találni a 27-et.

C++ implementáció – Branch and Bound (mélységi kereséssel):

#include <bits/stdc++.h>
using namespace std;

struct Item { int w; int v; double ratio; };

int N = 4;
int W = 15;
Item itemsArr[] = {{4,12}, {2,1}, {6,4}, {3,10}}; // példa tárgyak

// Globális legjobb eredmény
int bestValue = 0;
vector<int> bestTaken;

double fractionalBound(int index, int currentWeight, int currentValue, const vector<Item>& items) {
    // Ha már nincs kapacitás, a bound az aktuális érték
    if(currentWeight > W) return 0; 
    double boundValue = currentValue;
    int remainingCapacity = W - currentWeight;
    // Vegyük sorra a hátralévő tárgyakat index-től, mohón
    for(int j = index; j < N; ++j) {
        if(items[j].w <= remainingCapacity) {
            remainingCapacity -= items[j].w;
            boundValue += items[j].v;
        } else {
            // részleges befoglalás
            boundValue += items[j].v * ((double) remainingCapacity / items[j].w);
            break;
        }
    }
    return boundValue;
}

void knapsackBB(int index, int currentWeight, int currentValue, vector<int>& taken, const vector<Item>& items) {
    // Ha már az összes tárgyat eldöntöttük
    if(index == N) {
        if(currentWeight <= W && currentValue > bestValue) {
            bestValue = currentValue;
            bestTaken = taken;
        }
        return;
    }

    // Bound calculation for this node
    double boundVal = fractionalBound(index, currentWeight, currentValue, items);
    if(boundVal <= bestValue) {
        // Még a legoptimistább esetben sem verné meg a jelenlegi optimumot
        return;
    }

    // Próbáljuk felvenni az index-ik tárgyat
    if(currentWeight + items[index].w <= W) {
        taken[index] = 1;
        knapsackBB(index+1, currentWeight + items[index].w, currentValue + items[index].v, taken, items);
        taken[index] = 0;
    }
    // Próbáljuk kihagyni az index-ik tárgyat
    knapsackBB(index+1, currentWeight, currentValue, taken, items);
}

int main() {
    // Kiszámoljuk az arányokat és rendezzük a tárgyakat csökkenő value/weight szerint a bound-hoz
    vector<Item> items;
    for(int i=0;i<N;++i) {
        Item it = itemsArr[i];
        it.ratio = (double)it.v / it.w;
        items.push_back(it);
    }
    sort(items.begin(), items.end(), [](const Item& a, const Item& b){
        return a.ratio > b.ratio;
    });
    vector<int> taken(N, 0);
    knapsackBB(0, 0, 0, taken, items);
    cout << "Legjobb elert osszertek: " << bestValue << endl;
    cout << "Felvett targyak (rendezett sorrendben): ";
    for(int i = 0; i < N; ++i) {
        if(bestTaken[i]) cout << "T" << i+1 << " ";
    }
    cout << endl;
}

A kódban az Item struktúra tárolja a tárgy adatait, a globális bestValue és bestTaken pedig a legjobb talált megoldást. A fractionalBound függvény kiszámítja a felső becslést (bound) a jelenlegi részleges állapottól indulva: végigmegy a még hátralévő tárgyakon és feltölti a maradék kapacitást teljes vagy tört résztárgyakkal. A knapsackBB függvény végzi a backtracking keresést:

Ha a levélszintre ér (index == N), frissíti a legjobbat, ha az aktuális megoldás jobb.
Különben kiszámolja a boundVal értéket az aktuális csomópontra. Ha ez nem haladja meg a bestValue-t, akkor return - az ág lemetszése.
Ha van remény, akkor két irányba ágazunk: (1) ha lehetséges, hozzáadjuk a következő tárgyat (ha belefér a kapacitásba), és rekurzívan folytatjuk; (2) illetve kihagyjuk a tárgyat és folytatjuk. (Itt előbb próbáltuk felvenni, de a sorrend nem kötött; akár egy priorizált sorrend is lehet heuristika szerint.)
A taken vektor nyilvántartja, hogy a rendezett items listából mely indexek vannak aktuálisan felvéve.

A rendezés miatt a bestTaken kimenet is erre a rendezett listára vonatkozik. A fenti példában a rendezés a tárgyak sorrendjét megváltoztathatja, de a beazonosítás kedvéért kiírtuk az eredeti sorszámokat (T1, T2,…). Az algoritmus DFS jellege miatt nem garantált a legelső megtalált megoldás optimális, de a metszések jelentősen csökkentik a bejárandó csomópontok számát átlagos esetben. Legrosszabb esetben természetesen ${\textstyle 2^{N}}$ node is lehet (pl. ha sok egyforma értékű-súlyú tárgy van, a bound nem sokat segít), de gyakorlatban a branch and bound sok esetben hatékonyabb, mint a bruteforce.

4.3 Frakcionális hátizsák – Mohó algoritmus

A tört (frakcionális) hátizsák probléma megengedőbb: lehetőség van egy tárgynak csak egy részét is betenni. Ekkor a probléma greedy algoritmussal optimálisan megoldható. A megoldás kulcsa, hogy a legjobb stratégiánk mindig a legnagyobb érték/súly arányú tárgyakat előnyben részesíteni. Ennek intuitív belátása: ha egy tárgy egy egység súlyra nagyon sok értéket ad, akkor érdemes azt (vagy amennyit lehet belőle) elsőként pakolni, hogy a korlátozott súlykapacitást a lehető legjobban kihasználjuk. Formálisan bizonyítható, hogy ez a mohó stratégia ad optimális megoldást tört esetben.

Algoritmus:

Számoljuk ki minden tárgyra a ${\textstyle r_{i}=v_{i}/w_{i}}$ érték-súly arányt.
Rendezzük a tárgyakat csökkenő ${\textstyle r_{i}}$ szerint.
Kezdetben a hátizsák üres (maradék kapacitás ${\textstyle =W}$ ).
Sorban menjünk végig a rendezett listán:
- Ha a következő tárgy súlya belefér teljesen a maradék kapacitásba, vegyük be az egészet. (Kapacitás csökken ${\textstyle w_{i}}$ -vel, érték növekszik ${\textstyle v_{i}}$ -vel.)
- Ha már nem fér be teljesen, vegyük be amekkora arányban még befér. Tegyük fel ${\textstyle x}$ súlyt tudunk még betenni a ${\textstyle w_{i}}$ -ből; ez az ${\textstyle x/W}$ arányú rész a tárgy értékének ugyanekkora arányát hozza: ${\textstyle {\frac {x}{w_{i}}}v_{i}}$ . Vegyük fel ezt az értéket, és a kapacitást nullára merítjük.
- Folytassuk, amíg van kapacitás vagy el nem fogynak a tárgyak.
Az összegyűjtött érték lesz az optimális összérték.

Példa: ${\textstyle W=50}$ , tárgyak mint korábban: (10,60), (20,100), (30,120). Arányok: 6, 5, 4 (érték per súly). Rendezve marad ebben a sorrendben. Pakolás: először az 1. tárgy (10kg) -> érték 60, marad kapacitás 40. Utána 2. tárgy (20kg) -> érték +100=160, marad kapacitás 20. Utána 3. tárgy (30kg) -> csak 20kg-ot tudunk betenni belőle, ami a 30kg-os tárgy 2/3 része, így érték + ${\textstyle 120*(20/30)=80}$ . Összes érték = 240. Ez az optimális megoldás értéke a tört verzióban. (Megjegyzendő: a 0/1 verzióban ugyanennél a példánál 220 volt a maximum, mert ott nem vehetjük fel a 3. tárgy 2/3-át, csak egész tárgyakat.)

C++ implementáció – Frakcionális knapsack:

#include <bits/stdc++.h>
using namespace std;

struct Item { int w; int v; };

double fractionalKnapsack(int W, vector<Item>& items) {
    // Rendezzük az itemeket csökkenő érték/súly szerint
    sort(items.begin(), items.end(), [](const Item& a, const Item& b){
        return (double)a.v / a.w > (double)b.v / b.w;
    });
    double totalValue = 0.0;
    int remainingCapacity = W;
    for(auto& it : items) {
        if(it.w <= remainingCapacity) {
            // teljes tárgyat bele
            totalValue += it.v;
            remainingCapacity -= it.w;
        } else {
            // tört rész
            totalValue += (double)it.v * remainingCapacity / it.w;
            remainingCapacity = 0;
            break;
        }
    }
    return totalValue;
}

int main() {
    int W = 50;
    vector<Item> items = {{10,60}, {20,100}, {30,120}};
    double maxVal = fractionalKnapsack(W, items);
    cout << "Maximalis ertek (tort knapsack): " << maxVal << endl;
}

A kód először rendezi a tárgyakat a megadott kritérium szerint (lambdában számítja a ${\textstyle v/w}$ arányt). Ezután megy végig a rendezett listán, és amíg fér, teljes tárgyakat pakol be, ha már nem fér egy tárgy, akkor kiszámítja, mekkora tört része fér be és hozzáadja az arányos értéket. Végül visszaadja a kalkulált értéket. A fenti bemenetnél kiírja: Maximalis ertek (tort knapsack): 240.

Megjegyzés: A tört hátizsák mindig legalább olyan értékű vagy jobb megoldást ad, mint a 0/1 verzió, hiszen a 0/1 megoldásterének egy felülről vett kontinuuma (relaxációja). Ezért a frakcionális optimum jó felső korlát a 0/1 optimumra – ezt használtuk ki a branch and boundban is. Ugyanakkor a 0/1 eset jóval nehezebb, ott nem működik a mohó: ellenpélda pl. ha van egy nagyon nagy értékű de kicsit rosszabb arányú tárgy, amit egészben csak úgy tudunk bevenni, ha több kisebb jó arányút kihagyunk – itt a greedy nem ad optimális megoldást. Erre példa: W=50, tárgyak (49kg, ${\textstyle v=100}$ ) és (30kg, ${\textstyle v=90}$ ),(20kg, ${\textstyle v=90}$ ). Arányok: 100/49≈2.04, 90/30=3, 90/20=4. Greedy a 20kg és 30kg-t választaná (összérték 180), de a optimális 49kg-s tárgy+20kg-s nem fér, 49kg-s + 30kg-s nem fér, csak 49kg-s egyedül (érték 100) ami kevesebb, viszont 49kg-s + 1kg még valami kéne de nincs, szóval itt mégis a greedy adott jót… keressünk másikat: (40kg, ${\textstyle v=500}$ ) és (20kg, ${\textstyle v=400}$ ),(20kg, ${\textstyle v=400}$ ), W=40. Arányok: 12.5, 20, 20. Greedy két 20-ast venne (800), de nem lehet kétszer 20, W=40 úgy pont fér 2x20: 800. Az 500-as kimarad, optimum valóban 800, tehát ez nem ellenpélda. Hmm. Az ellenpélda tipikusan olyan, ahol egy nagy értékű item combos. Mondjuk (W=50): (50kg, ${\textstyle v=100}$ ) vs (30kg, ${\textstyle v=60}$ )+(20kg, ${\textstyle v=60}$ ). Arányok:2, 2,2. Itt mindegy, 100 vs 120 opt. Greedy nem hibázik. Valójában a greedy arányra nem ad optimális 0/1 megoldást tipikus példája a klasszikus: (W=50): (49kg, ${\textstyle v=50}$ ) (1kg, ${\textstyle v=1}$ *sokszor). Arány mind ~1, de optimum talán más. Mindegy, a lényeg: 0/1-nél DP vagy B&B kell, tört-nél greedy optimális.

Összefoglalás: Az operációkutatás fenti problémáira különböző algoritmusokat ismertettünk. A szimplex lineáris programozásban garantált optimumot ad polinomiális lépésszám mellett átlagosan, a szállítási feladat speciális szerkezetét kihasználva Vogel közelítés gyors kezdőpontot ad, majd a MODI/Stepping Stone finomít optimummá. A hozzárendelési (assignment) probléma magyar módszere mátrixredukcókkal és párosítással polinomiális időben megoldja a feladatot optimálisan. A hátizsák probléma 0/1 esete NP-nehéz, de dinamikus programozás segít kis kapacitásig, vagy branch and bound metszésekkel átlagban kezelhető méretig skáláz. A frakcionált változat mohó stratégiával lineáris idő alatt (rendezés ${\textstyle O(N\log N)}$ plusz lineáris bepakolás) optimálisan oldható. A fenti algoritmusok mind fontos eszközök az operációkutatás gyakorlatában, és számos kombinatorikus optimalizálási feladatra adnak hatékony megoldást.

angol: operations research (en), operational research (en)
francia: recherche opérationnelle (fr)
orosz: исследование операций (ru) (issledovanije operacij)

További információk

operációkutatás - Értelmező szótár (MEK)
operációkutatás - Etimológiai szótár (UMIL)
operációkutatás - Szótár.net (hu-hu)
operációkutatás - DeepL (hu-de)
operációkutatás - Яндекс (hu-ru)
operációkutatás - Google (hu-en)
operációkutatás - Helyesírási szótár (MTA)
operációkutatás - Wikidata
operációkutatás - Wikipédia (magyar)