Transportni Problemi Logistika

Sadržaj 1. Uvod............................................................................................................1 2. Transportni problem....................................................................................2 2.1. Otvoreni tansportni problemi...............................................................4 2.2. Metode za rešavajnje transportnog problema......................................6 2.3. „Lanac” za dobijanje optimalnog rešenja transportnog problema.......6 3. Zadatak broj 4..............................................................................................7 4. Rešenje zadatka broj 4.................................................................................8 5. Zaključak.....................................................................................................11 6. Literatura.....................................................................................................12

Logistika u Saobraćaju

1. Uvod

Logistika u saobraćaju predstavlj upravljanje tokovima materijala, informacija, novca i ideja putem usklaćivanja procesa u lancima snadbevanja i putem strategiskog dodavanja vrijednosti u pogledu mjesta vremena i pakovanja. Logistička funkcija obuhvata upravljanje skupom sredstava koji se koriste za transport i transformaciju proizvoda tamo gdje je i onda kada je to potrebno sa minimumom ukupnih troškova. Logistika je dio operacioni istraživanja i obuhvata studiranje svih problema savladavnja vremena i prostora u procesima proizvodnje, transporta i distribucije proizvoda i pratećih usluga U okviru logistike u saobraćaju rešavaju se zadatci iz transportnih problema. Svrha rešavanja transportnog problema je minimizacija troškova prevoza na relaci između otpremne stanice i prijemne stanice uz uslov da se zadovolje potrebe prijemne stanice i u potpunosti iskoriste ponude otpremne. U ovom seminarskom radu biće prikazan način rešavanja transportnog problema u opštem obliku kao i jedan primer transportnog problema sa svim pravilima za uspešnno rešavanje ove vrste zadatak.

2

Logistika u Saobraćaju

2.Transportni problem

Transportni problem je dio problema linearnog programiranja koji rješava problem prijevoza istovrsnog tereta iz više otpremnih stanica u više prijemnih stanica, odnosno iz m otpremnih stanica u n prijemnih stanica. Otpremne stanice imaju fiksnu ponudu ai , ( i = 1,2,..., m ), dok prijemne stanice imaju fiksnu potražnju b j , ( j = 1,2,..., n ). Transportni problem ima tablični izgled sa m redova koji predstavljaju otpremne stanice i sa n kolona koji predstavljaju prijemne stanice.

j i O1

P1

P2

C11 X1 1

...

Pn

.....

C1n X1 a1 n a2 . . . Cmn Xmn am

...

Bn

O2 . . . Om bj

Cm1 Xm 1 b1 b2

ai

Tabela 1. Opšta tabela transportnog problema Svrha rješavanja transportnog problema je minimalizacija troškova prijevoza na relacijama između otpremnih stanica i prijemnih stanica uz uslov da se zadovolje potrebe prijemnih stanica i u potpunosti iskoriste ponude otpremnih stanica. Matematička formula funkcije cilja transportnog problema :

3

Logistika u Saobraćaju n

m

F = ∑∑ Cij ⋅ X ij → min j =1 i =1

Oznaka Cij trošak prijevoza po jedinici tereta na relaciji i → j , a X ij je oznaka količine tereta od određene otpremne stanice, ai , do određene prijemne stanice, b j .

Opšti primjer transportnog problema moguće je prikazati pomoću mreže koja sadrži m otpremnih stanica, n prijemnih stanica te m ⋅ n veza između pojedinih otpremnih i prijemnih stanica Otpremne stanice

Prijemne stanice

C11,x11

a1

b1

a2 . . .

b2 . . .

. . .

am Slika 1. Mreža otpremnih i pijemnih stanica.

. . . bn

Jedno od ograničenja transportnog problema je suma kapaciteta otpremne stanice jednaka sumi kapaciteta prijemne stanice. m

n

i =1

j =1

∑ ai = ∑ b j Takav se oblik transportnog problema, u kojem su sume kapaciteta otpremne i prijemne stanice jednake, naziva zatvoreni transportni problem. No, kako je poznato, u praksi gotovo nikad nemamo primjer zatvorenog transportnog problema, drugim riječima rijetko se može susresti takav problem kojem bi suma kapaciteta otpreme stanice bila jednaka sumi kapaciteta prijemne stanice. Transportni problem kod kojeg kapaciteti otpreme stanice i prijemne stanice nisu jednaki naziva se otvoreni transportni problem.

4

Logistika u Saobraćaju

2.1. Otvoreni tansportni problemi Otvoreni transportni problem je transportni problem kod kojeg suma kapaciteta otpreme stanice nije jednaka sumi kapaciteta prijemne stanice. m

n

i =1

j =1

∑ ai ≠ ∑ b j Višak koji se javlja moguć je na strani otpremene stanice ili na strani prijemne stanice te se prema tome može reći da postoje dvije vrste otvorenog transportnog problema, a to su: otvoreni transportni problem sa viškom u ponudi, i otvoreni transportni problem sa viškom u potražnji. Kod otvorenog transportnog problema sa viškom u ponudi višak se javlja na strani otpremene stanice, odnosno suma kapaciteta otpremene stanice veća je od sume potražnje prijemne stanice. m

n

i =1

j =1

∑ ai > ∑ b j Kako bi bilo moguće riješiti ovaj tip otvorenog transportnog problema potrebno je otvoreni transportni problem pretvoriti u zatvoreni transportni problem. Potrebno je dodati „fiktivnu“ prijemnu stanicu (Pf) čiji je kapacitet (bf) onoliko koliko je veća ponuda od potražnje. m

n

i =1

j =1

b f = ∑ ai − ∑ b j Jedinični troškovi prijevoza su nula. Tada se zatvoreni transportni problem može ovako tablično prikazati:

O1

P1 P2 Cij xij

...

Pn

O2

Pf 0

ai a1

0

a2

. . . 0

Om

am

Bj b1 b2 ... bn bf Tabela 2. Tabela otvorenog transportnog problema kada je kapcitet otpremne stanice veći od prijemne stanice.

5

Logistika u Saobraćaju Otvoreni transportni problem sa viškom u potražnji je problem kod kojeg je suma otpremne stanice manja od sume prijemne stanice, što znači da je ponuda manja od potražnje. m

n

i =1

j =1

∑ ai < ∑ b j Jednako kao i u prethodnom slučaju, kod otvorenog transportnog problema sa viškom u ponudi, i otvoreni transportni problem sa viškom u potražni potrebno je pretvoriti u zatvoreni transportni problem, a to se postiže dodavanjem „fiktivne“ otpremne stanice (Of) čiji kapacitet (af) je onoliko kolika je razlika između ponude i potražnje, a jedinični troškovi prijevoza jednaki su nuli.

n

m

j =1

i =1

a f = ∑ b j − ∑ ai

Tablični prikaz transportnog problema ovog tipa izgleda ovako:

O1

P1 P2 Cij xij

...

Pn

ai a1

O2

a2

. . . Om Of Bj

am 0

0

b1

b2

0 ...

af

bn

Tabela 3.Ttabela otvorenog transpoirtnog problema gde je kapacitet prijemne stanice veći od otpremne stanice

6

Logistika u Saobraćaju

2.2. Metode za rešavajnje transportnog problema Postoji velik broj razrađenih metoda koje se primjenjuju za rješavanje transportnog problema. Metode koje se koriste za dobivanje početnog rasporeda tereta su sljedeće: 1. Metoda sjeverozapadnog ugla. 2. Metoda minimalnih troškova i 3. Vogelova aproksimativna metoda, A metode za dobivanje optimalnog rješenja transportnog problema su: 1. metoda relativnih troškova i 2. MODI metoda.

2.3. „Lanac” za dobijanje optimalnog rešenja transportnog problema Sve dok na poljima u tabeli postoji negativni koficijent ne baznih polja nismo postigli optimalno rešenje. Najveći negativni koficijent ne baznoga polja uzimamo za polaznu tačku lanca sa kojim vršimo preraspodelu otpremni kapaciteta u tabeli, da bi došli do optimalnoga rešenja. Lanac počinje i završava se u datom polju. Sa datog polja u pravoj lini (gore-dole) ili (lijevo-desno) “skače” se na bazna polja sve do povratka u početno polje. Početno polje nosi predznak plus „+” dok susedno nosi predznak minus „-˝ i tako se predznaci menju, do povratka u početnio polje. Zatim se bira minimum od susednih polja ili minimumu svih minimuma, koji se oduzimaju od polja ili dodaju u zavisnoisti od predznaka polja. Na taj način dobivamo novu preraspoldelu u tabeli na osnovu koje tražimo optimalno rešenje.

Slika 2 i 3. Mogući izgledi lanca

7

Logistika u Saobraćaju

3. Zadatak broj 4.

Transportno preduzeće obavlja prevoz šećera iz četiri skladišta ( A1 , A2 , A3 , A4 ), iz koji snadbeva četiri veleprodaje ( B1 , B2 , B3 , B4 ). Kapaciteti skladišta su: A1 = 13t , A2 = 36t , A3 = 23t , A3 = 11t , dok potržnja veleprodajnih centara iznosi: B1 = 13t , B2 = 16t , B3 = 15t , B4 = 12t. Troškovi prevoza po jednoj toni dati su n.j. u sledećoj tabeli:

B1 A1 A2 A3 A4

B2 2 3 9 10

B3 8 5 7 2

4 1 8 6

B4 9 11 4 12

Tabela 4. Troškovi prevoza po jednoj toni

Naći optimaln plan transporta šećera iz skladišta A1 , A2 , A3 , A4 u veleprodaje objekte B1 , B2 , B3 , B4 za minimalne ukupne troškove prevoza.

8

Logistika u Saobraćaju

4. Rešenje zadatka broj 4. Na početku izrade transportnog zadatka potrebno je utvrditi da li se radi o zatvorenom transportnom zadatku ili otvorenom i koga je on tipa.

∑A ∑A

i

= A1 + A2 + A3 + A4

i

= 13 + 36 + 23 + 11 = 83

∑B ∑B

j

= B1 + B2 + B3 + B4

j

= 13 + 16 + 15 + 12 = 56

∑A > ∑B i

j

U ovom zadatku reč je otvorenom tarnsportnom problemu, gde se javlja višak na strani otpremne stanice. Zbog toga moramo uvesti fiktivnu prijemnu stanicu, gde su troškovi prevoza po jednoj toni jednaki nuli.

∑ A −∑B i

j

= 83 − 56 = 27

Kapacitet fiktivne prijemne stanice je B f = 27.

B1 PS OS A1 A2 A3 A4

13 36 23

11

B2

B3

B4

Bf

13

16

15

12

27

2 3 9 10

8 5 7 2

4 1 8 6

9 11 4 12

0 0 0

Tabel 5. Kapaciteti otpremnih i prijemnih stanica

Dati trnasportni problem rešavamo metodom dvostrukog precrtavanja. Formiramo početnu tabelu. Tražimo minimalne cijene po kolonam i vrstama i stavljmo zvezdicu za minimalnu cenu u koloni i vrsti. Polje koje je minimum po vrst i koloni imamo dve zvjezdice.

9

0

Logistika u Saobraćaju

PS B1 OS A1 A2 A3 A4

13 36 23

11

13 2** 3 9 10

B2

B3

16 8 5 7 2**

15 4 1** 8 6

B4 12 9 11 4** 12

Bf 27 0 0 0 0

Tabe 6. Polja sa minimalnim cjenama

Nakon što smo označili polja sa minimalnim cenama, vršimo njihovo popunjavanje. Pri tome moramo voditi računa da se ispuni uslov za broj baznih polja. Uslov je dat formulom

m + n − 1 = broj baznih polja.

Ako ovaj uslov nije ispunjen sa minimalnim cenama dodajemo određen broj fiktivnih nula u polja tako da ona postaju bazična.

PS B1 OS A1

B2 13

B3 16

13

2**

36

3

A3

23

9

7

A4

11

10

2**

B4 15

Bf

12

27

8

4

9

0

5

1**

11

0

8

4**

0

6

12

13 A2

0

5

15

16 12

11 0

11 Taba 7. Raspored tereta po baznim poljima

Broj baznih polja: m+n-1=4+5-1=8 Dodajemo jednu fiktivnu nulu u polje k 21 , da bi ispunili uslov o broju baznih polja. Nakon raspodele tereta po bazinim poljima tražimo optimalno rešenje metodom koficijenata.

α i + β j = Cij ; Za polje α 1 usvajamo da je nula, odnosno α 1 = 0 . 10

Logistika u Saobraćaju

Zatim se za svako ne bazno polje računa koficijent po sledećoj formuli: K ij = Cij − (α i − β j ) ; Dok ne dobijemo sve pozitivne vrednosti koficijenta K ij nije pronađeno optimalno rešenje. Kada imamo sve pozitivne vrednosti koficijenta u ne baznim poljima računamo ukupnu cenu prevoza F.

PS OS A1

13

B1

B2

B3

13 2**

16 8

15 4

B4 12 9

Bf 27 0

αi

13 A2

36

3

0 5

0 A3

23

9

1** 5

11

0

15

7

8

4**

A4

10

2**

6

1

11

1

0 12

11

16 0

12

-2

11

βj

2

4

0

3

-1

Tabela 8. Računanje koficijenata u ne bazičnim poljima. Vrijednost koficjenata u ne baznim poljima.

K12 = 8 − ( 0 + 4) = 4;

K 32 = 7 − (1 + 4 ) = 2;

K14 = 9 − ( 0 + 3) = 6;

K 41 = 10 − ( − 2 + 2) = 10;

K13 = 4 − ( 0 + 0) = 4; K1 f = 0 − ( 0 − 1) = 1;

K 24 = 11 − (1 + 3) = 7; K 31 = 9 − (1 + 2) = 6;

K 33 = 8 − (1 + 0) = 7;

K 43 = 6 − ( 0 − 2 ) = 8;

K 44 = 12 − ( − 2 + 3) = 11; K 4 f = 0 − (−2 − 1) = 3;

K ij ≥ ∀ij Vidimo da su svi korficijenti u ne baznim poljima pozitivni, što znači da je dobiveno optimalno rešenje. Iz čega slede troškovi prevoza:

F = 2 ⋅13 + 5 ⋅ 5 + 1 ⋅15 + 4 ⋅12 + 2 ⋅11 F = 136 N.J. – Miminalna cijena prevoza.

11

Logistika u Saobraćaju

5. Zaključak Na osnovu svega prikazanog u ovom seminarskom radu možemo vidjeti šta je to transportni problem i šta on prestavlja. Takođe smo vidjeli da postoji više vrsta transportnog problema kao i metoda za njegovo rešavanje. Cilj rešavanja transportnog problema je dobijanje optimalnog rešenja koji je u našem slučaju minimizacija troškova prevoza. Na urđenom zadatku primenili smo jednu od jednostavnih metoda za rešavanje ove vrste zadataka (dvostruko precrtavanje) kao što smo i prikazali neke od uslova potrebni za uspešno rešavanje transportnih zadataka.

12

Logistika u Saobraćaju

6. Literatura

1) dr Marko Vasiljević: Predavanja iz logistika u saobraćaju, 2009 Saobraćajni Fakultet Doboj. 2) mr Zoran Rsitikić: Vježbe iz logistike u saobraćaju, 2009 Saobraćajni Fakultet Doboj. 3) dr Ranko Božičković: Predavanja iz operacionih istraživanja, 2009 Saobraćajni Fakultet Doboj. 4) Čupić M., Radivojević G., Revanović B., Specijalna poglavlja iz teorije odlučivanja: Kvantitativna analiza , 2009 Novi Sad.

13