Szállítási feladat
Feladat: Modellezzük le a következő szállítási feladatot: Adott k db üzem meghatározott termelési kapacitással. Adott n db fogyasztó meghatározott igényekkel. Minden üzem és fogyasztó közötti úton megadott mennyiségű áru szállítható megadott áron. Melyik útvonalon mennyit szállítsunk, hogy a költség minimális legyen.
A feladat egy klasszikus lineáris programozási feladat. A megoldás során k*n darab változóban tároljuk, hogy az egyes éleken mennyi árut szállítunk. Három típusú feltételt veszünk fel. Egyrészt az üzemek nem termelhetnek többet a kapacitásnál (sup), másrészt, a fogyasztók igényeit ki kell elégíteni(dem), harmadik feltétünk pedig, hogy az egyes útvonalak maximális kapacitását nem léphetjük túl (cap). A célfüggvény az egyes útvonalakon szállított áru és az egységenkénti ár szorzatösszege (cost).
# Balogh Szabolcs, NIO402
# 2014 június
# Adatok:
param k; # üzemek száma
param n; # fogyasztók száma
param s{1..k}; # üzem termelése
param d{1..n}; # fogyasztó igényei
param c{1..k, 1..n}; # útvonal kapacitás
param f{1..k, 1..n}; # szállítási költség egy adott útvonalon
# Változók: k*n db változó bevezetése:
# Jelentése: Mennyit szállítunk i és j pont között?
var x{1..k, 1..n} >= 0;
# Feltételek
# k db feltétel bevezetése a fogyasztásra
# Egyik üzem sem termelhet többet a kapacitásnál
subject to sup{i in 1..k}: sum{j in 1..n} x[i,j] <= s[i];
# n db feltétel bevezetése a kiszolgáláshoz
# Minden fogyasztóhoz érkezzen meg a szükséges mennyiség
# Megj: Lehetne >= is, de a megoldáson nem változtatna!
s.t. dem{j in 1..n}: sum{i in 1..k} x[i,j] = d[j];
# k*n db feltétel bevezetése a szállításhoz
# Minden útvonalon max annyit szállíthatunk, amennyi annak a kapacitása!
cap{i in 1..k, j in 1..n}: x[i,j] <= c[i,j];
# Célfüggvény
# A fenti feltételek függvényében hogyan lehetne a legolcsóbban kiszolgálni a fogyasztókat?
minimize cost: sum{i in 1..k, j in 1..n} f[i,j] * x[i,j];
# Ellenőrzés: A teljes fogyasztás ne legyen nagyobb, mint a gyártási képesség
# Ha ez elbukik, rögtön dobjon hibát!
check sum{j in 1..n} d[j] < sum{i in 1..k} s[i];
# Megoldás keresése
solve;
printf "\n\n\n";
# Eredmény kiírása
# Ez valójában egy dupla for-ciklus!
for {i in 1..k, j in 1..n} {
# printf "minta", változók[]
# A minta egy if then else szerkezet
printf (if (x[i,j] > 0) then "Uzem: %2d, Fogy: %2d, Menny: %4d \n" else ""), i, j, x[i,j];
}
# Célfüggvény eredménye
printf "Osszkoltseg: %d\n", cost;
printf "\n\n\n";
# Adat rész
data;
# k, n, s, d
param k := 2;
param n := 4;
param s :=
1 200
2 1400;
param d :=
1 40
2 500
3 300
4 250;
# kapacitás listásan megadva
param c :=
1 1 0
1 2 200
1 3 200
1 4 100
2 1 100
2 2 450
2 3 1000
2 4 200;
# költség mátrixosan megadva
param f default 100 (tr)
: 1 2 :=
1 . 160
2 . 180
3 60 90
4 160 190 ;
end;
A modell futtatása során a következő kimenetet kapjuk:
GLPSOL: GLPK LP/MIP Solver, v4.53
Parameter(s) specified in the command line:
--cover --clique --gomory --mir -m szallitas.mod
Reading model section from szallitas.mod...
Reading data section from szallitas.mod...
96 lines were read
Generating sup...
Generating dem...
Generating cap...
Generating cost...
Checking (line 39)...
Model has been successfully generated
GLPK Simplex Optimizer, v4.53
15 rows, 8 columns, 32 non-zeros
Preprocessing...
5 rows, 6 columns, 12 non-zeros
Scaling...
A: min|aij| = 1.000e+000 max|aij| = 1.000e+000 ratio = 1.000e+000
Problem data seem to be well scaled
Constructing initial basis...
Size of triangular part is 5
0: obj = 1.709000000e+005 infeas = 1.000e+002 (0)
* 2: obj = 1.654000000e+005 infeas = 0.000e+000 (0)
* 3: obj = 1.574000000e+005 infeas = 0.000e+000 (0)
OPTIMAL LP SOLUTION FOUND
Time used: 0.0 secs
Memory used: 0.1 Mb (120754 bytes)
Uzem: 1, Fogy: 2, Menny: 150
Uzem: 1, Fogy: 4, Menny: 50
Uzem: 2, Fogy: 1, Menny: 40
Uzem: 2, Fogy: 2, Menny: 350
Uzem: 2, Fogy: 3, Menny: 300
Uzem: 2, Fogy: 4, Menny: 200
Osszkoltseg: 157400
Model has been successfully processed
Készítette: Balogh Szabolcs, 2014
Fejlesztő környezet: GUSEK v0.2.16, GLPK LP/MIP Solver, v4.53
További példák
További példák találhatók a gusek fejlesztői környezet csomagjában, mint pl a 3SAT probléma, számos gráf alapú feladat, sudoku, stb.
Futtatás
A modellek futtatásához szükségünk lesz a GLPK Solver-re. Ez letölthető a projekt honlapjáról. A modellünket parancssorból a glpsol programmal értékelhetjük ki. A glpsol-nak a --model kapcsolóval adhatjuk meg a .mod fájlt, a --data-val a .dat fájlt, amennyiben az adatsorokat külön fájlba írtuk. A kimenet a --display kapcsolóval egy írányítható át.
glpsol --model mymodel.mod
glpsol --model mymodel.mod --data mydata.dat
glpsol --model mymodel.mod --data mydata.dat --display results.out
glpsol -m mymodel.mod -d mydata.dat -y results.out # rövid kapcsolókkal