1

Zarządzanie transportem

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

Metoda przydziału

Piotr Sawicki / Zarządzanie transportem

2

Plan prezentacji



Istota problemu przydziału pracowników do zadań

•

istota problemu

•

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 rzeczywistego problemu przydziału

2

Piotr Sawicki / Zarządzanie transportem

3

Wprowadzenie

Istota problemu przydziału



Rozważmy problem przydziału pracowników do obsługi poszczególnych 
regionów

Przypadek 1

Przypadek 1

Przypadek 1

Przypadek 2

Przypadek 

Przypadek 

2

2

Piotr Sawicki / Zarządzanie transportem

4

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

3

Piotr Sawicki / Zarządzanie transportem

5

Wprowadzenie

Istota problemu przydziału



Z uwagi na wiele możliwości przydziału większość przedsiębiorstw

•

porzuca próby racjonalnego przydziału pracowników

•

decyduje się na „zgadywanie” najlepszego przydziału



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

•

efektywnością pracy

•

umiejętnościami

•

zdolnościami

•

doświadczeniem

•

….



W tej sytuacji traktując pracowników jako niezróżnocowane zasoby 

przedsiębiorstwo traci szansę znaczącego podniesienia produktywności



Menadżer (pracodawca) chcący dobrać najlepszych ludzi do najlepszej 

realizacji zdefiniowanych zadań musi

•

przewidzieć zapotrzebowanie na pracę

•

poszukiwać odpowiednich ludzi

•

dokonywać efektywnej alokacji pracowników

Piotr Sawicki / Zarządzanie transportem

6

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

4

Piotr Sawicki / Zarządzanie transportem

7

Metoda przydziału

Istota problemu przydziału



Podział zadań ze względu na liczbę jednocześnie wykonujących 
pracowników (osób)

…

¯

kierowanie pociągiem pasażerskim IC

…

…

…

…

…

…

…

¯

gra w piłkę nożną

…

…

…

…

…

¯

¯

¯

¯

rozładunek wagonu

…

…

…

…

…

¯

kierowanie pociągiem towarowym

¯

kierowanie tramwajem

11

3

2

1

Ludzie

Zadania

Piotr Sawicki / Zarządzanie transportem

8

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

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

– x

ij

= 1 jeżeli i-ty pracownik 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

5

Piotr Sawicki / Zarządzanie transportem

9

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

Piotr Sawicki / Zarządzanie transportem

10

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

6

Piotr Sawicki / Zarządzanie transportem

11

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

Piotr Sawicki / Zarządzanie transportem

12

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Ę

7

Piotr Sawicki / Zarządzanie transportem

13

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

Piotr Sawicki / Zarządzanie transportem

14

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

8

Piotr Sawicki / Zarządzanie transportem

15

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

Piotr Sawicki / Zarządzanie transportem

16

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

najszybszy czas realizacji zadania 1

najszybszy czas realizacji zadania 1

najszybszy czas realizacji zadania 2

najszybszy czas realizacji zadania 2

najszybszy czas realizacji zadania 3

najszybszy czas realizacji zadania 3

najszybszy czas realizacji zadania 4

najszybszy czas realizacji zadania 4

9

Piotr Sawicki / Zarządzanie transportem

17

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

Piotr Sawicki / Zarządzanie transportem

18

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

10

Piotr Sawicki / Zarządzanie transportem

19

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

Piotr Sawicki / Zarządzanie transportem

20

Metoda przydziału

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



KROK 5: najmniejszą wartość w całej tablicy

•

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

11

Piotr Sawicki / Zarządzanie transportem

21

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

Piotr Sawicki / Zarządzanie transportem

22

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

12

Piotr Sawicki / Zarządzanie transportem

23

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

Piotr Sawicki / Zarządzanie transportem

24

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)

13

Piotr Sawicki / Zarządzanie transportem

25

Metoda przydziału

Analiza przypadku



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

•

przeprowadź analizę problemu

•

sformułuj problem

•

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 motorniczych do 13 zadań
– wariant 2: przydział 14 motorniczych do 14 zadań

•

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

Przykład

Przykład

Piotr Sawicki / Zarządzanie transportem

26

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)

14

Piotr Sawicki / Zarządzanie transportem

27

Metoda przydziału

Analiza przypadku / W1



Definiowanie 
parametrów modelu 
w Solverze

Piotr Sawicki / Zarządzanie transportem

28

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

15

Piotr Sawicki / Zarządzanie transportem

29

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

Piotr Sawicki / Zarządzanie transportem

30

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

16

Piotr Sawicki / Zarządzanie transportem

31

Podsumowanie



Podstawowe pojęcia

•

matematyczne sformułowanie 
problemu przydziału

•

zmienna binarna i jej interpretacja

•

tablica przydziału

•

istota metody przydziału

•

algorytm metody przydziału