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 KNnaklady = 6*BP + 2*BN + 3*KP + 5*KNohranicenia = [ 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)