dnes je 3.7.2022

Input:

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

22.7.2010, , Zdroj: Verlag Dashöfer

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 ƒ1(x), ƒ2(x), ..., ƒp(x) nabývají co možná největších hodnot.

Dominovaná a nedominovaná řešení

Rysy 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ť x1 a x2 jsou přípustná řešení. Řekneme, že řešení x1 dominuje nad řešením x2 (a řešení x2 je dominováno řešením x1), jestliže pro všechna k = 1, ..., p platí ƒk(x1) ≥ ƒk(x2), přičemž existuje r takové, že ƒr(x 1) > ƒr(x2). To znamená, že x1 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.

Příklad 1 Je dán následující problém dvoukriteriálního programování:

         
ƒ1(x) = x1 + 3 x2 max
ƒ2(x) = 5 x1 + x2 max
x1 + 2 x2 7
2 x1 + x2 8
–x1 + x2 2
x1, x2 0

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 ƒ1(x) na této množině nastává v bodě D a maximum funkce ƒ2(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í xA je dominováno všemi ostatními uvedenými řešeními a řešení xE je dominováno řešeními xC a xD. Řešení xB, xC a xD jsou vzájemně nedominovaná a navzájem nedominovaná jsou i řešení xB a xE.

x xA xB xC xD xE
ƒ1(x) 0 4 9 10 6
ƒ2(x) 0 20 17 8 2

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 ƒ1(x) a současně klesají hodnoty funkce ƒ2(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.

Metody 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.

Znalost 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.

Interaktivní 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.

Preference 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).

Normalizace 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 ƒkD, resp. ƒkH 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 ƒkmin a ƒkmax, určené takto:

Agregace 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 vk 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.

Příklad 2 Řešme úlohu z příkladu 1 metodou agregace kritérií.

Nejprve proveďme normalizaci kritérií: ƒ1min = ƒ1min = 0, ƒ1max = 10, ƒ2max = 20, takže

a

Agregační funkce typu váženého součtu pak vypadá takto

Jestliže obě kritéria považujeme za stejně důležitá, tj. v1 = v2 = 0,5, pak dostáváme jednokriteriální úlohu LP:

                 
F(x) = 0,175 x1 + 0,175 x2 max
x1 + 2 x2 7
2 x1 + x2 8
x1 + x2 2
x1, x2 0

V následující tabulce jsou uvedena získaná řešení pro různé volby váhových koeficientů. Vidíme, že získáváme pouze nedominovaná řešení.

v1 v2 x* ƒ1(x*) ƒ2(x*)
0,1 0,9 (4; 0) 4 20
0,3 0,7 (4; 0) 4 20
0,5 0,5 (3; 2) 9 17
0,7 0,3 (3; 2) 9 17
0,9 0,1 (1; 3) 10 8

Jestliže se požaduje, aby váhy byly

Nahrávám...
Nahrávám...