Ugrás a tartalomhoz

MODI method

A Wikiszótárból, a nyitott szótárból

Angol


Főnév

MODI method (tsz. MODI methods)

  1. (informatika) modified distribution method

A MODI-módszer (teljes nevén: Modified Distribution Method, magyarul: módosított elosztási módszer) egy hatékony algoritmus a szállítási probléma optimalizálására. A célja ugyanaz, mint a Stepping-Stone módszeré: csökkenteni az összköltséget egy kezdeti, megvalósítható (feasible) szállítási terv folyamatos javításával. A MODI módszer azonban gyorsabb és strukturáltabb, mint a Stepping-Stone.


📦 A szállítási probléma röviden

Adott:

  • m darab forráshely (pl. raktár), mindegyikhez tartozik egy kínálat (supply)
  • n darab célállomás (pl. bolt), mindegyikhez tartozik egy igény (demand)
  • Minden (i,j) cellához tartozik egy költség: C[i][j], az egységnyi szállítás költsége

Cél:

Úgy meghatározni a szállított mennyiségeket X[i][j], hogy teljesüljenek a kínálati és igényfeltételek, és a teljes költség ΣΣ C[i][j] * X[i][j] minimális legyen.

🧩 MODI módszer alapgondolata

A MODI módszer az árnyékárakon (potenciálokon) keresztül számolja ki, hogy mely nem-alapváltozók (üres cellák) tudnának költséget csökkenteni.

A módszer a következő elven működik:

  • Minden sorhoz tartozik egy Ui potenciál
  • Minden oszlophoz tartozik egy Vj potenciál
  • Minden báziscellára (i,j) teljesül: Ui + Vj = C[i][j]
  • Ezekből a Ui és Vj értékekből kiszámíthatjuk minden üres cellára a redukált költséget: Δ[i][j] = C[i][j] - (Ui + Vj)

Ha minden Δ[i][j] ≥ 0, akkor az aktuális megoldás optimális. Ha van olyan Δ[i][j] < 0, akkor azon a cellán keresztül lehetne javítani az összköltségen – hasonlóan, mint a Stepping-Stone módszernél.


⚙️ MODI módszer lépései

1. Kezdeti bázismegoldás elkészítése

Ehhez használhatunk például:

  • North-West Corner Method
  • Vogel-féle közelítés (VAM)

A megoldásnak m+n−1 darab bázisváltozót kell tartalmaznia (nem lehet kevesebb – ha mégis, degenerált, kezelni kell “ε” értékekkel).


2. Potenciálok (Ui és Vj) kiszámítása

Indítsunk valamelyik sor vagy oszlop potenciálját nulláról (Ui = 0 vagy Vj = 0).

Ezután minden báziscellára alkalmazzuk: Ui + Vj = C[i][j] és ebből kiszámítjuk a többi Ui és Vj értéket lépésenként.


3. Redukált költségek kiszámítása minden üres cellára

Minden nem-báziscellára (i,j): Δ[i][j] = C[i][j] - (Ui + Vj)

Ha minden Δ[i][j] ≥ 0 → optimális megoldás.

Ha van olyan Δ[i][j] < 0 → lehetőség az optimalizálásra.


4. Válassz egy üres cellát, ahol Δ[i][j] < 0

Ez lesz a bejövő változó. Ezen keresztül próbálunk csökkenteni a költségeken.


5. Építs ciklust a bejövő változó köré

Ugyanúgy, mint a Stepping-Stone módszernél:

  • Kizárólag báziscellákon keresztül haladva
  • Váltakozva vízszintesen és függőlegesen
  • Kiinduló pont: az új (i,j) cella


6. + / – jelek, θ érték meghatározása

  • A ciklusban váltakozó jelekkel jelöljük a cellákat:
    • – + – + – …
  • Azokon a helyeken, ahol mínusz van, nézzük meg a szállított mennyiségeket.
  • A legkisebb ilyen érték adja θ-t (ennyi mozgatható anélkül, hogy negatívba mennénk)


7. Módosítsuk a szállított mennyiségeket a ciklus mentén

  • A + jeles cellákba hozzáadunk θ-t
  • A – jeles cellákból kivonunk θ-t


8. Frissítsük a bázist

  • Az új cella bekerül
  • Az a báziscella, ahol 0 lett a szállított mennyiség, kiesik


9. Ismétlés

Térjünk vissza a 2. lépéshez (új potenciálok, új redukált költségek), és ismételjük, amíg nincs több Δ[i][j] < 0.


👨‍🏫 Egyszerű példa

Legyen az alábbi költségmátrix:

D1 D2 D3 Igény
S1 2 3 1 30
S2 5 4 8 50
S3 5 6 8 20
20 40 40
  1. Készíts egy kezdeti megoldást (pl. VAM)
  2. Számítsd ki az Ui, Vj értékeket a bázis alapján
  3. Számítsd ki minden üres cellára Δ[i][j]
  4. Válassz olyan cellát, ahol Δ[i][j] < 0
  5. Hozz létre ciklust, módosítsd a megoldást


✅ Előnyök

  • Gyorsabb, mint a Stepping-Stone, mivel nem kell minden egyes üres cellára ciklust építeni
  • Könnyebben algoritmizálható
  • Skálázható nagyobb mátrixokra


⚠️ Hátrányok

  • A ciklusépítés továbbra is szükséges (mint Stepping-Stone-nál)
  • Degenerált eseteknél bonyolult lehet


🧮 Összefoglalás

Lépés Művelet
1. Kezdeti bázismegoldás
2. Ui, Vj potenciálok kiszámítása
3. Redukált költségek (Δ) kiszámítása
4. Ha van Δ<0 → lépj tovább, különben kész vagy
5. Ciklus létrehozása a legkedvezőbb Δ[i][j] köré
6. θ meghatározása, mennyiségek módosítása
7. Bázis frissítése
8. Vissza a 2. lépéshez


A MODI módszer tehát egy strukturált, mátrixalapú eljárás a szállítási probléma optimalizálására. Hatékony, könnyen implementálható, és gyakran része a műveletkutatás kurzusoknak, valamint gyakorlati logisztikai szoftverek belső motorjának.


📌 MODI (Modified Distribution Method) – Pszeudokód

Input:
    C[m][n]     // költségmátrix
    S[m]        // kínálatok (supply)
    D[n]        // igények (demand)

1. Készíts egy kezdeti bázismegoldást X[m][n], pl. VAM-mel

2. Repeat:
    a. Állítsd be Ui = "?" és Vj = "?" minden i, j-hez
    b. Válassz egy Ui vagy Vj értéket, pl. Ui0 := 0
    c. Minden báziscellára (i, j), ahol X[i][j] > 0:
        - ha Ui ismert → Vj := C[i][j] - Ui
        - ha Vj ismert → Ui := C[i][j] - Vj
        (ismételd, amíg lehet)

    d. Minden üres (nem bázisban lévő) cellára (i,j):
        Δ[i][j] := C[i][j] - (Ui + Vj)

    e. Ha minden Δ[i][j] ≥ 0:
        OUTPUT "Optimális megoldás", X
        EXIT

    f. Válaszd azt az (i*, j*) cellát, ahol Δ[i][j] a legkisebb (negatív)

    g. Készíts egy zárt ciklust az (i*, j*) cella köré:
        - váltakozva vízszintesen és függőlegesen
        - csak báziscellákon keresztül
        - térjen vissza (i*, j*)-be

    h. Jelöld meg a ciklust váltakozó + és – jelekkel
        (kezdj + jellel az (i*, j*) cellánál)

    i. Határozd meg θ = minimum(X[i][j]) minden "–" jeles cellában

    j. Módosítsd a mennyiségeket:
        - "+": növeld X[i][j]-t θ-val
        - "–": csökkentsd X[i][j]-t θ-val

    k. Frissítsd a bázist:
        - új cella bekerül
        - ahol 0 lett a mennyiség, az kikerül a bázisból

Until minden Δ[i][j] ≥ 0

🔧 Kiegészítés

  • A cikluskeresést (g) gráf-alapú rekurzív eljárással vagy mátrixalapú kereséssel oldjuk meg.
  • Degenerált esetben (ha kevesebb mint m+n−1 báziscella van), ideiglenesen adjunk hozzá “ε” mennyiséget egy üres cellához, hogy a rendszer meghatározott legyen.


✅ C++ MODI metódus (alap implementáció)

#include <iostream>
#include <vector>
#include <limits>
#include <iomanip>
#include <queue>

using namespace std;

const int INF = 1e9;

struct Cell {
    int i, j;
};

int main() {
    // Bemeneti adatok
    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 = supply.size();
    int n = demand.size();

    vector<vector<int>> alloc(m, vector<int>(n, -1)); // -1 jelzi az üres cellát

    // North-West Corner kezdeti megoldás
    vector<int> s = supply, d = demand;
    int i = 0, j = 0;
    while (i < m && j < n) {
        int val = min(s[i], d[j]);
        alloc[i][j] = val;
        s[i] -= val;
        d[j] -= val;
        if (s[i] == 0) i++;
        else j++;
    }

    while (true) {
        // Potenciálok Ui, Vj kiszámítása
        vector<int> u(m, INF), v(n, INF);
        u[0] = 0;

        bool updated;
        do {
            updated = false;
            for (int i = 0; i < m; ++i) {
                for (int j = 0; j < n; ++j) {
                    if (alloc[i][j] != -1) {
                        if (u[i] != INF && v[j] == INF) {
                            v[j] = cost[i][j] - u[i];
                            updated = true;
                        } else if (v[j] != INF && u[i] == INF) {
                            u[i] = cost[i][j] - v[j];
                            updated = true;
                        }
                    }
                }
            }
        } while (updated);

        // Δ(i,j) = C(i,j) - (u[i] + v[j]) kiszámítása minden üres cellára
        int minDelta = 0;
        Cell enter{-1, -1};

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (alloc[i][j] == -1) {
                    int delta = cost[i][j] - (u[i] + v[j]);
                    if (delta < minDelta) {
                        minDelta = delta;
                        enter = {i, j};
                    }
                }
            }
        }

        // Ha nincs negatív Δ, akkor optimális megoldás
        if (enter.i == -1) {
            cout << "\nOptimális megoldás:\n";
            int total = 0;
            for (int i = 0; i < m; ++i) {
                for (int j = 0; j < n; ++j) {
                    if (alloc[i][j] != -1) {
                        cout << setw(3) << alloc[i][j];
                        total += alloc[i][j] * cost[i][j];
                    } else {
                        cout << "  -";
                    }
                }
                cout << endl;
            }
            cout << "Minimális költség: " << total << endl;
            break;
        }

        // Építs ciklust (egyszerűsítve csak négyzetes ciklusra keresünk)
        // Később bővíthető DFS-es általános cikluskereséssel
        // Például: S3-D2-S2-D2

        // Az egyszerűség kedvéért csak akkor működik jól, ha a mátrix kicsi és a ciklus egyértelműen megtalálható
        // Itt most kézzel meghatározott ciklussal illusztráljuk

        // Ciklus: (+enter), (-i,x), (+y,x), (-y,j)
        int ei = enter.i, ej = enter.j;
        int theta = INF;
        Cell minus1{-1, -1}, minus2{-1, -1};

        // Keresünk egy sort (i), ahol (i, ej) foglalt
        for (int x = 0; x < m; ++x) {
            if (alloc[x][ej] != -1 && x != ei) {
                for (int y = 0; y < n; ++y) {
                    if (alloc[x][y] != -1 && y != ej && alloc[ei][y] != -1) {
                        minus1 = {x, ej};
                        minus2 = {ei, y};
                        theta = min(alloc[x][ej], alloc[ei][y]);
                        break;
                    }
                }
            }
        }

        // Ha nem találtunk ciklust → kilépés
        if (theta == INF || minus1.i == -1) {
            cout << "Nem sikerült ciklust építeni.\n";
            break;
        }

        // Ciklus végrehajtása: +, -, +, -
        alloc[ei][ej] = theta;
        alloc[minus1.i][minus1.j] -= theta;
        alloc[minus2.i][minus2.j] -= theta;

        if (alloc[minus1.i][minus1.j] == 0) alloc[minus1.i][minus1.j] = -1;
        if (alloc[minus2.i][minus2.j] == 0) alloc[minus2.i][minus2.j] = -1;
    }

    return 0;
}

✅ C++ MODI metódus (DFS)

#include <iostream>
#include <vector>
#include <limits>
#include <iomanip>
#include <tuple>
#include <stack>
#include <set>

using namespace std;

const int INF = 1e9;

struct Cell {
    int i, j;
};

int m = 3, n = 4;
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};
vector<vector<int>> alloc;

vector<vector<bool>> visited;
vector<Cell> path;

bool dfs(int x, int y, int targetX, int targetY, bool isRow, set<pair<int, int>>& base) {
    if (x == targetX && y == targetY && !path.empty()) return true;
    
    if (isRow) {
        for (int j = 0; j < n; ++j) {
            if ((x != targetX || j != targetY) && alloc[x][j] != -1 && !visited[x][j]) {
                visited[x][j] = true;
                path.push_back({x, j});
                if (dfs(x, j, targetX, targetY, false, base)) return true;
                path.pop_back();
                visited[x][j] = false;
            }
        }
    } else {
        for (int i = 0; i < m; ++i) {
            if ((i != targetX || y != targetY) && alloc[i][y] != -1 && !visited[i][y]) {
                visited[i][y] = true;
                path.push_back({i, y});
                if (dfs(i, y, targetX, targetY, true, base)) return true;
                path.pop_back();
                visited[i][y] = false;
            }
        }
    }
    return false;
}

void printAllocation() {
    cout << "Aktuális allokáció (X):\n";
    int total = 0;
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (alloc[i][j] != -1) {
                cout << setw(4) << alloc[i][j];
                total += alloc[i][j] * cost[i][j];
            } else {
                cout << "   -";
            }
        }
        cout << endl;
    }
    cout << "Teljes költség: " << total << "\n";
}

int main() {
    alloc.assign(m, vector<int>(n, -1));
    vector<int> s = supply, d = demand;

    // North-West Corner kezdő megoldás
    int i = 0, j = 0;
    while (i < m && j < n) {
        int val = min(s[i], d[j]);
        alloc[i][j] = val;
        s[i] -= val;
        d[j] -= val;
        if (s[i] == 0) i++;
        else j++;
    }

    while (true) {
        vector<int> u(m, INF), v(n, INF);
        u[0] = 0;
        bool changed;
        do {
            changed = false;
            for (int i = 0; i < m; ++i) {
                for (int j = 0; j < n; ++j) {
                    if (alloc[i][j] != -1) {
                        if (u[i] != INF && v[j] == INF) {
                            v[j] = cost[i][j] - u[i];
                            changed = true;
                        } else if (v[j] != INF && u[i] == INF) {
                            u[i] = cost[i][j] - v[j];
                            changed = true;
                        }
                    }
                }
            }
        } while (changed);

        int minDelta = 0;
        Cell enter{-1, -1};

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (alloc[i][j] == -1) {
                    int delta = cost[i][j] - (u[i] + v[j]);
                    if (delta < minDelta) {
                        minDelta = delta;
                        enter = {i, j};
                    }
                }
            }
        }

        if (enter.i == -1) {
            cout << "\nMODI végeredmény:\n";
            printAllocation();
            break;
        }

        // Ciklus DFS keresése
        visited.assign(m, vector<bool>(n, false));
        path.clear();
        set<pair<int, int>> base;
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j)
                if (alloc[i][j] != -1)
                    base.insert({i, j});

        dfs(enter.i, enter.j, enter.i, enter.j, true, base);
        path.insert(path.begin(), enter);

        // Jelek és theta
        int theta = INF;
        for (int k = 1; k < path.size(); k += 2) {
            theta = min(theta, alloc[path[k].i][path[k].j]);
        }

        for (int k = 0; k < path.size(); ++k) {
            auto [x, y] = path[k];
            if (alloc[x][y] == -1) alloc[x][y] = 0;
            if (k % 2 == 0) alloc[x][y] += theta;
            else alloc[x][y] -= theta;
            if (alloc[x][y] == 0) alloc[x][y] = -1;
        }
    }

    return 0;
}

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=MODI_method&oldid=3495430”