Transportni Problem LP-A OPTIPLANPOK

May 5, 2018 | Author: Anonymous | Category: Documents
Report this link


Description

Katedra za upravljanje proizvodnjom Transportni problem LP-a Optimiranje i planiranje pokusa Miro Hegedić [email protected] 1 Katedra za upravljanje proizvodnjom Sadržaj • Uvod • Osnovne značajke TP-a • Opći slučaj • Matematički model TP-a • Određivanje početnog rješenja • Određivanje optimalnog rješenja 2 Katedra za upravljanje proizvodnjom Cilj transportnog problema • Prvi objavili radove iz ovog područja – L.V.Kantorović 1939.godine – L.F.Hičkok 1941.god. Cilj transportnog problema LP-a: Odrediti najbolji način transporta od više izvora sredstava tj. ishodišta (npr.skladišta sirovina, materijala, proizvodna poduzeća koja opskrbljuju potrošača) do korisnika izvora sredstava tj.odredišta. 3 Katedra za upravljanje proizvodnjom Problem minimizacije Najčešće se razmatra problem minimizacije transportnih troškova prijevoza neke robe. 4 Izvor: J.Heizer, B.Render: Operations Management, 10th edition Katedra za upravljanje proizvodnjom Osnovne značajke transportnoga problema • Izvori sredstava, tj. ishodišta (npr. skladišta sirovina, materijala, proizvodna poduzeća koja opskrbljuju potrošača) označavaju se s R1, R2, ...., Ri (i = 1, 2, ..., r), a njihov kapacitet s xi0. • Korisnici izvora sredstava, tj. odredišta označavaju se sa S1, S2, ..., Sj (j = 1, 2, ..., s), a njihovi kapaciteti s x0j. • xij - količina materijala koja se preveze iz bilo kojeg i-tog ishodišta u bilo koje j-to odredište, • cij - trošak transporta jedinice tereta iz bilo kojeg i-tog ishodišta u bilo koje j-to odredište. 5 Katedra za upravljanje proizvodnjom Opći slučaj Mogu nastupiti dvije situacije: 1. Suma ponude jednaka je sumi potražnje, u kojem slučaju se govori o zatvorenom modelu transporta, tj. 2. Suma ponude nije jednaka sumi potražnje, a u tom se slučaju govori o otvorenom modelu transporta, tj. Za drugi slučaj: potrebno je model zatvoriti uvođenjem fiktivnog ishodišta, odnosno odredišta (ovisno o tome nedostaje li ponude ili potražnje). 6      r 1i s 1j ojio xx      r 1i s 1j ojio xx Katedra za upravljanje proizvodnjom Rješavanje transportnog problema 1. Za zadani problem potrebno je definirati: 1. Funkciju cilja – F(x) 2. Sistem ograničenja. Iz definicije transportnog problema: Potrebno je odrediti nenegativne vrijednosti varijable xij (i = 1, 2, ..., r ; j = 1, 2, ..., s) tako da se ostvare minimalni ukupni troškovi transporta iz r-tog ishodišta u s-to odredište, a da se pri tome zadovolje uvjeti ponude i potražnje. 7 Katedra za upravljanje proizvodnjom Primjer 1 8 TRANSPORTNI PROBLEM LP-a Jedinični troškovi ci,j Odredišta Ponuda ishodišta xio S1 S2 S3 S4 Ishodišta R1 8 18 9 10 60 R2 10 12 3 15 80 R3 12 15 16 4 60 Potražnja odredišta xoj 40 60 30 70 200 TRANSPORTNI PROBLEM LP-a Prevezene količine xi,j Odredišta Ponuda ishodišta xio S1 S2 S3 S4 Ishodišta R1 x11 x12 x13 x14 60 R2 x21 x22 x23 x24 80 R3 x31 x32 x33 x34 60 Potražnja odredišta xoj 40 60 30 70 200 Katedra za upravljanje proizvodnjom Primjer 1 9 F(x) = 8  x11 + 18  x12 + 9  x13 + 10  x14 + 10  x21 + 12  x22 + 3  x23 + 15  x24 + 12  x31 + 15  x32 + 16  x33 + 4  x34  MIN Funkcija cilja glasi: ponude uvjeti 60xxxx 80xxxx 60xxxx 34333231 24232221 14131211         uz ograničenja: potražnje uvjeti 70xxx 30xxx 60xxx 40xxx 342414 332313 322212 312111            TRANSPORTNI PROBLEM LP-a Jedinični troškovi ci,j Odredišta Ponuda ishodišta xio S1 S2 S3 S4 Ishodišta R1 8 18 9 10 60 R2 10 12 3 15 80 R3 12 15 16 4 60 Potražnja odredišta xoj 40 60 30 70 200 Katedra za upravljanje proizvodnjom Matematička formulacija problema: 10 minxcF(x) r 1i s 1j ijij    ponude uvjeti xx ............. xx xx s 1j r0rj s 1j 202j s 1j 101j                     potražnje uvjeti xx ............. xx xx r 1i 0sis r 1i 02i2 r 1i 01i1                     xij  0 (i = 1, 2, ..., r ; j = 1, 2, ..., s) - uvjet nenegativnosti varijabli Katedra za upravljanje proizvodnjom U općem slučaju 11 Može se postaviti ukupno (r+s) jednadžbi • r jednadžbi za ishodišta • s jednadžbi za odredišta Zbog uvjeta jednakosti sume ponude i sume potražnje • broj neovisnih jednadžbi bit će (r + s - 1) Broj neovisnih varijabli određuje broj varijabli xij koje mogu poprimiti vrijednost veću od nule (xij > 0) u nekom otvorenom nedegeneriranom rješenju. Varijable koje imaju vrijednost strogo veću od nule (>), zovu se bazne varijable. Katedra za upravljanje proizvodnjom U općem slučaju (1) 12 Ako je broj baznih varijabli manji od (r + s - 1), tada će nastupiti degeneracija, a takvo se rješenje u teoriji LP-a naziva osnovno degenerirano rješenje. Katedra za upravljanje proizvodnjom Značajke metoda za rješavanje TP-a Problem rješavaju u dvije faze: a) Određivanje početnog rješenja, b) Poboljšanje početnog rješenja ( što je u većini slučajeva iterativni postupak pronalaženju konačnog, tj. optimalnog rješenja) 13 Katedra za upravljanje proizvodnjom Određivanje početnog rješenja 14 Metoda sjeverozapadnog kuta (Northwest corner rule) Kao polaznu tablicu, uzima tablicu u kojoj su dane ponude ishodišta i potražnje odredišta. 1. Polazi se od lijevog gornjeg kuta, te se uspoređuju potrebe x10 i x01. a) Ako je x10 > x01  x11 = x01, a razlika x10 - x01 stavlja se u sljedeći stupac u istom redu ( x12 = x10 -x01 ) Ako je potražnja odredišta S2 manja od ove razlike: x12 = x02, a razlika x10 - x01 - x02 prenosi se u treći stupac u istom redu (sve dok se ponuda ishodišta R1 ne iskoristi) Katedra za upravljanje proizvodnjom Određivanje početnog rješenja 15 Metoda sjeverozapadnog kuta (Northwest corner rule) b) Ako je x10 = x01  x11 = x10 = x01 zatim se prelazi na određivanje varijable x22 (tj. ide se dijagonalno od lijevog gornjeg kuta do donjeg desnog kuta). c) Ako je x10 < x01,  x11 = x10, razlika (x01 - x10 stavlja se u drugi redak u istom stupcu (prelazi se na određivanje varijable x21). Postupak dalje slično kao pod a), samo se mora uzeti u obzir da je ovdje prelazak vertikalan. Katedra za upravljanje proizvodnjom Primjer 2 16 Metoda sjeverozapadnog kuta (Northwest corner rule) TRANSPORTNI PROBLEM LP-a ci,j S1 S2 S3 S4 S5 xio R1 4 2 5 7 6 20 R2 7 8 3 4 5 110 R3 2 1 4 3 2 120 xoj 70 40 30 60 50 250/250 F(x) = 4  x11 + 2  x12 + 5  x13 + 7  x14 + 6  x15 + 7  x21 + 8  x22 + 3  x23 + 4  x24 + 5 x25 +2  x31 + 1  x32 + 4  x33 + 3  x34 + 2  x35  MIN ponude uvjeti 201xxxxx 101xxxxx 20xxxxx 3534333231 2524232221 1514131211         potražnje uvjeti 05xxx 06xxx 30xxx 04xxx 07xxx 352515 342414 332313 322212 312111               Katedra za upravljanje proizvodnjom Primjer 2 17 Metoda sjeverozapadnog kuta (Početno rješenje) TRANSPORTNI PROBLEM LP-a xi,j S1 S2 S3 S4 S5 xio R1 20 R2 110 R3 120 xoj 70 40 30 60 50 250/250 c) Ako je x10 < x01,  x11 = x10, razlika (x01 - x10 stavlja se u drugi redak u istom stupcu (prelazi se na određivanje varijable x21). Postupak dalje slično kao pod a), samo se mora uzeti u obzir da je ovdje prelazak vertikalan. 20 50 40 20 10 60 50 F(x)=1130 Katedra za upravljanje proizvodnjom Određivanje početnog rješenja 18 Vogelova metoda Vrlo efikasna u određivanju prvog osnovnog rješenja transportnog problema. Postupak rada može se prikazati u četiri faze: 1. Za svako ishodište i odredište potrebno je odrediti kaznu za nekorištenje najjeftinijeg puta: • Kazna se računa kao razlika dviju najmanjih cijena za svaki redak i stupac. • Ako su u nekom retku (stupcu) dvije cijene iste, kazna je za to odredište (ishodište) jednaka nuli. Katedra za upravljanje proizvodnjom Određivanje početnog rješenja 19 Vogelova metoda 2. Izabrati redak ili stupac sa najvećom kaznom i u njemu polje (i, j) s minimalnim troškom transporta. U to se polje matrice unosi vrijednost varijable xij = min (xio, xoj). Time se iscrpljuje i-ti redak ili stupac, pa se izostavlja iz daljnjeg razmatranja. 3. Kad je redak (stupac) izostavljen, ponovo se računa kazna za svaki redak (stupac). 4. Potrebno je ponoviti faze 2 i 3 dok se ne dobije cijelo početno osnovno rješenje. Katedra za upravljanje proizvodnjom Određivanje početnog rješenja 20 Vogelova metoda (Posebni slučajevi) U drugoj fazi postoji više redaka ili stupaca sa jednakim maksimalnim kaznama. Postupak: 1. Pogleda se je li minimalna cijena u jednom od tih redaka (stupaca) ujedno i minimalna u stupcu (retku) u kojem se nalazi? Ako je, bira se taj redak (stupac). Ako nije, računaju se sekundarne kazne za retke i stupce koji imaju istu kaznu. Katedra za upravljanje proizvodnjom Određivanje početnog rješenja 21 Vogelova metoda (Posebni slučajevi) 2. Računanje sekundarne kazne Izračuna se razlika između drugog najmanjeg troška u retku i najmanjeg troška u stupcu što sadrži taj najmanji trošak. (Sekundarna kazna za stupac računa se na isti način). 3. Odabere se redak ili stupac sa najvećom sekundarnom kaznom. Katedra za upravljanje proizvodnjom Određivanje početnog rješenja 22 Vogelova metoda (Primjer 3) (1) TRANSPORTNI PROBLEM LP-a Jedinični troškovi ci,j Odredišta Ponuda ishodišta xio S1 S2 S3 S4 Ishodišta R1 8 18 9 10 60 R2 10 12 3 15 80 R3 12 15 16 4 60 Potražnja odredišta xoj 40 60 30 70 200 PRIMJENA VOGELOVE METODE ci,j Odredišta xio c'ioS1 S2 S3 S4 Is h o d iš ta R1 8 18 9 10 60 1 R2 10 12 3 15 80 7 R3 12 15 16 4 60 8 xoj 40 60 30 70 200 c'oj 2 3 6 6  xij = min (xio, xoj) x34 = min (60, 70) = 60 Katedra za upravljanje proizvodnjom Određivanje početnog rješenja 23 Vogelova metoda (Primjer 3) (2) PRIMJENA VOGELOVE METODE xi,j Odredišta S1 S2 S3 S4 Is h o d iš ta R1 R2 R3 60  xij = min (xio, xoj) x23 = min (80, 30) = 30 SUPTABLICA 2x4 ci,j Odredišta xio c'ioS1 S2 S3 S4 Is h o d iš ta R1 8 18 9 10 60 1 R2 10 12 3 15 80 7 xoj 40 60 30 10 140 c'oj 2 6 6 5 30 Katedra za upravljanje proizvodnjom Određivanje početnog rješenja 24 Vogelova metoda (Primjer 3) (3) PRIMJENA VOGELOVE METODE xi,j Odredišta S1 S2 S3 S4 Is h o d iš ta R1 R2 30 R3 60  xij = min (xio, xoj) x23 = min (50, 60) = 50 SUPTABLICA 2x3 ci,j Odredišta xio c'io S1 S2 S4 Is h o d iš ta R1 8 18 10 60 2 R2 10 12 15 50 2 xoj 40 60 10 110 c'oj 2 6 5 50 Katedra za upravljanje proizvodnjom Određivanje početnog rješenja 25 Vogelova metoda (Primjer 3) (4) PRIMJENA VOGELOVE METODE xi,j Odredišta S1 S2 S3 S4 Is h o d iš ta R1 R2 50 30 R3 60 SUPTABLICA 1x3 ci,j Odredišta xio c'io S1 S2 S4 R1 8 18 10 60 2 xoj 40 10 10 60 𝑥𝑖𝑗 = 40 10 0 50 0 0 0 30 10 0 0 60 𝐹 𝑥 = 40 ∗ 8 + 10 ∗ 18 + 10 ∗ 10 + 50 ∗ 12 + 30 ∗ 3 + 60 ∗ 4 = 𝟏𝟓𝟑𝟎 𝑀𝑒𝑡𝑜𝑑𝑎 𝑠𝑗𝑒𝑣𝑒𝑟𝑜𝑧𝑎𝑝𝑎𝑑𝑛𝑜𝑔 𝑘𝑢𝑡𝑎: 𝐹 𝑥 = 1640 40 10 10 Katedra za upravljanje proizvodnjom Primjer 4 26 Vogelovom metodom pronaći rješenje F(x) = 3  x11 + 9  x12 + 8  x13 + 10  x14 + 4  x15 + 6  x21 + 10  x22 + 3  x23 + 2  x24 + 3 x25 + 3  x31 + 2  x32 + 7  x33 + 10  x34 + 3  x35 + 3  x41 + 5  x42 + 3  x43 + 2  x44 + 8  x45  MIN ponude uvjeti 81xxxxx 91xxxxx 13xxxxx 28xxxxx 4544434241 3534333231 2524232221 1514131211            potražnje uvjeti 8xxxx 20xxxx 10xxxx 16xxxx 24xxxx 45352515 44342414 43332313 42322212 41312111               TRANSPORTNI PROBLEM LP-a ci,j S1 S2 S3 S4 S5 xio R1 3 9 8 10 4 28 R2 6 10 3 2 3 13 R3 3 2 7 10 3 19 R4 3 5 3 2 8 18 xoj 24 16 10 20 8 78/78 Katedra za upravljanje proizvodnjom Primjer 4 27 Vogelovom metodom pronaći rješenje TRANSPORTNI PROBLEM LP-a ci,j S1 S2 S3 S4 S5 xio c'io R1 3 9 8 10 4 28 1 R2 6 10 3 2 3 13 1 R3 3 2 7 10 3 19 1 R4 3 5 3 2 8 18 1 xoj 24 16 10 20 8 78/78 c'oj 0 3 0 0 0 TRANSPORTNI PROBLEM LP-a xij /ci,j S1 S2 S3 S4 S5 xio c'io R1 3 9 8 10 4 28 1 R2 6 10 3 2 3 13 1 R3 3 16 7 10 3 19 3 1 R4 3 5 3 2 8 18 1 xoj 2 4 16 10 20 8 78/78 c'oj 0 3 0 0 0 Katedra za upravljanje proizvodnjom Primjer 4 28 Vogelovom metodom pronaći rješenje TRANSPORTNI PROBLEM LP-a xij /ci,j S 1 S2 S3 S4 S5 xio c'io C’’io R1 3 8 10 4 28 1 1 R2 6 3 2 3 13 1 0 R3 3 16 7 10 3 3 0 R4 3 3 2 8 18 1 0 xoj 2 4 10 20 8 78/78 c'oj 0 0 0 0 TRANSPORTNI PROBLEM LP-a xij /ci,j S1 S2 S3 S4 S5 xio c'io C’’io R1 24 8 10 4 28 4 1 1 R2 6 3 2 3 13 1 0 R3 3 16 7 10 3 3 0 R4 3 3 2 8 18 1 0 xoj 24 10 20 8 78/78 c'oj 0 0 0 0 Katedra za upravljanje proizvodnjom TRANSPORTNI PROBLEM LP-a xij /ci,j S1 S2 S3 S4 S5 xio c'io C’’io R1 24 8 10 4 4 4 5 R2 3 2 3 13 1 R3 16 7 10 3 3 4 4 R4 3 2 8 18 1 xoj 10 20 8 4 78/78 c'oj 0 0 0 Primjer 4 29 Vogelovom metodom pronaći rješenje TRANSPORTNI PROBLEM LP-a xij /ci,j S1 S2 S3 S4 S5 xio c'io C’’io R1 24 8 10 4 4 4 5 R2 3 2 3 13 1 R3 16 7 10 3 3 4 4 R4 3 2 8 18 1 xoj 10 20 8 78/78 c'oj 0 0 0 Katedra za upravljanje proizvodnjom Primjer 4 30 Vogelovom metodom pronaći rješenje TRANSPORTNI PROBLEM LP-a xij /ci,j S1 S2 S3 S4 S5 xio c'io R1 24 4 R2 3 2 3 13 1 R3 16 7 10 3 3 4 R4 3 2 8 18 1 xoj 10 20 4 78/78 c'oj 0 0 0 TRANSPORTNI PROBLEM LP-a xij /ci,j S1 S2 S3 S4 S5 xio c'io R1 24 4 R2 3 2 3 13 1 R3 16 7 10 3 3 4 R4 3 2 8 18 1 xoj 10 20 4 1 78/78 c'oj 0 0 0 Katedra za upravljanje proizvodnjom Primjer 4 31 Vogelovom metodom pronaći rješenje TRANSPORTNI PROBLEM LP-a xij /ci,j S1 S2 S3 S4 S5 xio c'io R1 24 4 R2 3 2 3 13 1 R3 16 3 R4 3 2 8 18 1 xoj 10 20 1 78/78 c'oj 0 0 5 TRANSPORTNI PROBLEM LP-a xij /ci,j S1 S2 S3 S4 S5 xio c'io R1 24 4 R2 3 2 1 13 12 1 R3 16 3 R4 3 2 8 18 1 xoj 10 20 1 78/78 c'oj 0 0 5 Katedra za upravljanje proizvodnjom Primjer 4 32 Vogelovom metodom pronaći rješenje TRANSPORTNI PROBLEM LP-a xij /ci,j S1 S2 S3 S4 S5 xio c'io R1 24 4 R2 3 2 1 12 1 R3 16 3 R4 3 2 18 1 xoj 10 20 78/78 c'oj 0 0 TRANSPORTNI PROBLEM LP-a xij /ci,j S1 S2 S3 S4 S5 xio c'io R1 24 4 R2 3 2 1 12 1 R3 16 3 R4 3 18 18 1 xoj 10 20 2 78/78 c'oj 0 0 Katedra za upravljanje proizvodnjom Primjer 4 33 Vogelovom metodom pronaći rješenje TRANSPORTNI PROBLEM LP-a xij /ci,j S1 S2 S3 S4 S5 xio c'io R1 24 4 R2 3 2 1 12 1 R3 16 3 R4 18 xoj 10 2 78/78 c'oj 0 0 TRANSPORTNI PROBLEM LP-a xi,j S1 S2 S3 S4 S5 xio c'io R1 24 4 R2 10 2 1 12 R3 16 3 R4 18 xoj 10 2 78/78 c'oj F(x) = 24  3 + 4  4 + 10  3+ 2  2+ 1  3+ 16  2+ 3  3+ 18  2 = 202 Katedra za upravljanje proizvodnjom Određivanje optimalnog rješenja 34 Mogu se koristiti sljedeće metode (Posebni slučajevi) 1. Stepping-Stonova metoda 2. MODI metoda 3. Ford-Fulkersonova metoda Postupak: 1. Provjerava se je li početno osnovno rješenje optimalno. 2. Pronalazi se bolje rješenje. Katedra za upravljanje proizvodnjom Stepping-Stonova metoda (Metoda skakanja s kamena na kamen) 35 Ispitivanje optimalnosti osnovnog rješenja 1. Računanje relativnih troškova za nezauzeta polja matrice transporta. DEGENERACIJA KOD TP-a ci,j xi,j Odredišta xio S1 S2 S3 Is h o d iš ta R1 8 𝟑𝟎 10 4 30 R2 9 3 𝟐𝟎 6 20 R3 6 8 𝟐𝟎 5 𝟐𝟎 40 R4 7 9 3 𝟑𝟎 30 xoj 30 40 50 120 120 Katedra za upravljanje proizvodnjom Stepping-Stonova metoda (Metoda skakanja s kamena na kamen) 36 Ispitivanje optimalnosti osnovnog rješenja 1. Računanje relativnih troškova za nezauzeta polja matrice transporta. Relativni troškovi (dij)  pokazuju za koliko bi se promijenili ukupni troškovi transporta, ako bi se jedinica robe transportirala preko nezauzetog polja. a. Pozitivni relativni troškovi – povećanje transportnih troškova. b. Negativni relativni troškovi – smanjenje transportnih troškova. Optimalni plan transporta  u osnovnom rješenje ne postoji niti jedan negativni relativni trošak. Katedra za upravljanje proizvodnjom Degeneracija kod TP-a 37 Nastupa kad je broj bazičnih varijabli manji od (r+s-1) Primjer 5 DEGENERACIJA KOD TP-a ci,j Odredišta xio S1 S2 S3 Is h o d iš ta R1 8 10 4 30 R2 9 3 6 20 R3 6 8 5 40 R4 7 9 3 30 xoj 30 40 50 120/120 Prvo osnovno rješenje dobiveno Metodom sjeverozapadnog kuta DEGENERACIJA KOD TP-a ci,j xi,j Odredišta xio S1 S2 S3 Is h o d iš ta R1 8 𝟑𝟎 10 4 30 R2 9 3 𝟐𝟎 6 20 R3 6 8 𝟐𝟎 5 𝟐𝟎 40 R4 7 9 3 𝟑𝟎 30 xoj 30 40 50 120 120 r+s-1 = 4+3-1 = 6 Broj bazičnih varijabli = 5 *Degeneracija F(x) = 650 Varijable koje imaju vrijednost strogo veću od nule (>), zovu se bazne varijable. ε – fiktivna bazna varijabla Katedra za upravljanje proizvodnjom Degeneracija kod TP-a 38 Primjer 5 DEGENERACIJA KOD TP-a ci,j Odredišta xio S1 S2 S3 Is h o d iš ta R1 8 𝟑𝟎 10 4 30 R2 9 3 𝟐𝟎 6 20 R3 6 8 𝟐𝟎 5 𝟐𝟎 40 R4 7 9 3 𝟑𝟎 30 xoj 30 40 50 120 120 d12 = c12 - c32 + c31 - c11 = 10 – 8 + 6 – 8 = 0 d13 = c13 - c33 + c31 - c11 = 4 – 5 + 6 – 8 = -3 d21 = c21 - c22 + c32 – c31 = 9 – 3 + 8 – 6 = 8 d23 = c23 - c33 + c32 - c22 = 6 – 5 + 8 – 3 = 6 d41 = c41 - c43 + c33 - c31 = 7 – 3 + 5 – 6 = 3 d42 = c42 - c43 + c33 - c32 = 9 – 3 + 5 – 8 = 3 c12 (1,2) c11 c31 c32 - + - min (20-x=0, 30-x=0) x=20 x11 = 10, x33 = 0 x13 = 20, x31 = 20 ε Katedra za upravljanje proizvodnjom Degeneracija kod TP-a 39 Primjer 5 DEGENERACIJA KOD TP-a ci,j Odredišta xio S1 S2 S3 Is h o d iš ta R1 8 30− 𝒙 10 4 +𝒙 30 R2 9 3 20 6 20 R3 6 𝜀 + 𝒙 8 20 5 20− 𝒙 40 R4 7 9 3 30 30 xoj 30 40 50 120 120 d13 = c13 - c33 + c31 - c11 = 4 – 5 + 6 – 8 = -3 c13 (1,3) c11 c31 c33 - + - min (20-x=0, 30-x=0) x=20 x11 = 10, x33 = 0 x13 = 20, x31 = 20 Katedra za upravljanje proizvodnjom Degeneracija kod TP-a 40 Primjer 5 DEGENERACIJA KOD TP-a ci,j Odredišta xio S1 S2 S3 Is h o d iš ta R1 8 10 10 4 20 30 R2 9 3 20 6 20 R3 6 20 8 20 5 40 R4 7 9 3 30 30 xoj 30 40 50 120 120 min (20-x=0, 30-x=0) x=20 x11 = 10, x33 = 0 x13 = 20, x31 = 20 F(x)’ = F(x)+d13*x F(x)’ = 650+(-3)*20 F(x)’ = 590 Katedra za upravljanje proizvodnjom Primjer 6 41 TRANSPORTNI PROBLEM LP-a xi,j S1 S2 S3 S4 S5 xio R1 20 20 R2 50 40 20 110 R3 10 60 50 120 xoj 70 40 30 60 50 250/250 Stepping-Stoneovom metodom pronaći optimalno rješenje. r+s-1 = 5+3-1 = 7 Broj bazičnih varijabli = 7 *nema degeneracija TRANSPORTNI PROBLEM LP-a xi,j S1 S2 S3 S4 S5 xio R1 20 -3 5 8 8 20 R2 50 40 20 2 4 110 R3 -6 -8 10 60 50 120 xoj 70 40 30 60 50 250/250 Prvo optimalno rješenje F(x) = 1130 Katedra za upravljanje proizvodnjom Primjer 6 42 Stepping-Stoneovom metodom pronaći optimalno rješenje. TRANSPORTNI PROBLEM LP-a xi,j S1 S2 S3 S4 S5 xio R1 20 -3 5 8 8 20 R2 50 40 20 2 4 110 R3 -6 -8 10 60 50 120 xoj 70 40 30 60 50 250/250 Prvo optimalno rješenje TRANSPORTNI PROBLEM LP-a xi,j S1 S2 S3 S4 S5 xio R1 20 20 R2 50 30 30 110 R3 10 60 50 120 xoj 70 40 30 60 50 250/250 F(x)’ = F(x)+d32*x F(x)’ = 1130+(-8)*10 F(x)’ = 1050 x = 10 Katedra za upravljanje proizvodnjom Zadatak 1 43 1. Za transportni problem zadan tablicom potrebno je odrediti matematički model transporta te izračunati vrijednost funkcije cilja za optimalno rješenje TRANSPORTNI PROBLEM LP-a ci,j Odredišta xioS1 S2 S3 S4 Is h o d iš ta R1 7 3 2 10 400 R2 4 12 6 8 150 R3 1 9 10 6 500 xoj 350 300 200 100 950\ 1050 Katedra za upravljanje proizvodnjom Zadatak 1 44 Rješenje TRANSPORTNI PROBLEM LP-a xi,j Odredišta xioS1 S2 S3 S4 S5 Is h o d iš ta R1 7 / 350 –x 3 / 50 +x 2 / (-2) 10 / (10) 0 / (6) 400 R2 4 / (-12) 12 / 150 6 / (-7) 8 / (-1) 0 / (-3) 150 R3 1 / (-12) +x 9 / 100 -x 10 / 200 6 / 100 0 / 100 500 xoj 350 300 200 100 100 950\ 1050 Katedra za upravljanje proizvodnjom Zadatak 1 45 Rješenje – Stepping Stoneova Metoda TRANSPORTNI PROBLEM LP-a xi,j Odredišta xioS1 S2 S3 S4 S5 Is h o d iš ta R1 7 / 250 3 / 150 2 / (-2) 10 / (10) 0 / (6) 400 R2 4 / (-12) 12 / 150 6 / (-7) 8 / (-1) 0 / (-3) 150 R3 1 / 100 9 / 0 10 / 200 6 / 100 0 / 100 500 xoj 350 300 200 100 100 950\ 1050 Katedra za upravljanje proizvodnjom Zadatak 2 46 2. Za transportni problem zadan tablicom potrebno je odrediti matematički model transporta te izračunati vrijednost funkcije cilja za optimalno rješenje. (Vogelova metoda) TRANSPORTNI PROBLEM LP-a ci,j Odredišta xioS1 S2 S3 S4 Is h o d iš ta R1 18 2 3 15 300 R2 6 12 7 6 250 R3 4 6 10 2 200 xoj 200 250 250 150 850\ 750 Katedra za upravljanje proizvodnjom Zadatak 2 47 Rješenje TRANSPORTNI PROBLEM LP-a xi,j Odredišta xio c'io S1 S2 S3 S4 Is h o d iš ta R1 18 / 2 / 3 / 15 / 300 1 R2 6 / 12 / 7 / 6 / 250 0 R3 4 / 6 / 10 / 2 / 200 2 R4 0 / 100 0 / 0 / 0 / 100 0 xoj 200 100 250 250 150 850\850 c'oj 4 2 3 2 Katedra za upravljanje proizvodnjom Zadatak 2 48 Rješenje TRANSPORTNI PROBLEM LP-a xi,j Odredišta xio c'io S1 S2 S3 S4 Is h o d iš ta R1 18 / 2 / 250 3 / 15 / 300 50 1 R2 6 / 12 / 7 / 6 / 250 0 R3 4 / 6 / 10 / 2 / 200 2 R4 0 / 100 100 xoj 200 100 250 250 150 850\850 c'oj 2 4 4 4 c'sek 4 1 0 Katedra za upravljanje proizvodnjom Zadatak 2 49 Rješenje TRANSPORTNI PROBLEM LP-a xi,j Odredišta xio c'io S1 S2 S3 S4 Is h o d iš ta R1 18 / 2 / 250 3 / 50 15 / 300 50 12 R2 6 / 7 / 6 / 250 0 R3 4 / 10 / 2 / 200 2 R4 0 / 100 100 xoj 200 100 250 250 200 150 850\850 c'oj 2 4 4 Katedra za upravljanje proizvodnjom Zadatak 2 50 Rješenje TRANSPORTNI PROBLEM LP-a xi,j Odredišta xio c'io S1 S2 S3 S4 Is h o d iš ta R1 2 / 250 3 / 50 300 50 R2 6 / 7 / 6 / 250 0 R3 4 / 10 / 2 / 150 200 50 2 R4 0 / 100 100 xoj 200 100 250 250 200 150 850\850 c'oj 2 3 4 Katedra za upravljanje proizvodnjom Zadatak 2 51 Rješenje TRANSPORTNI PROBLEM LP-a xi,j Odredišta xio c'io S1 S2 S3 S4 Is h o d iš ta R1 2 / 250 3 / 50 300 50 R2 6 / 7 / 250 1 R3 4 / 50 10 / 2 / 150 200 50 6 R4 0 / 100 100 xoj 200 100 50 250 250 200 150 850\850 c'oj 2 3 Katedra za upravljanje proizvodnjom Zadatak 2 52 Rješenje TRANSPORTNI PROBLEM LP-a xi,j Odredišta xio c'io S1 S2 S3 S4 Is h o d iš ta R1 2 / 250 3 / 50 300 50 R2 6 / 50 7 / 200 250 R3 4 / 50 2 / 150 200 50 R4 0 / 100 100 xoj 200 100 50 250 250 200 150 850\850 c'oj 2 3 Katedra za upravljanje proizvodnjom Zadatak 2 53 Rješenje TRANSPORTNI PROBLEM LP-a xi,j Odredišta xio c'io S1 S2 S3 S4 Is h o d iš ta R1 2 / 250 3 / 50 300 50 R2 6 / 50 7 / 200 250 R3 4 / 50 2 / 150 200 50 R4 0 / 100 100 xoj 200 100 50 250 250 200 150 850\850 c'oj F(x)=2850 Katedra za upravljanje proizvodnjom Zadatak 3 54 3. Za transportni problem zadan tablicom potrebno je odrediti matematički model transporta te izračunati vrijednost funkcije cilja za optimalno rješenje. (Vogelova metoda) TRANSPORTNI PROBLEM LP-a ci,j Odredišta xioS1 S2 S3 Is h o d iš ta R1 70 30 60 75 R2 40 80 20 40 R3 10 50 90 35 xoj 20 45 30 95 \ 150 Katedra za upravljanje proizvodnjom Zadatak 3 55 Rješenje TRANSPORTNI PROBLEM LP-a xi,j Odredišta xio c'io S1 S2 S3 S4 Is h o d iš ta R1 70 / 30 / 60 / 0 / 75 30 R2 40 / 80 / 20 / 0 / 40 20 R3 10 / 50 / 90 / 0 / 35 10 xoj 20 45 30 55 150\ 150 c'oj 30 20 40 0 Katedra za upravljanje proizvodnjom Zadatak 3 56 Rješenje TRANSPORTNI PROBLEM LP-a xi,j Odredišta xio c'io S1 S2 S3 S4 Is h o d iš ta R1 70 / 30 / 60 / 0 / 75 30 R2 40 / 80 / 20 / 20 0 / 40 20 R3 10 / 50 / 90 / 0 / 35 10 xoj 20 45 30 55 150\ 150 c'oj 30 20 40 0 Katedra za upravljanje proizvodnjom Zadatak 3 57 Rješenje TRANSPORTNI PROBLEM LP-a xi,j Odredišta xio c'io S1 S2 S3 S4 Is h o d iš ta R1 70 / 30 / 0 / 75 30 R2 40 / 80 / 30 0 / 10 10 40 R3 10 / 50 / 0 / 35 10 xoj 20 45 55 150\ 150 c'oj 30 20 0 Katedra za upravljanje proizvodnjom Zadatak 3 58 Rješenje TRANSPORTNI PROBLEM LP-a xi,j Odredišta xio c'io S1 S2 S3 S4 Is h o d iš ta R1 70 / 30 / 0 / 75 30 R2 30 10 R3 10 / 20 50 / 0 / 35 10 xoj 20 45 45 150\ 150 c'oj 60 20 0 Katedra za upravljanje proizvodnjom Zadatak 3 59 Rješenje TRANSPORTNI PROBLEM LP-a xi,j Odredišta xio c'io S1 S2 S3 S4 Is h o d iš ta R1 30 / 0 / 75 30 R2 30 10 R3 20 0 / 15 15 50 xoj 45 45 150\ 150 c'oj 20 0 Katedra za upravljanje proizvodnjom Zadatak 3 60 Rješenje TRANSPORTNI PROBLEM LP-a xi,j Odredišta xio c'io S1 S2 S3 S4 Is h o d iš ta R1 30 / 45 0 / 30 75 30 R2 30 10 R3 20 15 15 50 xoj 45 30 150\ 150 c'oj 20 0 Katedra za upravljanje proizvodnjom Zadatak 3 61 Rješenje TRANSPORTNI PROBLEM LP-a xi,j Odredišta xio c'io S1 S2 S3 S4 Is h o d iš ta R1 30 / 45 0 / 30 R2 20 / 30 0 / 10 R3 10 / 20 0 / 15 xoj 150\ 150 c'oj F(x) = 10*20+30*40+20*30+0*30+0*10+0*15 = 200+1200+600=2000 Katedra za upravljanje proizvodnjom Literatura • N.Šakić, N.Štefanić, Inženjerski priručnik IP4, treći svezak, poglavlje 11. Metode optimiranja proizvodnje, Zagreb 2002. 62


Comments

Copyright © 2025 UPDOCS Inc.