ZarzÄ…dzanie transportem
Metoda przydziału
Piotr Sawicki
Wydział Maszyn Roboczych i Transportu
pok. 719, tel. [phone]
E-mail: [e-mail]
URL: http://www.put.poznan.pl/~piotrs
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
Piotr Sawicki / ZarzÄ…dzanie transportem 2
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 2
Przypadek 2
Piotr Sawicki / ZarzÄ…dzanie transportem 3
Wprowadzenie
Istota problemu przydziału
Problemy spotykane w praktyce charakteryzują się znacznie większym
stopniem skomplikowania
Liczba Liczba
Liczba Liczba
pracowników permutacji
pracowników permutacji
i regionów
i regionów
1 1
2 2
3 6
4 24
5 120
6 720
7 5.040
8 40.320
9 362.880
10 3.628.800
& &
& &
16 20.922.789.888.000
Piotr Sawicki / ZarzÄ…dzanie transportem 4
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 5
Metoda przydziału
Istota problemu przydziału
Problem przydziału w ogólności polega na delegowaniu
pracowników do poszczególnych prac, w taki sposób, aby
pracowników
koszt realizacji wszystkich prac był minimalny
koszt
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
Piotr Sawicki / ZarzÄ…dzanie transportem 6
Metoda przydziału
Istota problemu przydziału
Podział zadań ze względu na liczbę jednocześnie wykonujących
pracowników (osób)
Ludzie
1 2 3 & 11
Zadania
kierowanie tramwajem &
kierowanie pociÄ…giem towarowym &
kierowanie pociągiem pasażerskim IC &
& & & & & &
rozładunek wagonu &
& & & & & &
gra w piłkę nożną &
Piotr Sawicki / ZarzÄ…dzanie transportem 7
Metoda przydziału
Istota problemu przydziału
Jeżeli tylko jeden pracownik może zostać przydzielony do jednego zadania,
pracownik zadania
wówczas
" z punktu widzenia matematycznego zapisu problemu zmienną decyzyjną będzie
wartość
 xij = 0 jeżeli i-ty pracownik nie jest przedzielony do wykonywania j-tej pracy
 xij = 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 PRZYDZIAA
U
METODA PRZYDZIAA
U
Piotr Sawicki / ZarzÄ…dzanie transportem 8
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
TABLICA PRZYDZIAA
U
TABLICA PRZYDZIAA
U
Magazyny odbiorców Zadania
Dostawcy
Podaż
Pracownicy
1 2 3 4
Efektywność
Efektywność
c11 c12 c13 c14
przydziału 1 1
przydziału
x11 x12 x13 x14
pracownika do
pracownika do
c21 c22 c23 c24
zadania
zadania
2 1
x21 x22 x23 x24
c31 c32 c33 c34
Przydział
Przydział
3 1
pracownika do x31 x32 x33 x34
pracownika do
zadania (0 lub 1) 
zadania (0 lub 1) 
c41 c42 c43 c44
4 1
ZMIENNA BINARNA
ZMIENNA BINARNA
ZMIENNA BINARNA
x41 x42 x43 x44
Popyt
1 1 1 1 4
Każde zadanie może mieć Każdy pracownik
Każde zadanie może mieć Każdy pracownikmoże
może
przedzielone jednego pracownika wykonać jedno zadanie
przedzielone jednego pracownika wykonać jedno zadanie
Piotr Sawicki / ZarzÄ…dzanie transportem 9
Metoda przydziału
Istota problemu przydziału
Interpretacja zmiennej decyzyjnej
" załóżmy, że pomijamy wartości cij oraz np. x23 = 1
" co to w praktyce oznacza zmienna xij?
Magazyny odbiorców Zadania
Dostawcy
Podaż
Pracownicy
1 2 3 4
c11 c12 c13 c14
1 1
x11 x12 x13 x14
c21 c22 c23 c24
2 1
x21 x22 x1 x24
23
c31 c32 c33 c34
3 1
x31 x32 x33 x34
c41 c42 c43 c44
4 1
x41 x42 x43 x44
Popyt 1 1 1 1 4
jeżeli x23 = 1 x21= x22 = x24= 0
jeżeli x23= 1 x21 = x22= x24 = 0
również x13 = x33= x43 = 0
również x13= x33 = x43= 0
Piotr Sawicki / ZarzÄ…dzanie transportem 10
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)
m n
Koszt = xij min
""cij
i =1 j =1
gdzie:
cij  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)
xij  zmienna decyzyjna wskazująca przydział i-tego pracownika do j-tego zadania,
xij = 0 *" 1
Piotr Sawicki / ZarzÄ…dzanie transportem 11
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-
Czas
gicznego urzÄ…dzenia)
KRZYWA UCZENIA SI

" częstotliwości powtarzania
" &
" doświadczenia i praktyki
pracownika
Liczba powtórzeń
Piotr Sawicki / ZarzÄ…dzanie transportem 12
Jednostkowy czas realizacji
Skumulowana liczba zrealizowanych zada
Å„
Metoda przydziału
Model matematyczny problemu
Ograniczenia
Pracownicy Zadania
" i-ty pracownik może być
1 1
przydzielony tylko do jednego
xi1
zadania
2
2
xi2
n
xij
xij = 1; i = 1,2,...., m
"
i j
j =1
xin
n
m
Pracownicy Zadania
" do j-tego zadania może być 1 1
x1j
przydzielony tylko jeden
2
2
x2j
pracownik
m
xij
i j
xij = 1; j = 1,2,...., n
"
xmj
i =1
m
n
Piotr Sawicki / ZarzÄ…dzanie transportem 13
Metoda przydziału
Model matematyczny problemu
Model matematyczny problemu przydziału klasyczny przypadek
" funkcja celu minimalizacja kosztu wykonania wszystkich zadań
m n
Koszt = xij min
""cij
i =1 j =1
" przy ograniczeniach
n
xij = 1; i = 1,2,...., m
"
j =1
m
xij = 1; j = 1,2,...., n
"
i =1
xij " 0 *"1
" przyjęte ograniczenie wymusza kwadratowy wymiar tablicy m=n
 liczba pracowników równa jest liczbie zadań do wykonania
Piotr Sawicki / ZarzÄ…dzanie transportem 14
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
Zadania
Pracownicy Przydział
1 2 3 4
1 c11 c12 c13 c14 1
2 c21 c22 c23 c24 1
3 c31 c32 c33 c34 1
4 c41 c42 c43 c44 1
Przydział 1 1 1 1 4
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
Piotr Sawicki / ZarzÄ…dzanie transportem 15
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.]
Zadania
Pracownicy Przydział
1 2 3 4
1 5 3 1 5 1
2 6 6 2 7 1
3 5 5 3 8 1
4 8 2 4 3 1
Przydział 1 1 1 1 4
najszybszy czas realizacji zadania 4
najszybszy czas realizacji zadania 4
najszybszy czas realizacji zadania 3
najszybszy czas realizacji zadania 3
najszybszy czas realizacji zadania 2
najszybszy czas realizacji zadania 2
najszybszy czas realizacji zadania 1
najszybszy czas realizacji zadania 1
Piotr Sawicki / ZarzÄ…dzanie transportem 16
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
Zadania
Pracownicy Przydział
1 2 3 4
1 5  1 3  1 1  1 5  1 1
2 6  2 6  2 2  2 7  2 1
3 5  3  3  3  3
5 3 8 1
4 8  2 2  2 4  2 3  2 1
Przydział 1 1 1 1 4
Piotr Sawicki / ZarzÄ…dzanie transportem 17
Metoda przydziału
Rozwiązanie problemu przydziału pracowników do zadań
Tablica przydziału po kroku 1
Zadania
Pracownicy Przydział
1 2 3 4
1 4  2  0  0  1
2 0 4 1
2 4  2  0  0  1
4 0 5 1
3 2  2  0  0  1 1
2 0 5
4 6  2 0  0 2  0 1  1 1
Przydział 1 1 1 1 4
KROK 2: od każdego  czasu realizacji w kolumnie odejmij najmniejszą
wartość w tej kolumnie
Piotr Sawicki / ZarzÄ…dzanie transportem 18
Metoda przydziału
Rozwiązanie problemu przydziału pracowników do zadań
Tablica przydziału po kroku 2
Zadania
Pracownicy Przydział
1 2 3 4
1 2 2 0 3 1
2 2 4 0 4 1
3 0 2 0 4 1
4 4 0 2 0 1
Przydział 1 1 1 1 4
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
Piotr Sawicki / ZarzÄ…dzanie transportem 19
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
Zadania
Pracownicy Przydział
1 2 3 4
1 2  2  2
1
2 0 3  2
2 2  2  2
1
4 0 4  2
+2
3 0 2 0 4 1
+2
4 4 0 2 0 1
Przydział 1 1 1 1 4
Piotr Sawicki / ZarzÄ…dzanie transportem 20
Metoda przydziału
Rozwiązanie problemu przydziału pracowników do zadań
Tablica przydziału po kroku 5
Zadania
Pracownicy Przydział
1 2 3 4
1 0 0 0 1 1
2 0 2 0 2 1
3 0 2 2 4 1
4 4 0 4 0 1
Przydział 1 1 1 1 4
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ą
Piotr Sawicki / ZarzÄ…dzanie transportem 21
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
Zadania
Pracownicy Przydział
1 2 3 4
1 5 3 1 5 1
2 6 6 2 7 1
3 5 5 3 8 1
4 8 2 4 3 1
Przydział 1 1 1 1 4
Czas realizacji prac (efektywność realizacji wszystkich zadań wynosi:
5×(1) + 3×(1) + 2×(1) + 3×(1) = 13 godz.
Piotr Sawicki / ZarzÄ…dzanie transportem 22
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 wskaz
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 przejdz
do kroku (5)
(5) znajdz
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 23
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) przejdz
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)
Piotr Sawicki / ZarzÄ…dzanie transportem 24
Metoda przydziału
Analiza przypadku
Dokonaj analizy problemu, zgodnie z załączonym opisem
problemu
" przeprowadz
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 25
Metoda przydziału
Analiza przypadku / W1
Tworzenie arkuszy
roboczego w MS
Excel dla Wariantu 1
Tablica kosztów realizacji
Tablica kosztów realizacji
poszczególnych zadań
poszczególnych zadań
Tablica przydziału
Tablica przydziału
pracowników do zadań
pracowników do zadań
Funkcja celu (suma iloczynów)
Funkcja celu (suma iloczynów)
Piotr Sawicki / ZarzÄ…dzanie transportem 26
Metoda przydziału
Analiza przypadku / W1
Definiowanie
parametrów modelu
w Solverze
Piotr Sawicki / ZarzÄ…dzanie transportem 27
Metoda przydziału
Analiza przypadku / W1
Rozwiązanie problemu w wariancie 1 dobowy koszt realizacji zadań
(1-13) wynosi 307 jednostek
G
H B
A G I
K H E
M D J
F C L B
0:00 4:00 8:00 12:00 15:00 19:00 22:00 2:00
Piotr Sawicki / ZarzÄ…dzanie transportem 28
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 29
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
Nowy pracownik
G B
N
H F
A G I
K H E
M D J
C N L B
0:00 4:00 8:00 12:00 15:00 19:00 22:00 2:00
Piotr Sawicki / ZarzÄ…dzanie transportem 30
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
Piotr Sawicki / ZarzÄ…dzanie transportem 31