Úlohy vícekriteriálního programování

17.5.3

Úlohy vícekriteriálního programování

Doc. Ing. Alois Fiala, CSc.

Úlohu vícekriteriálního programování můžeme formulovat takto:

kde

Tento zápis neurčuje úlohu vícekriteriálního programování jednoznačně, neboť význam operátoru max není pro vektory přesně definován.

Úkolem je najít takový vektor x, který splňuje omezující podmínky a v němž kriteriální funkce ƒ₁(x), ƒ₂(x), ..., ƒ_p(x) nabývají co možná největších hodnot.

 NahoruDominovaná a nedominovaná řešení

 NahoruRysy kompromisní varianty

Je jasné, že jen velmi zřídka můžeme najít variantu, která by byla skutečně nejlepší z hlediska každého zadaného kritéria, a že se tedy většinou musíme spokojit s nějakým kompromisem. Je přirozené považovat za kompromisní takovou variantu, k níž neexistuje žádná varianta, která by byla lepší alespoň v jednom kritériu a v žádném nebyla horší. Takto vymezená kompromisní varianta se nazývá efektivní, nedominovaná nebo paretovsky optimální.

Nechť x₁ a x₂ jsou přípustná řešení. Řekneme, že řešení x₁ dominuje nad řešením x₂ (a řešení x₂ je dominováno řešením x₁), jestliže pro všechna k = 1, ..., p platí ƒ_k(x₁) ≥ ƒ_k(x₂), přičemž existuje r takové, že ƒ_r(x ₁) > ƒ_r(x₂). To znamená, že x₁ musí být lepší alespoň podle jednoho kritéria, přičemž podle žádného není horší.

Řekneme, že řešení x je nedominované (paretovsky optimální), jestliže neexistuje žádné přípustné řešení, které by nad ním dominovalo. Nedominovanost, resp. paretovská optimalita tedy znamená takový stav, kdy žádné kritérium nemůže být zlepšeno, aniž by došlo ke zhoršení nějakého jiného kritéria.

Grafické znázornění problému vidíme na následujícím obrázku. Množinou přípustných řešení je pětiúhelník ABCDE, kde A = (0; 0), B = (4; 0), C = (3; 2), D = (1; 3), E = (0; 2). Maximum funkce ƒ₁(x) na této množině nastává v bodě D a maximum funkce ƒ₂(x) nastává v bodě B.

Analyzujme na základě hodnot účelových funkcí uvedených v následující tabulce vzájemné vztahy řešení, odpovídajících jednotlivým vrcholům množiny zmíněného pětiúhelníka. Vidíme, že řešení x_A je dominováno všemi ostatními uvedenými řešeními a řešení x_E je dominováno řešeními x_C a x_D. Řešení x_B, x_C a x_D jsou vzájemně nedominovaná a navzájem nedominovaná jsou i řešení x_B a x_E.

Analýzou předchozího obrázku zjistíme, že ke každému bodu množiny přípustných řešení mimo lomenou čáru BCD existuje nějaký jiný bod, který jej dominuje. Pokud se pohybujeme po lomené čáře BCD od bodu B směrem k bodu D, rostou hodnoty funkce ƒ₁(x) a současně klesají hodnoty funkce ƒ₂(x). Pokud se pohybujeme po této čáře od bodu D k bodu B, je tomu naopak. Pro kterýkoli bod lomené čáry BCD platí, že hodnotu jedné funkce můžeme zvýšit pouze za cenu snížení hodnoty druhé funkce. Lomená čára BCD tedy představuje množinu nedominovaných (paretovsky optimálních) řešení dané úlohy.

 NahoruMetody vícekriteriálního programování

Metody vícekriteriálního programování

Tyto metody jsou v podstatě založeny na jednorázovém nebo opakovaném použití metod jednokriteriální optimalizace. Podle toho, zda a kdy jsou k dispozici nějaké doplňující informace o rozhodovatelových preferencích, lze specifikovat následující případy:

• jsou k dispozici apriorní informace o preferencích rozhodovatele,

• doplňující informace o preferencích rozhodovatele jsou zadávány až v průběhu řešení úlohy,

• žádné doplňující informace o preferencích rozhodovatele nejsou k dispozici.

 NahoruZnalost preferencí rozhodovatele

Jestliže jsou předem k dispozici informace o preferencích rozhodovatele, pak lze danou úlohu převést na úlohu jednokriteriální optimalizace, resp. na posloupnost takových úloh. Těmito informacemi mohou být váhy kritérií, pořadí důležitosti kritérií nebo požadované (ideální) hodnoty kritérií. Podle charakteru informací o preferencích rozhodovatele rozlišujeme tyto metody:

• metody agregace kritérií,

• metody lexikografické optimalizace,

• metody optimalizace nejhorší hodnoty kritérií,

• metody minimalizace vzdálenosti od ideálního vektoru.

 NahoruInteraktivní metody

Jsou-li doplňující informace o preferencích rozhodovatele zadávány až v průběhu řešení úlohy, jedná se o tzv. interaktivní metody, které spočívají na dialogu mezi rozhodovatelem a řešitelem (tím je obvykle počítač), při nichž se střídají dvě fáze - fáze výpočetní a fáze rozhodovací. Výpočetní fáze je prováděna řešitelem a jejím výstupem je jedno nebo více provizorních řešení úlohy a případně nějaké další informace důležité pro rozhodovatele. Při výpočtu provizorního řešení se obvykle používá princip agregace kritérií nebo princip minimalizace vzdálenosti od ideálního vektoru. V rozhodovací fázi rozhodovatel posoudí předložené provizorní řešení, a jestliže je dosud nepokládá za vyhovující, poskytne řešiteli informace o svých preferencích. Na jejich podkladě pak může řešitel stanovit nové provizorní řešení, které bude rozhodovateli více vyhovovat. Interaktivní metody můžeme členit do dvou skupin:

• Metody s explicitně vyjádřenou hodnotou záměny vyžadují od rozhodovatele, aby určil míry substituce mezi jednotlivými kritérii. Míra substituce mezi i-tým a j-tým kritériem udává, jaké zhoršení i-tého kritéria kompenzuje zlepšení j-tého kritéria o jednu jednotku. Do této skupiny patří metoda GDF a Ziontsova-Walleniusova metoda.

• Metody s explicitně vyjádřenou hodnotou záměny od rozhodovatele vyžadují, aby posoudil úrovně jednotlivých kritérií dosažené v provizorním řešení a určil pro další krok nové mezní hodnoty kritérií. Mezi nejznámější metody této skupiny patří metoda STEM a Steuerova metoda.

 NahoruPreference nejsou známé

Nejsou-li žádné doplňující informace o preferencích rozhodovatele k dispozici, jde o úlohu nalezení množiny všech nedominovaných variant, což je úloha dosti náročná (tuto množinu můžeme zkoumat např. metodami parametrického programování). Rozhodovatel nakonec ale stejně musí vybrat jednu variantu, což je komplikováno tím, že množina všech nedominovaných variant je obvykle dost rozsáhlá a nebo dokonce nekonečná. Navíc také může mít složitou strukturu. Například ačkoli jsou všechny funkce v úloze z příkladu 1 lineární, je množina všech nedominovaných řešení nekonvexní (to ilustruje příslušný obrázek, kde je množina nedominovaných řešení tvořena lomenou čarou BCD).

 NahoruNormalizace kritérií

Normalizace kritérií

Ve většině metod vícekriteriální optimalizace je obvykle třeba provést určitou normalizaci kritérií, tj. vyloučit vliv jednotek měření jednotlivých účelových funkcí. To lze provést například tak, že funkce ƒ_k(x) se nahradí funkcemi ^~ƒ_k(x) danými vztahem:

kde ƒ_k^D, resp. ƒ_k^H je dolní, resp. horní mez hodnot funkce ƒ_k(x) na množině přípustných řešení dané úlohy. Roli těchto mezí mohou sehrát hodnoty ƒ_k^min a ƒ_k^max, určené takto:

 NahoruAgregace kritérií

Agregace kritérií

Ze zadaných kritérií se pomocí vhodné agregační funkce konstruuje jedno skalární kritérium. Nejčastějším případem agregační funkce je vážený součet kritérií:

kde v_k jsou váhy kritérií, charakterizující jejich důležitost. Je třeba poznamenat, že agregační funkce je pouze nástrojem pro nalezení nějakého kompromisního řešení a její hodnoty samy o sobě nemusejí mít žádný význam.