Cílové programování
Představuje jiný přístup k řešení úlohy LR Místo stanovení omezujících podmínek a kritéria optimality se zde stanoví pevné a volné cíle s přiřazenými cílovými hodnotami. U pevných cílů musí být tato hodnota splněna (analogie omezujících podmínek). U volných cílů můžeme dosáhnout vyšší i nižší hodnoty než je cíl (avšak ne moc odlišné). Protože cílových hodnot bývá několik a zpravidla není možné dosažení všech, volí se obvykle jeden ze dvou přístupů:
► pomocí preferencí - nejprve je optimalizován cíl s nejvyšší preferencí, atd. nebo
► pomocí vah - koeficientů vyjadřujících důležitost daného cíle, optimalizuje se pak vážený součet odchylek od všech cílů
Modely cílového programování jsou obecnější než standardní modely LP, protože v praxi zpravidla nemáme jediné kritérium optimality, ale sledujeme více hodnot.
Cílové programování - příklad
Příklad z J. Jablonský, Operační výzkum: Vedení penzijního fondu se rozhoduje o nákupu dvou druhů cenných papírů (akcie a obligace). Má k dispozici prostředky, které není nutné úplně vyčerpat, nelze je však překročit. Do akcií lze investovat maximálně 50 % celkového objemu prostředků a do obligací maximálně 75 % prostředků. Očekávaný výnos z akcií je 15 % a z obligací 10 % p.a., míra rizika investice je ohodnocena koeficientem 5 u akcií a 2 u obligací. Navrhněte takovou skladbu portfolia [xi, x2], aby se dosáhlo
průměrného výnosu 12 % p.a. a aby byla vážená míra rizika rovna 3 .
Při standardním přístupu LP bychom museli zvolit jako účelovou funkci jen jedno z nich, např. výnos a k omezujícím podmínkám pro objem investic přidat další omezení, totiž že míra rizika nesmí překročit hodnotu 3. Lze spočítat, že optimálního řešení při tomto přístupu dosáhneme, dáme-li | prostředků do akcií a § do obligací. Při průměrném riziku 3 tak získáme 11,67 % p.a.
Nebo naopak budeme minimalizovat účelovou funkci vyjádřenou váženým rizikem a jako dodatečnou podmínku stanovíme omezení, aby průměrný výnos byl nejméně 12 % p.a. Pak je optimální investovat 40 % prostředků do akcií a 60 % do obligací. Při výsledném výnosu 12 % p.a. pak bude míra rizika 3,2.
Cílové programování - formulace modelu
U volných cílů se používají odchylkové proměnné pro vyjádření kladných a záporných odchylek (značíme je c/+, resp. dj~) od cílových hodnot. Je-li cíle splněn, platí c/+ = dj~ = 0, dojde-li k přesáhnutí cíle, pak je c/+ > 0, dj~ = 0 a není-li cíl dosažen, je c/+ = 0, dj~ > 0. Pevné cíle musí být respektovány, žádné odchylky se nepřipouští.
V modelu cílového programování je vždy účelová funkce vyjádřena jako minimalizace odchylkových proměnných, přičemž do ní lze zahrnout buď pouze kladné, pouze záporné nebo oba typy odchylek ( pak se cílovým hodnotám blížíme shora, zdola nebo "oboustranně"). Zápis úlohy o optimalizaci portfolia by tedy byl:
d£,     ->> min, za podmínek:
< 0,5; x2 < 0,75 15*1 + 10x2 + GÍ+ - dT = 12 5*1 + 2x2 + c/2+ - d~ = 3 Xi,x2,c/1+,c/1",c/2+,c/2" > 0
Cílové programování - odlišení cílů vahami
Při současné minimalizaci více odchylek můžeme odlišit jejich důležitost vahami. Abychom se vyhnuli problémům s různými jednotkami, je lepší
pracovat s relativními odchylkami kde g, značí /'- tou cílovou
hodnotu. Pokud je pro nás výnos pětkrát důležitější než riziko, stanovíme
váhy 5 a 1 a účelová funkce bude mít podobu z = 5^- + Dále lze úlohu řešit běžnou simplexovou metodou.
Řešením je dát \ prostředků do akcií a § do obligací, přitom je zcela splněna cílová hodnota rizika a výnos je 11,67%.
Cílové programování - odlišení cílů preferencemi
Při odlišení cílů preferencemi minimalizujeme nejprve odchylku od důležitějšího cíle a pokud má množina optimálních řešení více prvků, minimalizujeme na této množině druhou nejzávažnější odchylku, atd. Má-li v naší úloze vyšší prioritu výnos, minimalizujeme nejprve . Znázorněme situaci graficky v rovině xi, x2.
Protože se přímky protínají mimo přípustnou množinu, nelze dosáhnout rovnosti     = 0. Musíme riziko zvýšit, tj. posunout modrou přímku tak, aby se dotkla optimální úsečky proc/^. Našli jsme bod optima x* = [0,4; 0,6].
Vícekriteriální programování
Ve vícekriteriálním programování jde o optimalizaci více účelových funkcí na přípustné množině definované sadou omezení. Narozdíl od úloh VHV je množina variant v úlohách nekonečná a kritéria jsou definována v podobě funkcí. Jsou-li všechny účelové funkce i omezující podmínky lineární, mluvíme o vícekriteriálním lineárním programování (VLP). Problém VLP tedy můžeme formulovat jako úlohu "optimalizovat"
Z\ = C1   X, Z2 = C2 • X, . . . Z/c = ck • X,
za podmínek
x £ X = {x £ Rn|Ax < b, x > 0}, kde c1 je cenový vektor /-té účelové funkce.
Pomocí ekvivalence minimalizační úlohy pro z, s maximalizační úlohou pro -Zj můžeme převést úlohu do takové podoby, aby všechna kritéria měla maximalizační charakter. Úlohu je pak možné zapsat pomocí maticového zápisu, označíme-li z = (z^, z2,..., zk) vektor účelových funkcí a C matici vytvořenou z cenových vektorů c1, c2,... ck: z = C x    MAX, x g X.
Model VLP - základní pojmy
Podobně jako u VHV je typicky cílem nalézt v množině všech přípustných řešení pomocí vhodného postupu nějaké prakticky přijatelné, tzv. kompromisní řešení. Je dobré si uvědomit, že při hledání kompromisního řešení se opět stačí omezit na nedominovaná řešení. Řešení x g X je nedominované, pokud neexistuje žádné přípustné řešení, jehož vektor kriteriálních hodnot by byl ve všech složkách větší nebo roven vektoru C • x (s vyloučením případu rovnosti vektorů).
Většina principů pro hledání kompromisního řešení je založena na řešení
dílčích úloh lineárního programování z, = c1 x —^ max, x g X standardní
simplexovou metodou. Vektor xH, ve kterém všechny účelové funkce nabývají svých optimálních hodnot nazýváme ideální řešení. Analogicky bychom mohli zavést bazálni řešení xD. Optimální a bazálni řešení zpravidla neleží v přípustné množině.
Model VLP - grafické znázornění
Vícekriteriální lineární model je možné zobrazovat v rozhodovacím nebo kriteriálním prostoru. Nejprve schematicky znázorněme úlohu se dvěma proměnnými v rozhodovacím prostoru, kde souřadné osy budou reprezentovat hodnoty proměnných.
Na hranici množiny přípustných řešení vymezené kriteriálním kuželem leží všechna nedominovaná řešení.
Model VLP - grafické znázornění
Při zobrazování v kriteriálním prostoru vynášíme na jednotlivé osy přímo hodnoty účelových funkcí.
A
z1
2 2 C X
2 1 C X
Modře jsou vyznačeny nedominované hodnoty
Vícekriteriální programování - klasifikace metod
Při řešení úloh VLP můžeme požadovat výsledky v podobě úplného popisu množiny nedominovaných řešení nebo nalezení nějaké její reprezentativní podmnožiny nebo výběru několika kompromisních variant. Chce-li uživatel vybrat jedinou kompromisní variantu, bude jeho rozhodnutí značně záviset na preferencích jednotlivých kritérií. Ty mohou být zadávány v různých fázích výpočtu:
► před započetím výpočtu,
► interaktivně v průběhu výpočtu,
► po skončení výpočtu,
a to opět prostřednictvím aspiračních úrovní kritérií, pořadím kritérií, váhami kritérií nebo mírou kompenzace kriteriálních hodnot. Podle toho, kdy je informace o kritériích do modelu zapracována, dělíme výpočetní metody na:
► metody s preferenční informací a priori
► metody s preferenční informací a posteriori
► metody s postupným zpřesňováním preferenční informace
► metody kombinované
Vícekriteriální programování - klasifikace metod
Metody s informací apriori dělíme do několika skupin:
► metoda lexikografická
► metoda minimální komponenty
► řešení jednokriteriální úlohy s agregovanými kritérii
► záměna kritérií za omezení
► "minimalizace odchylek"od ideálních hodnot (při vhodně zvolené metrice)
Metody s informací aposteriori spočívají v popisu množiny nedominovaných řešení, ve které následně uživatel vybírá kompromisní řešení. Patří sem:
► metoda parametrická (agregujeme kritéria s parametricky zadaným vektorem vah)
► metoda omezení (hledá nedominovaná řešení, kde hodnoty kritérií dosahují parametricky zadaných cílových hodnot)
► vícekriteriální simplexový algoritmus (postupně určuje nedominovaná bazická řešení)
Metody interaktivní probíhají iterativně a jsou založeny na komunikaci mezi uživatelem a rozhodovatelem.
Vícekriteriální programování - příklad
Příklad z knihy Tomáš Šubrt, Ekonomicko-matematické metody: Vedení půjčovny lyžařského a snowboardového vybavení zvažuje optimalizaci sortimentu zboží. Do kalkulací zahrnuje obvyklou cenu za půjčení vybavení i riziko, že utrpí ztrátu, protože vybavení nebude půjčeno. Denní zisk [v Kč] při půjčení jednotlivých kompletů i riziko ztráty při nepůjčení [v bodech] jsou uvedeny v tabulce.
	lyžařský	lyžařský	lyžařský	snowboardový
	komplet	komplet	komplet	komplet
	sjezdový	sjezdový	běžecký	
	dospělý	dětský		
zisk	300	200	170	250
riziko	10	15	25	5
Společnost chce investovat nejvýše 1 mil. Kč do nákupu kompletů, přičemž snowboardové komplety chce nakoupit alespoň za 200 tis. Kč. Pořizovací cena každého z kompletů je 10 tis. Kč. Navrhněte, jak má společnost investovat, aby maximalizovala zisk a minimalizovala ztrátu.
VLP - příklad, matematický model
Označme xi,..., x4 proměnné vyjadřující počty nakoupených kompletů. Kriteriální funkce tedy jsou
Zi = 300xi + 200x2 + 170x3 + 250x4 -> max z2 = 10xi + 15x2 + 25x3 + 5x4 /77/h
Při pořizovací ceně kompletů 10 000 Kč budou mít omezení následující podobu: celkem lze koupit maximálně 100 ks kompletů, z toho nejméně 20 ks musí být snowboardové komplety:
Xi +x2 + x3 + x4 < 100 x4 > 20
Dále musíme přidat obligátní podmínky :
xi,x2,x3,x4 > 0
Správně bychom měli přidat ještě podmínky celočíselnosti, ale nebudeme pro zjednodušení zatím uvažovat.
Řešením zjednodušených úloh modelu, kdy uvažujeme vždy pouze jednu kriteriální funkci dostaneme dílčí optimální řešení.
VLP - dílčí optimální řešení, příklad
Snadno lze zjistit, že minimálního rizika půjčovna dosáhne, jestliže nakoupí pouze požadované snowboardové komplety, tj. 20 ks po 10 000 Kč a ostatní komplety nebude kupovat vůbec.
Podobně maximálního zisku půjčovna dosáhne, jestliže po zakoupení požadovaného množství snowboardových kompletů (tj. 20 ks) utratí všechny zbývající peníze za nejziskovější sjezdové komplety pro dospělé. Prostředky postačí pro zakoupení 80 ks těchto kompletů.
Dílčí optimální řešení můžeme znázornit v kriteriální tabulce:
	Kriteriál výnos	ní funkce riziko
80 dospělých sjezdových + 20 snowboardových	29000	880
20 snowboardových	5000	100
Z hlavní diagonály tabulky vidíme, že ideální řešení je ohodnoceno kriteriálními hodnotami zisku a rizika 29000 a 100, ale reálně neexistuje.
VLP - lexikografická metoda
Popišme si některé z metod s apriorní preferenční informací. Při použití lexikografické metody rozhodovatel určí pořadí významnosti kriteriálních funkcí (předpokládejme, že již jsou funkce označeny tak, že zi je nejvýznamnější a zk nejméně významné, jejich optimální hodnoty označme z°pt,..., z°kpt). Hledání kompromisního řešení spočívá v postupném řešení sekvence optimalizačních úloh
max. z\ = c1 x, x e X. Pokud má úloha více optimálních řešení, řešíme
dalšujlohu^^^^^^^^^^^^^
max. z2 = c2 • x, x g X, c1 x > z°pt. Opět je-li řešení více, postupujeme
dále, až nalezneme kompromisní řešení jako bod optima úlohy
max. zk = ck x, x e X, c1x > zop\..., ck"1x > z°kp\.
Zmírnit předpoklad, že jednotlivé úlohy mají více než jedno řešení, je možné připuštěním odchylky 5-,, o kterou se můžou v jednotlivých krocích lišit hodnoty preferovaných účelových funkcí od svých optim. Například v druhém kroku bychom řešili úlohu
max. z2 = c2 • x, x g X, c1x > z°pt - £1, atd. Popsaná metoda v podstatě kopíruje reálné uvažování manažerů.
VLP - lexikografická metoda, příklad
Již víme, že při preferenci rizika je nejvýhodnější nakoupit pouze 20 snowboardových kompletů a při preferenci zisku 20 snowboardových a 80 dospělých sjezdových kompletů.
Jaké by měla úloha řešení, jestliže budeme preferovat riziko, ale připustíme jeho odchylku z ideální hodnoty 100 na 120? Maximalizujeme tedy zisk Z\ = 300xi + 200x2 + 170x3 + 250x4 za omezení
z2 = 10xi + 15x2 + 25x3 + 5x4 < 120 , (tj. že riziko nepřesáhne hodnotu 120) a dalších omezení modelu
^ + x2 + x3 + x4 < 100 x4 > 20 , Xi,..., x4 > 0.
Snadno vypočteme optimální řešení    = 2, x2 = 0, x3 = 0, x4 = 20, tedy k požadovaným dvaceti snowboardovým přikoupíme ještě 2 dospělé sjezdové komplety. Zíkáme tak 5600 Kč a riziko bude rovno limitním 120 bodům.
VLP - metoda minimální komponenty
Jiným přístupem je stanovení kompromisního řešení podle minimální komponenty, kdy maximalizujeme nejmenší, tedy nejhorší komponentu vektoru hodnot účelových funkcí. Dostaneme tedy úlohu LP maximalizovat
z = ô za podmínek c1 • x > ô, c2 • x > ô,... ck • x > ô, x e X .
Pokud mají kritéria rozdílnou povahu, je třeba je nejprve převést všechna na maximalizační a upravit na bezrozměrné, aby byla zajištěna jejich srovnatelnost.
VLP - metoda agregace kriteriálních funkcí
Pomocí vhodně zvoleného operátoru je možné sloučit všechny kriteriální funkce do jediné. Obecně se při agregaci používají různé operátory, zde se jeví nejvhodnější lineární kombinace jednotlivých funkcí za použití normovaného vektoru vah v = (ví,..., vk). Místo původní optimalizační úlohy_
z = C x —>• MAX, x g X. řešíme jednorozměrnou úlohu zv = v C x    max, x g X.
Pozor! Při nastavení vektoru vah je třeba vzít v úvahu, že hodnoty funkcí se pohybují na různých škálách. Vyznačme agregované kritérium graficky (zelená přímka). Nemá praktickou interpretaci, je pouze kritériem pomocným.
VLP - metoda agragace, příklad
Při agregaci funkce zisku zi a funkce rizika z2 je třeba vzít v úvahu odlišnou povahu kritérií, například můžeme vynásobit z2 koeficientem (-1). Jestliže nastavíme vektor vah
v      V 100' 100/ '
pak agregovaná účelová funkce bude mít tvar
zv = 5,5x<\ - 4,25x2 - 15,25x3 + 7,75x4.
Snadno nahlédneme, že optimální řešení tedy bude x\ = 0, x2 = 0, x3 = 0, x4 = 100, všechny peníze utratíme za snowboardové komplety. Optimální hodnota účelové funkce zv = 775, což nemá žádnou vypovídací schopnost, ale můžeme pro nalezené řešení dopočítat hodnotu zisku 25000 Kč a hodnotu rizika 500 bodů.
VLP - převod kriteriálních funkcí na omezení
Při postupném převodu kritérií na omezení postupujeme podobně jako u lexikografické metody. Předpokládáme opět, že jsou funkce označeny od nejvýznamnějšího po nejméně významné). Hledání kompromisního řešení spočívá v postupném řešení sekvence optimalizačních úloh
max. zi = c1 x, x e X. Optimální hodnotu označíme z* a řešíme další úlohu, kde připustíme určitou odchylku od z*:
max. z2 = c2 • x, x g X, c1 x > z* - ô<\. Opět zjistíme z| a postupujeme dále, až nalezneme kompromisní řešení jako bod optima úlohy max. z/c = ck • x, x g X, c1x > z* - ô<\,..., ck_1x > zjJL-, - ôk.
Kritéria lze také převést na omezení najednou tak, že maximalizujeme pouze nejdůležitější kritérium zi a přidáme do modelu současně všechna omezení Zj > auj, i = 2,... k ( aspirační úrovně všech kritérií auh i = 2,... k nastavíme někam mezi bazálni a ideálni hodnotu pro dané kritérium (z,m/A?, z,max).) Nevýhodou tohoto přístupu je, že může být obtížné nastavení aspiračních úrovní, aby nebyla přípustná množina prázdná nebo aby nebyl vliv kritérií eliminován úplně.
Literatura
► Fletcher, Roger: Practical methods of optimization, 1st ed., Chichester: John Wiley and Sons, 1987.
Šubrt, Tomáš a kol.: Ekonomicko-matematické metody, Plzeň : Vydavatelství a nakladatelství Aleš Čeněk, 2011
► Pánková, Václava: Nelineární optimalizace pro ekonomy,1. vyd., Praha : Professional Publishing, 2003
► Intriligator, Michael D.: Mathematical optimization and economic theory,Philadelphia : Siam, 2002
► Jablonský, Josef, Petr Fiala, Miroslav Maňas: Vícekriteriální rozhodování,1. vyd.,Praha : Vysoká škola ekonomická v Praze, 1994.
► Klapka, Jindřich, Jiří Dvořák, Pavel Popela Metody operačního výzkumu, Vyd. 2., Brno : VUTIUM, 2001
► Klein, Michael W.: Mathematical methods for economics, 2nd ed., Boston : Addison-Wesley, c2002
► JABLONSKÝ, Josef: Operační výzkum kvantitativní modely pro ekonomické rozhodování, 1. vyd. Praha: Professional Publishing, 2002
► PLEVNÝ, Miroslav a Miroslav ŽIŽKA: Modelování a optimalizace v manažerském rozhodování, Vyd. 2. Plzeň: Západočeská univerzita, 2010
► GROS, Ivan: Kvantitativní metody v manažerském rozhodování, 1. vyd. Praha: Grada, 2003
► Jana Friebelová - Jana Klicnarová: Rozhodovací modely pro ekonomy, 1. vyd. České Budějovice: Jihočeská univerzita v Českých Budějovicích,
2007