Vogel's approximation method (tsz. Vogel's approximation methods)
A szállítási feladat egy speciális lineáris programozási probléma, ahol:
A cél: Minimális költséggel szállítani úgy, hogy minden kereslet és kínálat teljesüljön.
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).
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 |
Ha a teljes kínálat ≠ kereslet, akkor a problémát kiegyensúlyozni kell:
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:
Input:
- supply : készletek minden sorhoz
- demand : igények minden oszlophoz
- cost : költségmátrix
Output:
- allocation : szállítási mennyiség minden cellában
Initialize:
- Mark all rows and columns as unfulfilled
- allocation = 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, demand)
- allocation = x
- supply -= x
- demand -= x
6. If supply == 0:
- Mark row i as fulfilled
7. If demand == 0:
- Mark column j as fulfilled
8. If both supply and demand == 0:
- Mark either row or column (but not both!) to avoid degeneracy
Return allocation matrix
A VAM célja, hogy “jó” első bázismegoldást adjon a szállítási problémához azáltal, hogy:
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.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.allocated)
cout << setw(2) << alloc.amount << "(" << cost << ") ";
else
cout << " (" << setw(2) << cost << ") ";
}
cout << " | " << supply << "\n";
}
cout << " ";
for (int j = 0; j < n; ++j) cout << " " << setw(2) << demand << " ";
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.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) continue;
vector<int> rowCosts;
for (int j = 0; j < n; ++j) if (!colDone) rowCosts.push_back(cost);
if (rowCosts.size() >= 2) {
sort(rowCosts.begin(), rowCosts.end());
rowPenalty = rowCosts - rowCosts;
}
}
for (int j = 0; j < n; ++j) {
if (colDone) continue;
vector<int> colCosts;
for (int i = 0; i < m; ++i) if (!rowDone) colCosts.push_back(cost);
if (colCosts.size() >= 2) {
sort(colCosts.begin(), colCosts.end());
colPenalty = colCosts - colCosts;
}
}
// Step 2: Find max penalty
int maxPen = -1, isRow = true, idx = -1;
for (int i = 0; i < m; ++i)
if (rowPenalty > maxPen) { maxPen = rowPenalty; isRow = true; idx = i; }
for (int j = 0; j < n; ++j)
if (colPenalty > maxPen) { maxPen = colPenalty; 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 && cost < minCost) {
minCost = cost;
selI = idx;
selJ = j;
}
}
} else {
for (int i = 0; i < m; ++i) {
if (!rowDone && cost < minCost) {
minCost = cost;
selI = i;
selJ = idx;
}
}
}
// Step 4: Allocate
int quantity = min(supply, demand);
alloc = {quantity, true};
supply -= quantity;
demand -= quantity;
if (supply == 0) rowDone = true;
if (demand == 0) colDone = 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;
}