Transport 2

RJEŠAVANJE TRANSPORTNOG PROBLEMA Postupak točno prati korake simpleks metode. No, umjesto korištenja standardne simpleks tablice uzimaju se prednosti od posebne strukture transportnog modela kako bi prikazali postupak rješavanja transportnog problema u jednostavnijoj formi. Postoji velik broj razrađenih metoda koje se primjenjuju za rješavanje transportnog problema linearnog programiranja i moguće ih je podijeliti u dvije osnovne grupe:  

metode za čije je rješavanje potreban početni raspored tereta i metode za čije rješavanje nije potreban početni raspored tereta.

U ovom će radu biti razrađene metode za čije je rješavanje potreban početni raspored tereta, a one se dijele na:  

metode za dobivanje početnog rasporeda tereta i metode za dobivanje optimalnog rješenja transportnog problema linearnog programiranja.

Metode koje se koriste za dobivanje početnog rasporeda tereta su sljedeće: 1. metoda sjeverozapadnog kuta, 2. metoda minimalnih troškova i 3. Vogelova aproksimativna metoda, a metode za dobivanje optimalnog rješenja transportnog problema linearnog programiranja su: 1. metoda relativnih troškova i 2. MODI metoda METODE ZA DOBIVANJE POČETNOG RASPOREDA TERERA Metoda sjeverozapadnog kuta Metodu sjeverozapadnog kuta nazivamo i dijagonalnom metodom. Ta metoda daje početno bazično nedegenerirano rješenje kod kojeg je broj zauzetih polja jednak m+n-1. Kako bi dobili početni raspored tereta prema toj metodi potrebno je uraditi sljedeće. Raspored tereta započinje u gornjem lijevom kutu („sjeverozapadnom kutu“). Na polje 1,1 stavlja se maksimalna količina tereta koja je moguća s obzirom na kapacitete ishodišta I1 i potrebe odredišta O1. Ako je kapacitet ishodišta I1 u potpunosti iskorišten prelazimo na pole 2,1, tj. na ishodišta I2 kako bi zadovoljili sve potrebe odredišta O1, a ako su zadovoljene potrebe odredišta O1, a kapacitet ishodišta I1 nije u potpunosti iskorišten tada prelazimo na polje 1,2, tj. zadovoljavamo potrebe odredišta O2 preostalom ponudom iz ishodišta I1. Taj postupak se nastavlja sve do donjeg desnog kuta, polja m,n, dok svi kapaciteti ishodišta nisu iskorišteni i sve potrebe odredišta nisu zadovoljene.

Primjer: Kapaciteti ishodišta su: 50, 30, 10; Kapaciteti odredišta su: 25, 15, 22, 28; O1 I1 I2 I3 bj

1

O2 5

25 2 7 25

O3 8

15

O4 2

10

6

3

9

12 18 11 3 10

15

22

4

28

ai 50 30 10 90

Kako se vidi iz primjera, na polje 1,1 stavljamo količinu od 25 težinskih jedinica jer je tolika potreba odredišta O1 te prelazimo na polje 1,2 jer nije iskorišten sav kapacitet ishodišta I1 i njime se zadovoljava potreba odredišta O2 od 15 težinskih jedinica. Potreba odredišta O2 je zadovoljena, ali još uvijek nije iskorišten kapacitet ishodišta I1. Prelazimo na polje 1,3 i na njega stavljamo preostali teret ishodišta I 1 od 10 težinskih jedinica te je sada kapacitet ishodišta I1 u potpunosti iskorišten. Sada prelazimo na ishodište I2 sa kojeg uzimamo 12 težinskih jedinica tereta i stavljamo ih na polje 2,3. Time je zadovoljena potreba odredišta O3 , no kapacitet ishodišta I2 nije iskorišten. Iz ishodišta I2 uzimamo preostali teret od 18 težinskih jedinica i stavljamo na polje 2,4. Kako bi se zadovoljile potrebe odredišta O4 na polje 3,4 stavljamo teret sa ishodišta I3 od 10 težinskih jedinica. Time je dobiven početni raspored tereta pomoću metode sjeverozapadnog kuta, a ukupni troškovi iznose: z = C11x11 + C12x12 + C13x13 + C23x23 + C24x24 + C34x34 = = 1*25 + 5*15 + 8*10 + 3*12 + 4*18 + 3*10 = 318 novčanih jedinica Primjenom metode sjeverozapadnog kuta ne obraća se pozornost na troškove prijevoza. Ova metoda vodi računa samo o zadovoljenju uvjet iz skupa ograničenja za ishodišta i odredišta te je zbog toga početni rasporede tereta dobiven tom metodom jako udaljen od optimalnog rješenja. Metoda minimalnih troškova Metoda minimalnih troškova daje bolji početni raspored tereta od metode sjeverozapadnog kuta, odnosno taj je početni raspored tereta bliži optimalnom rješenju nego početni raspored tereta dobiven metodom sjeverozapadnog kuta. Metoda minimalnih troškova vodi računa i o visini troškova, a ne samo o zadovoljavanju uvjeta ishodišta i odredišta. Kako bi dobili početni raspored tereta pomoću metodom minimalnih troškova potrebno je u matrici troškova pronaći najmanji trošak. Na to polje upisuje se maksimalna količina tereta s obzirom na kapacitet ishodišta i potrebe odredišta. Ukoliko se u matrici troškova pronađu dva ili više minimalnih troškova prvo je potrebno popuniti polje na koje je moguće staviti više tereta. Ako je zadovoljena potreba određenog odredišta ili je iskorišten kapacitet nekog od ishodišta u sljedećem razmatranju isključujemo taj stupac ili redak. Postupak se ponavlja na

ostatku matrice troškova tako dugo dok svi kapaciteti ishodišta nisu potrošeni i sve potrebe odredišta nisu zadovoljene. Primjer: Kapaciteti ishodišta su: 50, 30, 10; Kapaciteti odredišta su: 25, 15, 22, 28; O1 I1 I2 I3 bj

1

O2 5

O3 8

O4 2

25 2

25 6

3 8

7

9

4 22 11 3

7 25

15

50 30

3 22

ai

28

10 90

Metoda minimalnih troškova započinje razmatranjem matrice troškova i traženjem najmanjeg troška u matrici. Na datom primjeru vidi se da se najmanji trošak nalazi na polju 1,1 i iznosi jednu novčanu jedinicu te se na to polje stavlja maksimalna količina tereta od 25 težinskih jedinica. Zadovoljavanjem potreba odredišta O1 više ne razmatramo troškove prvog stupca. Tražimo najmanji trošak u preostaloj matrici, a on se nalazi na polju 1,4. Na to se polje stavlja 25 težinskih jedinica tereta te se time iskorištava kapacitet ishodišta I1 i u sljedećem se koraku ne gledamo više niti prvi redak. Postupak nastavljamo do iskorištenja svih kapaciteta. Ukupni troškovi prijevoza početnog rasporeda dobiveni metodom minimalnih troškova iznose: z = C11x11 + C14x14 + C22x22 + C23x23 + C32x32 + C34x34 = = 1*25 + 2*25 + 6*8 + 3*22 + 9*7 + 3*3 = 271 novčana jedinica Vogelova aproksimativna metoda Vogelova aproksimativna metoda najefikasnija je metoda za dobivanje početnog rasporeda tereta. Početni raspored tereta najbliži je optimalnom rješenju, ako nije i samo optimalno rješenje. Ova metoda stavlja u odnos troškove prijevoza i na temelju toga raspoređuje teret uz zadane uvjete ishodišta i odredišta. Vogelova aproksimativna metoda za traženje početnog rasporeda tereta sastoji se od više koraka. U prvom koraku te metode potrebno je u svakom redu i svakom stupcu pronaći dva najmanja troška te između njih pronaći razliku koja se upisuje u stupac „razlika reda“ (rj) te redak „razlika stupca“ (ri). U drugom koraku potrebno je pronaći najveću razliku redaka ili stupaca. U retku ili stupcu u kojem je najveća razlika troška pronalazi se najmanji trošak i na to se polje upisuje maksimalna količina tereta. Postupak je potrebno ponavljati od prvog koraka sve dok se svi kapaciteti ishodišta ne iskoriste, a sve potrebe odredišta ne zadovolje. Ako se kod izračunavanja razlike redaka i stupaca pojave dva ili više ista najveća broja, tada je potrebno provjeriti u kojem se od tih redaka ili stupaca nalazi manji trošak prijevoza i na njega se stavlja maksimalna količina tereta, a ako se dogodi da

su i troškovi jednaki tada se odabire ono polje na koje je moguće staviti veću količinu tereta. Primjer: Kapaciteti ishodišta su: 50, 30, 10; Kapaciteti odredišta su: 25, 15, 22, 28; O1 I1 I2 I3

1

O2 5

25 2

8

O4 2

7 6

18 3

8 7

O3

9

4 22 11 3

25

15

rj

1,1, 1,1

1,1, 1,1

22 5

50 30

10

bj

ai

28

10

ri 1,1,1,4 1,2,2,4 4,4

90

1,1, 2

Početni raspored tereta dobiven Vogelovom aproksimativnom metodom najbliži je optimalnom rješenju transportnog problema, što se vidi i iz danog primjera. Ukupni troškovi početno rasporeda ovom metodom iznose: z = C11x11 + C12x12 + C14x14 + C22x22 + C23x23 + C34x34 = = 1*25 + 5*7 + 2*18 + 6*8 + 3*22 + 3*10 = 240 novčanih jedinica METODE ZA DOBIVANJE OPTIMALNOG RJEŠENJA TR. PROBLEMA Metoda skakanja s kamena na kamen Metoda skakanja s kamena na kamen naziva se još i metoda relativnih troškova. To je metoda za dobivanje optimalnog rješenja transportnog problema za koju je potreban početni raspored tereta. Nakon dobivanja početnog rasporeda tereta jednom od metoda započinje primjena metode skakanja s kamena na kamen. Prvo je potrebno izračunati relativne troškove (Cij*) za sva nezauzeta polja, tj. za sva polja na kojima se ne nalazi teret. Relativni trošak može biti pozitivan ili negativan broj, a on nam pokazuje za koliko novčanih jedinica bi se ukupni troškovi smanjili ili povećali po jedinici tereta ukoliko bi se odabere određena relacija. Dakle, pozitivan relativni trošak pokazuje za koliko novčanih jedinica po jedinici tereta su ukupni troškovi uvećani zbog toga što neka relacija, za koju se izračunava relativni trošak, nije na ruti transporta. Negativni relativni trošak pokazuje za koliko novčanih jedinica po jedinici tereta su ukupni troškovi smanjeni zbog toga što je neka relacija, za koju se izračunava relativni trošak, na ruti transporta. Sve dok se na bilo kojem polju nalazi pozitivni relativni trošak nije postignut optimalno rješenje i potrebno je napraviti novi raspored tereta koji uključuje i polje sa pozitivnim relativnim troškom. Ako smo dobili više pozitivnih relativnih troškova tada

uzimamo najveći zbog toga što će se ukupni troškovi najviše smanjiti (brzina smanjivanja ukupnih troškova direktno ovisi o relativnim troškovima i količini tereta). Ako postoje dva ili više jednaka najveća pozitivna relativna troška tada biramo onaj na čije polje možemo staviti najviše tereta kako bi se ukupni troškovi brže smanjivali. Kako bi utvrdili da li smo došli do optimalnog rješenja ponovno je potrebno izračunati relativne troškove za sva nezauzeta polja. Kako bi izračunali relativne troškove potrebno je pronaći „zatvoreni put“ preko zauzetih polja. „Zatvoreni put“ moguće je definirati kroz tri pravila: 1. Bilo koja dva uzastopna polja moraju se nalaziti u istom stupcu ili retku; 2. Tri uzastopna polja ne mogu se nalaziti u istom stupcu ili retku; 3. Posljednje polje mora se nalaziti u istom stupcu ili retku u kojem se nalazi i polje za koje računamo relativni trošak. Na sljedećim slikama prikazano je kako može izgledati „zatvoreni put“.

Nakon što smo odredili „zatvoreni put“ potrebno je zbrojiti troškove prijevoza i to na način da polje za koje se računa relativni trošak ima negativan predznak, prvo zauzeto polje na putu negativan, sljedeće opet pozitivan i tako sve do polja od koje smo krenuli. Primjer: Kapaciteti ishodišta su: 50, 30, 10 Kapaciteti odredišta su: 25, 15, 22, 28 U sljedećem primjeru na kojem će biti prikazana metoda skakanja s kamena na kamen početni raspored tereta dobiven je metodom minimalnih troškova i dobiven je nedegenerirani početni raspored tereta sa m+n-1 = 3+4-1 = 6 zauzetih polja, a ukupni troškovi za ovaj početni raspored iznose: z = C11x11 + C14x14 + C22x22 + C23x23 + C32x32 + C34x34 = = 1*25 + 2*25 + 6*8 + 3*22 + 9*7 + 3*3 = 271 novčana jedinica O1 I1 I2 I3

1

O2 5

25 2

6

O4 2

-3 3

25

4 22 -4 11 3 7 -5 3 8

9 -5

8 3

-3 7

O3

ai 50 30 10

bj

25

15

22

28

90

Zauzeta polja su 1,1; 1,4; 2,2; 2,3; 3,2 i 3,4. Za sva ostala polja potrebno je izračunati relativne troškove. Za polje 1,2 to je moguće učiniti preko polja 1,4; 3,4 i 3,2: 1,2

1,4

3,2

3,4

C12* = - C12 + C14 – C34 + C32 = -5+2-3+9 = 3 Sljedeće nezauzeto polje je 1,3 i za njega je izračun relativnih troškova moguć preko polja 1,4; 3,4; 3,2; 2,2 i 2,3: 1,3

2,2

1,4

2,3

3,2

3,4

C13* = - C13 + C14 – C34 + C32 – C22 + C23 = -8+2-3+9-6+3 = -3 Postupak se nastavlja sve do posljednjeg nezauzetog polja: C21* = - C21 + C22 – C32 + C34 – C14 + C11 = -2+6-9+3-2+1 = -3 C24* = - C24 + C34 – C32 + C22 = -4+3-9+6 = -4 C31* = - C31 + C11 – C14 + C34 = -7+1-2+3 = -5 C33* = - C33 + C32 – C22 + C23 = -11+9-6+3 = -5 U polju 1,2 nalazi se pozitivan relativni trošak što nam pokazuje da ovo nije optimalno rješenje. Potrebno je na polje 1,2 staviti određenu količinu tereta. Teret se seli po istom putu po kojem se računao i relativni trošak. Teret se dodaje na polje 1,2; oduzima sa polja 1,4; dodaje na polje 3,4 i oduzima sa polja 3,2. Količina tereta koju selimo je najmanja količina tereta koja se nalazi na poljima sa kojih se oduzima teret, a to je u danom primjeru količina od 7 težinskih jedinica tereta i nalazi se na polju 3,2. Nije moguće preseliti veću količinu tereta jer teret ne može biti negativan. Nakon što se teret preseli, novi raspored tereta izgleda ovako: O1 I1 I2 I3

1

O2 5

25 2

8 7

6 0

O3

2 -6

3 8

O4 18 4

22 -1 7 9 11 3 -5 -3 -8 10

ai 50 30 10

bj

25

15

22

28

90

Novi ukupni troškovi prijevoza iznose: z = C11x11 + C12x12 + C14x14 + C22x22 + C23x23 + C34x34 = = 1*25 + 5*7 + 2*18 + 6*8 + 3*22 + 3*10 = 240 novčana jedinica Dobivanjem novog rasporeda tereta i novih ukupnih troškova završena je prva iteracija.Druga iteracija započinje izračunavanjem relativnih troškova za sva nezauzeta polja: C13* = - C13 + C23 – C22 + C12 = -8+3-6+5 = -6 C21* = - C21 + C22 – C12 + C11 = -2+6-5+1 = 0 C24* = - C24 + C14 – C12 + C22 = -4+2-5+6 = -1 C31* = - C31 + C11 – C14 + C34 = -7+1-2+3 =-5 C32* = - C32 + C12 – C14 + C34 = -9+5-2+3 = -3 C33* = - C33 + C23 – C22 + C12 – C14 + C34 = -11+3-6+5-2+3 = -8 Nakon izračunavanja relativnih troškova vidi se da nije dobiven niti jedan pozitivni relativni trošak te je ovaj raspored tereta optimalno rješenje. Ukupni troškovi optimalnog rješenja iznose 240 novčanih jedinica. U polju 2,1 vrijednost relativnog troška je nula iz čega se vidi da osim ovog optimalnog rješenja postoji još jedno optimalno rješenje. Broj optimalnih rješenja = 2broj nula Ako želimo dobiti drugo optimalno rješenje nulu tretiramo kao pozitivan broj i izvršimo premještaj tereta. Drugo optimalno rješenje izgleda ovako: O1 I1 I2 I3 bj

1

O2 5

17 2

8

O4 2

15 6

8 7

O3

9

18 3

4 22 11 3

15

22

50 30

10 25

ai

28

10 90

Ukupni troškovi ovog optimalnog rješenja jednaki su ukupnim troškovima prvog optimalnog rješenja: z = C11x11 + C12x12 + C14x14 + C21x21 + C23x23 + C34x34 = = 1*17 + 5*15 + 2*18 + 2*8 + 3*22 + 3*10 = 240 novčana jedinica MODI metoda MODI metoda je skraćeni naziv za „The Modified Distribution Method“. To je metoda za koju je također potreban početni raspored tereta i ravnopravna je metodi skakanja s kamene na kamen. MODI metoda je modificirana i specijalizirana simpleks metoda

za rješavanje transportnog problema. MODI metoda izračunava relativne troškove uz pomoć dualnih varijabli, ui i vj. Za svaki redak potrebno je izračunati vrijednost dualne varijable ui , a za svaki stupac vrijednost varijable vj. Za svako zauzeto polje vrijedi da je Cij = ui + vj. Kako bi bilo moguće izračunati vrijednosti za ui i vj uzima se da je u1 = 0 te se sada mogu izračunati sve vrijednosti dualnih varijabli. Kapaciteti ishodišta su: 50, 30, 10; Kapaciteti odredišta su: 25, 15, 22, 28; Početni raspored tereta dobiven je metodom sjeverozapadnog kuta i ukupni troškovi tog rasporeda iznose: z = C11x11 + C12x12 + C13x13 + C23x23 + C24x24 + C34x34 = = 1*25 + 5*15 + 8*10 + 3*12 + 4*18 + 3*10 = 318 novčanih jedinica O1 I1 I2 I3

1

O2 5

25 2

O3 8

15 6

-6

O4 2

10 3

7 4

-6

12 18 7 9 11 3 -12 -10 -9 10

bj

25

15

22

28

vj

1

5

8

9

ai

ui

50

0

30

-5

10

-6

90

u1+ v1 = C11 0 + v1 = 1 v1 = 1 u1+ v2 = C12 0 + v2 = 5 v2 = 5 u1+ v3 = C13 0 + v3 = 8 v3 = 8 u2+v3 = C23 u2+v3 = 3 u2 = -5 u2+v4 = C24 u2+v4 = 4 v4 = 9 u3+v4 = C34 u3+v4 = 3 u3 = -6 Kada su izračunate sve dualne varijable potrebno je izračunati relativne troškove za nezauzeta polja po formuli Cij* = (ui + vj) - Cij. U danom primjeru to izgleda ovako: C14* = (u1 + v4) – C14 = (0+9)-2 = 7 C21* = (u2 + v1) – C21 = (-5+1)-2 = -6 C22* = (u2 + v2) – C22 = (-5+5)-6 = -6 C31* = (u3 + v1) – C31 = (-6+1)-7 = -12 C32* = (u3 + v2) – C32 = (-6+5)-9 = -10 C33* = (u3 + v3) – C33 = (-6+8)-11 = -9 Nakon što su izračunati relativni troškovi postupak je jednak kao i kod metode skakanja s kamena na kamen, odabire se pozitivan relativni trošak, traži se „zatvoreni put“ preko zauzetih polja i po tom putu seli se teret. Nakon preraspodjele tereta izračunavaju se ukupni troškovi i završava prva iteracija. O1 I1

1

O2 5

O3 8

O4 2

ai

ui

50

0

25 I2 I3

2

15 6

-7 3

1

10 4

1

22 8 7 9 11 3 -5 -3 -9 10

bj

25

15

22

28

vj

1

5

1

2

30

2

10

1

90

Ukupni troškovi dobivenog rasporeda tereta iznose: z = C11x11 + C12x12 + C14x14 + C23x23 + C24x24 + C34x34 = = 1*25 + 5*15 + 2*10 + 3*22 + 4*8 + 3*10 = 248 novčanih jedinica Optimalno rješenje nije dobiveno jer imamo dva pozitivna relativna troška i to jednaka. Potrebno je pronaći „zatvoreni put“ za oba polja i ustanoviti na koje polje je moguće staviti više tereta. Za polje 2,1 „zatvoreni put“ je 2,1; 1,1; 1,4 i 2,4 i moguće je preseliti 8 težinskih jedinica tereta, dok je za polje 2,2 „zatvoreni put“ 2,2; 1,2; 1,4 i 2,4 i također je moguće preseliti 8 težinskih jedinica tereta. Sada je moguće odabrati bilo koje polje. Ako odaberemo polje 2,1 tada novi raspored tereta izgleda ovako:

O1 I1 I2 I3

1

O2 5

8

17 2

O3

15 6

O4 2

-6

18

3

4 22 -1 7 9 11 3 -5 -3 -9 10 8

0

bj

25

15

22

28

vj

1

5

2

2

ai

ui

50

0

30

1

10

1

90

Ukupni troškovi iznose: z = C11x11 + C12x12 + C14x14 + C21x21 + C23x23 + C34x34 = = 1*17 + 5*15 + 2*18 + 2*8 + 3*22 + 3*10 = 240 novčana jedinica Kada se izračunaju relativni troškovi vidi se da je dobiveni raspored tereta optimalno rješenje i također se vidi da smo odabrali polje 2,2 dobili bi drugo optimalno rješenje koje možemo dobiti ako tretiramo nulu na tom polju kao pozitivan broj. DEGENERACIJA KOD TRANSPORTNOG PROBLEMA Kod transportnog se problema degeneracija javlja kada je neka parcijalna suma od a i jednaka nekoj parcijalnoj sumi od bj . Nedegenerirano bazično rješenje je ono koje ima m+n-1 zauzetih polja, dok je degenerirano bazično rješenje ono kojem je kojem je zbroj zauzetih polja manji od m+n-1 i takvo bazično rješenje nije moguće poboljšati metodama za dobivanje optimalnog rješenja koje zahtijevaju početni raspored već je potrebno degenerirano rješenje pretvoriti u nedegenerirano. Degeneraciju je moguće

dobiti prilikom postavljanja početnog rasporeda tereta bilo kojom od metoda ili u nekoj od iteracija. Kapaciteti ishodišta su: 50, 90, 60 Kapaciteti odredišta su: 50,40,70,40

2 5 4 5    Cij = 1 2 1 4 3 1 5 2    O1 I1 I2 I3 bj rj

2

O2 5

O3 4

O4 5

50

50 1

2

1 20

3

1

4

5

50

40

1,1

1,1, 1

90

70 2

20

40 70 3

ai

40

60

ri 2,3 0,1,2 1,1,1

200

2,2, 2

z = C11x11 + C12x12 + C14x14 + C22x22 + C23x23 + C34x34 = = 1*25 + 5*7 + 2*18 + 6*8 + 3*22 + 3*10 = 240 novčanih jedinica Degeneraciju je moguće prikazati grafički pomoću stabla sa čvorovima koji predstavljaju ishodišta i odredišta te granama koje prikazuju veze između njih. Kada prikazujemo nedegenerirano rješenje drvo je neprekinuto, a sastoji se od m+n čvorova i m+n-1 grana. O1

O2

I1

O3

I2

O4

I3

Kod degeneracije drvo je na određenom mjestu ili na više mjesta prekinuto. O1

O2

I1

O3

I2

O4

I3

Iz slike se vidi da ne postoji nikakva povezanost između ishodišta I1 i odredišta O1, i ishodišta I2, I3 i odredišta O2, O3 i O4. Pretvaranje degeneriranog bazičnog rješenja u nedegenerirano bazično rješenje je spajanje ta dva parcijalna dijela drveta . O1

O2

O3

I1

I2

O4

I3

To spajanje ne mora se izvršiti na načina na koji je to prikazano na slici, te parcijalne dijelove drveta moguće je spojiti tako da se spoji bilo koje ishodište jednog parcijalnog dijela sa bilo kojim odredištem drugog parcijalnog dijela. Nakon što se degeneracija uoči i nakon što se odredi koje ishodište ćemo povezati s kojim odredištem u tablicu je potrebno upisati na odabrano polje fiktivni teret. Fiktivni teret ne smije utjecati na ukupne troškove te se zbog toga on određuje vrijednošću nula. Kada jednom postavimo fiktivni teret na određeno polje s njime postupamo kao i sa svakim drugim zauzetim poljem. Fiktivni teret može nestati kroz iteracije. Kapaciteti ishodišta su: 50, 90, 60 Kapaciteti odredišta su: 50,40,70,40 U danom primjeru fiktivni teret moguće je staviti na bilo koje slobodno polje u prvom redu i na bilo koje slobodno polje u prvom stupcu. U tablici fiktivni teret stavljen je na polje 2,1 i ako izračunamo relativne troškove vidimo da je taj raspored ujedno i optimalno rješenje. O1 I1 I2 I3

2

O2 5

50 1

4 -2

2 0

3

5

1

-1 4

70 5

20

O4

-2

20 1

-3

O3

-1 2

-5

40

bj

50

40

70

40

vj

2

3

2

4

ai

ui

50

0

90

-1

60

-2

200

z = C11x11 + C12x12 + C14x14 + C22x22 + C23x23 + C34x34 = = 1*25 + 5*7 + 2*18 + 6*8 + 3*22 + 3*10 = 240 novčanih jedinica U tablici fiktivni teret stavljen je na polje 1,2 i nakon izračunavanja relativnih troškova vidimo da dobiven raspored nije optimalno rješenje te je potrebno izvršiti premještaj tereta i to fiktivnog tereta sa polja 1,2 na polje 1,4. Nakon ponovnog izračunavanja relativnih troškova vidi se da je taj raspored optimalno rješenje. O1

O2

O3

O4

ai

ui

I1 I2 I3

2

5

4

50 1

2 -2

3

5

0

0 1

20 1

-5

1 4

70 5

20

-1 2

-5

40

bj

50

40

70

40

vj

2

5

4

6

50

0

90

-3

60

-4

200

z = C11x11 + C12x12 + C14x14 + C22x22 + C23x23 + C34x34 = = 1*25 + 5*7 + 2*18 + 6*8 + 3*22 + 3*10 = 240 novčanih jedinica O1 I1 I2 I3

2

O2 5

50 1

4 -1

2 -1

3

5

1

0 4

70 5

20

O4

-1

20 1

-4

O3

-1 2

-5

40

bj

50

40

70

40

vj

2

4

3

5

ai

ui

50

0

90

-2

60

-3

200

z = C11x11 + C12x12 + C14x14 + C22x22 + C23x23 + C34x34 = = 1*25 + 5*7 + 2*18 + 6*8 + 3*22 + 3*10 = 240 novčanih jedinica