1

Metody rozwiązywania
problemów decyzyjnych

Metody rozwiązywania
problemów decyzyjnych

Piotr Sawicki

Piotr Sawicki

Wydział Maszyn Roboczych i Transportu
pok. 719, tel. [phone]
E-mail: [e-mail]
URL: http://www.put.poznan.pl/~piotrs

Harmonogramowanie pracy

Zastosowanie metody przydziału

Harmonogramowanie pracy

Zastosowanie metody przydziału

33

2

Piotr Sawicki / Metody rozwi

ązywania problemów decyzyjnych

Plan prezentacji

Istota problemu przydziału pracowników do zadań

•

wprowadzenie

•

praktyczne aspekty problemu

Matematyczne sformułowanie problemu przydziału

•

zmienna decyzyjna

•

funkcja celu

•

ograniczenia

•

struktura problemu przydziału

Metoda przydziału

•

tablica przydziału

•

główne kroki metody przydziału

•

uogólniony algorytm metody przydziału

Analiza przypadku

Podsumowanie

2

33

3

Piotr Sawicki / Metody rozwi

ązywania problemów decyzyjnych

Wprowadzenie

Istota problemu przydziału

Rozważmy problem przydziału pracowników do obsługi kilku regionów
sprzedaży

Przypadek 1

Przypadek 1

Przypadek 1

Przypadek 2

Przypadek

Przypadek

2

2

33

4

Piotr Sawicki / Metody rozwi

ązywania problemów decyzyjnych

Wprowadzenie

Istota problemu przydziału

Problem przydziału pracowników do obsługi kilku regionów…cd

Przypadek 3

Przypadek

Przypadek

3

3

3

33

5

Piotr Sawicki / Metody rozwi

ązywania problemów decyzyjnych

Wprowadzenie

Istota problemu przydziału

Problemy spotykane w praktyce charakteryzują się znacznie większym
stopniem skomplikowania

20.922.789.888.000

16

…

…

…

…

3.628.800

10

362.880

9

40.320

8

5.040

7

720

6

120

5

24

4

6

3

2

2

1

1

Liczba

Liczba

permutacji

permutacji

Liczba

Liczba

pracowników

pracowników

i regionów

i regionów

33

6

Piotr Sawicki / Metody rozwi

ązywania problemów decyzyjnych

Wprowadzenie

Istota problemu przydziału

Istnieje wiele możliwości przydziału pracowników do zadań

•

w praktyce

– porzuca się próby racjonalnego przydziału pracowników
– decyduje się na „zgadywanie” najlepszego przydziału

Człowiek jako pracownik charakteryzuje się określonymi cechami

•

efektywność pracy

•

umiejętności

•

zdolności

•

doświadczenia

•

….

Traktując pracowników jako niezróżnicowane zasoby przedsiębiorstwo traci

szansę znaczącego podniesienia produktywności

Menadżer (pracodawca) chcący dobrać ludzi do realizacji zdefiniowanych

zadań w najlepszy możliwy sposób musi

•

przewidzieć zapotrzebowanie na pracę

•

poszukiwać odpowiednich ludzi

•

dokonywać efektywnej alokacji pracowników

4

33

7

Piotr Sawicki / Metody rozwi

ązywania problemów decyzyjnych

Metoda przydzia

łu

Istota problemu przydziału

Problem przydziału w ogólności polega na delegowaniu

pracowników

pracowników

do poszczególnych prac, w taki sposób, aby

koszt

koszt

realizacji wszystkich prac był minimalny

Szersze rozumienie problemu

•

pracownik Æ urządzenie

•

koszt Æ czas, odległość, inne mierniki efektywności

Założenie dotyczące przydziału pracowników do zadań

•

tylko jeden pracownik może być przydzielony do jednego zadania

•

jedno zadanie ma przydzielone tylko jednego pracownika

33

8

Piotr Sawicki / Metody rozwi

ązywania problemów decyzyjnych

Metoda przydzia

łu

Istota problemu przydziału

Przykłady zadań jednocześnie wykonywanych przez różną liczbę
pracowników (osób)

…

¯

kierowanie autobusem międzymiastowym
(przewóz międzynarodowy)

…

…

…

…

…

…

…

¯

gra w piłkę nożną

…

…

…

…

…

¯

¯

¯

¯

rozładunek towaru

…

…

…

…

…

¯

kierowanie autobusem międzymiastowym
(przewóz krajowy)

¯

kierowanie autobusem miejskim

11

3

2

1

Ludzie

Zadania

5

33

9

Piotr Sawicki / Metody rozwi

ązywania problemów decyzyjnych

Metoda przydzia

łu

Istota problemu przydziału

Jeżeli tylko jeden

pracownik

pracownik

może zostać przydzielony do jednego

zadania

zadania

,

wówczas

•

z punktu widzenia matematycznego zapisu problemu zmienną decyzyjną będzie
wartość

– x

ij

= 1 jeżeli i-ty pracownik jest przedzielony do wykonywania j-tej pracy

– x

ij

= 0 jeżeli i-ty pracownik nie jest przedzielony do wykonywania j-tej pracy

•

poszukujemy rozwiązania

– całkowitoliczbowego
– binarnego (0 lub 1)

•

sformułowanie i rozwiązanie problemu

– problem można sformułować w postaci zadania programowania liniowego

{

z ograniczeniem o binarnych charakterze zmiennych decyzyjnych

– problem można rozwiązać za pomocą znanych metod

{

płaszczyzn odcinających Gomory’ego

{

ograniczeń i rozgałęzień

– istnieje specyficzna metoda rozwiązywania problemu przydziału Æ

METODA PRZYDZIA

METODA PRZYDZIA

Ł

Ł

U

U

33

10

Piotr Sawicki / Metody rozwi

ązywania problemów decyzyjnych

Metoda przydzia

łu

Istota problemu przydziału

Założenia metody

•

problem przydziału można potraktować jako specyficzny przypadek problemu
transportowego

•

problem przydziału można zatem rozwiązać z zastosowaniem metody transportowej

c

44

c

43

c

42

c

41

1

4

x

44

x

43

x

42

x

41

4

1

1

1

1

Popyt

x

34

x

33

x

32

x

31

1

c

34

c

33

c

32

c

31

3

x

24

x

23

x

22

x

21

1

c

24

c

23

c

22

c

21

2

x

14

x

13

x

12

x

11

1

c

14

c

13

c

12

c

11

1

4

3

2

1

Podaż

Magazyny odbiorców

/

Zadania

Dostawcy/

Pracownicy

Każdy pracownik może

wykonać jedno zadanie

Każdy

pracownik

może

wykonać jedno zadanie

Każde zadanie może mieć

przedzielone jednego pracownika

Każde zadanie może mieć

przedzielone jednego pracownika

Przydział

pracownika do

zadania (0 lub 1) –

ZMIENNA BINARNA

Przydział

pracownika do

zadania (0 lub 1) –

ZMIENNA BINARNA

ZMIENNA BINARNA

Efektywność

przydziału

pracownika do

zadania

Efektywność

przydziału

pracownika do

zadania

TABLICA PRZYDZIAŁU

TABLICA PRZYDZIAŁU

6

33

11

Piotr Sawicki / Metody rozwi

ązywania problemów decyzyjnych

Metoda przydzia

łu

Istota problemu przydziału

Interpretacja zmiennej decyzyjnej

•

załóżmy, że pomijamy wartości c

ij

oraz np. x

23

= 1

•

co to w praktyce oznacza zmienna x

ij

?

c

44

c

43

c

42

c

41

1

4

x

44

x

43

x

42

x

41

4

1

1

1

1

Popyt

x

34

x

33

x

32

x

31

1

c

34

c

33

c

32

c

31

3

x

24

x

23

x

22

x

21

1

c

24

c

23

c

22

c

21

2

x

14

x

13

x

12

x

11

1

c

14

c

13

c

12

c

11

1

4

3

2

1

Podaż

Magazyny odbiorców

Æ

Zadania

Dostawcy

Pracownicy

1

jeżeli x

23

= 1 Æ x

21

= x

22

= x

24

= 0

jeżeli x

23

= 1 Æ x

21

= x

22

= x

24

= 0

również x

13

= x

33

= x

43

= 0

również x

13

= x

33

= x

43

= 0

33

12

Piotr Sawicki / Metody rozwi

ązywania problemów decyzyjnych

Metoda przydzia

łu

Model matematyczny problemu

Problem przydziału sformułowany w postaci zadania programowania
liniowego

Ogólne sformułowanie funkcji celu Æ minimum całkowitych kosztów
realizacji wszystkich zadań (prac)

gdzie:

c

ij

– jednostkowy koszt realizacji j-tego zadania przez i-tego pracownika,

i = 1, 2, ..., m; j = 1, 2, ..., n

m

– zbiór pracowników

n

– zbiór zadań (prac)

x

ij

– zmienna decyzyjna wskazująca przydział i-tego pracownika do j-tego zadania,

x

ij

= 0

∪ 1

min

Koszt

→

=

∑∑

=

=

m

i

n

j

ij

ij

x

c

1

1

7

33

13

Piotr Sawicki / Metody rozwi

ązywania problemów decyzyjnych

Metoda przydzia

łu

Model matematyczny problemu

Jednostkowy koszt realizacji
j-tego zadania przez i-tego
pracownika zależy od

•

predyspozycji i inteligencji

•

motywacji

•

kompetencji pracownika

•

wieku

•

wyposażenia stanowiska
(zaawansowania technolo-
gicznego urządzenia)

•

częstotliwości powtarzania

•

…

•

doświadczenia i praktyki
pracownika

Skumulowana liczba zrealizowanych zada

ń

Czas Æ

Liczba powtórzeń Æ

Jednost

kowy czas realizacji

KRZYWA UCZENIA SIĘ

33

14

Piotr Sawicki / Metody rozwi

ązywania problemów decyzyjnych

Metoda przydzia

łu

Model matematyczny problemu

Ograniczenia

•

i-ty pracownik może być
przydzielony tylko do jednego
zadania

•

do j-tego zadania może być
przydzielony tylko jeden
pracownik

m

1,2,....,

i

;

=

=

∑

=

1

1

n

j

ij

x

n

1,2,....,

j

;

=

=

∑

=

1

1

m

i

ij

x

1

2

i

m

1

2

j

n

x

i1

x

i2

x

ij

x

in

1

2

i

m

1

2

j

n

x

1j

x

2j

x

ij

x

mj

Pracownicy

Zadania

Pracownicy

Zadania

8

33

15

Piotr Sawicki / Metody rozwi

ązywania problemów decyzyjnych

Metoda przydzia

łu

Model matematyczny problemu

Model matematyczny problemu przydziału Æ klasyczny przypadek

•

funkcja celu Æ minimalizacja kosztu wykonania wszystkich zadań

•

przy ograniczeniach

•

przyjęte ograniczenie wymusza kwadratowy wymiar tablicy m=n

– liczba pracowników równa jest liczbie zadań do wykonania

min

Koszt

→

=

∑∑

=

=

m

i

n

j

ij

ij

x

c

1

1

m

1,2,....,

i

;

=

=

∑

=

1

1

n

j

ij

x

n

1,2,....,

j

;

=

=

∑

=

1

1

m

i

ij

x

1

0

∪

∈

ij

x

33

16

Piotr Sawicki / Metody rozwi

ązywania problemów decyzyjnych

Metoda przydzia

łu

Rozwiązanie problemu przydziału pracowników do zadań

Zważywszy na postać zmiennej decyzyjnej tablica przydziału może przyjąć
postać uwzględniającą wyłącznie komórki kosztów

Problem Æ dokonaj przydziału pracowników do zadań w kategoriach czasu
realizacji zadań (minimalizacja czasu wykonania wszystkich prac)

•

pracownicy: 1, 2, 3, 4

•

zadania: 1, 2, 3, 4

c

44

c

43

c

42

c

41

1

4

4

1

1

1

1

Przydział

1

c

34

c

33

c

32

c

31

3

1

c

24

c

23

c

22

c

21

2

1

c

14

c

13

c

12

c

11

1

4

3

2

1

Przydział

Zadania

Pracownicy

9

33

17

Piotr Sawicki / Metody rozwi

ązywania problemów decyzyjnych

Metoda przydzia

łu

Rozwiązanie problemu przydziału pracowników do zadań

W tablicy zamieszczono szacunkowe czasy realizacji poszczególnych zadań
przez każdego z pracowników, wyrażone w [godz.]

3

4

2

8

1

4

4

1

1

1

1

Przydział

1

8

3

5

5

3

1

7

2

6

6

2

1

5

1

3

5

1

4

3

2

1

Przydział

Zadania

Pracownicy

najkrótszy czas realizacji zadania 1

najkrótszy czas realizacji zadania 1

najkrótszy czas realizacji zadania 2

najkrótszy czas realizacji zadania 2

najkrótszy czas realizacji zadania 3

najkrótszy czas realizacji zadania 3

najkrótszy czas realizacji zadania 4

najkrótszy czas realizacji zadania 4

33

18

Piotr Sawicki / Metody rozwi

ązywania problemów decyzyjnych

Metoda przydzia

łu

Rozwiązanie problemu przydziału pracowników do zadań

KROK 1: od każdego „czasu realizacji” w wierszu odejmij najmniejszą
wartość w tym wierszu

3

4

2

8

1

4

4

1

1

1

1

Przydział

1

8

3

5

5

3

1

7

2

6

6

2

1

5

1

3

5

1

4

3

2

1

Przydział

Zadania

Pracownicy

–1

–1

–1

–1

–2

–2

–2

–2

–3

–3

–3

–3

–2

–2

–2

–2

10

33

19

Piotr Sawicki / Metody rozwi

ązywania problemów decyzyjnych

Metoda przydzia

łu

Rozwiązanie problemu przydziału pracowników do zadań

Tablica przydziału po kroku 1

KROK 2: od każdego „czasu realizacji” w kolumnie odejmij najmniejszą
wartość w tej kolumnie

1

2

0

6

1

4

4

1

1

1

1

Przydział

1

5

0

2

2

3

1

5

0

4

4

2

1

4

0

2

4

1

4

3

2

1

Przydział

Zadania

Pracownicy

–2

–2

–2

–2

–0

–0

–0

–0

–0

–0

–0

–0

–1

–1

–1

–1

33

20

Piotr Sawicki / Metody rozwi

ązywania problemów decyzyjnych

Metoda przydzia

łu

Rozwiązanie problemu przydziału pracowników do zadań

Tablica przydziału po kroku 2

KROK 3: Narysuj minimalną liczbę linii przechodzących przez wszystkie
„zera”

KROK 4: Oceń ile powstało linii

•

ponieważ tablica ma wymiar 4¯4 Æ minimalna liczba linii powinna wynosić 4,
wówczas przydział pojedynczych pracowników do zadań będzie optymalny

•

jeżeli warunek nie jest spełniony Æ poszukujemy innych możliwości Æ KROK 5

0

2

0

4

1

4

4

1

1

1

1

Przydział

1

4

0

2

0

3

1

4

0

4

2

2

1

3

0

2

2

1

4

3

2

1

Przydział

Zadania

Pracownicy

11

33

21

Piotr Sawicki / Metody rozwi

ązywania problemów decyzyjnych

Metoda przydzia

łu

Rozwiązanie problemu przydziału pracowników do zadań

KROK 5: Znajdź najmniejszą liczbę spośród wartości, przez które nie
przechodzi żadna linia

•

odejmij od każdego „czasu realizacji” nie objętego linią

•

dodaj do każdego „czasu realizacji” objętego dwiema liniami

0

2

0

4

1

4

4

1

1

1

1

Przydział

1

4

0

2

0

3

1

4

0

4

2

2

1

3

0

2

2

1

4

3

2

1

Przydział

Zadania

Pracownicy

–2

–2

–2

–2

–2

–2

+

2

+

2

33

22

Piotr Sawicki / Metody rozwi

ązywania problemów decyzyjnych

Metoda przydzia

łu

Rozwiązanie problemu przydziału pracowników do zadań

Tablica przydziału po kroku 5

KROK 6: Ponownie narysuj minimalną liczbę linii przechodzących przez
wszystkie „zera”

KROK 7: Oceń ile powstało linii

•

minimalna liczba linii wynosi 4 Æ możliwy jest optymalny przydział pracowników do
zadań

•

powstała tablica jest tablicą finalną

0

4

0

4

1

4

4

1

1

1

1

Przydział

1

4

2

2

0

3

1

2

0

2

0

2

1

1

0

0

0

1

4

3

2

1

Przydział

Zadania

Pracownicy

12

33

23

Piotr Sawicki / Metody rozwi

ązywania problemów decyzyjnych

Metoda przydzia

łu

Rozwiązanie problemu przydziału pracowników do zadań

KROK 8: Powróć do pierwotnej tablicy przydziału i dokonaj przydziału na
podstawie komórek, które w finalnej tablicy miały wartość „zero”

Czas realizacji prac (efektywność realizacji wszystkich zadań wynosi:
5

×(1) + 3×(1) + 2×(1) + 3×(1) = 13 godz.

3

4

2

8

1

4

4

1

1

1

1

Przydział

1

8

3

5

5

3

1

7

2

6

6

2

1

5

1

3

5

1

4

3

2

1

Przydział

Zadania

Pracownicy

33

24

Piotr Sawicki / Metody rozwi

ązywania problemów decyzyjnych

Metoda przydzia

łu

Rozwiązanie problemu przydziału pracowników do zadań

Algorytm metody przydziału

(

0

) przygotuj tablicę przydziału, zawierającą koszty przydziału (lub inny wskaźnik

efektywności) pracowników do zadań

(1)

zidentyfikuj najmniejszą wartość w każdym wierszu i odejmij ją od każdego

elementu w tym wierszu

(2)

zidentyfikuj najmniejszą wartość w każdej kolumnie i odejmij ją od każdego
elementu w tej kolumnie

(3)

narysuj minimalną liczbę linii przechodzących przez wszystkie „zera”

(4)

oceń ile linii powstało w kroku (3)

• jeżeli liczba linii równa jest wymiarowi tablicy n, wówczas możliwy jest optymalny

przydział pracowników

• jeżeli liczba linii jest mniejsza od n przejdź do kroku (5)

(5)

znajdź najmniejszą liczbę w tablicy, spośród wartości, przez które nie przechodzi
żadna linia

• odejmij tę wartość od tych, przez które nie przechodzi żadna linia
• dodaj tę wartość do wszystkich, przez które przechodzą 2 linie

13

33

25

Piotr Sawicki / Metody rozwi

ązywania problemów decyzyjnych

Metoda przydzia

łu

Rozwiązanie problemu przydziału pracowników do zadań

Algorytm metody przydziału …cd

(6)

na tablicy powstałej w kroku (5) zrealizuj krok (3), ponownie rysując minimalną
liczbę linii łączących wszystkie „zera”

(7)

przejdź do kroku (4) oceniając liczbę linii

• jeżeli minimalna liczba linii jest równa wymiarowi tablicy przydziału,

–

dokonaj przydziału pracowników do zadań na podstawie komórek, które w finalnej
tablicy przydziału mają wartości „zero”

–

oblicz wartość funkcji celu

• jeżeli minimalna liczba linii jest mniejsza niż wymiar tablicy przydziału wróć do kroku (5)

33

26

Piotr Sawicki / Metody rozwi

ązywania problemów decyzyjnych

Metoda przydzia

łu

Analiza przypadku

Rozwi

ązanie

Rozwi

ązanie

Dokonaj analizy problemu, zgodnie z załączonym
opisem przypadku

•

przeprowadź analizę problemu

•

sformułuj model matematyczny problemu

•

rozwiąż problem z zastosowaniem metody przydziału

•

wykorzystaj Solver dla MS Excel

Istota problemu

•

przydział motorniczych do realizacji poszczególnych
zadań

– wariant 1: przydział 13 kierowców do 13 zadań
– wariant 2: przydział 14 kierowców do 14 zadań

•

jak zmieni się przydział pracowników (1-13) po
wprowadzeniu pracownika nr 14?

Opis

problemu

Opis

problemu

14

33

27

Piotr Sawicki / Metody rozwi

ązywania problemów decyzyjnych

Metoda przydzia

łu

Analiza przypadku / W1

Tworzenie arkuszy
roboczego w MS
Excel dla Wariantu 1

Tablica kosztów realizacji

poszczególnych zadań

Tablica kosztów realizacji

poszczególnych zadań

Tablica przydziału

pracowników do zadań

Tablica przydziału

pracowników do zadań

Funkcja celu (suma iloczynów)

Funkcja celu (suma iloczynów)

33

28

Piotr Sawicki / Metody rozwi

ązywania problemów decyzyjnych

Metoda przydzia

łu

Analiza przypadku / W1

Definiowanie
parametrów modelu
w Solverze

15

33

29

Piotr Sawicki / Metody rozwi

ązywania problemów decyzyjnych

Metoda przydzia

łu

Analiza przypadku / W1

Rozwiązanie problemu w wariancie 1 Æ dobowy koszt realizacji zadań
(1-13) wynosi 307 jednostek

F

0:00 4:00 8:00 12:00 15:00

19:00 22:00 2:00

M

C

D

K

A

H

H

G

G

L

J

E

I

B

B

33

30

Piotr Sawicki / Metody rozwi

ązywania problemów decyzyjnych

Metoda przydzia

łu

Analiza przypadku / W2

Tworzenie arkuszy
roboczego w MS
Excel dla Wariantu 2

14-te (dodatkowe) zadanie

14-te (dodatkowe) zadanie

14-ty (dodatkowy) pracownik

14-ty (dodatkowy) pracownik

16

33

31

Piotr Sawicki / Metody rozwi

ązywania problemów decyzyjnych

Metoda przydzia

łu

Analiza przypadku / W2

Rozwiązanie problemu w wariancie 2 Æ dobowy koszt realizacji zadań
(1-14) wynosi 329 jednostek

•

wykonanie zadań (1-13)
329 – 20 = 309

C

0:00 4:00 8:00 12:00 15:00

19:00 22:00 2:00

M

N

D

K

A

H

H

G

G

L

J

E

I

B

B

N

Nowy pracownik

F

33

32

Piotr Sawicki / Metody rozwi

ązywania problemów decyzyjnych

Podsumowanie

Podstawowe pojęcia

•

matematyczne sformułowanie
problemu przydziału

•

zmienna binarna i jej interpretacja

•

tablica przydziału

•

istota klasycznej metody przydziału

•

algorytm metody przydziału

•

metoda przydziału a metoda
transportowa

17

33

33

Piotr Sawicki / Metody rozwi

ązywania problemów decyzyjnych

Podsumowanie

Zalety zastosowania metody
przydziału

•

proste sformułowanie matematyczne

•

jeden pracownik do jednego zadania
choć możliwe jest zastosowanie zadań
przewidzianych do realizacji
równocześnie przez dwie osoby

•

metoda rozwiązywalna za pomocą
klasycznego narzędzia MS Excel
(max 200 zmiennych decyzyjnych)

Metody rozwiązywania
problemów decyzyjnych

Metody rozwiązywania
problemów decyzyjnych

Piotr Sawicki

Piotr Sawicki

Wydział Maszyn Roboczych i Transportu
pok. 719, tel. [phone]
E-mail: [e-mail]
URL: http://www.put.poznan.pl/~piotrs

Wydział Maszyn Roboczych i Transportu
pok. 719, tel. [phone]
E-mail: [e-mail]
URL: http://www.put.poznan.pl/~piotrs

Harmonogramowanie pracy

Zastosowanie metody przydziału

Harmonogramowanie pracy

Zastosowanie metody przydziału