Oi106oitransportrasporedjivanje
This document was uploaded by user and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this DMCA report form. Report DMCA
Overview
Download & View Oi106oitransportrasporedjivanje as PDF for free.
More details
- Words: 4,711
- Pages: 56
OPERACIONA ISTRAŽIVANJA
6. LINEARNO PROGRAMIRANJE TRANSPORTNI PROBLEM PROBLEM RASPOREDJIVANJA
šk.god. 2007/2008.
dr Tadej Mateljan
2.5.1. TRANSPORTNI PROBLEM 2.5.1. TRANSPORTNI PROBLEM • Postavka zadatka • Matematički model • Metoda “sjeverozapadnog ugla” (određivanje početnog dopustivog rješenja) • Stepping Stone Method – Metoda “skakanje s kamena na kamen” (nalaženje optimalnog rješenja) 2.5.2. PROBLEM RASPOREĐIVANJA • Postavka zadatka • Matematički model • Mađarska metoda
2.5.1. TRANSPORTNI PROBLEM Izučavanja problema transporta primjenom anali-tičkih metoda potiče iz polovine prošlOg stoljeća. Tim se problemom bavilo više poznatih istraživača, mEđu kojima su značajni rezultati sovjetskog naučnika L. V. Kantroviča iz 1939 i američkog naučnika F. L. Hitchcocka-a iz 1941 godine. Nekako u isto vrijeme, veliki istraživački napori i rezultati su bili vezani za zadatak linearnog programiranja. Pokazalo se da je transportni problem njegov specijalan slučaj i da može biti riješen nekom od metoda za rješavanje zadatka LP. Međutim, pokazalo se, također, da zbog svoje specifične
2.5.1. TRANSPORTNI PROBLEM
Tako je Dantzig je objavio rješenje bazirano na simpleks množiteljima, Vogel je predložio aproksimativnu metodu za nalaženje početnog rješenja Charnes i Cooper su 1953. god. i objavili metodu danas poznatu kao metoda „skakanja s kamena na kamen“ (Stepping Stone Method) Ford i Fulkenson su 1956. godine objavili metodu za rješenje TP
2.5.1. TRANSPORTNI PROBLEM
Naziv ovog problema potiče od toga što su se prvo rješavali problemi transporta – naći minimalne troškove transporta kroz zadanu transportnu mrežu i uz zadana transportna sredstva. Međutim danas se u ove probleme uključuju zadaci optimalnog razmje-štanja mašina, postrojenja, službi, skladišta, servisa, energetskih objekata, prodajnih objekata, ...
2.5.1. TRANSPORTNI PROBLEM Postavka zadatka Pronalaženje optimalnog plana transporta se najčešće svodi na zadatak transporta jedne vrste proizvoda iz određenog broja mjesta skladištenja u određeni broj mjesta potrošnje uz minimalne troškove. Pri tom su poznate količine proizvoda smještene u skladištima količine proizvoda koje potražuju mjesta potrošnje jedinični troškovi transporta iz bilo kojeg
2.5.1. TRANSPORTNI PROBLEM Pri definiranju matematičkog modela transportnog problema uobičajeno se koristi sljedeće obilježa-vanje: m – broj ishodišta (skladišta) n – broj odredišta (mjesta potrošnje) ai, i = 1,2,…,m – količine proizvoda u ishodištima bj, j = 1,2,…,n – količine koje potražuju odredišta cij, i = 1,2,…,m i j = 1,2,…,n – jedinični troškovi transporta iz ishodišta i u odredište j xij, i = 1,2,…,m i j = 1,2,…,n – količine koje treba
2.5.1. TRANSPORTNI PROBLEM Raspložive količine ai i potraživane količine bj moraju biti pozitivne veličine dok su jednični troškovi transporta cij i prevezene količine xij u pravilu nenegativni: ai > 0 bj > 0 cij ≥ 0 xij ≥ 0
i = 1,2,…,m j = 1,2,…,n i = 1,2,…,m i j = 1,2,…,n i = 1,2,…,m i j = 1,2,…,n
Pored toga, pretpostavlja se da je ukupna raspoloživa količina jednaka ukupnoj potraživanoj količini: m
n
Σ ai = Σ bj
2.5.1. TRANSPORTNI PROBLEM C11 x11 a1
A1
C12 x12 C21 x21
a2
A2
C22 x22
B1
b1
B2
b2
C2n x2n Cm1 xm1 am
Am
C1n x1n Cm2 xm2 Cmn xmn
Sl. 2.5.1. Šematski prikaz transporta
Bn
bn
2.5.1. TRANSPORTNI PROBLEM Matematički model transportnog zadatka Minimizirati Z = c11 x11 + c12 x12 + … + c1n x1n + + c21 x21 + c22 x22 + … + c2n x2n + (2.5.1) + ... + m n + cm1 xm1 + cm2 xm2 + … + cmn xmn = Σ Σ cij xij i=1 j=1
Uz ograničenja za isporuke iz ishodišta: x11 + x12 + ... x21 + x22 + ... (2.5.2) ... xm1 + xm2 + ...
+ x1n = a1 + x2n = a2 + xmn = am
ograničenja za potrebe odredišta: x11 + x21 + ... + xn1 = b1 x12 + x22 + ... + xn2 = b2 (2.5.3) ... x1m + x2m + ... + xnm = bn ograničenja na nenegativnost promjenljivih:
2.5.1. TRANSPORTNI PROBLEM Ukupan broj promjenljivih xij je m∙n dok je broj jednačina m+n. Dakle, matrica ograničenja je dimenzija (m+n)x(m∙n) i specijalnog je oblika.
Sumiranjem lijevih i desnih strana ograničenja (2.5.2) i (2.5.3) dobije se: m
n
m
Σ Σ xij = Σ ai i=1 j=1 n
m
i=1 n
Σ Σ xij = Σ bj
2.5.1. TRANSPORTNI PROBLEM Pošto je: m
n
Σ ai = Σ bj i=1
j=1
Postoji linearna zavisnost sistema jednačina (2.5.2) i (2.5.3) tako da je broj linearno nezavisnih ograničenja
r=m+n-1 Prema tome, bazno rješenje TP ima (m + n -1) baznih elemenata.
2.5.1. TRANSPORTNI PROBLEM TP je moguće riješiti pomoću simpleks algoritma, medjutim, koristeći specifičnu strukturu TP, moguće je razviti efikasnije algoritme. Većina do sada razvijenih metoda pretpostavlja da je nekim drugim postupkom već određeno početno dopustivo rješenje. Zato je razvijen veći broj metoda za određivanje početnog dopustivog rješenje kao na primjer: •
metoda “sjeverozapadnog ugla”
2.5.1. TRANSPORTNI PROBLEM Metoda “sjeverozapadnog ugla” (određivanje početnog dopustivog rješenja) Dodjeljivanje vrijednosti promjenljivim počinje od gornjeg lijevog ugla (sjeverozapad na geofrafskim kartama), na sljedeći način:
• •
•
Promjenjliva x11 dobija maksimalnu vrijednost koja je ograničena manjim od kapaciteta a1 i b1 Preostala količina se dalje dodjeljuje sljedećoj promjenljivoj (x12 ako je a1>b1, odnosno, x21 ako je b1>a2) dok se ne istroši raspoloživa zaliha ishodišta, odnosno, zadovolji potražnja odredišta. Postupak se nastavlja pražnjenjem zalihe odnosno zadovoljavanjem potražnje. Posupak se završava kada se rasporede sve zalihe odnosno zadovolji sva tražnja
2.5.1. TRANSPORTNI PROBLEM Primjer 2.5.1. S1 S2 S3 Potrebe
i. l.
q.
P1 8 6 5 90
P2 9 9 6 125
P3 4 5 7 80
P4 6 3 4 65
X11 = min(100, 90) = 90, u S1 je ostalo još 10 jedinica pa je x12 = min(10, 125) = 10 x22 = min(120, 115) = 115 u S2 je ostalo još 5 jedinica pa je x23 = min(5, 80) = 5 x33 = min(140, 75) = 75 u S3 je ostalo još 65 jedinica pa je x34 = min(65, 65)
Raspodijeljene su sve zalihe i zadovoljene sve potrebe. Troškovi polaznog rješenja su: 90 ∙ 8 + 10 ∙ 9 + 115 ∙ 9 + 5 ∙ 5 + 75 ∙ 7 + 65 ∙ 4 = 2655
Zalihe 100 120 140
2.5.1. TRANSPORTNI PROBLEM Stepping Stone Method – Metoda “skakanje s kamena na kamen” (nalaženje optimalnog rješenja) Pored ovog naziva, ova metoda se u literaturi može naći i pod nazivima – metod raspodjele, distributivni metod, metod šahovke kule, ... Za ovu metodu je potrebno predhodno odrediti početno dopustivo rješenje što se može uraditi bilo kojom od naprijed pomenutih metoda za nalaženje početnog dopustivog rješenja. Osnova ideje ove metode je u tom, da se u tekućem dopustivom rješenju ispituju nezauzeta polja, tj. ispituje se da li bi uključenjem trans-porta na to polje ukupni trošak porastao ili bi ostao isti ili bi se smanjio. Kada se nađe polje čije uključenje u transport smanjuje ukupni trošak, izvrši se promjena tekuće raspodjele vodeći pri tom računa da se ne naruši dopustivost rješenja. Algoritam se zaustavlja kada se pri određenoj raspodjeli ne može naći nijedno polje koje smanjuje ukupni trošak transporta.
2.5.1. TRANSPORTNI PROBLEM Metod se primjenjuje tako što se iz svakog praznog polja tekućeg rješenja formira pravougaoni poligon čiji ostali vrhovi leže u popunjenim poljima. Za svako prazno polje se može formirati samo jedan poli-gon koji može imati najmanje 4 a najviše m+n vrhova. Na osnovu poligona izračunavamo relativne koeficijente troškova koji pokazuju za koliko će se promijeniti ukupni troškovi ako u prazno polje uvrstimo jednu jedinicu prevezene
2.5.1. TRANSPORTNI PROBLEM Relativni koeficijenti troškova se izračuna-vaju tako što se jedinični troškovi naiz-mjenično uvećavaju i umanjuju za cijene koje koje se nalaze u vrhovima poligona. Ako postoji makar jedan poligon koji umanjuje ukupni trošak, tekuće rješenje se mijenja tako da se transport “praznog polja” uveća što je više moguće a da se pri tom ne naruši dopustivost rješenja.
2.5.1. TRANSPORTNI PROBLEM Primjer 2.5.2. Razmotrićemo predhodni zadatak sa početnim dopustivim rješenjem koje je određeno metodom “sjevero-zapadnog ugla”: P1
P2
P3
P4
Zalihe
-----------------------------------------------------------------------------------------------------
8
S1 S2 S3
9
4
90
10
0
0
115
5
0
0
6 5
9 6
5 7
6
0 0
75
65
90 125 80
65
3 4
100 120 140
-----------------------------------------------------------------------------------------------------
Potrebe
Troškovi polaznog rješenja su: Z = 90 ∙ 8 + 10 ∙ 9 + 115 ∙ 9 + 5 ∙ 5 + 75 ∙ 7 + 65 ∙ 4 =
2.5.1. TRANSPORTNI PROBLEM Nepopunjena polja su: x13, x14, x21, x24, x31, x32 P1
P2
P3
P4
10
0
0
0
115
5
0
0
75
65
90
125
80
Zalihe
----------------------------------------------------------------------------------------------------8 9 4 6
S1 S2 S3
90
6 5
9
6
5 7
0
100
3
120
4
140
-----------------------------------------------------------------------------------------------------
Potrebe
65
Relativni koeficijenti troškova su: d13 = c13 – c12 + c22 – c23 = 4 – 9 + 9 – 5 = – 1 d14 = c14 – c12 + c22 – c23 + c33 – c34 = =6–9+9–5+7–4= 4 d21 = c21 – c22 + c12 – c11 = 6 – 9 + 9 – 8 = – 2 d24 = c24 – c23 + c33 – c34 = 3 – 5 + 7 – 4 = 1 d31 = c31 – c33 + c23 – c22 + c12 – c11 = =5–7+5–9+9–8=–5 d32 = c32 – c33 + c32 – c22 = 6 – 7 + 5 – 9 = – 5
2.5.1. TRANSPORTNI PROBLEM Pošto relativni koeficijenti troškova predstavljaju promjenu ukupnih troškova ako bi se izvršila promjena rasporeda transporta po navedenim poljima poligona za jednu jedinicu transportovane robe, najveće umanjenje troškova se može očekivati ako izvršimo promjenu transporta po poligonu za koji se dobio “najnenegativniji” rezultat. U ovom slučaju najmanji koeficijent troškova se dobije za d31 i d32. Može se odabrati bilo koji, tako da biramo koeficijent d31. To znači da ćemo uvećati transport iz S1 u P3 što je moguće više a da pri tom ne narušimo dopusti-vost zadatka.
2.5.1. TRANSPORTNI PROBLEM Količine transporta u vrhovima izabranog poligona su sljedeće: 90
10 115
0
5 75
Pošto uvećanju transporta u jednom polju odgovara uma-njenje u poljima koja su s njim u istom redu i u istoj koloni, najveća moguća promjena odgovara najmanjoj vrijednosti u poljima koja se umanjuju. Polja koja se umanjuju su x11 = 90, x22 = 115 i x33 = 75. Dakle najveća moguća promjena transporta je 75 pa će sada vrijednosti transporta po poligonu biti: x31 = 0+75 = 75, x33 = 75–75 = 0, x23 = 5+75 =
2.5.1. TRANSPORTNI PROBLEM Novi dopustivo rješenje je sada P1
P2
P3
P4
----------------------------------------------------------------------------------------------------8 9 4
S1 S2 S3
15
85
0
0
40
80
6 5
75
9
6
5 7
0 0
0
0
65
125
80
65
Zalihe 6
3 4
-----------------------------------------------------------------------------------------------------
Potrebe
90
Z = 15 8 + 85 9 + 40 9 + 80 5 + 75 5 + 65 4 = 2280 Relativni koeficijenti troškova za prazna polja su: d13 = c13 – c12 + c22 – c23 = 4 – 9 + 9 – 5 = – 1 d14 = c14 – c11 + c31 – c34 = 6 – 8 + 5 – 4 = – 1 d21 = c21 – c22 + c12 – c11 = 6 – 9 + 9 – 8 = – 2 d24 = c24 – c22 + c12 – c11 + c31 – c34 = =3–9+9–8+5–4=–4 d32 = c32 – c31 + c11 – c12 = 6 – 5 + 8 – 9 = 0 d33 = c33 – c31 + c11 – c12 + c22 – c23 = =7–5+8–9+9–5= 5
100 120 140
2.5.1. TRANSPORTNI PROBLEM “Najnegativniji” relativni koeficijent je d24. Količine trans-porta u vrhovima izabranog poligona su sljedeće: 15
85 40
75
0 65
Polja koja se umanjuju su x22 = 40, x11 = 15 i x34 = 65. Dakle najveća moguća promjena transporta je 15 pa će sada vrijednosti transporta po poligonu biti: x24 = 0+15 = 15, x22 = 40–15 = 25, x13 = 85+15 = 100, x11 = 15–15 = 0, x31 = 75+15 = 90, x34 = 65– 15 = 50
2.5.1. TRANSPORTNI PROBLEM Novi dopustivo rješenje je sada P1
P2
P3
P4
----------------------------------------------------------------------------------------------------8 9 4
S1 S2 S3
0
100
0
25
6 5
90
9
6
0
5
80
7
0 15
0
0
50
125
80
65
Zalihe 6
3 4
-----------------------------------------------------------------------------------------------------
Potrebe
90
Z = 100 9 + 25 9 + 80 5 + 15 3 + 90 5 + 50 4 = 2220 Relativni koeficijenti troškova za prazna polja su: d11 = c11 – c12 + c22 – c24 + c34 – c14 = =8–9+9–3+4–5= 4 d13 = c13 – c12 + c22 – c23 = 4 – 9 + 9 – 5 = – 1 d14 = c14 – c12 + c22 – c24 = 6 – 9 + 9 – 3 = 3 d21 = c21 – c24 + c34 – c14 = 6 – 3 + 4 – 5 = 2 d32 = c32 – c34 + c24 – c22 = 6 – 4 + 3 – 9 = – 4 d33 = c33 – c34 + c24 – c32 = 7 – 4 + 3 – 5 = 1
100 120 140
2.5.1. TRANSPORTNI PROBLEM “Najnegativniji” relativni koeficijent je d32. Količine trans-porta u vrhovima izabranog poligona su sljedeće: 25
15
0
50
Polja koja se umanjuju su x34 = 50 i x22 = 25. Dakle najveća moguća promjena transporta je 25 pa će sada vrijednosti transporta po poligonu biti: x32 = 0+25 = 25, x34 = 50–25 = 25, x24 = 15+25 = 40, x22 = 25–25 = 0
2.5.1. TRANSPORTNI PROBLEM Novi dopustivo rješenje je sada P1
P2
P3
P4
----------------------------------------------------------------------------------------------------8 9 4
S1 S2 S3
0
6
100 9
0
5
0
0
90
25
0
25
125
80
65
5
6
80
0
7
40
Zalihe 6
3 4
-----------------------------------------------------------------------------------------------------
Potrebe
90
Z = 100 9 + 80 5 + 40 3 + 90 5 + 25 6 + 25 4 = 2120 Relativni koeficijenti troškova za prazna polja su: d11 = c11 – c12 + c32 – c31 = 8 – 9 + 6 – 5 = 0 d13 = c13 – c12 + c32 – c34 + c24 – c23 = =4–9+6–4+3–5=–5 d14 = c14 – c12 + c22 – c24 = 6 – 9 + 6 – 4 = – 1 d21 = c21 – c24 + c34 – c14 = 6 – 3 + 4 – 5 = 2 d22 = c22 – c24 + c34 – c32 = 9 – 3 + 4 – 6 = 4 d33 = c33 – c34 + c24 – c32 = 7 – 4 + 3 – 5 = 1
100 120 140
2.5.1. TRANSPORTNI PROBLEM “Najnegativniji” relativni koeficijent je d13. Količine trans-porta u vrhovima izabranog poligona su sljedeće: 100
0
80 25
40 25
Polja koja se umanjuju su x12 = 100, x34 = 25 i x23 = 80. Najveća moguća promjena transporta je 25 pa će sada vrijednosti transporta po poligonu biti: x13 = 0+25 = 25, x12 = 100–25 = 75, x32 = 25+25 = 50, x34 = 25–25 = 0, x24 = 40+25 = 65, x23 = 80–25 = 55
2.5.1. TRANSPORTNI PROBLEM Novi dopustivo rješenje je sada P1
P2
P3
P4
----------------------------------------------------------------------------------------------------8 9 4
S1 S2 S3
0
75
25
0
0
0
55
65
90
50
0
0
125
80
65
6 5
9 6
5 7
Zalihe 6
3 4
-----------------------------------------------------------------------------------------------------
Potrebe
90
Z = 75 9 + 25 4 + 55 5 + 65 3 + 90 5 + 50 6 = 1995 Relativni koeficijenti troškova za prazna polja su: d11 = c11 – c12 + c32 – c14 = 8 – 9 + 6 – 5 = 0 d14 = c14 – c13 + c23 – c24 = 6 – 4 + 5 – 3 = 4 d21 = c21 – c31 + c32 – c12 + c13 – c23 = =6–5+6–9+4–5=–3 d22 = c22 – c23 + c13 – c12 = 9 – 5 + 4 – 9 = – 1 d33 = c33 – c32 + c12 – c13 = 7 – 6 + 9 – 4 = 6 d34 = c34 – c32 + c12 – c13 + c23 – c24 = =4–6+9–4+5–3= 5
100 120 140
2.5.1. TRANSPORTNI PROBLEM “Najnegativniji” relativni koeficijent je d21. Količine trans-porta u vrhovima izabranog poligona su sljedeće: 75
0 90
25 55
50
Polja koja se umanjuju su x31 = 90, x12 = 75 i x23 = 55. Najveća moguća promjena transporta je 55 pa će sada vrijednosti transporta po poligonu biti: x21 = 0+55 = 55, x31 = 90–55 = 35, x32 = 50+55 = 105, x12 = 75–55 = 20, x13 = 25+55 = 80, x23 = 55–55 = 0
2.5.1. TRANSPORTNI PROBLEM Novi dopustivo rješenje je sada P1
P2
P3
P4
----------------------------------------------------------------------------------------------------8 9 4
S1 S2 S3
0
20
55
0
0
35
105
0
0
80
65
6 5
9 6
80
5 7
0 65
Zalihe 6
3 4
-----------------------------------------------------------------------------------------------------
Potrebe
90
125
Z = 20 9 + 80 4 + 55 6 + 65 3 + 35 5 + 105 6 = 1830 Relativni koeficijenti troškova za prazna polja su: d11 = c11 – c12 + c32 – c14 = 8 – 9 + 6 – 5 = 0 d14 = c14 – c12 + c32 – c31 + c21 – c24 = =6–9+6–5+6–3= 1 d22 = c22 – c21 + c31 – c32 = 9 – 6 + 5 – 6 = 2 d23 = c23 – c21 + c31 – c32 + c12 – c13 = =5–6+5–6+9–4= 3 d33 = c33 – c32 + c12 – c13 = 7 – 6 + 9 – 4 = 6 d34 = c34 – c31 + c21 – c24 = 4 – 5 + 6 – 3 = 2
100 120 140
2.5.1. TRANSPORTNI PROBLEM
Pošto su svi relativni koeficijenti troškova veći ili jednaki nuli, ovo rješenje je optimalno. x11 = 0 0 x21 = 55 65 x31 = 35 0
x12 = 20
x13 = 80 x14 =
x22 = 0
x23 = 0
x32 = 105 x33 = 0
x24 = x34 =
2.5.2. PROBLEM RASPOREDJIVANJA Postavka zadatka Problem raspoređivanja (asignacije) je specijalan oblik zadatka LP a po strukturi i načinu rješavanja, sličan je problemu transporta. Sam problem se predstaviti na sljedeći način: Rasporediti određeni broj izvršilaca (nekoga ili neče-ga što može da obavi ili proizvede neke aktivnosti – radnika, studenata, takmičara, prodavnica, novca, ...) na određeni broj mjesta (na kojima se mogu realizirati te aktivnosti – poslova, mašina, ispita, radnih mjesta, sportskih disciplina, pogona, lokacija, ...).
2.5.2. PROBLEM RASPOREDJIVANJA Pri tom jedan izvršilac može da bude raspore-đen na samo jedno mjesto, jednom mjestu može biti dodijeljen samo jedan izvršilac Svaki konkretni raspored proizvodi određeni efekat (povećanje vrijednosti ili povećanje troška). Potrebno je naći takav raspored izvršilaca na određena mjesta koji će dati optimalni efekat (maksimum ili minimum)
2.5.2. PROBLEM RASPOREDJIVANJA Pri definiranju modela raspoređivanja (asignacije) uobičajeno se koristi sljedeće obilježavanje: m – broj izvršilaca n – broj mjesta (radnih zadataka) cij, i = 1,2,…,m i j = 1,2,…,n – troškovi (dobiti) rasporeda izvršioca i na mjesto j xij, i = 1,2,…,m i j = 1,2,…,n – označava da li je izvršilac i raspoređen na mjesto j 1 - Ako je izvršilac i raspoređen na
2.5.2. PROBLEM RASPOREDJIVANJA Matematički model problema raspoređivanja Minimizirati Z = c11 x11 + c12 x12 + … + c1n x1n + + c21 x21 + c22 x22 + … + c2n x2n + (2.5.5) + ... + + cm1 xm1 + cm2 xm2 + … + cmn xmn = m
n
= Σ Σ cij xij i=1 j=1
uz ograničenja: m
Σ xij = 1
i=1
j = 1, 2, ..., n
(2.5.6)
i = 1, 2, ..., m
(2.5.7)
n
Σ xij = 1
j=1
xij = 0 ili 1
2.5.2. PROBLEM RASPOREDJIVANJA Ovako definiran model predstavlja poseban oblik modela LP, tzv. 0-1 programiranje. U odnosu na transportni model, ovdje je specifično, što su ponude iz svih ishodišta jednake jedinici, odnosno, sve potrebe odredišta su jednake jedinici. Da bi se problem raspoređivanja mogao riješiti potrebno je da broj izvršilaca i broj (radnih) mjesta bude jednak (m=n)
2.5.2. PROBLEM RASPOREDJIVANJA Ako je n = m imamo zatvoreni model raspoređivanja. Ako nije jednak broj izvršilaca i mjesta, to jest ako je m#n, tada imamo otvoreni model raspoređivanja. On se prevodi u zatvoreni, uvođenjem fiktivnih promjenljivih. Da bi se uravnotežio broj izvršilaca i mjesta, uvodi se fiktivno mjesto, odnosno fiktivni izvršilac. Tada se uzima da je efikasnost fiktivnog mjesta cif = 0, (i = 1, 2, …, m), odnosno, fiktivnog izvršioca cfj= 0, (j = 1, 2, …, n).
2.5.2. PROBLEM RASPOREDJIVANJA Metoda raspoređivanja za minimalnu vrijednost funkcije cilja – mađarska metoda Problem raspoređivanja se može riješiti korištenjem više metoda koje su, inače, razvijene za rješavanje drugih problema (Linearno programiranje, transportni problem). Problem raspoređivanja se može riješiti i ispitivanjem svih mogućih kombinacija i biranjem one kombinacije koja daje najbolji rezultat. Međutim, broj mogućih kombinacija je n! pa se već za n = 10 dobije broj kombinacija jednak 3,628.800. Jasno je da je ovakav pristup neprimjenljiv za iole veće
2.5.2. PROBLEM RASPOREDJIVANJA Ovaj problem se može riješiti i metodom grananja (Branch and Bound) koja omogu-ćava ispitivanje samo onih kombinacija koje su po određenom kriteriju bolje od nekih drugih koje odbacujemo. Međutim, danas se najčešće koristi metoda posebno razvijena za rješavanje problema raspoređivanja (mađarska metoda po tehnici Flooda).
2.5.2. PROBLEM RASPOREDJIVANJA Postupak se zasniva na korištenju matrice efikasnosti (troškova) C čiji su elementi koeficijenti funkcije cilja. Ako se pretpostavi da je broj izvršilaca i broj mjesta jednak, matrica C će biti: |̄ c11 | c21 C = | ... | ... |̱ cn1
c12 ... c22 ...
cn2 ...
c1n |̄ c2n | | | cnn |̱
Smatra se da je efikasnost veća što je
2.5.2. PROBLEM RASPOREDJIVANJA Postupak se realizira kroz tri koraka:
• Zadana matrica efikasnosti C se prevodi u
matricu C’ tako što se svi članovi svakog reda polazne matrice umanje za vrijednost najma-njeg elementa tog reda. Na taj način se u svakom redu dobije najmanje jedna nula. Zatim se, u tako dobijenoj matrici, svi članovi svake kolone umanje za vrijednost najmanjeg elementa te kolone. Na taj način formirana matrica sadrži
2.5.2. PROBLEM RASPOREDJIVANJA 2. Označavaju se nule matrice na sljedeći način: a. Polazeći od prvog reda matrice, nalaze se redovi koji imaju samo jednu nulu. Ta se nula označi a ostale nule u koloni sa označenom nulom se prekriže. Ovaj postupak se sprovodi dok ima redova sa jednom neoznačenom nulom. b. Isti postupak se primjeni na kolone. Postupci a. i b. se ponavljaju dok sve nule ne budu označene ili prekrižene. Ako se u svakom redu i u svakoj koloni nalazi po jedna označena nula postupak je završen. U suprotnom prelazi se na korak 3.
2.5.2. PROBLEM RASPOREDJIVANJA 3. Proizvodi se nova matrica slijede}im postupkom: a. Označe se strelicama redovi koji nemaju označene nule b. Označe se strelicama kolone koje u ozna-čenim redovima imaju prekrižene nule c. Označe se redovi koji imaju označenu nulu u označenoj koloni d. Ponavljaju se postupci b. i c. dok se lanac ne zatvori
2.5.2. PROBLEM RASPOREDJIVANJA e. Povuku se linije kroz neoznačene redove i označene kolone; kroz svaku označenu nulu (asignaciju) mora prolaziti jedna linija, dakle, treba da dobijemo onoliko linija koliko imamo označenih nula f. Formira se nova matrica, tako što se najmanji nepokriveni (neprecrtan linijom) element cij predhodne matrice: (1) oduzme od svakog nepokrivenog
elementa
(2) doda svakom elementu dva puta prekriženom, tj. elementima koji se nalaze na pre sjeku dviju linija Elementi prekriveni jednom linijom se prepišu u novu matricu.
2.5.2. PROBLEM RASPOREDJIVANJA Na ovako dobijenu matricu primjenjuje se korak 2. Ako se ne nađe optimalno rješenje, nastavlja se sa korakom 3. i to se nastavlja dok se ne nađe optimalno rješenje. Kada se dobije matrica sa potpunom asignacijom, koja sadrži n zaokruženih nula, iz nje se može odrditi optimalno rješenje. Zaokružene nule označavaju varijable čije su vrijednosti jednake jedinici (xij = 1).
2.5.2. PROBLEM RASPOREDJIVANJA Primjer 2.5.3. Naći optimalno rješenje problema raspo-ređivanja za sljedeću matricu koštanja: |
P1 P2 P3 P4 P5
----------------------------------------------------------------------
I1 I2 I3 I4 I5
| | | | |
11 9 13 21 14
17 7 16 24 10
8 12 15 17 12
16 6 12 28 11
20 15 16 26 15
2.5.2. PROBLEM RASPOREDJIVANJA Rješenje Sve članovi svakog reda polazne matrice umanje se za vrijednost najmanjeg elementa tog reda |
P1
P2
P3
P4
P5
----------------------------------------------------------------------
I1 I2 I3 I4 I5
| | | | |
3 3 1 4 4
9 1 4 7 0
0 6 3 0 2
8 0 0 11 1
12 9 4 9 5
2.5.2. PROBLEM RASPOREDJIVANJA Svi članovi svake kolone ove matrice umanje se za vrijednost najmanjeg elementa te kolone |
P1
P2
P3
P4
P5
----------------------------------------------------------------------
I1 I2 I3 I4 I5
| | | | |
2 2 0 3 3
9 1 4 7 0
0 6 3 0 2
8 0 0 11 1
8 5 0 5 1
2.5.2. PROBLEM RASPOREDJIVANJA Polazeći od prvog reda matrice, nalaze se redovi koji imaju samo jednu nulu. Ta se nula označi a ostale nule u koloni sa označenom nulom se prekriže. Isti postupak se uradi i sa kolonama dok sve nule ne budu obilježene ili prekrižene. |
P1
P2
P3
P4
P5
----------------------------------------------------------------------
I1 I2 I3 I4 I5
| | | | |
2 2 0 3 3
9 1 4 7 0
0 6 3 0 2
8 0 0 11 1
8 5 0 5 1
2.5.2. PROBLEM RASPOREDJIVANJA Postupak nije završen jer nemamo 5 obilježenih nula, naime izvršilac 4 i posao 5 nisu raspodjeljeni. Sada strelicama označimo redove koji nemaju označenih nula i kolone koje u označenim redovima imaju prekrižene nule |
P1
P2
P3
P4
P5
----------------------------------------------------------------------
I1 I2 I3 I4 I5
| | | | |
2 2 0 3 3
9 1 4 7 0
0 6 3 0 2
8 0 0 11 1
8 5 0 5 1
2.5.2. PROBLEM RASPOREDJIVANJA Označe se redovi koji imaju označenu nulu u označenoj koloni. Ponavljaju se postupci dok u označenim redovima ima prekriženih nula |
P1
P2
P3
P4
P5
----------------------------------------------------------------------
I1 I2 I3 I4 I5
| | | | |
2 2 0 3 3
9 1 4 7 0
0 6 3 0 2
8 0 0 11 1
8 5 0 5 1
2.5.2. PROBLEM RASPOREDJIVANJA Povuku se linije kroz neoznačene redove i označene kolone; kroz svaku zaokruženu nulu (asignaciju) mora da prolazi jedna i samo jedna linija, dakle, treba da dobijemo onoliko linija koliko imamo zaokruženih nula |
P1
P2
P3
P4
P5
----------------------------------------------------------------------
I1 I2 I3 I4 I5
| | | | |
2 2 0 3 3
9 1 4 7 0
0 6 3 0 2
8 0 0 11 1
8 5 0 5 1
2.5.2. PROBLEM RASPOREDJIVANJA Primjenjuje se Korak 2., tj. nalaze se redovi koji imaju samo jednu nulu i ta se nula označi a ostale nule u koloni sa označenom nulom se prekriže. b. Isti postupak se primjeni na kolone. |
P1
P2
P3
P4
P5
----------------------------------------------------------------------
I1 I2 I3 I4 I5
| | | | |
0 2 0 2 3
7 1 4 5 0
0 8 5 0 4
6 0 0 9 1
6 5 0 3 1
2.5.2. PROBLEM RASPOREDJIVANJA Dobili smo optimalno rješenje: x11 = 1 x24 = 1 x35 = 1 x43 = 1 x52 = 1 Z = c11 + c24 + c35 + c43 + c52 = = 11 + 6 + 16 + 17 + 10 = 60
3. LITERATURA • • • • • • • • • •
Backović M., Vuleta J., „Ekonomsko matematički metodi i modeli”, CID, Beograd, 2000. Bronštejn I.N. i dr., „Matematički priručnik”, Golden marketing-Tehnička knjiga, Zagreb, 2004. Carter M.W., Price C.C., “Operations Research – A Practical Introduction”, CRC Press, 2001. Chandrasekhara Rao K., “Operations Research”, Alpha Science International Ltd., 2005. Hillier F.S., Lieberman G.J., “Introduction to Operations Research”, McGrow-Hill, New York, 2005. Krčevinac S. i dr., “Operaciona istraživanja”, Fakultet organizacionih nauka, Beograd, 2004. Neralić L., „Uvod u matematičko programiranje 1”, Element, Zagreb, 2003. Petrić J.: “Operaciona istraživanja”, Nauka, Beograd, 1997. Pierre D.A., “Optimization theory with applications”, Dover publications, NewYork, 1986. Zečević T., “Operaciona istraživanja”, Naučna knjiga, Beograd, 1974. šk.god. 2007/2008.
dr Tadej Mateljan
6. LINEARNO PROGRAMIRANJE TRANSPORTNI PROBLEM PROBLEM RASPOREDJIVANJA
šk.god. 2007/2008.
dr Tadej Mateljan
2.5.1. TRANSPORTNI PROBLEM 2.5.1. TRANSPORTNI PROBLEM • Postavka zadatka • Matematički model • Metoda “sjeverozapadnog ugla” (određivanje početnog dopustivog rješenja) • Stepping Stone Method – Metoda “skakanje s kamena na kamen” (nalaženje optimalnog rješenja) 2.5.2. PROBLEM RASPOREĐIVANJA • Postavka zadatka • Matematički model • Mađarska metoda
2.5.1. TRANSPORTNI PROBLEM Izučavanja problema transporta primjenom anali-tičkih metoda potiče iz polovine prošlOg stoljeća. Tim se problemom bavilo više poznatih istraživača, mEđu kojima su značajni rezultati sovjetskog naučnika L. V. Kantroviča iz 1939 i američkog naučnika F. L. Hitchcocka-a iz 1941 godine. Nekako u isto vrijeme, veliki istraživački napori i rezultati su bili vezani za zadatak linearnog programiranja. Pokazalo se da je transportni problem njegov specijalan slučaj i da može biti riješen nekom od metoda za rješavanje zadatka LP. Međutim, pokazalo se, također, da zbog svoje specifične
2.5.1. TRANSPORTNI PROBLEM
Tako je Dantzig je objavio rješenje bazirano na simpleks množiteljima, Vogel je predložio aproksimativnu metodu za nalaženje početnog rješenja Charnes i Cooper su 1953. god. i objavili metodu danas poznatu kao metoda „skakanja s kamena na kamen“ (Stepping Stone Method) Ford i Fulkenson su 1956. godine objavili metodu za rješenje TP
2.5.1. TRANSPORTNI PROBLEM
Naziv ovog problema potiče od toga što su se prvo rješavali problemi transporta – naći minimalne troškove transporta kroz zadanu transportnu mrežu i uz zadana transportna sredstva. Međutim danas se u ove probleme uključuju zadaci optimalnog razmje-štanja mašina, postrojenja, službi, skladišta, servisa, energetskih objekata, prodajnih objekata, ...
2.5.1. TRANSPORTNI PROBLEM Postavka zadatka Pronalaženje optimalnog plana transporta se najčešće svodi na zadatak transporta jedne vrste proizvoda iz određenog broja mjesta skladištenja u određeni broj mjesta potrošnje uz minimalne troškove. Pri tom su poznate količine proizvoda smještene u skladištima količine proizvoda koje potražuju mjesta potrošnje jedinični troškovi transporta iz bilo kojeg
2.5.1. TRANSPORTNI PROBLEM Pri definiranju matematičkog modela transportnog problema uobičajeno se koristi sljedeće obilježa-vanje: m – broj ishodišta (skladišta) n – broj odredišta (mjesta potrošnje) ai, i = 1,2,…,m – količine proizvoda u ishodištima bj, j = 1,2,…,n – količine koje potražuju odredišta cij, i = 1,2,…,m i j = 1,2,…,n – jedinični troškovi transporta iz ishodišta i u odredište j xij, i = 1,2,…,m i j = 1,2,…,n – količine koje treba
2.5.1. TRANSPORTNI PROBLEM Raspložive količine ai i potraživane količine bj moraju biti pozitivne veličine dok su jednični troškovi transporta cij i prevezene količine xij u pravilu nenegativni: ai > 0 bj > 0 cij ≥ 0 xij ≥ 0
i = 1,2,…,m j = 1,2,…,n i = 1,2,…,m i j = 1,2,…,n i = 1,2,…,m i j = 1,2,…,n
Pored toga, pretpostavlja se da je ukupna raspoloživa količina jednaka ukupnoj potraživanoj količini: m
n
Σ ai = Σ bj
2.5.1. TRANSPORTNI PROBLEM C11 x11 a1
A1
C12 x12 C21 x21
a2
A2
C22 x22
B1
b1
B2
b2
C2n x2n Cm1 xm1 am
Am
C1n x1n Cm2 xm2 Cmn xmn
Sl. 2.5.1. Šematski prikaz transporta
Bn
bn
2.5.1. TRANSPORTNI PROBLEM Matematički model transportnog zadatka Minimizirati Z = c11 x11 + c12 x12 + … + c1n x1n + + c21 x21 + c22 x22 + … + c2n x2n + (2.5.1) + ... + m n + cm1 xm1 + cm2 xm2 + … + cmn xmn = Σ Σ cij xij i=1 j=1
Uz ograničenja za isporuke iz ishodišta: x11 + x12 + ... x21 + x22 + ... (2.5.2) ... xm1 + xm2 + ...
+ x1n = a1 + x2n = a2 + xmn = am
ograničenja za potrebe odredišta: x11 + x21 + ... + xn1 = b1 x12 + x22 + ... + xn2 = b2 (2.5.3) ... x1m + x2m + ... + xnm = bn ograničenja na nenegativnost promjenljivih:
2.5.1. TRANSPORTNI PROBLEM Ukupan broj promjenljivih xij je m∙n dok je broj jednačina m+n. Dakle, matrica ograničenja je dimenzija (m+n)x(m∙n) i specijalnog je oblika.
Sumiranjem lijevih i desnih strana ograničenja (2.5.2) i (2.5.3) dobije se: m
n
m
Σ Σ xij = Σ ai i=1 j=1 n
m
i=1 n
Σ Σ xij = Σ bj
2.5.1. TRANSPORTNI PROBLEM Pošto je: m
n
Σ ai = Σ bj i=1
j=1
Postoji linearna zavisnost sistema jednačina (2.5.2) i (2.5.3) tako da je broj linearno nezavisnih ograničenja
r=m+n-1 Prema tome, bazno rješenje TP ima (m + n -1) baznih elemenata.
2.5.1. TRANSPORTNI PROBLEM TP je moguće riješiti pomoću simpleks algoritma, medjutim, koristeći specifičnu strukturu TP, moguće je razviti efikasnije algoritme. Većina do sada razvijenih metoda pretpostavlja da je nekim drugim postupkom već određeno početno dopustivo rješenje. Zato je razvijen veći broj metoda za određivanje početnog dopustivog rješenje kao na primjer: •
metoda “sjeverozapadnog ugla”
2.5.1. TRANSPORTNI PROBLEM Metoda “sjeverozapadnog ugla” (određivanje početnog dopustivog rješenja) Dodjeljivanje vrijednosti promjenljivim počinje od gornjeg lijevog ugla (sjeverozapad na geofrafskim kartama), na sljedeći način:
• •
•
Promjenjliva x11 dobija maksimalnu vrijednost koja je ograničena manjim od kapaciteta a1 i b1 Preostala količina se dalje dodjeljuje sljedećoj promjenljivoj (x12 ako je a1>b1, odnosno, x21 ako je b1>a2) dok se ne istroši raspoloživa zaliha ishodišta, odnosno, zadovolji potražnja odredišta. Postupak se nastavlja pražnjenjem zalihe odnosno zadovoljavanjem potražnje. Posupak se završava kada se rasporede sve zalihe odnosno zadovolji sva tražnja
2.5.1. TRANSPORTNI PROBLEM Primjer 2.5.1. S1 S2 S3 Potrebe
i. l.
q.
P1 8 6 5 90
P2 9 9 6 125
P3 4 5 7 80
P4 6 3 4 65
X11 = min(100, 90) = 90, u S1 je ostalo još 10 jedinica pa je x12 = min(10, 125) = 10 x22 = min(120, 115) = 115 u S2 je ostalo još 5 jedinica pa je x23 = min(5, 80) = 5 x33 = min(140, 75) = 75 u S3 je ostalo još 65 jedinica pa je x34 = min(65, 65)
Raspodijeljene su sve zalihe i zadovoljene sve potrebe. Troškovi polaznog rješenja su: 90 ∙ 8 + 10 ∙ 9 + 115 ∙ 9 + 5 ∙ 5 + 75 ∙ 7 + 65 ∙ 4 = 2655
Zalihe 100 120 140
2.5.1. TRANSPORTNI PROBLEM Stepping Stone Method – Metoda “skakanje s kamena na kamen” (nalaženje optimalnog rješenja) Pored ovog naziva, ova metoda se u literaturi može naći i pod nazivima – metod raspodjele, distributivni metod, metod šahovke kule, ... Za ovu metodu je potrebno predhodno odrediti početno dopustivo rješenje što se može uraditi bilo kojom od naprijed pomenutih metoda za nalaženje početnog dopustivog rješenja. Osnova ideje ove metode je u tom, da se u tekućem dopustivom rješenju ispituju nezauzeta polja, tj. ispituje se da li bi uključenjem trans-porta na to polje ukupni trošak porastao ili bi ostao isti ili bi se smanjio. Kada se nađe polje čije uključenje u transport smanjuje ukupni trošak, izvrši se promjena tekuće raspodjele vodeći pri tom računa da se ne naruši dopustivost rješenja. Algoritam se zaustavlja kada se pri određenoj raspodjeli ne može naći nijedno polje koje smanjuje ukupni trošak transporta.
2.5.1. TRANSPORTNI PROBLEM Metod se primjenjuje tako što se iz svakog praznog polja tekućeg rješenja formira pravougaoni poligon čiji ostali vrhovi leže u popunjenim poljima. Za svako prazno polje se može formirati samo jedan poli-gon koji može imati najmanje 4 a najviše m+n vrhova. Na osnovu poligona izračunavamo relativne koeficijente troškova koji pokazuju za koliko će se promijeniti ukupni troškovi ako u prazno polje uvrstimo jednu jedinicu prevezene
2.5.1. TRANSPORTNI PROBLEM Relativni koeficijenti troškova se izračuna-vaju tako što se jedinični troškovi naiz-mjenično uvećavaju i umanjuju za cijene koje koje se nalaze u vrhovima poligona. Ako postoji makar jedan poligon koji umanjuje ukupni trošak, tekuće rješenje se mijenja tako da se transport “praznog polja” uveća što je više moguće a da se pri tom ne naruši dopustivost rješenja.
2.5.1. TRANSPORTNI PROBLEM Primjer 2.5.2. Razmotrićemo predhodni zadatak sa početnim dopustivim rješenjem koje je određeno metodom “sjevero-zapadnog ugla”: P1
P2
P3
P4
Zalihe
-----------------------------------------------------------------------------------------------------
8
S1 S2 S3
9
4
90
10
0
0
115
5
0
0
6 5
9 6
5 7
6
0 0
75
65
90 125 80
65
3 4
100 120 140
-----------------------------------------------------------------------------------------------------
Potrebe
Troškovi polaznog rješenja su: Z = 90 ∙ 8 + 10 ∙ 9 + 115 ∙ 9 + 5 ∙ 5 + 75 ∙ 7 + 65 ∙ 4 =
2.5.1. TRANSPORTNI PROBLEM Nepopunjena polja su: x13, x14, x21, x24, x31, x32 P1
P2
P3
P4
10
0
0
0
115
5
0
0
75
65
90
125
80
Zalihe
----------------------------------------------------------------------------------------------------8 9 4 6
S1 S2 S3
90
6 5
9
6
5 7
0
100
3
120
4
140
-----------------------------------------------------------------------------------------------------
Potrebe
65
Relativni koeficijenti troškova su: d13 = c13 – c12 + c22 – c23 = 4 – 9 + 9 – 5 = – 1 d14 = c14 – c12 + c22 – c23 + c33 – c34 = =6–9+9–5+7–4= 4 d21 = c21 – c22 + c12 – c11 = 6 – 9 + 9 – 8 = – 2 d24 = c24 – c23 + c33 – c34 = 3 – 5 + 7 – 4 = 1 d31 = c31 – c33 + c23 – c22 + c12 – c11 = =5–7+5–9+9–8=–5 d32 = c32 – c33 + c32 – c22 = 6 – 7 + 5 – 9 = – 5
2.5.1. TRANSPORTNI PROBLEM Pošto relativni koeficijenti troškova predstavljaju promjenu ukupnih troškova ako bi se izvršila promjena rasporeda transporta po navedenim poljima poligona za jednu jedinicu transportovane robe, najveće umanjenje troškova se može očekivati ako izvršimo promjenu transporta po poligonu za koji se dobio “najnenegativniji” rezultat. U ovom slučaju najmanji koeficijent troškova se dobije za d31 i d32. Može se odabrati bilo koji, tako da biramo koeficijent d31. To znači da ćemo uvećati transport iz S1 u P3 što je moguće više a da pri tom ne narušimo dopusti-vost zadatka.
2.5.1. TRANSPORTNI PROBLEM Količine transporta u vrhovima izabranog poligona su sljedeće: 90
10 115
0
5 75
Pošto uvećanju transporta u jednom polju odgovara uma-njenje u poljima koja su s njim u istom redu i u istoj koloni, najveća moguća promjena odgovara najmanjoj vrijednosti u poljima koja se umanjuju. Polja koja se umanjuju su x11 = 90, x22 = 115 i x33 = 75. Dakle najveća moguća promjena transporta je 75 pa će sada vrijednosti transporta po poligonu biti: x31 = 0+75 = 75, x33 = 75–75 = 0, x23 = 5+75 =
2.5.1. TRANSPORTNI PROBLEM Novi dopustivo rješenje je sada P1
P2
P3
P4
----------------------------------------------------------------------------------------------------8 9 4
S1 S2 S3
15
85
0
0
40
80
6 5
75
9
6
5 7
0 0
0
0
65
125
80
65
Zalihe 6
3 4
-----------------------------------------------------------------------------------------------------
Potrebe
90
Z = 15 8 + 85 9 + 40 9 + 80 5 + 75 5 + 65 4 = 2280 Relativni koeficijenti troškova za prazna polja su: d13 = c13 – c12 + c22 – c23 = 4 – 9 + 9 – 5 = – 1 d14 = c14 – c11 + c31 – c34 = 6 – 8 + 5 – 4 = – 1 d21 = c21 – c22 + c12 – c11 = 6 – 9 + 9 – 8 = – 2 d24 = c24 – c22 + c12 – c11 + c31 – c34 = =3–9+9–8+5–4=–4 d32 = c32 – c31 + c11 – c12 = 6 – 5 + 8 – 9 = 0 d33 = c33 – c31 + c11 – c12 + c22 – c23 = =7–5+8–9+9–5= 5
100 120 140
2.5.1. TRANSPORTNI PROBLEM “Najnegativniji” relativni koeficijent je d24. Količine trans-porta u vrhovima izabranog poligona su sljedeće: 15
85 40
75
0 65
Polja koja se umanjuju su x22 = 40, x11 = 15 i x34 = 65. Dakle najveća moguća promjena transporta je 15 pa će sada vrijednosti transporta po poligonu biti: x24 = 0+15 = 15, x22 = 40–15 = 25, x13 = 85+15 = 100, x11 = 15–15 = 0, x31 = 75+15 = 90, x34 = 65– 15 = 50
2.5.1. TRANSPORTNI PROBLEM Novi dopustivo rješenje je sada P1
P2
P3
P4
----------------------------------------------------------------------------------------------------8 9 4
S1 S2 S3
0
100
0
25
6 5
90
9
6
0
5
80
7
0 15
0
0
50
125
80
65
Zalihe 6
3 4
-----------------------------------------------------------------------------------------------------
Potrebe
90
Z = 100 9 + 25 9 + 80 5 + 15 3 + 90 5 + 50 4 = 2220 Relativni koeficijenti troškova za prazna polja su: d11 = c11 – c12 + c22 – c24 + c34 – c14 = =8–9+9–3+4–5= 4 d13 = c13 – c12 + c22 – c23 = 4 – 9 + 9 – 5 = – 1 d14 = c14 – c12 + c22 – c24 = 6 – 9 + 9 – 3 = 3 d21 = c21 – c24 + c34 – c14 = 6 – 3 + 4 – 5 = 2 d32 = c32 – c34 + c24 – c22 = 6 – 4 + 3 – 9 = – 4 d33 = c33 – c34 + c24 – c32 = 7 – 4 + 3 – 5 = 1
100 120 140
2.5.1. TRANSPORTNI PROBLEM “Najnegativniji” relativni koeficijent je d32. Količine trans-porta u vrhovima izabranog poligona su sljedeće: 25
15
0
50
Polja koja se umanjuju su x34 = 50 i x22 = 25. Dakle najveća moguća promjena transporta je 25 pa će sada vrijednosti transporta po poligonu biti: x32 = 0+25 = 25, x34 = 50–25 = 25, x24 = 15+25 = 40, x22 = 25–25 = 0
2.5.1. TRANSPORTNI PROBLEM Novi dopustivo rješenje je sada P1
P2
P3
P4
----------------------------------------------------------------------------------------------------8 9 4
S1 S2 S3
0
6
100 9
0
5
0
0
90
25
0
25
125
80
65
5
6
80
0
7
40
Zalihe 6
3 4
-----------------------------------------------------------------------------------------------------
Potrebe
90
Z = 100 9 + 80 5 + 40 3 + 90 5 + 25 6 + 25 4 = 2120 Relativni koeficijenti troškova za prazna polja su: d11 = c11 – c12 + c32 – c31 = 8 – 9 + 6 – 5 = 0 d13 = c13 – c12 + c32 – c34 + c24 – c23 = =4–9+6–4+3–5=–5 d14 = c14 – c12 + c22 – c24 = 6 – 9 + 6 – 4 = – 1 d21 = c21 – c24 + c34 – c14 = 6 – 3 + 4 – 5 = 2 d22 = c22 – c24 + c34 – c32 = 9 – 3 + 4 – 6 = 4 d33 = c33 – c34 + c24 – c32 = 7 – 4 + 3 – 5 = 1
100 120 140
2.5.1. TRANSPORTNI PROBLEM “Najnegativniji” relativni koeficijent je d13. Količine trans-porta u vrhovima izabranog poligona su sljedeće: 100
0
80 25
40 25
Polja koja se umanjuju su x12 = 100, x34 = 25 i x23 = 80. Najveća moguća promjena transporta je 25 pa će sada vrijednosti transporta po poligonu biti: x13 = 0+25 = 25, x12 = 100–25 = 75, x32 = 25+25 = 50, x34 = 25–25 = 0, x24 = 40+25 = 65, x23 = 80–25 = 55
2.5.1. TRANSPORTNI PROBLEM Novi dopustivo rješenje je sada P1
P2
P3
P4
----------------------------------------------------------------------------------------------------8 9 4
S1 S2 S3
0
75
25
0
0
0
55
65
90
50
0
0
125
80
65
6 5
9 6
5 7
Zalihe 6
3 4
-----------------------------------------------------------------------------------------------------
Potrebe
90
Z = 75 9 + 25 4 + 55 5 + 65 3 + 90 5 + 50 6 = 1995 Relativni koeficijenti troškova za prazna polja su: d11 = c11 – c12 + c32 – c14 = 8 – 9 + 6 – 5 = 0 d14 = c14 – c13 + c23 – c24 = 6 – 4 + 5 – 3 = 4 d21 = c21 – c31 + c32 – c12 + c13 – c23 = =6–5+6–9+4–5=–3 d22 = c22 – c23 + c13 – c12 = 9 – 5 + 4 – 9 = – 1 d33 = c33 – c32 + c12 – c13 = 7 – 6 + 9 – 4 = 6 d34 = c34 – c32 + c12 – c13 + c23 – c24 = =4–6+9–4+5–3= 5
100 120 140
2.5.1. TRANSPORTNI PROBLEM “Najnegativniji” relativni koeficijent je d21. Količine trans-porta u vrhovima izabranog poligona su sljedeće: 75
0 90
25 55
50
Polja koja se umanjuju su x31 = 90, x12 = 75 i x23 = 55. Najveća moguća promjena transporta je 55 pa će sada vrijednosti transporta po poligonu biti: x21 = 0+55 = 55, x31 = 90–55 = 35, x32 = 50+55 = 105, x12 = 75–55 = 20, x13 = 25+55 = 80, x23 = 55–55 = 0
2.5.1. TRANSPORTNI PROBLEM Novi dopustivo rješenje je sada P1
P2
P3
P4
----------------------------------------------------------------------------------------------------8 9 4
S1 S2 S3
0
20
55
0
0
35
105
0
0
80
65
6 5
9 6
80
5 7
0 65
Zalihe 6
3 4
-----------------------------------------------------------------------------------------------------
Potrebe
90
125
Z = 20 9 + 80 4 + 55 6 + 65 3 + 35 5 + 105 6 = 1830 Relativni koeficijenti troškova za prazna polja su: d11 = c11 – c12 + c32 – c14 = 8 – 9 + 6 – 5 = 0 d14 = c14 – c12 + c32 – c31 + c21 – c24 = =6–9+6–5+6–3= 1 d22 = c22 – c21 + c31 – c32 = 9 – 6 + 5 – 6 = 2 d23 = c23 – c21 + c31 – c32 + c12 – c13 = =5–6+5–6+9–4= 3 d33 = c33 – c32 + c12 – c13 = 7 – 6 + 9 – 4 = 6 d34 = c34 – c31 + c21 – c24 = 4 – 5 + 6 – 3 = 2
100 120 140
2.5.1. TRANSPORTNI PROBLEM
Pošto su svi relativni koeficijenti troškova veći ili jednaki nuli, ovo rješenje je optimalno. x11 = 0 0 x21 = 55 65 x31 = 35 0
x12 = 20
x13 = 80 x14 =
x22 = 0
x23 = 0
x32 = 105 x33 = 0
x24 = x34 =
2.5.2. PROBLEM RASPOREDJIVANJA Postavka zadatka Problem raspoređivanja (asignacije) je specijalan oblik zadatka LP a po strukturi i načinu rješavanja, sličan je problemu transporta. Sam problem se predstaviti na sljedeći način: Rasporediti određeni broj izvršilaca (nekoga ili neče-ga što može da obavi ili proizvede neke aktivnosti – radnika, studenata, takmičara, prodavnica, novca, ...) na određeni broj mjesta (na kojima se mogu realizirati te aktivnosti – poslova, mašina, ispita, radnih mjesta, sportskih disciplina, pogona, lokacija, ...).
2.5.2. PROBLEM RASPOREDJIVANJA Pri tom jedan izvršilac može da bude raspore-đen na samo jedno mjesto, jednom mjestu može biti dodijeljen samo jedan izvršilac Svaki konkretni raspored proizvodi određeni efekat (povećanje vrijednosti ili povećanje troška). Potrebno je naći takav raspored izvršilaca na određena mjesta koji će dati optimalni efekat (maksimum ili minimum)
2.5.2. PROBLEM RASPOREDJIVANJA Pri definiranju modela raspoređivanja (asignacije) uobičajeno se koristi sljedeće obilježavanje: m – broj izvršilaca n – broj mjesta (radnih zadataka) cij, i = 1,2,…,m i j = 1,2,…,n – troškovi (dobiti) rasporeda izvršioca i na mjesto j xij, i = 1,2,…,m i j = 1,2,…,n – označava da li je izvršilac i raspoređen na mjesto j 1 - Ako je izvršilac i raspoređen na
2.5.2. PROBLEM RASPOREDJIVANJA Matematički model problema raspoređivanja Minimizirati Z = c11 x11 + c12 x12 + … + c1n x1n + + c21 x21 + c22 x22 + … + c2n x2n + (2.5.5) + ... + + cm1 xm1 + cm2 xm2 + … + cmn xmn = m
n
= Σ Σ cij xij i=1 j=1
uz ograničenja: m
Σ xij = 1
i=1
j = 1, 2, ..., n
(2.5.6)
i = 1, 2, ..., m
(2.5.7)
n
Σ xij = 1
j=1
xij = 0 ili 1
2.5.2. PROBLEM RASPOREDJIVANJA Ovako definiran model predstavlja poseban oblik modela LP, tzv. 0-1 programiranje. U odnosu na transportni model, ovdje je specifično, što su ponude iz svih ishodišta jednake jedinici, odnosno, sve potrebe odredišta su jednake jedinici. Da bi se problem raspoređivanja mogao riješiti potrebno je da broj izvršilaca i broj (radnih) mjesta bude jednak (m=n)
2.5.2. PROBLEM RASPOREDJIVANJA Ako je n = m imamo zatvoreni model raspoređivanja. Ako nije jednak broj izvršilaca i mjesta, to jest ako je m#n, tada imamo otvoreni model raspoređivanja. On se prevodi u zatvoreni, uvođenjem fiktivnih promjenljivih. Da bi se uravnotežio broj izvršilaca i mjesta, uvodi se fiktivno mjesto, odnosno fiktivni izvršilac. Tada se uzima da je efikasnost fiktivnog mjesta cif = 0, (i = 1, 2, …, m), odnosno, fiktivnog izvršioca cfj= 0, (j = 1, 2, …, n).
2.5.2. PROBLEM RASPOREDJIVANJA Metoda raspoređivanja za minimalnu vrijednost funkcije cilja – mađarska metoda Problem raspoređivanja se može riješiti korištenjem više metoda koje su, inače, razvijene za rješavanje drugih problema (Linearno programiranje, transportni problem). Problem raspoređivanja se može riješiti i ispitivanjem svih mogućih kombinacija i biranjem one kombinacije koja daje najbolji rezultat. Međutim, broj mogućih kombinacija je n! pa se već za n = 10 dobije broj kombinacija jednak 3,628.800. Jasno je da je ovakav pristup neprimjenljiv za iole veće
2.5.2. PROBLEM RASPOREDJIVANJA Ovaj problem se može riješiti i metodom grananja (Branch and Bound) koja omogu-ćava ispitivanje samo onih kombinacija koje su po određenom kriteriju bolje od nekih drugih koje odbacujemo. Međutim, danas se najčešće koristi metoda posebno razvijena za rješavanje problema raspoređivanja (mađarska metoda po tehnici Flooda).
2.5.2. PROBLEM RASPOREDJIVANJA Postupak se zasniva na korištenju matrice efikasnosti (troškova) C čiji su elementi koeficijenti funkcije cilja. Ako se pretpostavi da je broj izvršilaca i broj mjesta jednak, matrica C će biti: |̄ c11 | c21 C = | ... | ... |̱ cn1
c12 ... c22 ...
cn2 ...
c1n |̄ c2n | | | cnn |̱
Smatra se da je efikasnost veća što je
2.5.2. PROBLEM RASPOREDJIVANJA Postupak se realizira kroz tri koraka:
• Zadana matrica efikasnosti C se prevodi u
matricu C’ tako što se svi članovi svakog reda polazne matrice umanje za vrijednost najma-njeg elementa tog reda. Na taj način se u svakom redu dobije najmanje jedna nula. Zatim se, u tako dobijenoj matrici, svi članovi svake kolone umanje za vrijednost najmanjeg elementa te kolone. Na taj način formirana matrica sadrži
2.5.2. PROBLEM RASPOREDJIVANJA 2. Označavaju se nule matrice na sljedeći način: a. Polazeći od prvog reda matrice, nalaze se redovi koji imaju samo jednu nulu. Ta se nula označi a ostale nule u koloni sa označenom nulom se prekriže. Ovaj postupak se sprovodi dok ima redova sa jednom neoznačenom nulom. b. Isti postupak se primjeni na kolone. Postupci a. i b. se ponavljaju dok sve nule ne budu označene ili prekrižene. Ako se u svakom redu i u svakoj koloni nalazi po jedna označena nula postupak je završen. U suprotnom prelazi se na korak 3.
2.5.2. PROBLEM RASPOREDJIVANJA 3. Proizvodi se nova matrica slijede}im postupkom: a. Označe se strelicama redovi koji nemaju označene nule b. Označe se strelicama kolone koje u ozna-čenim redovima imaju prekrižene nule c. Označe se redovi koji imaju označenu nulu u označenoj koloni d. Ponavljaju se postupci b. i c. dok se lanac ne zatvori
2.5.2. PROBLEM RASPOREDJIVANJA e. Povuku se linije kroz neoznačene redove i označene kolone; kroz svaku označenu nulu (asignaciju) mora prolaziti jedna linija, dakle, treba da dobijemo onoliko linija koliko imamo označenih nula f. Formira se nova matrica, tako što se najmanji nepokriveni (neprecrtan linijom) element cij predhodne matrice: (1) oduzme od svakog nepokrivenog
elementa
(2) doda svakom elementu dva puta prekriženom, tj. elementima koji se nalaze na pre sjeku dviju linija Elementi prekriveni jednom linijom se prepišu u novu matricu.
2.5.2. PROBLEM RASPOREDJIVANJA Na ovako dobijenu matricu primjenjuje se korak 2. Ako se ne nađe optimalno rješenje, nastavlja se sa korakom 3. i to se nastavlja dok se ne nađe optimalno rješenje. Kada se dobije matrica sa potpunom asignacijom, koja sadrži n zaokruženih nula, iz nje se može odrditi optimalno rješenje. Zaokružene nule označavaju varijable čije su vrijednosti jednake jedinici (xij = 1).
2.5.2. PROBLEM RASPOREDJIVANJA Primjer 2.5.3. Naći optimalno rješenje problema raspo-ređivanja za sljedeću matricu koštanja: |
P1 P2 P3 P4 P5
----------------------------------------------------------------------
I1 I2 I3 I4 I5
| | | | |
11 9 13 21 14
17 7 16 24 10
8 12 15 17 12
16 6 12 28 11
20 15 16 26 15
2.5.2. PROBLEM RASPOREDJIVANJA Rješenje Sve članovi svakog reda polazne matrice umanje se za vrijednost najmanjeg elementa tog reda |
P1
P2
P3
P4
P5
----------------------------------------------------------------------
I1 I2 I3 I4 I5
| | | | |
3 3 1 4 4
9 1 4 7 0
0 6 3 0 2
8 0 0 11 1
12 9 4 9 5
2.5.2. PROBLEM RASPOREDJIVANJA Svi članovi svake kolone ove matrice umanje se za vrijednost najmanjeg elementa te kolone |
P1
P2
P3
P4
P5
----------------------------------------------------------------------
I1 I2 I3 I4 I5
| | | | |
2 2 0 3 3
9 1 4 7 0
0 6 3 0 2
8 0 0 11 1
8 5 0 5 1
2.5.2. PROBLEM RASPOREDJIVANJA Polazeći od prvog reda matrice, nalaze se redovi koji imaju samo jednu nulu. Ta se nula označi a ostale nule u koloni sa označenom nulom se prekriže. Isti postupak se uradi i sa kolonama dok sve nule ne budu obilježene ili prekrižene. |
P1
P2
P3
P4
P5
----------------------------------------------------------------------
I1 I2 I3 I4 I5
| | | | |
2 2 0 3 3
9 1 4 7 0
0 6 3 0 2
8 0 0 11 1
8 5 0 5 1
2.5.2. PROBLEM RASPOREDJIVANJA Postupak nije završen jer nemamo 5 obilježenih nula, naime izvršilac 4 i posao 5 nisu raspodjeljeni. Sada strelicama označimo redove koji nemaju označenih nula i kolone koje u označenim redovima imaju prekrižene nule |
P1
P2
P3
P4
P5
----------------------------------------------------------------------
I1 I2 I3 I4 I5
| | | | |
2 2 0 3 3
9 1 4 7 0
0 6 3 0 2
8 0 0 11 1
8 5 0 5 1
2.5.2. PROBLEM RASPOREDJIVANJA Označe se redovi koji imaju označenu nulu u označenoj koloni. Ponavljaju se postupci dok u označenim redovima ima prekriženih nula |
P1
P2
P3
P4
P5
----------------------------------------------------------------------
I1 I2 I3 I4 I5
| | | | |
2 2 0 3 3
9 1 4 7 0
0 6 3 0 2
8 0 0 11 1
8 5 0 5 1
2.5.2. PROBLEM RASPOREDJIVANJA Povuku se linije kroz neoznačene redove i označene kolone; kroz svaku zaokruženu nulu (asignaciju) mora da prolazi jedna i samo jedna linija, dakle, treba da dobijemo onoliko linija koliko imamo zaokruženih nula |
P1
P2
P3
P4
P5
----------------------------------------------------------------------
I1 I2 I3 I4 I5
| | | | |
2 2 0 3 3
9 1 4 7 0
0 6 3 0 2
8 0 0 11 1
8 5 0 5 1
2.5.2. PROBLEM RASPOREDJIVANJA Primjenjuje se Korak 2., tj. nalaze se redovi koji imaju samo jednu nulu i ta se nula označi a ostale nule u koloni sa označenom nulom se prekriže. b. Isti postupak se primjeni na kolone. |
P1
P2
P3
P4
P5
----------------------------------------------------------------------
I1 I2 I3 I4 I5
| | | | |
0 2 0 2 3
7 1 4 5 0
0 8 5 0 4
6 0 0 9 1
6 5 0 3 1
2.5.2. PROBLEM RASPOREDJIVANJA Dobili smo optimalno rješenje: x11 = 1 x24 = 1 x35 = 1 x43 = 1 x52 = 1 Z = c11 + c24 + c35 + c43 + c52 = = 11 + 6 + 16 + 17 + 10 = 60
3. LITERATURA • • • • • • • • • •
Backović M., Vuleta J., „Ekonomsko matematički metodi i modeli”, CID, Beograd, 2000. Bronštejn I.N. i dr., „Matematički priručnik”, Golden marketing-Tehnička knjiga, Zagreb, 2004. Carter M.W., Price C.C., “Operations Research – A Practical Introduction”, CRC Press, 2001. Chandrasekhara Rao K., “Operations Research”, Alpha Science International Ltd., 2005. Hillier F.S., Lieberman G.J., “Introduction to Operations Research”, McGrow-Hill, New York, 2005. Krčevinac S. i dr., “Operaciona istraživanja”, Fakultet organizacionih nauka, Beograd, 2004. Neralić L., „Uvod u matematičko programiranje 1”, Element, Zagreb, 2003. Petrić J.: “Operaciona istraživanja”, Nauka, Beograd, 1997. Pierre D.A., “Optimization theory with applications”, Dover publications, NewYork, 1986. Zečević T., “Operaciona istraživanja”, Naučna knjiga, Beograd, 1974. šk.god. 2007/2008.
dr Tadej Mateljan
Related Documents
Oi106oitransportrasporedjivanje
May 2020 0More Documents from "jablana"
Oi106oitransportrasporedjivanje
May 2020 0