Metody rozwiązywania
Metody rozwiązywania
problemów decyzyjnych
problemów decyzyjnych
Harmonogramowanie pracy
Harmonogramowanie pracy
Zastosowanie wielokryterialnej
Zastosowanie wielokryterialnej
metody przydziału
metody przydziału
Piotr Sawicki
Piotr Sawicki
Wydział Maszyn Roboczych i Transportu
Wydział Maszyn Roboczych i Transportu
pok. 719, tel. [phone]
pok. 719, tel. [phone]
E-mail: [e-mail]
E-mail: [e-mail]
URL: http://www.put.poznan.pl/~piotrs
URL: http://www.put.poznan.pl/~piotrs
Harmonogramowanie pracy
Plan prezentacji
Wprowadzenie
" harmonogramowanie a problem przydziału
" jedno vs. wiele kryteriów przydziału
" rozwiązanie wielokryterialne
 charakterystyczne pojęcia
Metoda rozwiązywania problemu
" algorytm wielokryterialnej metody przydziału
" ustalanie kompromisu kryteriów
Analiza przypadku
" istota problemu
" kryteria oceny rozwiązań
" rozwiązanie problemu / ustalenie kompromisu
Podsumowanie
" wnioski
" przypomnienie pojęć
2
Piotr Sawicki / Metody rozwiązywania problemów decyzyjnych
25
1
Wprowadzenie
Harmonogramowanie a problem przydziału
Harmonogramowanie
" znane
 lista zadań/prac do wykonania
" problem polega na zaplanowaniu kolejności wykonywania zadań/prac
 na poszczególnych stanowiskach
 w oparciu o dostępne zasoby (ludzkie i techniczne)
Problem przydziału
" znane
 kolejność wykonywania zadań
 dostępne zasoby
ludzie: kierowcy, operatorzy, ...
środki techniczne: pojazdy, urządzenia przeładunkowe,...
" problem polega na optymalnym przydziale zasobów do realizacji zadań
 pracowników do zadań
 pojazdów do zadań
 ....
3
Piotr Sawicki / Metody rozwiązywania problemów decyzyjnych
25
Wprowadzenie
Harmonogramowanie a problem przydziału
Zestaw 13 zadań (1, 2, ..., 13) do realizacji
8
7 13
6 8 12
5 7 11
2 4 10
Rozwiązanie problemu przydziału
1 3 9 13
0:00 4:00 8:00 12:00 15:00 19:00 22:00 2:00
Przydział 13 pracowników (A, B, ...M) do zadań
HARMONOGRAM PRACY KIEROWCÓW
G
H B
A G I
K H E
M C J
F D L B
0:00 4:00 8:00 12:00 15:00 19:00 22:00 2:00
4
Piotr Sawicki / Metody rozwiązywania problemów decyzyjnych
25
2
Wprowadzenie
Jedno vs. wiele kryteriów przydziału
Potencjalne kryteria przydziału
Charakter kryteriów
Kryteria
Ekonomiczne Techniczne Społeczne Marketingowe
1 Koszt realizacji zadań


2 Efektywność realizacji zadań


3 Atrakcyjność zadań


4 Równomierny rozkład dni wolnych


5 Liczba nadgodzin


6 Jakość realizacji zadań


7 Inne
Poziom skomplikowania problemu
" rozwiązanie problemu jednokryterialnego przysparza trudności
 np.: 20 pracowników i 20 zadań 400 zmiennych decyzyjnych
" rozwiązanie problemu wielokryterialnego powoduje dodatkową trudność
 konieczność podjęcia decyzji jednocześnie w wielu wymiarach
5
Piotr Sawicki / Metody rozwiązywania problemów decyzyjnych
25
Wprowadzenie
Rozwiązanie wielokryterialne / Charakterystyczne pojęcia
Charakterystyczne pojęcia
" rozwiązanie niezdominowane
" punkt nadir
" punkt ideal
6
Piotr Sawicki / Metody rozwiązywania problemów decyzyjnych
25
3
Wprowadzenie
Rozwiązanie wielokryterialne / Charakterystyczne pojęcia
Rozwiązanie niezdominowane (sprawne) (B.Roy, 1990)
" rozwiązanie dla którego nie można znalez
ć innych rozwiązań w przestrzeni
kryterialnej, które byłyby lepsze względem jednego kryterium i nie gorsze względem
pozostałych
Przykład
 ocena 5 firm kurierskich (A, B, C, D, E)
 4 kryteria oceny (2 minimalizowane, 2 maksymalizowane)
 znajdz
rozwiązania niezdominowane
Kryteria oceny
Firmy kurierskie (warianty)
Czas Koszt Jakość Zasięg
(min) (min) (max) (max)
Niezdominowane
Niezdominowane
1 Firma A 12 4634 ,76 1000 Niezdominowane
12 4634 ,76 1000
Zdominowane
2 Firma B 12 4850 ,65 1000 Zdominowane
12 4850 ,65 1000 Zdominowane
3 Firma C 12 2437 ,57 1300 Niezdominowane
12 2437 ,57 1300 Niezdominowane
Niezdominowane
4 Firma D 12 1204 ,51 2000 Niezdominowane
12 1204 ,51 2000 Niezdominowane
Niezdominowane
5 Firma E 12 542 ,46 2100
12 542 ,46 2100 Niezdominowane
Niezdominowane
Niezdominowane
7
Piotr Sawicki / Metody rozwiązywania problemów decyzyjnych
25
Wprowadzenie
Rozwiązanie wielokryterialne / Charakterystyczne pojęcia
Punkt nadir (P.Vincke, 1992)
" rozwiązanie złożone z najgorszych ocen w przestrzeni kryterialnej
 max dla kryteriów minimalizowanych
 min dla kryteriów maksymalizowanych
" rozwiązanie nie istnieje w rzeczywistości
Przykład
 parametry jak wcześniej
 znajdz
punkt nadir
Kryteria oceny
Firmy kurierskie (warianty)
Czas Koszt Jakość Zasięg
(min) (min) (max) (max)
1 Firma A 12 4634 ,76 1000
12 4634 ,76 1000
Zdominowane
Zdominowane
Zdominowane
2 Firma B 12 4850 ,65 1000
3 Firma C 12 2437 ,57 1300
12 2437 ,57 1300
4 Firma D 12 1204 ,51 2000
12 1204 ,51 2000
5 Firma E 12 542 ,46 2100
12 542 ,46 2100
 punkt nadir: 12; 4634; 0,46; 1000
8
Piotr Sawicki / Metody rozwiązywania problemów decyzyjnych
25
4
Wprowadzenie
Rozwiązanie wielokryterialne / Charakterystyczne pojęcia
Punkt ideal (P.Vincke, 1992)
" rozwiązanie złożone z najlepszych ocen w przestrzeni kryterialnej
 min dla kryteriów minimalizowanych
 max dla kryteriów maksymalizowanych
" rozwiązanie nie istnieje w rzeczywistości
Przykład
 parametry jak wcześniej
 znajdz
punkt ideal
Kryteria oceny
Firmy kurierskie (warianty)
Czas Koszt Jakość Zasięg
(min) (min) (max) (max)
1 Firma A 12 4634 ,76 1000
12 4634 ,76 1000
Zdominowane
Zdominowane
2 Firma B 12 4850 ,65 1000 Zdominowane
3 Firma C 12 2437 ,57 1300
12 2437 ,57 1300
4 Firma D 12 1204 ,51 2000
12 1204 ,51 2000
5 Firma E 12 542 ,46 2100
12 542 ,46 2100
 punkt ideal: 12; 542; 0,76; 2100
9
Piotr Sawicki / Metody rozwiązywania problemów decyzyjnych
25
Metoda rozwiązywania problemu
Algorytm wielokryterialnej metody przydziału
Ogólny schemat postępowania
Rozpoznaj specyfikę problemu
Rozpoznaj specyfikę problemu
Zdefiniuj k-kryteriów przydziału
Zdefiniuj k-kryteriów przydziału
(k
(k= 1, 2, ..., n)
= 1, 2, ..., n)
Rozwiąż problem Rozwiąż problem Rozwiąż problem
Rozwiąż problem Rozwiąż problem Rozwiąż problem
...
...
dla kryterium 1 dla kryterium 2 dla kryterium n
dla kryterium 1 dla kryterium 2 dla kryterium n
Optymalne Optymalne Optymalne
Optymalne Optymalne Optymalne
rozwiązanie rozwiązanie ... rozwiązanie
rozwiązanie rozwiązanie ... rozwiązanie
dla kryterium 1 dla kryterium 2 dla kryterium n
dla kryterium 1 dla kryterium 2 dla kryterium n
Poszukaj kompromisu k-kryteriów
Poszukaj kompromisu k-kryteriów
(k
(k= 1, 2, ..., n)
= 1, 2, ..., n)
10
Piotr Sawicki / Metody rozwiązywania problemów decyzyjnych
25
5
Metoda rozwiązywania problemu
Algorytm wielokryterialnej metody przydziału
Sformułowanie matematyczne wielokryterialnego problemu przydziału
" zmienna decyzyjna (zmienna binarna)
xij - przydział i-tego pracownika do realizacji j-tego zadania
" funkcja celu
m m
k
xij max lub min
""wij
i =1 j =1
gdzie:
k
wij - element tablicy przydziału dla k-tego kryterium przydziału
" ograniczenia
m
= 1 dla j = 1, 2, ...,m
"xij
i =1
oraz
m
= 1 dla i = 1, 2, ...,m
"xij
j =1
11
Piotr Sawicki / Metody rozwiązywania problemów decyzyjnych
25
Metoda rozwiązywania problemu
Algorytm wielokryterialnej metody przydziału
Sformułowanie matematyczne wielokryterialnego problemu przydziału
" zbiór rozwiązań optymalnych
fk" = (f1", f2", ..., fn")
 zbiór zawiera tyle rozwiązań ile jest kryteriów
fk" = (f1", f2", ..., fn")
Optymalna wartość kryterium 1
Optymalna wartość kryterium 1
Optymalna wartość kryterium 2 Optymalna wartość kryterium n
Optymalna wartość kryterium 2 Optymalna wartość kryterium n
12
Piotr Sawicki / Metody rozwiązywania problemów decyzyjnych
25
6
Metoda rozwiązywania problemu
Algorytm wielokryterialnej metody przydziału
Sformułowanie matematyczne wielokryterialnego problemu przydziału
" kompromis
 uzyskiwany dla takich zmiennych decyzyjnych xij, które minimalizują wartość funkcji d1 i d2
n m m
1
k
d1 = xij
" ""wij
fk"
k =1 i =1 j =1
2
n m m
Ą# ń#
1
k
d2 = xij -1Ą#
"ó#f " ""wij
k =1 i =1 j =1
Ł# k Ś#
13
Piotr Sawicki / Metody rozwiązywania problemów decyzyjnych
25
Analiza przypadku
Istota problemu
Rozważany problem
" przydział kierowców do realizacji zadań
 13 kierowców
 13 zadań (tras realizowanych według rozkładu)
" kryteria przydziału
 koszt realizacji [zł]
 efektywność pracy [%]
 jakość obsługi pasażerów [pkt]
" poszukiwane rozwiązanie kompromisowe
14
Piotr Sawicki / Metody rozwiązywania problemów decyzyjnych
25
7
Analiza przypadku
Kryteria oceny rozwiązania
Kryterium kosztu realizacji zadań (kosztu obsługi rozkładu)
" kryterium wyrażone w [zł]
" minimalizowane
Kryterium 1: Koszt realizacji [zł]
Zadania
1 2 3 4 5 6 7 8 9 10 11 12 13
Pracownicy
A 87 84 86 85 87 84 96 94 94 88 95 96 94
B 85 85 83 87 87 87 96 95 96 89 89 105 94
C 83 84 83 82 96 87 92 97 94 88 89 96 100
D 87 83 82 83 92 89 89 93 97 94 90 95 96
E 84 83 83 87 90 87 87 91 96 97 88 91 97
F 82 83 84 87 90 88 88 87 95 96 89 94 98
G 85 85 86 92 94 88 86 84 96 95 96 98 95
H 85 84 85 92 91 87 84 85 90 96 97 99 97
I 84 85 94 94 90 94 87 91 90 96 98 90 97
J 84 86 86 94 89 95 86 94 89 87 98 94 96
K 85 87 87 83 86 94 85 87 89 89 94 91 100
L 86 85 85 83 90 96 89 85 88 94 94 91 104
M 87 82 85 84 90 97 94 86 89 94 89 93 95
Koszt realizacji zadania 4 przez pracownika L
15
Piotr Sawicki / Metody rozwiązywania problemów decyzyjnych
25
Analiza przypadku
Kryteria oceny rozwiązania
Kryterium efektywności pracy
" kryterium wyrażone w [%]
" przedział zmienności: <0, 100>
" maksymalizowane
Kryterium 2: Efektywność pracy [%]
Zadania
1 2 3 4 5 6 7 8 9 10 11 12 13
Pracownicy
A 51 56 53 56 49 71 76 71 71 58 73 76 71
B 56 56 47 51 51 71 76 73 76 60 60 96 71
C 44 76 47 47 49 84 67 78 71 58 60 76 84
D 47 67 44 56 47 76 60 69 78 71 62 73 76
E 56 62 47 49 47 78 56 64 76 78 58 64 78
F 56 62 49 44 47 80 58 56 73 76 60 71 80
G 67 71 53 51 51 73 53 49 76 73 76 80 73
H 67 64 51 51 49 78 49 51 62 76 78 82 78
I 71 62 71 49 51 78 56 64 62 76 80 62 78
J 71 60 53 49 53 76 53 71 60 56 80 71 76
K 47 53 56 51 56 84 51 56 60 60 71 64 84
L 47 62 51 53 51 93 60 51 58 71 71 64 93
M 49 62 51 56 44 73 71 53 60 71 60 69 73
Efektywność realizacji zadania 4 przez pracownika L
16
Piotr Sawicki / Metody rozwiązywania problemów decyzyjnych
25
8
0-8
0-8
8-15
8-15
4-12
4-12
4-8,12-15
4-8,12-15
15-22
15-22
15-22
15-22
15-19;22-2
0-8
0-8
8-15
8-15
4-12
4-12
4-8,12-15
4-8,12-15
15-22
15-22
15-22
15-22
15-19;22-2
Analiza przypadku
Kryteria oceny rozwiązania
Kryterium jakości obsługi
" kryterium wyrażone w [pkt]
" przedział zmienności: <0, 100>
" maksymalizowane
Kryterium 3: Jakośc obsługi pasażerów [pkt]
Zadania
1 2 3 4 5 6 7 8 9 10 11 12 13
Pracownicy
A 77 68 66 78 77 78 80 74 76 70 67 67 68
B 79 66 67 72 78 79 81 74 73 69 67 66 67
C 79 69 73 72 78 80 72 76 72 76 66 67 76
D 78 71 75 79 76 72 77 65 74 71 69 65 64
E 79 69 73 78 79 70 73 69 72 69 66 65 65
F 86 71 67 70 76 76 73 65 72 78 68 67 67
G 76 78 76 76 70 77 78 67 69 66 69 66 68
H 76 78 77 78 71 71 87 69 69 69 67 67 65
I 82 74 79 76 70 71 78 64 78 69 65 66 65
J 78 68 76 71 69 80 76 76 71 77 66 68 68
K 82 67 69 71 71 76 73 65 68 76 67 69 69
L 80 70 69 77 78 71 76 69 72 70 64 65 66
M 77 76 68 71 76 71 75 66 72 79 69 64 67
Jakość obsługi pasażerów w ramach zad. 4 przez pracownika L
17
Piotr Sawicki / Metody rozwiązywania problemów decyzyjnych
25
Analiza przypadku
Rozwiązanie problemu
Optymalizacja jednokryterialna
(Kryterium 3)
Optymalizacja jednokryterialna
Optymalizacja jednokryterialna
(Kryterium 2)
(Kryterium 1)
18
Piotr Sawicki / Metody rozwiązywania problemów decyzyjnych
25
9
0-8
0-8
8-15
8-15
4-12
4-12
4-8,12-15
4-8,12-15
15-22
15-22
15-22
15-22
15-19;22-2
Analiza przypadku
Rozwiązanie problemu
Jak ustalić wartości kryteriów dla danego rozwiązania?
" rozwiązanie 1
Zadania
1 2 3 4 5 6 7 8 9 10 11 12 13
Pracownicy
Optimum dla kryterium 1 A 0 0 0 0 0 1 0 0 0 0 0 0 0 1
Optimum dla kryterium 1
B 0 0 0 0 0 0 0 0 0 0 0 0 1 1
C 0 0 0 1 0 0 0 0 0 0 0 0 0 1
D 0 0 1 0 0 0 0 0 0 0 0 0 0 1
Wartość kryterium 2 E 0 0 0 0 0 0 0 0 0 0 1 0 0 1
F 1 0 0 0 0 0 0 0 0 0 0 0 0 1
przyjmując rozwiązanie
G 0 0 0 0 0 0 0 1 0 0 0 0 0 1
H 0 0 0 0 0 0 1 0 0 0 0 0 0 1
dla optymalnej wartości kryterium 1
I 0 0 0 0 0 0 0 0 0 0 0 1 0 1
J 0 0 0 0 0 0 0 0 0 1 0 0 0 1
K 0 0 0 0 1 0 0 0 0 0 0 0 0 1
Wartość kryterium 3
L 0 0 0 0 0 0 0 0 1 0 0 0 0 1
M 0 1 0 0 0 0 0 0 0 0 0 0 0 1
przyjmując rozwiązanie
1 1 1 1 1 1 1 1 1 1 1 1 1
funkcja celu:
dla optymalnej wartości kryterium 1
1113 [zł]
19
Piotr Sawicki / Metody rozwiązywania problemów decyzyjnych
25
Analiza przypadku
Rozwiązanie problemu
Jak ustalić wartości kryteriów dla danego rozwiązania?
" rozwiązanie 3
Zadania
1 2 3 4 5 6 7 8 9 10 11 12 13
Wartość kryterium 1
Pracownicy
A 0 0 0 0 0 0 0 0 1 0 0 0 0 1
przyjmując rozwiązanie
B 0 0 0 0 0 1 0 0 0 0 0 0 0 1
dla optymalnej wartości kryterium 3 C 0 0 0 0 0 0 0 0 0 0 0 0 1 1
D 0 0 0 0 0 0 0 0 0 0 1 0 0 1
E 0 0 0 1 0 0 0 0 0 0 0 0 0 1
F 1 0 0 0 0 0 0 0 0 0 0 0 0 1
Wartość kryterium 2
G 0 1 0 0 0 0 0 0 0 0 0 0 0 1
H 0 0 0 0 0 0 1 0 0 0 0 0 0 1
przyjmując rozwiązanie
I 0 0 1 0 0 0 0 0 0 0 0 0 0 1
dla optymalnej wartości kryterium 3 J 0 0 0 0 0 0 0 1 0 0 0 0 0 1
K 0 0 0 0 0 0 0 0 0 0 0 1 0 1
L 0 0 0 0 1 0 0 0 0 0 0 0 0 1
M 0 0 0 0 0 0 0 0 0 1 0 0 0 1
Optimum dla kryterium 3
1 1 1 1 1 1 1 1 1 1 1 1 1
20
Piotr Sawicki / Metody rozwiązywania problemów decyzyjnych
25
10
0-8
0-8
8-15
8-15
4-12
4-12
4-8,12-15
4-8,12-15
15-22
15-22
15-22
15-22
15-19;22-2
0-8
0-8
8-15
8-15
4-12
4-12
4-8,12-15
4-8,12-15
15-22
15-22
15-22
15-22
15-19;22-2
Analiza przypadku
Rozwiązanie problemu
Jak wyznaczyć kompromis?
" poszukiwanie takich zmiennych decyzyjnych xij, które minimalizują wartość
funkcji d1 i d2
n m m
1
k
d1 = xij
" ""wij
fk"
k =1 i =1 j =1
1113 56,8 74
+ +
1113 75,5 78
1168 64,7 78
+ +
1113 75,5 78
21
Piotr Sawicki / Metody rozwiązywania problemów decyzyjnych
25
Analiza przypadku
Rozwiązanie problemu
Jak wyznaczyć kompromis?
" poszukiwanie takich zmiennych decyzyjnych xij, które minimalizują wartość
funkcji d1 i d2
2
n m m
Ą# ń#
1
k
d2 = xij -1Ą#
"ó#f " ""wij
k =1 i =1 j =1
Ł# k Ś#
2 2 2
1113 56,8 74
�# �# ś# �#
ś# -1ś# + -1 + -1ś#
ź# ś# ź# ś# ź#
75,5 78
�#1113 # �# # �# #
2 2 2
1168 64,7 78
�# �# ś# �#
ś# -1ś# + -1 + -1ś#
ź# ś# ź# ś# ź#
75,5 78
�#1113 # �# # �# #
22
Piotr Sawicki / Metody rozwiązywania problemów decyzyjnych
25
11
Analiza przypadku
Rozwiązanie problemu
Interpretacja rozwiązania
Zadania
1 2 3 4 5 6 7 8 9 10 11 12 13
" wszystkie 3 rozwiązania są
Pracownicy
A 0 0 0 0 0 0 0 0 1 0 0 0 0 1
niezdominowane
B 0 0 0 0 0 1 0 0 0 0 0 0 0 1
C 0 0 0 0 0 0 0 0 0 0 0 0 1 1
D 0 0 0 0 0 0 0 0 0 0 1 0 0 1
E 0 0 0 1 0 0 0 0 0 0 0 0 0 1
" rozwiązanie idealne: (1113; 75,5; 78)
F 1 0 0 0 0 0 0 0 0 0 0 0 0 1
G 0 1 0 0 0 0 0 0 0 0 0 0 0 1
H 0 0 0 0 0 0 1 0 0 0 0 0 0 1
" rozwiązanie nadir: (1214; 56,8; 73) I 0 0 1 0 0 0 0 0 0 0 0 0 0 1
J 0 0 0 0 0 0 0 1 0 0 0 0 0 1
K 0 0 0 0 0 0 0 0 0 0 0 1 0 1
L 0 0 0 0 1 0 0 0 0 0 0 0 0 1
" rozwiązanie 3 jest rozwiązaniem
M 0 0 0 0 0 0 0 0 0 1 0 0 0 1
1 1 1 1 1 1 1 1 1 1 1 1 1
funkcja celu:
kompromisowym
1010 [pkt]
" d1 i d2 uzyskują najniższe wartości
  odległość od rozwiązania idealnego jest
relatywnie najmniejsza
23
Piotr Sawicki / Metody rozwiązywania problemów decyzyjnych
25
Podsumowanie
Literatura uzupełniająca
" Roy B.,: Wielokryterialne wspomaganie decyzji.
Wydawnictwo Naukowo Techniczne, Warszawa, 1990
" Vincke P., Multicriteria Decision-Aid.
John Wiley & Sons, Chichester, 1992
Wnioski
" przedstawiona procedura pozwala rozwiązać wielokryterialny problem przydziału
" uzyskane rozwiązanie charakteryzuje się
 kompromisem uwzględnionych kryteriów
 uwzględnieniem szeregu aspektów podejmowania decyzji (ekonomicznych, społecznych,
marketingowych)
 możliwe jest do uzyskania dzięki ogólnodostępnym narzędziom obliczeniowym
(Solver dla MS Excel)
24
Piotr Sawicki / Metody rozwiązywania problemów decyzyjnych
25
12
0-8
0-8
8-15
8-15
4-12
4-12
4-8,12-15
4-8,12-15
15-22
15-22
15-22
15-22
15-19;22-2
Podsumowanie
Przypomnienie pojęć
" harmonogramowanie a problem przydziału
" jedno vs. wiele kryteriów przydziału
" rozwiązanie wielokryterialne
" rozwiązanie niezdominowane (sprawne)
" punkt nadir
" punkt ideal
" algorytm wielokryterialnej metody przydziału
" kompromis kryteriów (d1 i d2)
25
Piotr Sawicki / Metody rozwiązywania problemów decyzyjnych
25
Metody rozwiązywania
Metody rozwiązywania
problemów decyzyjnych
problemów decyzyjnych
Harmonogramowanie pracy
Harmonogramowanie pracy
Zastosowanie wielokryterialnej
Zastosowanie wielokryterialnej
metody przydziału
metody przydziału
Piotr Sawicki
Piotr Sawicki
Wydział Maszyn Roboczych i Transportu
pok. 719, tel. [phone]
E-mail: [e-mail]
URL: http://www.put.poznan.pl/~piotrs
13