Začíname s YALMIPom: 02. Distribučný problém

YALMIP je skvelý v tom, že dovoľuje veľmi jednoducho formulovať a riešiť takmer ľubovolné optimalizačné problémy prakticky použitím iba troch príkazov: sdpvar, optimize a value.

Na začiatok si zoberme si nasledovný príklad:

Firma vyrába potraviny v dvoch prevádzkach, jedna je v Bratislave a druhá v Košiciach. Zároveň má dve distribučné centrá, jedno v Poprade a druhé v Nitre. Prevádzky v Bratislave a Košiciach každá vyroví za mesiac maximálne 15 ton potravín. Distribučné centrum v Poprade požaduje mesačne 8 ton, Nitra zasa 18 ton. Cena prepravy je nasledovná:

6 eur za tonu z Bratislavy do Popradu
2 eurá za tonu z Bratislavy do Nitry
3 eurá za tonu z Košíc do Popradu
5 eur za tonu z Košíc do Nitry

Otázky:

koľko ton potravín treba vyrobiť v Bratislave a koľko v Košiciach?
koľko ton prepraviť do Popradu z Bratislavy a koľko z Košíc?
koľko ton prepraviť do Nitry z Bratislavy a koľko z Košíc?

tak, aby boli dodržané všetky kapacitné ohraničenia.

Najskôr je potrebné tento optimalizačný problém naformulovať. Na to je potrebné určiť rozhodovacie (=optimalizované) premenné, zadefinovať účelovú funkciu a ohraničenia.

Rozhodovacími premennými budú:

BP ako množstvo potravín prepravených z Bratislavy do Popradu
BN ako množstvo potravín prepravených z Bratislavy do Nitry
KP ako množstvo potravín prepravených z Košíc do Popradu
KN ako množstvo potravín prepravených z Košíc do Nitry

Je pritom zrejmé, že množstvo potravín vyrobených v Bratislave je BP+BN, a analogicky pre košickú výrobňu máme KP+KN. Podobne množstvo doručené do Nitry je BN+KN a do Popradu BP+KP.

Rozhodovacie premenné v YALMIPe zadefinujeme pomocou príkazu sdpvar:

sdpvar BP BN KP KN

Následne vytvoríme účelovú funkciu, kde budeme minimalizovať prepravné náklady vyjadrené ako množstvo potravín prepravovaných po jednotlivých cestách, vynásobené príslušnou cenou prepravy, teda:

naklady = 6*BP + 2*BN + 3*KP + 5*KN

Ostáva nám zadefinovať ohraničenia. Najskôr povieme, že je možné vyrábať a prepravovať iba nezáporné množstvo potravín:

ohranicenia = [ BP >= 0; ...
                BN >= 0; ...
                KP >= 0; ...
                KN >= 0 ]

Následne pridáme ohraničenie na maximálnu výrobu v Bratislave:

ohranicenia = ohranicenia + [ (BP+BN) <= 15 ]

a rovnako v Košiciach:

ohranicenia = ohranicenia + [ (KP+KN) <= 15 ]

Na koniec pridáme ohraničenia na potrebu distribučných centier, pričom tieto ohraničenia sú v tvare rovnosti:

ohranicenia = ohranicenia + [ (BP+KP) == 8 ]
ohranicenia = ohranicenia + [ (BN+KN) == 18 ]

pričom BP+KP vyjadruje množstvo potravín doručených do Popradu a BN+KN je zasa množstvo doručené do Nitry.

Akonáhle máme zadefinovanú účelovú funkciu aj ohraničenia, môžeme problém vyriešiť pomocou príkazu optimize:

optimize(ohranicenia, naklady)

pričom je potrebné dodržať poradie vstupných argumentov. Mali by sme dostať nasledovný výstup (hodnoty v yalmiptime a solvertime môžu byť iné):

ans = 

    yalmiptime: 0.1346
    solvertime: 0.0096
          info: 'Successfully solved (GLPK-GLPKMEX-CC)'
       problem: 0

Najdôležitejšou informáciou je problem=0, ktorý značí, že problém má riešenie. Optimálne hodnoty rozhodovacích premenných získame pomocou príkazu value:

BNopt = value(BN)
BPopt = value(BP)
KNopt = value(KN)
KPopt = value(KP)

V našom prípade je optimálne riešenie BNopt=15, BPopt=0, KNopt=3 a KPopt=8, teda bratislavská prevádzka vyrobí BNopt+BPopt=15 ton, pričom celá produkcia ide do Nitry. Prevádzka v Košiciach vyrobí KNopt+KPopt=11 ton (teda nebeží na plný výkon), pričom časť jej výroby ide do Popradu a časť do Nitry.

Príkaz value tiež zistí hodnotu účelovej funkcie:

minimalne_naklady = value(naklady)

minimalne_naklady =
    69

Na záver ešte celý kód:

sdpvar BP BN KP KN
naklady = 6*BP + 2*BN + 3*KP + 5*KN
ohranicenia = [ BP >= 0; BN >= 0; KP >= 0; KN >= 0 ];
ohranicenia = ohranicenia + [ (BP+BN) <= 15 ];
ohranicenia = ohranicenia + [ (KP+KN) <= 15 ];
ohranicenia = ohranicenia + [ (BP+KP) == 8 ];
ohranicenia = ohranicenia + [ (BN+KN) == 18 ];
optimize(ohranicenia, naklady)
optimalna_preprava = value([BP BN KP KN])
minimalne_naklady = value(naklady)

← OptiBlog