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. 665 22 30, 665 21 29 
E-mail:  piotr.sawicki@put.poznan.pl
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. 665 22 30, 665 21 29 
E-mail:  piotr.sawicki@put.poznan.pl
URL:  http://www.put.poznan.pl/~piotrs

Wydział Maszyn Roboczych i Transportu
pok. 719, tel. 665 22 30, 665 21 29 
E-mail:  piotr.sawicki@put.poznan.pl
URL:  http://www.put.poznan.pl/~piotrs

Harmonogramowanie pracy

Zastosowanie metody przydziału

Harmonogramowanie pracy

Zastosowanie metody przydziału