Gyártórendszerek modellezése: MILP modell PNS feladatokhoz

Jelölések

Matematikai modell

Megvalósítás

glpk-val

Gyártórendszerek modellezése MILP modell PNS feladatokhoz Hegyháti Máté

1

Pannon Egyetem M¶szaki Informatikai Kar Számítástudomány Alkalmazása Tanszék

Utolsó frissítés: 2008. november 16.

1

[email protected]

http://dcs.uni-pannon.hu/hegyhati/oktatas Hegyháti Máté Gyártórendszerek modellezése: MILP modell PNS feladatokhoz

PE-MIK-DCS

Jelölések

Matematikai modell

Megvalósítás

glpk-val

Alap jelölések M Anyagok halmaza, M = R ∪ I ∪ P R Nyersanyagok halmaza I Köztes anyagok halmaza P Termékek halmaza O M¶veleti egységek halmaza, ahol O ⊆ ℘(M ) × ℘(M ) ϕ− (m) m ∈ M-et gyártani képes m¶veleti egységek halmaza ϕ+ (m) m ∈ M-et felhasználni képes m¶veleti egységek

halmaza

Hegyháti Máté Gyártórendszerek modellezése: MILP modell PNS feladatokhoz

PE-MIK-DCS

Jelölések

Matematikai modell

Megvalósítás

glpk-val

Paraméterek

M¶veleti egységek paraméterei

∀o ∈ O-hoz:

capo M¶veleti egység mérete, mazimális kapacitása xo Kihasználtásgtól független x költség propo M¶ködési kapacitástól függ® arányos költség


PE-MIK-DCS

Jelölések

Matematikai modell

Megvalósítás

glpk-val

Paraméterek

Nyersanyagok paraméterei

∀r ∈ R-hez:

pricer Nyersanyag ára maxr Piacon vásárolható nyersanyag emnnyisége


PE-MIK-DCS

Jelölések

Matematikai modell

Megvalósítás

glpk-val

Paraméterek

Köztes anyagok paraméterei

∀i ∈ I -hez:

pricei Köztes anyag ára (opcionális termék) penali Büntetés megmaradó köztes anyagra maxi Fels® korlát a megmaradó köztes anyag mennyiségére


PE-MIK-DCS

Jelölések

Matematikai modell

Megvalósítás

glpk-val

Paraméterek

Termékek paraméterei

∀p ∈ P-hez:

pricep Termék ára minp Alsó korlát a gyártandó termék mennyiségére maxp Felsó korlát a termékek mennyiségére, a piac maximális igénye


PE-MIK-DCS

Jelölések

Matematikai modell

Megvalósítás

glpk-val

Paraméterek

Anyag - M¶veleti egység kapcsolat paraméterei

∀o ∈ O , m ∈ M-hez:

iro ,m Az o m¶veleti egység bemenetében az m aránya oro ,m Az o m¶veleti egység kimenetében az m aránya


PE-MIK-DCS

Jelölések

Matematikai modell

Megvalósítás

glpk-val

Változók

Változók

∀o ∈ O-hoz:

xo ∈ R+ 0 az o m¶veleti egység m¶ködési kapacitása yo ∈ {0, 1} 1, ha az o m¶veleti egység be van kapcsolva, 0 ha nem


PE-MIK-DCS

Jelölések

Matematikai modell

Megvalósítás

glpk-val

Korlátozási feltételek

Korlátozási feltétel m¶veleti egységekre

∀o ∈ O-hoz:

xo ≤ yo capo


PE-MIK-DCS

Jelölések

Matematikai modell

Megvalósítás

glpk-val


Korlátozási feltétel nyersanyagokra

∀r ∈ R-hez:

X

xo iro ,r ≤ maxr

o ∈ϕ+ (r )


PE-MIK-DCS

Jelölések

Matematikai modell

Megvalósítás

glpk-val


Korlátozási feltételek köztes anyagokra

∀i ∈ I -hez:

0≤

X o

∈ϕ− (i )

xo oro ,i −

X o

xo iro ,i ≤ maxi

∈ϕ+ (i )


PE-MIK-DCS

Jelölések

Matematikai modell

Megvalósítás

glpk-val


Korlátozási feltételek termékekre

∀p ∈ P-hez:

minp ≤

X o

∈ϕ− (p )

xo oro ,p −

X o


xo iro ,p ≤ maxi

∈ϕ+ (p )

PE-MIK-DCS

Jelölések

Matematikai modell

Megvalósítás

glpk-val

Célfüggvény

Célfüggvény: prot maximalizálás 

z =

X p



pricep 

∈P

o

 X ∈ϕ− (p )

 +

X i

xo oro ,p − o

r

−

∈R

X o

X o

pricer

∈ϕ+ (p )



(pricei − penali )  

−

xo iro ,p 



∈I

X

X

∈ϕ− (i )

xo oro ,i −

X o

xo iro ,i 

∈ϕ+ (i )

 X

xo iro ,r 

o ∈ϕ+ (r )

(xo yo + propo xo )

∈O


PE-MIK-DCS

Jelölések

Matematikai modell

Megvalósítás

glpk-val

Modell

GLPK modell

A megadott modell kissé máshogy épül fel, mint az el®z® fejezetben leírt, de természetesen ekvivalens azzal. Két új változóhalmaz került bevezetésre a könnyebb átlálthatóság kedvéért, melyek tárolják az egyes anyagokhoz az azokból gyártott, illetve felhasznált mennyiséget.


PE-MIK-DCS

Jelölések

Matematikai modell

Megvalósítás

glpk-val

Modell

Halmazok

set set set set set

O; R; I; P; M := P union I union R;


PE-MIK-DCS

Jelölések

Matematikai modell

Megvalósítás

glpk-val

Modell

Paraméterek

param param param param param param param param param

price{m in M}; penal{i in I}; max{m in M}; min{p in P}; cap{o in O}; fix{o in O}; prop{o in O}; iratio{o in O, m in M}; oratio{o in O, m in (P union I)};


PE-MIK-DCS

Jelölések

Matematikai modell

Megvalósítás

glpk-val

Modell

Változók

var var var var

x {o in O} >=0; y {o in O} >=0,<=1,integer; consumed {m in M}; produced {m in (P union I)};


PE-MIK-DCS

Jelölések

Matematikai modell

Megvalósítás

glpk-val

Modell

Korlátozási feltételek s.t. Unit_Capacity {o in O}: x[o]<=y[o]*cap[o]; s.t. Consumed_Material {m in M}: consumed[m]=sum{o in O}(x[o]*iratio[o,m]); s.t. Produced_Material {m in (P union I)}: produced[m]=sum{o in O}(x[o]*oratio[o,m]); s.t. Raw_Max {r in R}: consumed[r]<=max[r]; s.t. Intermediate_Min_Max {i in I}: 0<=produced[i]-consumed[i]<=max[i]; s.t. Product_Min_Max {p in P}: min[p]<=produced[p]-consumed[p]<=max[p];


PE-MIK-DCS

Jelölések

Matematikai modell

Megvalósítás

glpk-val

Modell

Célfüggvény

maximize profit: + sum{m in (P union I)}(price[m]*(produced[m]-consumed[m])) - sum{i in I}(penal[i]*(produced[i]-consumed[i])) - sum{r in R}(price[r]*consumed[r]) - sum{o in O}(x[o]*prop[o]+y[o]*fix[o]) ;


PE-MIK-DCS

Jelölések

Matematikai modell

Megvalósítás

glpk-val

Példa Adatok

Példa Adatok / 1

set set set set

O R I P

:= := := :=

O1 O2 O3; A B; C D; E;


PE-MIK-DCS

Jelölések

Matematikai modell

Megvalósítás

glpk-val

Példa Adatok

Példa Adatok / 2 param price := A 1 B 2 C 0 D 0 E 30; param penal:= C 0 D 5;


PE-MIK-DCS

Jelölések

Matematikai modell

Megvalósítás

glpk-val

Példa Adatok

Példa Adatok / 3 param max:= A 10 B 20 C 0 D 100 E 100; param min:= E 5; param cap:= O1 10 O2 10 O3 10; Hegyháti Máté Gyártórendszerek modellezése: MILP modell PNS feladatokhoz

PE-MIK-DCS

Jelölések

Matematikai modell

Megvalósítás

glpk-val

Példa Adatok

Példa Adatok / 4

param fix:= O1 5 O2 10 O3 5; param prop:= O1 5 O2 10 O3 0;


PE-MIK-DCS

Jelölések

Matematikai modell

Megvalósítás

glpk-val

Példa Adatok

Példa Adatok / 5 param iratio: A O1 0.5 O2 0.3 O3 0

B 0.5 0.7 0

C 0 0 1

param oratio: C O1 1 O2 0 O3 0

D 0 0 0.3

E:= 0 1 0.7;

D 0 0 0


E:= 0 0 0;

PE-MIK-DCS

Jelölések

Matematikai modell

Megvalósítás

glpk-val

Futtatás

Futtatás

bash# glpsol -m PNS_MILP.model -d PNS_MILP.data -o PNS_MILP.solution --log PNS_MILP.log

PNS_MILP.model A modellt tartalmazó fájl PNS_MILP.data A példát tartalmazó fájl PNS_MILP.solution A megoldást tartalmazó fájl PNS_MILP.log A glpsol kimenetét tartalmazó fájl


PE-MIK-DCS

Jelölések

Matematikai modell

Megvalósítás

glpk-val

Futtatás

PNS_MILP.log Reading model section from PNS_MILP.model... 47 lines were read Reading data section from PNS_MILP.data... 59 lines were read Generating Unit_Capacity... Generating Consumed_Material... Generating Produced_Material... Generating Raw_Max... Generating Intermediate_Min_Max... Generating Product_Min_Max... Generating profit... Model has been successfully generated glp_simplex: original LP has 17 rows, 14 columns, 42 non-zeros glp_simplex: presolved LP has 9 rows, 8 columns, 18 non-zeros lpx_adv_basis: size of triangular part = 9 0: objval = 0.000000000e+00 infeas = 1.000000000e+00 (0) 1: objval = 8.650000000e+01 infeas = 0.000000000e+00 (0) * 1: objval = 8.650000000e+01 infeas = 0.000000000e+00 (0) * 3: objval = 2.930000000e+02 infeas = 0.000000000e+00 (0) OPTIMAL SOLUTION FOUND Integer optimization begins... + 3: mip = not found yet <= +inf (1; 0) + 3: mip = 2.930000000e+02 <= 2.930000000e+02 0.0% (1; 0) + 3: mip = 2.930000000e+02 <= tree is empty 0.0% (0; 1) INTEGER OPTIMAL SOLUTION FOUND Time used: 0.0 secs Memory used: 0.2 Mb (164283 bytes) lpx_print_mip: writing MIP problem solution to `PNS_MILP.solution'... Hegyháti Máté Gyártórendszerek modellezése: MILP modell PNS feladatokhoz

PE-MIK-DCS

Jelölések

Matematikai modell

Megvalósítás

glpk-val

Futtatás

PNS_MILP.solution fontos részei Problem: Rows: Columns: Non-zeros: Status: Objective:

PNS_MILP 17 14 (3 integer, 3 binary) 42 INTEGER OPTIMAL profit = 293 (MAXimum) 293 (LP)

No. -----12 13 14

Row name Activity Lower bound Upper bound ------------------------ ------------- ------------Raw_Max[A] 8 10 Raw_Max[B] 12 20 Intermediate_Min_Max[C] 0 0 = 15 Intermediate_Min_Max[D] 3 0 100 16 Product_Min_Max[E] 17 5 100 17 profit 293

No. -----1 2 3 4 5 6

Column name -----------x[O1] x[O2] x[O3] y[O1] * y[O2] * y[O3] *

Activity Lower bound Upper bound ------------- ------------- ------------10 0 10 0 10 0 1 0 1 1 0 1 1 0 1


PE-MIK-DCS

Gyártórendszerek modellezése: MILP modell PNS feladatokhoz

Recommend Documents