Operační výzkum. Vícekriteriální programování. Lexikografická metoda. Metoda agregace účelových funkcí. Cílové programování

Operační výzkum Vícekriteriální programování. Lexikografická metoda. Metoda agregace účelových funkcí. Cílové programování.

Operační program Vzdělávání pro konkurenceschopnost Název projektu: Inovace magisterského studijního programu Fakulty ekonomiky a managementu Registrační číslo projektu: CZ.1.07/2.2.00/28.0326

Vícekriteriální programování


Definice: Úloha vícekriteriálního lineárního programování (VLP) je zobecněním úloh lineárního programování vzhledem k počtu účelových funkcí. Obecně uvažujeme úlohu s k účelovými funkcemi. Matematický model úlohy vícekriteriálního lineárního programování (VLP) má tvar 2 3 z1 = z1 (~x ) 6 z2 = z2 (~x ) 7 6 7 6 7 −→ „maxÿ .. 4 5 . zk = zk (~x ) při podmínkách A · ~x ≤ ~b, ~x ≥ ~o .

Michal Šmerek

Vícekriteriální programování.


Úvod do vícekriteriálního hodnocení variant Poznámka: V předešlé definici použité symboly chápeme tímto způsobem: zs = zs (~x ), s = 1, . . . , k, jsou účelové funkce, jejichž hodnota je funkcí ~x , 0 1 a11 . . . a1n B . .. C .. A = @ .. . . A je matice soustavy (nerovnic), am1 . . . amn 0 1 x1 B C ~x = @ ... A je vektor neznámých, xn 0 ~b = B @ 0 B ~o = @

1 b1 .. C . A je vektor pravých stran (nerovnic) a bm 1 0 .. C . A je nulový vektor. 0 Michal Šmerek



Úvod do vícekriteriálního hodnocení variant

Definice: Vektor ~x , splňující uvedená omezení, se nazývá přípustné řešení úlohy VLP. Množinu všech přípustných řešení značíme XP . Přípustné řešení ~x ◦ nazveme nedominovaným řešením úlohy VLP, jestliže neexistuje přípustné řešení takové, že ~z (~x ) ≥ ~z (~x ◦ ) (vektorová nerovnost splněná ve všech k souřadnicích). Množinu všech nedominovaných řešení zančíme XN . Kompromisní řešení je pak některé z nedominovaných řešení. K nalezení kompromisního řešení existuje více metod. Přitom každá z těchto metod může označit jiné řešení za kompromisní. Každá z metod vyžaduje nějakou další informaci k zadané úloze (např. váhy kritérií, apod.)

Michal Šmerek



Lexikografická metoda

Je třeba znát pořadí kritérií (účelových funkcí) podle důležitosti. Při řešení úlohy VLP lexikografickou metodou se postupuje následovně. Nejprve se určí množina X1 všech optimálních řešení vzhledem k nejdůležitější účelové funkci. Dále se řeší úloha vzhledem ke druhé nejdůležitější účelové funkci, přičemž za množinu všech přípustných řešení nyní bereme množinu X1 . Množina X2 všech optimálních řešení této úlohy je dále množinou všech přípustných řešení třetí jednokriteriální úlohy s třetí nejdůležitější účelovou funkcí; atd. Nakonec získáme lexikograficky optimální řešení úlohy VLP.

Michal Šmerek



Lexikografická metoda Lexikografická metoda – postup: Úloha VLP s k účelovými funkcemi se v této metodě nahrazuje řešením nejvýše k jednokriteriálních úloh LP: 1 První úloha: Na množině všech přípustných řešení původní úlohy VLP se maximalizuje nejdůležitější účelová funkce. Množina všech optimílních řešení této jednokrieriální úlohy označíme X1 . 2 Druhá úloha: Na množině X1 se maximalizuje druhá nejdůležitější účelová funkce. Množina všech optimílních řešení této jednokrieriální úlohy označíme X2 . 3 Třetí úloha: Na množině X2 se maximalizuje třetí nejdůležitější účelová funkce. Množina všech optimílních řešení této jednokrieriální úlohy označíme X3 . 4 Podobně postupujeme i dále. Skončíme buď po vyřešení t-té úlohy (t < k), jestliže množina Xt je jednoprvková, nebo nejpozději po vyřešení k-té úlohy. Za kompromisní řešení úlohy VLP pak považujeme řešení Xt , resp. Xk . V prvním případě je kompromisní řešení jednoprvkové, ve druhém případě může být kompromisních řešení více. Michal Šmerek




Př: Určete graficky množinu XN všech nedominovaných řešení úlohy VLP a graficky i početně lexikograficky optimální řešení. » – z1 = 5x1 + x2 −→ „maxÿ z2 = x2 za podmínek x1 + x2 ≤ 4,

(1)

x1 − 2x2 ≤ 3,

(2)

x1 ≥ 0, x2 ≥ 0. (3),(4) Pořadí důležitosti uvažujte a) 1. z1 , 2. z2 ; b) 1. z2 , 2. z1 .

Michal Šmerek



Lexikografická metoda Řešení: Množinou XP všech přípustných řešení úlohy je čtyřúhelník OABCD, XP = 4-úh. OABCD, kde O = [0, 0], A = [3, 0], B = [11/3, 1/3], C = [0, 4].

Obrázek: Úloha VLP, grafické znázornění XP , XN Michal Šmerek



Lexikografická metoda Na obrázku je množina XP vyšrafována. Jsou zde vyznačeny i normálové vektory ~n1 , ~n2 příslušné účelovým funkcím. Při řešení úlohy VLP lexikografickou metodou se nejprve určí množina X1 všech optimálních řešení vzhledem k nejdůležitější účelové funkci. V obou případech je množina X1 jednoprvková a tedy představuje jediné kompromisní řešení. Konkrétně: a ad a) X1 = B, tedy Xopt,lex = B, proto ~z a = (z1 (B), z2 (B)) = (56/3, 1/3). b ad b) X1 = C , tedy Xopt,lex = C , proto ~z b = (z1 (C ), z2 (C )) = (4, 4).

Vzhledem k tomu, jak vyšli obě jednokriteriální úlohy (vzhledem k účelové funkci z1 , resp. z2 ), je zřejmé, že množinou XN všech nedominovaných řešení úlohy VLP je celá úsečka BC: XN = BC . Grafické určení množin XP , XN i kompromisního řešení jak v případě a), tak i v případě b) je zřejmé z obrázku.

Michal Šmerek



Lexikografická metoda Početně pro případ a) postupujeme následovně: Převedeme nerovnice na rovnice zavedením doplňkových proměnných x10 , x20 a anulujeme účelové rovnice, ostatní je zřejmé z tabulky. Nejprve samozřejmě maximalizujeme nejdůležitější účelovou funkci. Z.p.

x1

x2

x10

x20

bi

p=

bi pro aik > 0 aik

x10

1

1

1

0

4

4

x20

(1)

−2

0

1

3

3

z1

−5

−1

0

0

0

max1

z2

0

−1

0

0

0

max2

x10

0

(3)

1

−1

1

1 3

x1

1

−2

0

1

3

−−

z1

0

−11

0

5

15

max1

z2

0

−1

0

0

0

max2

Tabulka: Lexikografická metoda, nedokončená tabulka Michal Šmerek



Lexikografická metoda Z.p.

x1

x10

x2

x20

bi

p=

bi pro aik > 0 aik

x10

1

1

1

0

4

4

x20

(1)

−2

0

1

3

3

z1

−5

−1

0

0

0

max1

z2

0

−1

0

0

0

max2

x10

0

(3)

1

−1

1

1 3

x1

1

−2

0

1

3

−−

z1

0

−11

0

5

15

max1

z2

0

−1

0

0

0

max2

1 3 2 3 11 3 1 3

− 31 1 3 4 3 − 31

1 3 11 3 56 3 1 3

x2

0

1

x1

1

0

z1

0

0

z2

0

0

MAX1 max2

Tabulka: Lexikografická metoda, kompletní tabulka Michal Šmerek




Poznámka: I z tabulky je zřejmé, že hodnotu účelové funkce z2 sice zvýšit lze, ale nikoliv bez současného snížení důležitejší účelové funkce. Tedy, řešení (x1 =

11 , x2 3

= 13 ) je jediným kompromisním řešením úlohy a).

Poznámka: Úloha b) by se početně řešila analogicky.

Michal Šmerek



Metoda agregace účelových funkcí

Metoda agregace účelových funkcí vyžaduje znalost vah kritérií vs , s = 1, 2, . . . , k. Vyjadřují relativní důležitost kritéria. Při agregaci účelových funkcí vytváříme z k účelových funkcí jednu novou účelovou funkci. Za kompromisní řešení úlohy VLP pak považujeme optimální řešení úlohy LP vzhledem k této agregované účelové funkci. Novou účelovou funkci definujeme vztahem z=

k X

vs zs ,

kde vs ≥ 0

s=1

∀s = 1, 2, . . . , k,

k X s=1

Michal Šmerek


vs = 1.



Př: Předchozí příklad » – z1 = 5x1 + x2 −→ „maxÿ z2 = x2 za podmínek x1 + x2 ≤ 4,

(1)

x1 − 2x2 ≤ 3,

(2)

x1 ≥ 0, x2 ≥ 0, (3),(4) řešte metodou agregace účelových funkcí pro v1 = 0, 4 a v2 = 0, 6.

Michal Šmerek




Řešení: Nejprve vyjádříme agregovanou účelovou funkci: z = v1 z1 + v2 z2 z = 0, 4.(5x1 + x2 ) + 0, 6.x2 z = 2x1 + x2 −→ max Nyní řešíme jednokriteriální úlohu LP. To lze buď graficky nebo početně.

Michal Šmerek



Metoda agregace účelových funkcí Graficky: Z grafu vyplývá optimální řešení ~xopt = B = (11/3, 1/3), z(xopt ) = 23/3, proto ~zopt = (z1 (B), z2 (B)) = (56/3, 1/3).

Obrázek: Úloha VLP, metoda agregace účelových funkcí Michal Šmerek



Metoda agregace účelových funkcí Početně: Z.p.

x1

x2

x10

x20

bi

p=

bi pro aik > 0 aik

x10

1

1

1

0

4

4

x20

(1)

−2

0

1

3

3

z

−2

−1

0

0

0

max

x10

0

(3)

1

−1

1

1 3

x1

1

−2

0

1

3

−−

z

0

−5

0

2

6

max

x2

0

1

1 3 2 3 5 3

− 13

1 3 11 3 23 3

MAX

x1

1

0

z

0

0

1 3

2

Tabulka: Metoda agregace účelových funkcí

Michal Šmerek




Z tabulky vyplývá optimální řešení ~xopt = B = (11/3, 1/3), z(xopt ) = 23/3, proto ~zopt = (z1 (B), z2 (B)) = (56/3, 1/3).

Michal Šmerek



Cílové programování

V metodě cílového programování (CP) se vyžaduje znalost tzv. cílových hodnot hs , s = 1, 2, . . . , k účelových funkcí. Principem CP je nalezení takového přípustného řešení, které by zabezpečovalo hodnoty účelových funkcí co nejblíže k cílovým hodnotám. Poznámka: Je zřejmé, že v případě řešení úlohy VLP metodou CP nemá smysl hovořit o typech účelových funkcí – pojmy maximalizační či minimalizační účelová funkce ztrácí smysl. Vzdálenost hodnot účelových funkcí (pro nějaké řešení ~x ) od cílových hodnot definujeme takto: k “ ” X | hs − zs | . d ~z (~x ), ~h = s=1

Michal Šmerek



Cílové programování Definice: Kladné, resp. záporné odchylky, ds+ , resp. ds− , s = 1, 2, . . . , k, jsou definovány následovně. Pro každé řešení ~x a s = 1, 2, . . . , k, nastane právě jedna ze dvou situací: 1

zs ≥ hs , pak ds+ :=| hs − zs | ∧ ds− := 0,

2

zs < hs , pak ds+ := 0 ∧ ds− :=| hs − zs |.

Pak se úloha VLP převádí na jednokriteriální úlohu LP danou tímto matematickým modelem: d=

k ` P

´ ds+ + ds− −→ min

s=1

při omezeních ~z (~x ) − ~d + + ~d − = ~h, A · ~x ≤ ~b, ~x , ~d + , ~d − ≥ ~o , ~d + · ~d − = 0. Michal Šmerek




Př: Úlohu » VLP – z1 = x1 + x2 z2 = 3x1 + x2 za podmínek 2x1 − x2 ≤ 10,

(1)

2x1 + x2 ≤ 18,

(2)

x1 ≥ 0, x2 ≥ 0,

(3),(4)

řešte metodou CP pro h1 = 20; h2 = 26.

Michal Šmerek




Řešení: Nejprve sestavíme příslušnou úlohu CP (jednokriteriální): d = d1+ + d1− + d2+ + d2− −→ min při omezeních x1 + x2 − d1+ + d1− = 20, 3x1 + x2 − d2+ + d2− = 26, 2x1 − x2 + x10 2x1 + x2

= 10, +

x20

= 18,

x1 , x2 , x10 , x20 , d1+ , d1− , d2+ , d2− ≥ 0, ~d + · ~d − = 0. Nyní úlohu CP vyřešíme simplexovou metodou, viz tabulka.

Michal Šmerek



Z.p.

x1

x2

x10

x20

d1+

d1−

d2+

d2−

bi

d1− d2− x10 x20 d

1 3 (2) 2 4

1 1 −1 1 2

0 0 1 0 0

0 0 0 1 0

−1 0 0 0 −2

1 0 0 0 0

0 −1 0 0 −2

0 1 0 0 0

20 26 10 18 46

d1− d2− x1 x20 d

0 0 1 0 0

3 2 5 2

− 12

− 21 − 23

(2) 4

−1 −2

0 0 0 1 0

−1 0 0 0 −2

1 0 0 0 0

0 −1 0 0 −2

0 1 0 0 0

15 11 5 8 26

– 4 min

d1− d2− x1 x2 d

0 0 1 0 0

0 0 0 1 0

1 4

− 34 − 54

−1 0 0 0 −2

1 0 0 0 0

0 −1 0 0 −2

0 1 0 0 0

9 1 7 4 10

MIN

1 2

− 41 1 4 − 21 0

1 4 1 2

−1

Tabulka: Metoda cílového programování Michal Šmerek


p=

bi pro aik > 0 aik

20 26 3

5 9 min 10 22 5



V posledním kroku tabulky jsme dospěli k optimálnímu řešení úlohy CP a tedy ke kompromisnímu řešení původní úlohy VLP: ~xopt = (7, 4), ~z (~xopt ) = (11, 25).

Poznámka: Modifikace CP, pokud nejsou explicitně zadané cílové hodnoty: Při řešení úlohy VLP vyřešíme úlohy LP pro jednotlivé účelové funkce zi , i = 1, 2, . . . , k zvlášť (řešíme k jednokriteriálních úloh). Tím obdržíme tzv. ideální hodnoty zi účelových funkcí, které považujeme za cílové hodnoty: hi = zi = zi,max , i = 1, 2, . . . , k.

Michal Šmerek


Operační výzkum. Vícekriteriální programování. Lexikografická metoda. Metoda agregace účelových funkcí. Cílové programování

Recommend Documents