Vícekriteriální programování

Jako vícekriteriální programování nebo též vícekriteriální optimální programování, vícekriteriální optimalizace či vektorová optimalizace se označuje odvětví vícekriteriálního rozhodování, kdy je množina posuzovaných variant popsána implicitně, tedy soustavou omezujících podmínek. Vedle vícekriteriálního hodnocení variant tak jde o jednu ze dvou základních částí vícekriteriálního rozhodování. Zároveň jde o subdisciplínu optimalizace.

Úloha

Úlohou vícekriteriálního programování je

$\underset{x\in M}{\min }𝐟(x),$

přičemž M je libovolná množina, R je množina reálných čísel, f : M → R^m je vektorová funkce, tedy f (x) je vektor o složkách (f₁ (x), …, f_m (x)).

Je otázkou, co se rozumí optimálním řešením této úlohy (vektory nelze přirozeně porovnávat). Obvykle se zavádí pojem tzv. eficientního řešení. Bod x ∈ M je eficientní řešení dané úlohy (používají se též pojmy paretovské řešení nebo nedominované řešení), jestliže pro všechna y ∈ M platí následující implikace: je-li f_i (x) > f_i (y) pro nějaké i ∈ {1, …, m}, potom existuje j ∈ {1, …, m} takové, že f_j (x) < f_j (y). Nedominované řešení tedy nelze v jednom kritériu zlepšit, aniž by se v jiném kritériu zhoršilo.

Eficientní řešení se často hledá ve tvaru

$\underset{x\in M}{\min }\sum _{i=1}^m{\lambda }_i{f}_i(x),{\lambda }_i\ge 0,$

kde λ_i jsou nějaké váhy. Takové eficientní řešení (získané podle nějakého dalšího kritéria  jako například vah v tomto případě) se nazývá kompromisní řešení.

Pokud jsou omezující podmínky popsány lineární funkcí (stejně jako u lineárního programování), jedná se o subdisciplínu vícekriteriálního programování zvanou vícekriteriální lineární programování nebo též vícekriteriální LP či VLP.

Metody řešení

Metody pro řešení úloh vícekriteriálního rozhodování lze rozdělit na metody:

• s apriorními informacemi: využívají možné informace od rozhodovatele před vlastním výpočtem kompromisního řešení, a převádějí tak vícekriteriální úlohu na řešení jedné (případně několika) jednokriteriální úlohy:
  • maximálně pravděpodobné kompromisní řešení
  • lexikograficky kompromisní řešení
  • kompromisní řešení podle minimální komponenty
  • cílové programování
• s průběžnou informací: využívají interakce mezi rozhodovatelem a analytikem pro předávání lokální informace vzhledem k dosaženému průběžnému řešení. Analytik na základě dodatečných informací hledá průběžná řešení. Rozhodovatel tato řešení posuzuje a dodává informace pro další průběžné řešení až do situace, kdy je spokojen s dosaženým řešením a zvolí ho za kompromisní řešení:
  • GD – explicitně vyjádřená hodnota záměny, na principu maximalizace užitku (s mírami substituce).
  • STEM – implicitně vyjádřená hodnota záměny, na principu minimalizace vzdálenosti od ideální varianty.
• s aposteriorní informací: vycházejí z reprezentaci množiny nedominovaných řešení, které poskytne analytik. Určení celé množiny kompromisních řešení je obtížná úloha a je zvládnutelná jen v lineárním případě. Analytik však může poskytnout určitou reprezentaci této množiny. Na základě toho rozhodovatel poskytne dodatečnou informaci a analytik vypočte odpovídající kompromisní řešení.

Reference

• Libuše Grygarová: Základy vícekriteriálního programování , skripta, Univerzita Karlova, Praha 1996, 1. vydání.