16 - Transportna Metoda

Menadžment i tehnologija građevinskih radova

Transportna metoda

15.08.09

Predavanja iz menadžmenta – 16 – Transportna metoda

1 od 38

Sadržaj • Postavka problema i matematička formulacija • Izbor početnog rešenja • Proračun karakteristika polja – metoda lanaca – metoda potencijala

• • • •

Preraspodela angažovanja Određivanje optimalnog rešenja Otvoren transportni problem Problem ograničene propusne moći

15.08.09

Predavanja iz menadžmenta – 16 – Transportna metoda

2 od 38

Transportni problem • Problem linearnog programiranja • Realan problem vezan za organizaciju transporta • Može biti rešavan SIMPLEX metodom, ali je to neefikasno, pogotovo bez računara

15.08.09

Predavanja iz menadžmenta – 16 – Transportna metoda

3 od 38

Postavka problema • Postoji m izvorišta • Svako izvorište ima svoj kapacitet, odnosno obim koji može da isporuči • Postoji n potrošača • Svaki potrošač ima svoje potrebe, odnosno obim koji može da potroši • Poznati su troškovi transporta između svakog para izvorištepotrošač • Naći šemu transporta koja će zahtevati najmanje troškove 15.08.09

Predavanja iz menadžmenta – 16 – Transportna metoda

4 od 38

Matematička formulacija • Naći minimum funkcije cilja: m

n

z = ∑∑ cij xij

min

i =1 j =1

• Pod sledećim ograničenjima: m

n

∑ a = ∑b i =1

n

∑x j =1

i

j =1

j

=A

m

ij

=ai , ∑ xij =b j i =1

ai , bi , cij , xij ≥ 0 15.08.09

Predavanja iz menadžmenta – 16 – Transportna metoda

5 od 38

Pretpostavke • Iz formulacije problema se vidi da su uvedene sledeće pretpostavke – ukupni kapacitet svih izvorišta identičan ukupnim potrebama svih potrošača – kapacitet i potrebe su uvek pozitivne, odnosno izvorište je samo izvorište, a potrošač je samo potrošač – cene transporta su pozitivne, odnosno transport je uvek trošak – nepoznate su uvek pozitivne, odnosno transport se uvek odvija od izvorišta do potrošača

• Osim prve, sve pretpostavke odgovaraju realnim uslovima transporta 15.08.09

Predavanja iz menadžmenta – 16 – Transportna metoda

6 od 38

Matematički okvir • Matematičkim metodama se može pokazati: – svaki transportni problem ima optimalno rešenje – rešenje ne sadrži više od m+n-1 prevoza koji su linearno nezavisni – ako su količine ai i bj celi brojevi i rešenje će sadržati samo cele brojeve

15.08.09

Predavanja iz menadžmenta – 16 – Transportna metoda

7 od 38

Rešavanje problema • Formira se tabela u koju se upisuju kapaciteti izvorišta, potrebe potrošača i cene transporta b1 a1 a2 a3 a4

c 11

b2 c 12

x 11 c 21

c 13 x 12

c 22 x 21

c 31

x 24

x 33

x 25 c 35

x 34 c 44

x 43

x 15 c 25

c 34

c 43 x 42

x 14

x 23

x 32

b5 c 15

c 24

c 33

c 42 x 41

x 13

x 22

x 31

b4 c 14

c 23

c 32

c 41

b3

x 35 c 45

x 44

x 45

• U svakoj koloni i vrsti, zbir xijova mora da bude ai, odnosno bj 15.08.09

Predavanja iz menadžmenta – 16 – Transportna metoda

8 od 38

Primer • Naša razmatranja ćemo obrazlagati na konkretnom primeru 80 80 100 100

60 15

50 20

90 18

90 16

70 18

30

20

19

18

15

25

15

20

30

14

22

25

28

25

20

• Kako je m+n-1=8 potrebno je da bude angažovano 8 polja

15.08.09

Predavanja iz menadžmenta – 16 – Transportna metoda

9 od 38

Početno rešenje • Slično SIMPLEX-u, moramo da počemo od nekog prihvatljivog rešenja • U principu, možemo da pođemo od bilo kog prihvatljivog rešenja, ali od izbora početnog rešenja zavisi broj koraka potrebnih za dostizanje optimalnog rešenja • Nadalje, polja u tabeli gde je xij ≠0 nazivaćemo “angažovana”, a ostala polja biće “neangažovana” 15.08.09

Predavanja iz menadžmenta – 16 – Transportna metoda

10 od 38

Izbor početnog rešenja • Metoda najmanje cene • Metoda najmanje cene u redu ili koloni • Fogelova aproksimacija

15.08.09

Predavanja iz menadžmenta – 16 – Transportna metoda

11 od 38

Metoda najmanje cene • Biramo polje u tabeli u kome se nalazi najmanja cena • To polje opterećujemo sa najvećom mogućom vrednošću, odnosno n m   xij′ = min ai − ∑ xij , b j − ∑ xij  j =1 i =1  

• Sada isključujemo to polje, i ponovo tražimo najmanju cenu • Korake ponavljamo dok ne dobijemo n

∑x j =1

15.08.09

ij

m

=ai , ∑ xij =b j i =1

Predavanja iz menadžmenta – 16 – Transportna metoda

12 od 38

Primer najmanje cene • Redosled opterećivanja polja je označen zaokruženim brojevima 60 80 80 100 100

15 2 30 25 22

50 20

90 18

60 20 15 3 25 7

19 6 20

10

90 16 4 18 5 30

18 20 15 70

30 20

28 8

70

25

14 1 20

70

80

• Funkcija cilja je z=6840 • Angažovano je 8 polja, što odgovara konkretnom problemu

15.08.09

Predavanja iz menadžmenta – 16 – Transportna metoda

13 od 38

Metoda najmanje cene u redu ili koloni • Biramo polje u tabeli u kome se nalazi najmanja cena • To polje opterećujemo sa najvećom mogućom vrednošću, odnosno n m   xij′ = min ai − ∑ xij , b j − ∑ xij  j =1 i =1  

• Sada isključujemo to polje, i ponovo tražimo najmanju cenu u istoj vrsti, odnosno koloni • Biramo vrstu ili kolonu, na kojoj još možemo da opterećujemo polja • Korake ponavljamo dok ne dobijemo n

∑x j =1

15.08.09

ij

m

=ai , ∑ xij =b j i =1

Predavanja iz menadžmenta – 16 – Transportna metoda

14 od 38

Primer najmanje cene u redu ili koloni • Redosled opterećivanja polja je označen zaokruženim brojevima 60 80 80 100 100

50

15 4 30

60

8

ε

25 22

20 3 20

90

90

18

16

18

19

18

15

20 5

15 2 25

70

20

80

30

14 1 20

30 28 7

90

25 6

70

10

• Funkcija cilja je z=6940 • Angažovano je 7 polja, što manje od potrebnog. Zato dodajemo 8. polje koje je opterećeno sa ε, odnosno dovoljno malom vrednošću 15.08.09

Predavanja iz menadžmenta – 16 – Transportna metoda

15 od 38

Fogelova aproksimacija • Redosled opterećivanja polja biramo prema “kaznenim poenima” • Kazneni poeni za vrstu ili kolonu se dobijaju kao razlika dve najmanje cene u toj vrsti ili koloni • Izaberemo kolonu ili vrstu koja ima najviše poena i u njoj opteretimo polje sa najmanjom cenom n m   xij′ = min ai − ∑ xij , b j − ∑ xij  j =1 i =1   15.08.09

Predavanja iz menadžmenta – 16 – Transportna metoda

16 od 38

Fogelova aproksimacija • Vrstu ili kolonu i polje koje smo opteretili isključujemo i ponovo sračunavamo kaznene poene • Korake ponavljamo dok ne dobijemo n

∑x j =1

m

ij

=ai , ∑ xij =b j i =1

• Obično se Fogelovom aproksimacijom dobija najbolje početno rešenje

15.08.09

Predavanja iz menadžmenta – 16 – Transportna metoda

17 od 38

Primer Fogelove aproksimacije • Redosled opterećivanja polja je označen zaokruženim brojevima 60 80 80 100 100

15 1 30

20

90 18

20

19

15 2 25

22 7 -

90 16 5 18 6 30

60

25

I II III IV V VI VII

50

20

18 20 60

50 28 8 5 5 -

90 1 1 1 1 1 1 1

70

25 7

15 4 14 3 20

20 50

10 2 2 2 2 2 7 5

I

II

III

IV

V

VI

VII

1

2

2

2

2

-

-

3

3

3

3

1

1

-

1

1

6

-

-

-

-

2

2

2

2

2

2

2

1 1 1 3 -

• Funkcija cilja je z=6820 • Angažovano je 8 polja, što odgovara konkretnom problemu 15.08.09

Predavanja iz menadžmenta – 16 – Transportna metoda

18 od 38

Optimalno rešenje • Optimalnost rešenja utvrđujemo kroz određivanje “karakteristika” neangažovanih polja • Ako je karakteristika: – veća od nule to je polje čije bi angažovanje povećalo funkciju cilja – manja od nule to je polje čije bi angažovanje smanjilo funkciju cilja – jednaka nuli to je polje čije angažovanje ne bi promenilo funkciju cilja 15.08.09

Predavanja iz menadžmenta – 16 – Transportna metoda

19 od 38

Proračun karakteristika • Metoda lanaca – očiglednija – neefikasna kada treba da se utvrde karakteristike svih neangažovanih polja – obično se koristi za preraspodelu angažovanih polja

• Metoda potencijala – manje očigledna – efikasna za utvrđivanje karakteristika većeg broja polja – obično se koristi za određivanje sledeće iteracije

15.08.09

Predavanja iz menadžmenta – 16 – Transportna metoda

20 od 38

Metoda lanaca • Lanac se formira na sledeći način: – polazimo od polja koje je neangažovano – krećemo se po vrsti ili koloni do prvog angažovanog polja – ako smo se kretali po vrsti, sada se krećemo po koloni, ili obrnuto – ponovo nalazimo angažovano polje – ponavljamo korake dok ne stignemo do početnog polja, čime zatvaramo lanac.

15.08.09

Predavanja iz menadžmenta – 16 – Transportna metoda

21 od 38

Karakteristika • Sračunavanje – posmatraju se cene Cij duž lanca – cena u početnom, neangažovanom polju dobija + (pozitivan) znak – sledeća cena u lancu dobija – (negativan) znak – ostale cene naizmenično dobijaju + i – znak – saberu se cene sa pridruženim znacima – takav zbir predstavlja karakteristiku prvog, neopterećenog, polja

15.08.09

Predavanja iz menadžmenta – 16 – Transportna metoda

22 od 38

Primer metode lanaca • Lanac za polje K31 60 80 80 100 100

15 − 30 25 + 22

50 20

90 18

16 + 18 − 30

60 20

19

15

90

20

18 20 60

50 25

28

25 90

70

15 + 14 − 20

20 50

10

• Karakteristika polja • K31=25-14+15-18+16-15=+9 • Zaključak je da ovo polje ne treba angažovati

15.08.09

Predavanja iz menadžmenta – 16 – Transportna metoda

23 od 38

Primer metode lanaca • Lanac za polje K23 80 80 100 100

60 15 60 30 25

50 20

90 18

20

19 + 20

15

90 16 20 18 − 60 30

70 18 15 20 14

50 22

25

50 28 −

90

25 +

20 10

• Karakteristika polja • K23=19-18+25-28=-2 • Zaključak je da ovo polje treba angažovati

15.08.09

Predavanja iz menadžmenta – 16 – Transportna metoda

24 od 38

Metoda potencijala • Može se pokazati da za angažovana polja važi: cij = U i + V j

• Za neangažovan polja važi: K ij = cij − (U i + V j )

• Veličine Ui i Vj zvaćemo “potencijali”

15.08.09

Predavanja iz menadžmenta – 16 – Transportna metoda

25 od 38

Praktična realizacija • Za neku vrstu ili kolonu usvojimo da je ona na “nultom” potencijalu • Koristeći poznata angažovana polja sračunamo potencijale ostalih vrsta i kolona • Koristeći sračunate potencijale sračunamo karakteristike neangažovanih polja

15.08.09

Predavanja iz menadžmenta – 16 – Transportna metoda

26 od 38

Primer proračuna potencijala • Ovako se dobijaju potencijali svih vrsta i kolona 60

18

90 16

60 30

70 18

20

19

18

15 60

25

15

20

30

20 14

50

Vj

15.08.09

25

15

14

50 28

25

20

90 19

10 16

13 (4) iz U2

22

Ui 0 (1) Početna vrednost

20

(2) iz U1

100

90

(9) iz U4

100

20

(8) iz U3

80

15

(7) iz U1

80

50

Predavanja iz menadžmenta – 16 – Transportna metoda

2 (3) iz V4 1 (5) iz V5 9 (6) iz V4

27 od 38

Primer proračuna karakteristika • Na osnovu potencija ovako se dobijaju karakteristike 60 80 80 100 100 Vj

15.08.09

50

15 30

20 60 13

25 22 15

9 -2

90 6

18

90 -1

16

70 18

Ui 5

20 20

4

15 25

19 20

50 2

14

-2 0

28 90 19

18 30

15 60 14

25

20 14 20

10 16

Predavanja iz menadžmenta – 16 – Transportna metoda

50 -2

0 2 1 9

13

28 od 38

Preraspodela • Ako postoji polje sa negativnom karakteristikom, treba izvršiti preraspodelu tako da to polje postane angažovano • Ako imamo više polja sa negativnom karakteristikom, biramo najmanju (najnegativniju) vrednost • Za preraspodelu koristimo metodu lanaca

15.08.09

Predavanja iz menadžmenta – 16 – Transportna metoda

29 od 38

Nove vrednosti • Preraspodela se vrši za najmanju vrednost angažovanja polja od onih čije cene u metodu lanaca imaju negativnu vrednost • Vrednost koja se preraspodeljuje se oduzima od polja u kojima cena ima negativni predznak a dodaje poljima u kojima cena ima pozitivan predznak

15.08.09

Predavanja iz menadžmenta – 16 – Transportna metoda

30 od 38

Primer preraspodele • Posmatrajmo angažovanje polja K23 80 80 100 100

60 15 60 30 25

50 20

90 18

20

19 + 20

15

90 16 20 18 − 60 30

70 18 15 20 14

50 22

25

50 28 −

90

25 +

20 10

• Polje K24 ima najmanju vrednost angažovanja od cena u 15.08.09

Predavanja iz menadžmenta – 16 – Transportna metoda

31 od 38

Nove vrednosti • Posle preraspodele se dobija sledeća tabela 80 80 100 100

60 15 60 30 25

50 20

90 18

20

19 + 20

15

60

90 16 20 18 0 − 30

70 18 15 20 14

50 22

25

50 28 −

30

25 +

20 70

• Angažovali smo jedno novo polje, a jedno polje je prestalo da bude angažovan

15.08.09

Predavanja iz menadžmenta – 16 – Transportna metoda

32 od 38

Nova iteracija • Može se desiti da prilikom preraspodele broj angažovanih polja postane manji od m+n-1 • U tom slučaju dodatno se angažuje se potreban broj polja, tako što njihova vrednost angažovanja postane ε, odnosno dovoljno mala vrednost • Takva polja se smatraju angažovanim, ali je njihova vrednost angažovanja nula

15.08.09

Predavanja iz menadžmenta – 16 – Transportna metoda

33 od 38

Nova iteracija • Za neangažovana polja u novoj tabeli ponovo se sračunavaju karakteristike • Ukoliko se sve karakteristike veće od nule, našli smo optimalno rešenje • Ukoliko postoje karakteristike jednake nuli a nema negativnih karakteristika, nađeno je optimalno rešenje, ali ono nije jedinstveno • Ukoliko postoje negativne karakteristike, ponavljamo postupak 15.08.09

Predavanja iz menadžmenta – 16 – Transportna metoda

34 od 38

Otvoren transportni problem • Ukoliko je ukupni kapacitet izvorišta veći od ukupnih potreba potrošača, imamo otvoren transportni problem • On se rešava tako što formiramo fiktivnog potrošača čije su potrebe jednake višku kapaciteta • Sve cene transporta za fiktivnog potrošača su jednake nuli

15.08.09

Predavanja iz menadžmenta – 16 – Transportna metoda

35 od 38

Ograničenje propusne moći • Ukoliko između jednog izvorišta i jednog potrošača ne može da se preveze neograničena količina resursa, imamo problem ograničene propusne moći • On se rešava tako što se takav stvarni potrošač zameni sa dva fiktvna. • Prvi fiktivni potrošač ima potrebe koje su jednake mogućoj propusnoj moći • Drugi fiktivni potrošač preuzima ostatak potreba 15.08.09

Predavanja iz menadžmenta – 16 – Transportna metoda

36 od 38

Ograničenje propusne moći • Prvi fiktivni potrošač zadržava sve cene koje je imao stvarni potrošač • Drugi fiktivni potrošač uzima sve cene koje je imao stvarni potrošač, osim cene prema izvorištu sa ograničenom propusnom moći • Ta cena dobija neku veliku vrednost, tako da optimalno rešenje sigurno ne sadrži taj pravac transporta

15.08.09

Predavanja iz menadžmenta – 16 – Transportna metoda

37 od 38

Pregled • Postavka problema i matematička formulacija • Izbor početnog rešenja • Proračun karakteristika polja – metoda lanaca – metoda potencijala

• • • •

Preraspodela angažovanja Određivanje optimalnog rešenja Otvoren transportni problem Problem ograničene propusne moći

15.08.09

Predavanja iz menadžmenta – 16 – Transportna metoda

38 od 38