Ugrás a tartalomhoz

Vogel's approximation method

A Wikiszótárból, a nyitott szótárból
(VAM szócikkből átirányítva)


Főnév

Vogel's approximation method (tsz. Vogel's approximation methods)

  1. (informatika) A Vogel-féle approximációs módszer (Vogel’s Approximation Method, röviden VAM) egy heurisztikus algoritmus, amelyet a szállítási feladat (transportation problem) kezdeti megoldásának meghatározására használnak. Ez egy lineáris programozási probléma, ahol a cél az, hogy a költségek minimalizálása mellett kielégítsük a különböző igényeket adott kapacitásból. A Vogel-módszer egy „okos” kezdeti lépést ad a probléma megoldásához, amely gyakran közel van az optimálishoz, így jó kiindulási alapot jelent az optimalizáló lépésekhez (pl. Stepping Stone vagy MODI-módszer).


🌐 1. A probléma háttere

A szállítási feladat egy speciális lineáris programozási probléma, ahol:

  • Adott m számú forrás (pl. raktár), ahol egyenként ismert a kínálat (supply).
  • Adott n számú célállomás (pl. bolt), ahol ismert az igény (demand).
  • Adott egy m × n-es mátrix, amely a szállítási költségeket tartalmazza.

A cél: Minimális költséggel szállítani úgy, hogy minden kereslet és kínálat teljesüljön.


🧠 2. Vogel-féle módszer célja

A módszer célja: egy kezdeti bázismegoldás meghatározása, azaz egy olyan megoldás, amely megfelel a korlátoknak (kereslet és kínálat), és amellyel elkezdhetjük az optimalizálási lépéseket. Nem garantálja az optimális megoldást, de gyakran jobb, mint az északi-nyugati sarok módszer (NWCM) vagy a legkisebb költség módszer (LCM).


📐 3. A Vogel-féle approximáció lépései

1. Különbségek (penalty) kiszámítása

  • Minden sorban és oszlopban megkeressük a két legkisebb költséget.
  • A különbség (más néven büntetés) = 2 legkisebb költség különbsége.
  • Ezeket a különbségeket elmentjük.

2. Maximális különbség kiválasztása

  • Megkeressük azt a sort vagy oszlopot, ahol a különbség a legnagyobb.
  • Ez azt jelzi, hogy itt a legfontosabb „jó döntést” hozni, mert a rossz választás itt kerülne a legtöbbe.

3. Minimum költségű cella kiválasztása

  • A kiválasztott sorban vagy oszlopban megkeressük a legalacsonyabb költségű cellát.
  • Ez lesz az a cella, ahová allokálunk (szállítunk).

4. Allokálás

  • A kiválasztott cellába annyit szállítunk, amennyi a sor (forrás) és az oszlop (cél) aktuális értékéből a minimum.
  • Ezután levonjuk ezt az értéket a sorból és oszlopból.

5. Sor vagy oszlop kizárása

  • Ha egy sor vagy oszlop 0-ra csökken, azt kizárjuk a további lépésekből.
  • Ha mindkettő 0 lesz egyszerre, csak az egyiket zárjuk ki (általában azt, ahol kevesebb a még hátralévő érték).

6. Ismétlés

  • Visszatérünk az első lépéshez, és ismételjük, amíg minden cellát ki nem töltöttünk.


🧾 4. Példa lépésenként

Tegyük fel, van 3 raktár (A, B, C) és 3 bolt (X, Y, Z), valamint a következő költségmátrix:

X Y Z Kínálat
A 19 30 50 7
B 70 30 40 9
C 40 8 70 18
Kereslet 5 8 21
  1. Különbségek számítása:
    • Sor A: min(19,30) → 11
    • Sor B: min(30,40) → 10
    • Sor C: min(8,40) → 32
    • Oszlop X: min(19,40) → 21
    • Oszlop Y: min(8,30) → 22
    • Oszlop Z: min(40,50) → 10
  2. Max büntetés: Sor C (32)
  3. Sor C-ben a legkisebb költség: 8 (Y) → allokálunk 8 egységet (Y keresletét kielégítjük).
  4. Frissítjük készletet és igényt:
    • C: 18 → 10
    • Y: 8 → 0 → oszlop Y kizárva
  5. Új különbségek kiszámítása… és folytatjuk így tovább.


📊 5. Előnyök és hátrányok

✅ Előnyök:

  • Jobb kezdeti megoldást ad, mint NWCM vagy LCM.
  • Egyszerűen programozható.
  • Közelebb van az optimálishoz → gyorsabb konvergencia az optimalizálás során.

❌ Hátrányok:

  • Nem mindig adja az optimális megoldást.
  • Több számítás, mint az NWCM-ben (büntetések miatt).
  • Csak kiegyensúlyozott problémákra alkalmazható – ha nem az, dummy sort/oszlopot kell hozzáadni.


🛠️ 6. Kiegyensúlyozatlan probléma kezelése

Ha a teljes kínálat ≠ kereslet, akkor a problémát kiegyensúlyozni kell:

  • Ha a kínálat nagyobb, adj hozzá egy dummy vevőt (fiktív oszlop) 0 költséggel.
  • Ha a kereslet nagyobb, adj hozzá egy dummy szállítót (fiktív sor) 0 költséggel.


💡 Összegzés

A Vogel-féle approximációs módszer egy praktikus technika a szállítási feladat kiinduló megoldásának megadására. Hatékonyabb, mint a klasszikus módszerek, és különösen hasznos, ha az optimalizálási algoritmust (pl. Stepping Stone) gyorsítani szeretnénk. Bár nem garantálja az optimális eredményt, az esetek többségében nagyon közel áll hozzá.


Itt van a Vogel-féle közelítő módszer (Vogel’s Approximation Method – VAM) részletes pszeudokódja, amely a szállítási feladatokhoz nyújt egy kezdeti bázismegoldást:


📌 Vogel-féle közelítő módszer – pszeudokód

Input:
    - supply[0..m-1]     : készletek minden sorhoz
    - demand[0..n-1]     : igények minden oszlophoz
    - cost[m][n]         : költségmátrix

Output:
    - allocation[m][n]   : szállítási mennyiség minden cellában

Initialize:
    - Mark all rows and columns as unfulfilled
    - allocation[m][n] = 0 for all i,j

While there are unfulfilled rows or columns:

    1. For each unfulfilled row:
        - Find the two lowest costs in the row
        - Calculate penalty = 2nd lowest - 1st lowest

    2. For each unfulfilled column:
        - Find the two lowest costs in the column
        - Calculate penalty = 2nd lowest - 1st lowest

    3. Find the row or column with the **maximum penalty**

    4. In that row or column, find the **cell with minimum cost** (i, j)

    5. Allocate to cell (i, j):
        - x = min(supply[i], demand[j])
        - allocation[i][j] = x
        - supply[i] -= x
        - demand[j] -= x

    6. If supply[i] == 0:
        - Mark row i as fulfilled

    7. If demand[j] == 0:
        - Mark column j as fulfilled

    8. If both supply[i] and demand[j] == 0:
        - Mark either row or column (but not both!) to avoid degeneracy

Return allocation matrix

🧠 Rövid magyarázat

A VAM célja, hogy “jó” első bázismegoldást adjon a szállítási problémához azáltal, hogy:

  • különbségi büntetéseket számol (penalty) minden sorra/oszlopra,
  • mindig a legnagyobb büntetéssel rendelkező sort/oszlopot választja ki,
  • és ott a legkisebb költségű cellát tölti fel,
  • ezután frissíti a készleteket és igényeket.

Ez az eljárás nem garantálja az optimális megoldást, de gyakran közel van hozzá, és jó kezdőpont a MODI vagy Stepping Stone módszerhez.


#include <iostream>
#include <vector>
#include <iomanip>
#include <limits>
#include <algorithm>
#include <conio.h> // for _getch() on Windows

using namespace std;

struct Allocation {
    int amount;
    bool allocated;
};

void printMatrix(const vector<vector<int>>& cost,
                 const vector<vector<Allocation>>& alloc,
                 const vector<int>& supply,
                 const vector<int>& demand) {
    int m = cost.size();
    int n = cost[0].size();

    cout << "\n     ";
    for (int j = 0; j < n; ++j) cout << " D" << j + 1 << "  ";
    cout << " Supply\n";
    for (int i = 0; i < m; ++i) {
        cout << "R" << i + 1 << " |";
        for (int j = 0; j < n; ++j) {
            if (alloc[i][j].allocated)
                cout << setw(2) << alloc[i][j].amount << "(" << cost[i][j] << ") ";
            else
                cout << "   (" << setw(2) << cost[i][j] << ") ";
        }
        cout << " |  " << supply[i] << "\n";
    }
    cout << "    ";
    for (int j = 0; j < n; ++j) cout << "  " << setw(2) << demand[j] << " ";
    cout << "  Demand\n\n";
}

int main() {
    vector<vector<int>> cost = {
        {19, 30, 50, 10},
        {70, 30, 40, 60},
        {40, 8, 70, 20}
    };

    vector<int> supply = {7, 9, 18};
    vector<int> demand = {5, 8, 7, 14};
    int m = cost.size();
    int n = cost[0].size();

    vector<vector<Allocation>> alloc(m, vector<Allocation>(n, {0, false}));

    vector<bool> rowDone(m, false), colDone(n, false);

    while (true) {
        // Step 1: Compute penalties
        vector<int> rowPenalty(m, -1), colPenalty(n, -1);

        for (int i = 0; i < m; ++i) {
            if (rowDone[i]) continue;
            vector<int> rowCosts;
            for (int j = 0; j < n; ++j) if (!colDone[j]) rowCosts.push_back(cost[i][j]);
            if (rowCosts.size() >= 2) {
                sort(rowCosts.begin(), rowCosts.end());
                rowPenalty[i] = rowCosts[1] - rowCosts[0];
            }
        }

        for (int j = 0; j < n; ++j) {
            if (colDone[j]) continue;
            vector<int> colCosts;
            for (int i = 0; i < m; ++i) if (!rowDone[i]) colCosts.push_back(cost[i][j]);
            if (colCosts.size() >= 2) {
                sort(colCosts.begin(), colCosts.end());
                colPenalty[j] = colCosts[1] - colCosts[0];
            }
        }

        // Step 2: Find max penalty
        int maxPen = -1, isRow = true, idx = -1;
        for (int i = 0; i < m; ++i)
            if (rowPenalty[i] > maxPen) { maxPen = rowPenalty[i]; isRow = true; idx = i; }
        for (int j = 0; j < n; ++j)
            if (colPenalty[j] > maxPen) { maxPen = colPenalty[j]; isRow = false; idx = j; }

        if (idx == -1) break; // done

        // Step 3: Find min cost cell in selected row/column
        int selI = -1, selJ = -1, minCost = numeric_limits<int>::max();
        if (isRow) {
            for (int j = 0; j < n; ++j) {
                if (!colDone[j] && cost[idx][j] < minCost) {
                    minCost = cost[idx][j];
                    selI = idx;
                    selJ = j;
                }
            }
        } else {
            for (int i = 0; i < m; ++i) {
                if (!rowDone[i] && cost[i][idx] < minCost) {
                    minCost = cost[i][idx];
                    selI = i;
                    selJ = idx;
                }
            }
        }

        // Step 4: Allocate
        int quantity = min(supply[selI], demand[selJ]);
        alloc[selI][selJ] = {quantity, true};
        supply[selI] -= quantity;
        demand[selJ] -= quantity;

        if (supply[selI] == 0) rowDone[selI] = true;
        if (demand[selJ] == 0) colDone[selJ] = true;

        printMatrix(cost, alloc, supply, demand);
        cout << "Press any key to continue..."; _getch(); cout << "\n";
    }

    cout << "Final allocation matrix:\n";
    printMatrix(cost, alloc, supply, demand);

    return 0;
}



A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=Vogel%27s_approximation_method&oldid=3495453”