Vícekriteriální programování

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledá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 : MRm je vektorová funkce, tedy f (x) je vektor o složkách (f1 (x), …, fm (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 yM platí následující implikace: je-li fi (x) > fi (y) pro nějaké i ∈ {1, …, m}, potom existuje j ∈ {1, …, m} takové, že fj (x) < fj (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í[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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