Optymalizacja wielokryterialna

Optymalizacja wielokryterialna

Optymalizacja wielokryterialna

Optymalizacja wielokryterialna

„

„

Dział badań operacyjnych zajmujący się

Dział badań operacyjnych zajmujący się

wyznaczaniem optymalnej decyzji w

wyznaczaniem optymalnej decyzji w

przypadku, gdy występuje

przypadku, gdy występuje

więcej niż jedno

więcej niż jedno

kryterium

kryterium

Problem wielokryterialny

Problem wielokryterialny

f

f

k

k

(

(

x

x

) → max (k = 1,...,s)

) → max (k = 1,...,s)

x

x

∈

∈

D

D

gdzie:

gdzie:

x

x

–

–

dowolne rozwi

dowolne rozwi

ą

ą

zanie (decyzja)

zanie (decyzja)

f

f

k

k

(

(

x

x

)

)

–

–

funkcja celu zwi

funkcja celu zwi

ą

ą

zana z k

zana z k

-

-

tym

tym

kryterium cz

kryterium cz

ą

ą

stkowym

stkowym

D

D

–

–

zbi

zbi

ó

ó

r rozwi

r rozwi

ą

ą

za

za

ń

ń

(decyzji)

(decyzji)

dopuszczalnych

dopuszczalnych

Porządkowanie rozwiązań

Porządkowanie rozwiązań

–

–

cele

cele

„

„

Uporządkowanie zbioru elementów w myśl

Uporządkowanie zbioru elementów w myśl

przyjętych reguł klasyfikacyjnych

przyjętych reguł klasyfikacyjnych

„

„

Wyróżnienie możliwie najmniejszego

Wyróżnienie możliwie najmniejszego

podzbioru stanowiącego podstawę do

podzbioru stanowiącego podstawę do

dokonywania wyborów

dokonywania wyborów

Przykład 1

Przykład 1

„

„

Spośród 10 uczniów ocenianych z 3

Spośród 10 uczniów ocenianych z 3

przedmiotów: biologii (B), historii (H)

przedmiotów: biologii (B), historii (H)

i matematyki (M) należy wybrać ucznia

i matematyki (M) należy wybrać ucznia

najlepszego.

najlepszego.

U

U

1

1

U

U

2

2

U

U

3

3

U

U

4

4

U

U

5

5

U

U

6

6

U

U

7

7

U

U

8

8

U

U

9

9

U

U

10

10

B

B

4

4

4

4

4

4

3

3

4

4

3

3

4

4

5

5

4

4

3

3

H

H

4

4

3

3

5

5

5

5

4

4

5

5

3

3

5

5

3

3

4

4

M

M

3

3

5

5

4

4

5

5

5

5

3

3

3

3

3

3

4

4

3

3

Przykład 1

Przykład 1

-

-

porównanie ocen

porównanie ocen

U

4

U

8

U

3

U

5

U

6

U

1

U

9

U

10

U

7

U

2

Diagram

Diagram

Hassego

Hassego

„

„

Definicja:

Definicja:

graf skierowany H(X,R), gdzie

graf skierowany H(X,R), gdzie

X jest zbiorem porównywanych elementów,

X jest zbiorem porównywanych elementów,

a R jest relacją częściowego porządku,

a R jest relacją częściowego porządku,

określoną na elementach zbioru X w taki

określoną na elementach zbioru X w taki

sposób, że:

sposób, że:

"

" .

uRw

w lepsze od

u

⇔

Przykład 1

Przykład 1

–

–

porównanie średniej

porównanie średniej

„

„

x

x

i

i

„lepsze od”

„lepsze od”

x

x

j

j

⇔

⇔

( )

( )

1

1

m

m

r

i

r

j

r

r

K

x

K

x

=

=

>

∑

∑

U

4

U

8

U

3

U

5

U

6

U

1

U

9

U

10

U

7

U

2

Przykład 1

Przykład 1

–

–

porównanie sumy ważonej

porównanie sumy ważonej

U

4

U

8

U

3

U

5

U

6

U

1

U

9

U

10

U

7

U

2

„

„

Przedmiotom

Przedmiotom

przypisano wagi:

przypisano wagi:

1

1

–

–

historia

historia

2

2

–

–

biologia

biologia

3

3

–

–

matematyka

matematyka

( )

( )

1

1

m

m

r

r

i

r

r

j

r

r

K

x

K

x

α

α

=

=

>

∑

∑

Przykład 1

Przykład 1

–

–

podsumowanie

podsumowanie

„

„

Uporządkowanie zależy od przyjętych kryteriów

Uporządkowanie zależy od przyjętych kryteriów

„

„

Kryteria chociaż podobne mogą prowadzić do

Kryteria chociaż podobne mogą prowadzić do

różnych wyników

różnych wyników

„

„

Kryteria szczegółowe (sformułowanie, wagi, itp.)

Kryteria szczegółowe (sformułowanie, wagi, itp.)

ustalane przez decydenta

ustalane przez decydenta

„

„

Kryteria nie są obiektywnym odbiciem

Kryteria nie są obiektywnym odbiciem

rzeczywistości, tylko odbiciem preferencji

rzeczywistości, tylko odbiciem preferencji

decydenta

decydenta

„

„

Brak odpowiedzi, które rozwiązanie jest

Brak odpowiedzi, które rozwiązanie jest

obiektywnie najlepsze

obiektywnie najlepsze

„

„

Uporządkowania pokazują, które rozwiązanie jest

Uporządkowania pokazują, które rozwiązanie jest

najlepsze w sensie przyjętego kryterium

najlepsze w sensie przyjętego kryterium

Przykład 2

Przykład 2

Fiat

Fiat

Panda

Panda

Fiat

Fiat

Seicento

Seicento

Opel

Opel

Astra

Astra

Renault

Renault

Megane

Megane

Seat

Seat

Toledo

Toledo

Skoda

Skoda

Fabia

Fabia

Ford

Ford

Focus

Focus

Cena

Cena

35

35

29

29

45

45

43

43

40

40

36

36

45

45

Serwis

Serwis

db

db

db

db

bdb

bdb

db

db

dst

dst

db

db

bdb

bdb

Zwrotność

Zwrotność

7,5

7,5

7,5

7,5

9

9

8,5

8,5

9

9

10

10

9

9

Paliwo

Paliwo

bdb

bdb

db

db

dst

dst

db

db

dst

dst

db

db

db

db

Bagażnik

Bagażnik

200

200

150

150

250

250

300

300

250

250

250

250

300

300

Przykład 2

Przykład 2

-

-

pytania

pytania

„

„

Jak porównywać kryteria ilościowe i

Jak porównywać kryteria ilościowe i

jakościowe?

jakościowe?

„

„

Jaka jest wrażliwość decydenta na różnice

Jaka jest wrażliwość decydenta na różnice

wartości kryteriów?

wartości kryteriów?

„

„

Czy dla wszystkich kryteriów istnieje taka

Czy dla wszystkich kryteriów istnieje taka

sama wartość progowa dla zmiany

sama wartość progowa dla zmiany

preferencji decydenta?

preferencji decydenta?

„

„

Czy w ocenie zróżnicowania jest pełna

Czy w ocenie zróżnicowania jest pełna

symetria?

symetria?

Progi nierozróżnialności

Progi nierozróżnialności

„

„

Brak symetrii oznacza istnienie dwóch

Brak symetrii oznacza istnienie dwóch

progów nierozróżnialności.

progów nierozróżnialności.

„

„

Sformułowanie progów nierozróżnialności:

Sformułowanie progów nierozróżnialności:

–

–

decyzja D

decyzja D

1

1

jest lepsza od decyzji D

jest lepsza od decyzji D

2

2

w sensie

w sensie

określonego kryterium, gdy wartość tego

określonego kryterium, gdy wartość tego

kryterium jest większa o p%,

kryterium jest większa o p%,

–

–

decyzja D

decyzja D

3

3

jest gorsza od decyzji D

jest gorsza od decyzji D

2

2

(w sensie

(w sensie

tego samego kryterium), gdy wartość kryterium

tego samego kryterium), gdy wartość kryterium

jest mniejsza o q%.

jest mniejsza o q%.

Przykład 3

Przykład 3

„

„

Trzy decyzje D

Trzy decyzje D

1

1

, D

, D

2

2

i D

i D

3

3

o wartościach

o wartościach

kryterium f

kryterium f

1

1

=105, f

=105, f

2

2

=100, f

=100, f

3

3

=96

=96

„

„

p = 5 oraz q = 3

p = 5 oraz q = 3

„

„

D

D

1

1

jest lepsza od D

jest lepsza od D

2

2

„

„

D

D

2

2

nie jest lepsza od D

nie jest lepsza od D

3

3

, natomiast D

, natomiast D

3

3

jest

jest

gorsza od D

gorsza od D

2

2

Przykład 4

Przykład 4

„

„

Przydzielanie kredytu

Przydzielanie kredytu

–

–

podejście 1

podejście 1

„

„

Na podstawie danych historycznych podzielić klientów na dwa

Na podstawie danych historycznych podzielić klientów na dwa

podzbiory „dobrych” i „niedobrych” kredytobiorców

podzbiory „dobrych” i „niedobrych” kredytobiorców

„

„

Wyznaczyć dla danego podzbioru wartości średnie i odchylenia

Wyznaczyć dla danego podzbioru wartości średnie i odchylenia

standardowe dla poszczególnych parametrów ekonomicznych

standardowe dla poszczególnych parametrów ekonomicznych

„

„

Porównać wartości z nowego wniosku z otrzymanymi na podst.

Porównać wartości z nowego wniosku z otrzymanymi na podst.

danych historycznych

danych historycznych

„

„

Jeśli mieszczą się w przedziałach określonych dla klientów dobry

Jeśli mieszczą się w przedziałach określonych dla klientów dobry

ch,

ch,

to przydzielić kredyt

to przydzielić kredyt

–

–

warunek zgodności ze wzorcem pozytywnym

warunek zgodności ze wzorcem pozytywnym

„

„

Jeśli mieszczą się w przedziałach dla klientów niedobrych odrzuc

Jeśli mieszczą się w przedziałach dla klientów niedobrych odrzuc

ić

ić

„

„

W przeciwnym przypadku przydzielić

W przeciwnym przypadku przydzielić

–

–

warunek niezgodności ze

warunek niezgodności ze

wzorcem negatywnym.

wzorcem negatywnym.

Przykład 4

Przykład 4

cd

cd

.

.

„

„

Przydzielanie kredytu

Przydzielanie kredytu

–

–

podejście 2

podejście 2

„

„

Uporządkować klientów wg „pożądanych” wartości

Uporządkować klientów wg „pożądanych” wartości

parametrów opisujących klienta i utworzyć zbiór

parametrów opisujących klienta i utworzyć zbiór

„najlepszych”, stosując określone reguły porządkowania:

„najlepszych”, stosując określone reguły porządkowania:

–

–

jeżeli dla pary klientów r i v wartość kryterium i (K

jeżeli dla pary klientów r i v wartość kryterium i (K

ri

ri

)

)

dla klienta r przewyższa wartość kryterium i (

dla klienta r przewyższa wartość kryterium i (

K

K

vi

vi

) dla

) dla

klienta v o pewną zadaną wartość d

klienta v o pewną zadaną wartość d

i

i

, to przyjmuje się,

, to przyjmuje się,

że klient r jest lepszy od klienta v w sensie kryterium i

że klient r jest lepszy od klienta v w sensie kryterium i

–

–

zlicza się dla ilu kryteriów spośród m klient r jest

zlicza się dla ilu kryteriów spośród m klient r jest

lepszy od klienta v, wartość oznaczona przez l(r,v)

lepszy od klienta v, wartość oznaczona przez l(r,v)

–

–

zlicza się dla ilu kryteriów r jest gorszy od v i oznacza

zlicza się dla ilu kryteriów r jest gorszy od v i oznacza

się przez g(r,v)

się przez g(r,v)

–

–

klient r jest lepszy od klienta v jeśli l(r,v) > g(r,v)

klient r jest lepszy od klienta v jeśli l(r,v) > g(r,v)

Zgodność kryteriów

Zgodność kryteriów

„

„

Dla dwóch kryteriów K

Dla dwóch kryteriów K

1

1

i K

i K

2

2

oraz dla dwóch

oraz dla dwóch

dowolnych decyzji x

dowolnych decyzji x

1

1

i x

i x

2

2

:

:

–

–

kryteria są zgodne jeśli

kryteria są zgodne jeśli

–

–

kryteria są niezgodne jeśli

kryteria są niezgodne jeśli

–

–

kryteria są przeciwstawne jeśli

( )

( )

( )

( )

1

2

1

1

1

2

2

1

2

2

,

x x

D

K

x

K

x

K

x

K

x

∈

≤

⇒

≤

∀

( )

( )

( )

( )

1

2

1

1

1

2

2

1

2

2

,

x x

D

K

x

K

x

K

x

K

x

∈

≤

⇒

≥

∃

kryteria są przeciwstawne jeśli

( )

( )

( )

( )

1

2

1

1

1

2

2

1

2

2

,

x x

D

K

x

K

x

K

x

K

x

∈

≤

⇒

≥

∀

Rozwiązania sprawne

Rozwiązania sprawne

„

„

Rozwiązaniem optymalnym w sensie

Rozwiązaniem optymalnym w sensie

Pareto

Pareto

nazywamy takie rozwiązanie

nazywamy takie rozwiązanie

x’

x’

∈

∈

D,

D,

ż

ż

e nie

e nie

istnieje

istnieje

ż

ż

adne inne rozwi

adne inne rozwi

ą

ą

zanie

zanie

x

x

∈

∈

D daj

D daj

ą

ą

ce

ce

popraw

popraw

ę

ę

warto

warto

ś

ś

ci chocia

ci chocia

ż

ż

jednej funkcji

jednej funkcji

celu, nie powoduj

celu, nie powoduj

ą

ą

c pogorszenia warto

c pogorszenia warto

ś

ś

ci

ci

innych funkcji celu. Rozwi

innych funkcji celu. Rozwi

ą

ą

zanie

zanie

optymalne w sensie

optymalne w sensie

Pareto

Pareto

nazywane jest

nazywane jest

r

r

ó

ó

wnie

wnie

ż

ż

rozwi

rozwi

ą

ą

zaniem sprawnym lub

zaniem sprawnym lub

efektywnym.

efektywnym.

Rozwiązania kompromisowe

Rozwiązania kompromisowe

„

„

Jedno rozwiązanie optymalne w sensie

Jedno rozwiązanie optymalne w sensie

Pareto

Pareto

występuje tylko wtedy, gdy wszystkie optima

występuje tylko wtedy, gdy wszystkie optima

cząstkowe znajdują się w tym samym punkcie, jest

cząstkowe znajdują się w tym samym punkcie, jest

to wtedy również rozwiązanie optymalne całego

to wtedy również rozwiązanie optymalne całego

problemu

problemu

„

„

Na ogół rozwiązań

Na ogół rozwiązań

Pareto

Pareto

-

-

optymalnych jest wiele,

optymalnych jest wiele,

w skrajnym przypadku każde rozwiązanie może

w skrajnym przypadku każde rozwiązanie może

być rozwiązaniem sprawnym

być rozwiązaniem sprawnym

„

„

Pytanie: Jak spośród wielu rozwiązań sprawnych

Pytanie: Jak spośród wielu rozwiązań sprawnych

wybrać jedno rozwiązanie, tzw.

wybrać jedno rozwiązanie, tzw.

rozwiązanie

rozwiązanie

kompromisowe

kompromisowe

?

?

Metody

Metody

„

„

Metakryterium

Metakryterium

„

„

Kryterium główne i kryteria drugorzędne

Kryterium główne i kryteria drugorzędne

„

„

Ścisła hierarchia celów

Ścisła hierarchia celów

„

„

Minimalizacja odległości od punktu

Minimalizacja odległości od punktu

idealnego

idealnego

Metakryterium

Metakryterium

„

„

Funkcja określona na kryteriach cząstkowych,

Funkcja określona na kryteriach cząstkowych,

podająca użyteczność poszczególnych decyzji dla

podająca użyteczność poszczególnych decyzji dla

decydenta:

decydenta:

„

„

Najprostsze

Najprostsze

metakryterium

metakryterium

–

–

suma ważona

suma ważona

„

„

Rozwiązanie zadania sprowadza się do znalezienia

Rozwiązanie zadania sprowadza się do znalezienia

w zbiorze rozwiązań dopuszczalnych decyzji

w zbiorze rozwiązań dopuszczalnych decyzji

najlepszej w sensie

najlepszej w sensie

metakryterium

metakryterium

u

u

(

(

x

x

). Decyzja

). Decyzja

najlepsza w sensie

najlepsza w sensie

u

u

(

(

x

x

) jest poszukiwaną decyzją

) jest poszukiwaną decyzją

kompromisową.

kompromisową.

( )

( ) ( )

( )

1

2

x

x ,

x , ,

x

s

u

u f

f

f

⎡

⎤

= ⎣

⎦

…

( )

( )

1

x

x

s

k

k

k

u

w f

=

=

∑

Kryterium główne i kryteria drugorzędne

Kryterium główne i kryteria drugorzędne

„

„

Gdy dla decydenta jedno kryterium jest zasadnicze (główne), a

Gdy dla decydenta jedno kryterium jest zasadnicze (główne), a

pozostałe mniej istotne (drugorzędne). Poszukiwane jest wtedy

pozostałe mniej istotne (drugorzędne). Poszukiwane jest wtedy

rozwiązanie najlepsze ze względu na kryterium główne,

rozwiązanie najlepsze ze względu na kryterium główne,

jednocześnie zapewniające określony poziom realizacji

jednocześnie zapewniające określony poziom realizacji

kryteriów drugorzędnych.

kryteriów drugorzędnych.

„

„

Wyznaczanie decyzji kompromisowej sprowadza się do

Wyznaczanie decyzji kompromisowej sprowadza się do

rozwiązania zadania:

rozwiązania zadania:

gdzie

gdzie

f

f

1

1

–

–

kryterium główne,

kryterium główne,

p

p

k

k

–

–

zadowalający poziom realizacji

zadowalający poziom realizacji

k

k

-

-

tego kryterium

tego kryterium

drugorzędnego

( )

( )

1

max

dla

2, ,

k

k

f
f

p

k

s

D

→

⎧

⎪

≥

=

⎨

⎪ ∈

⎩

x

x

x

…

drugorzędnego

Ścisła hierarchia celów

Ścisła hierarchia celów

„

„

Uporządkowanie wszystkich kryteriów malejąco

Uporządkowanie wszystkich kryteriów malejąco

od najważniejszego. Przy wyznaczaniu

od najważniejszego. Przy wyznaczaniu

rozwiązania kompromisowego, nie można

rozwiązania kompromisowego, nie można

przekroczyć ustalonego odstępstwa od

przekroczyć ustalonego odstępstwa od

maksymalnych wartości poszczególnych

maksymalnych wartości poszczególnych

kryteriów.

kryteriów.

„

„

Wyznaczanie decyzji kompromisowej polega na

Wyznaczanie decyzji kompromisowej polega na

rozwiązaniu ciągu zadań pomocniczych

rozwiązaniu ciągu zadań pomocniczych

L

L

k

k

(

(

k=

k=

1,...,

1,...,

s

s

). Rozwiązanie końcowego zadania

). Rozwiązanie końcowego zadania

L

L

s

s

,

,

wyznacza decyzję kompromisową zadania

wyznacza decyzję kompromisową zadania

wielokryterialnego.

wielokryterialnego.

Ścisła hierarchia celów

Ścisła hierarchia celów

cd

cd

.

.

„

„

Zadanie pomocnicze

Zadanie pomocnicze

L

L

k

k

przy założeniu, że kryterium o niższym indeksie jest ważniejsze

przy założeniu, że kryterium o niższym indeksie jest ważniejsze

od

od

kryterium o wyższym indeksie, a współczynnik odstępstwa dla dane

kryterium o wyższym indeksie, a współczynnik odstępstwa dla dane

go

go

kryterium oznaczono przez

kryterium oznaczono przez

d

d

k

k

(0

(0

≤

≤

d

d

k

k

≤

≤

1 dla

1 dla

k =

k =

1,

1,

…

…

,s

,s

-

-

1

1

).

( )

{

}

( )

{

}

( )

{

}

( )

{

}

1

1

1

1

1

1

1

1

1

1

1

1

1

1

max

:

gdzie

dla

1,

:

dla

2, , ,

max

:

,

min

:

,

.

k

k

k

k

k

k

k

k

k

k

k

k

k

k

k

k

k

k

f

D

D

D

k

D

D

f

x

M

d t

k

s

M

f

D

m

f

D

t

M

m

−

−

−

−

−

−

−

−

−

−

−

−

−

−

∈

=

=

=

∈

∧

≥

−

=

=

∈

=

∈

=

−

x x

x x

x x

x x

…

).

Minimalizacja odległości od punktu idealnego

Minimalizacja odległości od punktu idealnego

„

„

W przypadku, gdy nie ma żadnych preferencji dla

W przypadku, gdy nie ma żadnych preferencji dla

poszczególnych kryteriów cząstkowych, jako rozwiązanie

poszczególnych kryteriów cząstkowych, jako rozwiązanie

kompromisowe wybiera się punkt leżący najbliżej punktu

kompromisowe wybiera się punkt leżący najbliżej punktu

idealnego.

idealnego.

„

„

Punkt nazywamy

Punkt nazywamy

punktem idealnym

punktem idealnym

w

w

przestrzeni wyników, natomiast punkt

przestrzeni wyników, natomiast punkt

nazywamy

nazywamy

punktem idealnym

punktem idealnym

w przestrzeni rozwiązań o ile

w przestrzeni rozwiązań o ile

„

„

Jeżeli , to jest rozwiązaniem optymalnym. Jeżeli

Jeżeli , to jest rozwiązaniem optymalnym. Jeżeli

natomiast lub nie istnieje, to szukamy takiego punk

natomiast lub nie istnieje, to szukamy takiego punk

tu

tu

x

x

’

’

∈

∈

D

D

, aby punkt le

, aby punkt le

ż

ż

a

a

ł

ł

jak najbli

jak najbli

ż

ż

ej punktu

ej punktu

idealnego , gdzie

idealnego , gdzie

dla

dla

k

k

= 1,...,

= 1,...,

s

s

.

.

[

]

1

, ,

s

z

z

=

z

…

[

]

1

, ,

n

x

x

=

x

…

( )

( )

{

}

max

:

dla

1, , .

k

k

k

z

f

f

D

k

s

=

=

∈

=

x

x x

…

D

∈

x

x

D

∉

x

[

]

1

, ,

s

z

z

′

′

′

=

z

…

( )

k

k

f

′

′

=

z

x

z

Min.

Min.

odl

odl

. od punktu idealnego

. od punktu idealnego

–

–

cd

cd

.

.

„

„

Gdy każde jest dodatnie, to punkt

Gdy każde jest dodatnie, to punkt

x

x

wyznaczamy

wyznaczamy

rozwiązując pomocnicze zadanie:

rozwiązując pomocnicze zadanie:

gdzie

gdzie

y

y

–

–

minimalny stopień realizacji celów cząstkowych.

minimalny stopień realizacji celów cząstkowych.

k

z

( )

(

)

max

0

1, ,

k

k

y

f

z

k

s

D

→

⎧

⎪

−

≥

=

⎨

⎪ ∈

⎩

x

x

…

Min.

Min.

odl

odl

. od punktu idealnego

. od punktu idealnego

–

–

cd

cd

.

.

„

„

Gdy jest ujemne lub zerowe (co najmniej jedno kryterium z

Gdy jest ujemne lub zerowe (co najmniej jedno kryterium z

minimalizacją funkcji kryterialnej), to wprowadzając

minimalizacją funkcji kryterialnej), to wprowadzając

współczynnik odchylenia w realizacji

współczynnik odchylenia w realizacji

k

k

-

-

tego kryterium

tego kryterium

cząstkowego przez decyzję

cząstkowego przez decyzję

x

x

:

:

gdzie

gdzie

m

m

k

k

= min{

= min{

f

f

k

k

(

(

x

x

):

):

x

x

∈

∈

D

D

}.

}.

Rozwiązuje się wówczas zadanie

Rozwiązuje się wówczas zadanie

gdzie

gdzie

w

w

–

–

zmienna pomocnicza określająca maksymalne

zmienna pomocnicza określająca maksymalne

względne odstępstwo od optymalnej wartości kryterium.

względne odstępstwo od optymalnej wartości kryterium.

k

z

( )

(

)

min

1, ,

k

w

d

w

k

s

D

→

⎧

⎪

≤

=

⎨

⎪ ∈

⎩

x

x

…

( )

( )

k

k

k

k

k

z

f

d

z

m

−

=

−

x

x