Vícekriteriální programování

Vícekriteriální programování je odvětví optimalizace.

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

$\min_{x\in M} \mathbf{f}(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žívá se též 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

$\min_{x \in M} \sum_{i=1}^m \lambda_i f_i(x),\quad \lambda_i \geq 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í.

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ích úloh.
  • 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í.