3. TRANSPORTNI PROBLEMI
LINEARNOGA PROGRAMIRANJA
3.1. TEORIJSKE OSNOVE
Problem transporta javlja se u praksi u različitim oblicima ovisno o broju
vrsta jedinica koje se prevoze ili raspoređuju, broju vrsta i tipova prije-
voznih sredstava te broju ishodišta i odredišta ili pak načinu prijevoza tereta
(o tome detaljnije vidjeti u radu Z. Zenzerović i S. Bešlić [ ] ).
U ovom je poglavlju obrađena jedna vrsta transportnih problema koja se
naziva klasičnim problemom transporta i koja je sa stajališta operacijskih
istraživanja definirana na sljedeći način:
Transportni problem
je takva vrsta problema za koji je potrebno
programirati prijevoz, odnosno odrediti broj homogenih (istovrsnih) jedinica
(tereta, predmeta, osoba, …) koje treba prevesti, odnosno rasporediti iz više
ishodišta (mjesta gdje se nalaze jedinice) na više odredišta (mjesta na
kojima se podmiruje potražnja, odnosno zadovoljava zahtjev) s ciljem da
troškovi prijevoza (ili udaljenost, vrijeme, …) budu minimalni, odnosno
iznosi prihoda (dobiti, …) maksimalni. Pritom treba uzeti u obzir da ponuda
pojedinih ishodišta ne smije biti premašena i da potražnja svih odredišta
treba biti zadovoljena.
Primjerice
,
Prema obliku kojim su matematički izraženi, u ovom su poglavlju
prikazani transportni problemi linearnog programiranja, a to su transportni
problemi kod kojih su funkcija cilja kao i ograničenja izraženi u obliku
1
linearnih funkcija, za razliku od transportnih problema nelinearnoga pro-
gramiranja kod kojih su u matematičkom modelu nelinearne veze.
Svakom transportnom problemu pripada odgovarajuća matrica transporta
koja izgleda ovako:
Odredište
Ishodište
O
1
O
2
O
n
Ponuda
a
i
I
1
x
11
x
12
x
1n
a
1
I
2
x
21
x
22
x
2n
a
2
.
.
.
.
.
.
I
m
x
m1
x
m2
x
mn
a
m
Potražnja
b
j
b
1
b
2
b
n
Oznake u matrici:
m –
ukupan broj ishodišta (otpremnih postaja);
i
–
redni broj ishodišta,
i
= 1,2,…,
m
n
–
ukupan broj odredišta (prijemnih postaja);
j
–
redni broj odredišta,
j
= 1,2,…,
n
c
ij
–
trošak prijevoza (udaljenost, vrijeme ili iznos prihoda, dobiti) jedne
jedinice na relaciji od
i
-tog ishodišta do
j
-tog odredišta
x
ij
–
količina (ili iznos) koju treba prevesti, prenijeti ili rasporediti iz
i
-tog
ishodišta u
j
-to odredište
a
i
–
količina koja se raspoređuje iz pojedinih ishodišta (ponuda ishodišta)
b
j
–
količina koja je potrebna pojedinom odredištu (potražnja odredišta).
Na temelju matrice transporta postavlja se matematički model koji se
sastoji od funkcije kriterija i ograničenja.
2
c
11
c
12
c
1
n
m
c
21
c
22
c
2
n
c
m
1
c
m
2
c
mn
Iz matematičkog je modela vidljivo da je razmatrani problem transporta
problem linearnog programiranja koji se može rješavati, kao i svaki drugi
problem linearnog programiranja, pomoću simpleks metode.
Simpleks metoda
ovdje nije objašnjena iz razloga što je ta metoda u
literaturi o linearnom programiranju detaljno opisana (vidjeti [ ], [ ], [ ] u
popisu literature) te činjenice da je zbog velikog broja varijabli (
m
×
n
, gdje
je
m
ukupan broj ishodišta, a
n
ukupan broj odredišta) rješavanje trans-
portnog problema pomoću simpleks metode dugotrajno i ne preporuča se za
ručno rješavanje problema.
Navedeni su razlozi utjecali da su za rješavanje transportnih problema
razvijene
specijalizirane metode rješavanja
. One se mogu svrstati u dvije
skupine:
1)
Metode za postavljanje početnog programa
2) Metode za testiranje programa i dobivanje optimalnog rješenja,
iako postoje metode koje ne zahtijevaju postavljanje početnog programa, ali
zbog složenijeg algoritma nisu uzete u obzir.
Početni se program postavlja pomoću ovih metoda:
Metoda “sjeverozapadnog kuta” (North West Corner Rule)
Metoda najmanjih troškova
Vogelova metoda.
Metodom “sjeverozapadnog kuta”
, tzv. dijagonalnom metodom raspo-
ređivanje jedinica započinje od sjeverozapadnog kuta matrice transporta, tj.
od polja (1,1) u koje se stavlja najveći mogući broj jedinica zavisno od
ponude prvog ishodišta i potražnje prvog odredišta. Tim se brojem ili
iskoristi ponuda prvog ishodišta ili podmiri potražnja prvog odredišta koje
se isključuje iz daljnjeg raspoređivanja. Postupak se nastavlja na preostalim
4
poljima po dijagonali matrice sve do polja (
m
,
n
) dok se ne rasporede
raspoložive količine svih ishodišta, odnosno ne zadovolje zahtjevi svih
odredišta.
Po
metodi najmanjih troškova
početni se program dobiva stavljanjem
najvećeg mogućeg broja jedinica (zavisno od ponude i potražnje) na
najpovoljnije polje u matrici transporta, a to je polje s najmanjim, odnosno
najvećim
c
ij
zavisno od kriterija optimalnosti. Time se ili iscrpi ponuda
nekog ishodišta ili podmiri potražnja nekog odredišta, pa se taj redak
(ishodište) ili stupac (odredište) “izbacuje” iz daljnjeg raspoređivanja.
Postupak se ponavlja sve dotle dok se sve raspoložive jedinice ne rasporede
po pojedinim odredištima.
Početni program po
Vogelovoj metodi
dobiva se ovako:
1) Izračuna se razlika između dva “najmanja” troška (najmanjeg i sljedećeg
do njega po veličini) za svaki redak (∆
i
) i svaki stupac (∆
j
).
2) Odabire se redak ili stupac s maksimalnom razlikom, bilo ∆
i
ili ∆
j
iz
točke 1), i u najpovoljnije polje (polje s najmanjim
c
ij
) tog retka ili stupca
stavlja najveći mogući broj jedinica zavisno od ponude i potražnje. Time
se ili iskoristi ponuda nekog ishodišta ili podmiri potražnja nekog
odredišta pa se taj redak ili stupac “izbacuje” iz daljnjeg raspoređivanja.
3) Postupak se ponavlja, tj. vraća na točku 1) sve dotle dok se ne rasporede
sve jedinice. Međutim, ako je u točki 2) izbačen stupac iz daljnjeg
raspoređivanja, onda se ponovno izračunava samo razlika retka, jer su
razlike preostalih stupaca ostale nepromijenjene, a ako se izbaci redak
tada se izračunavaju ponovno samo razlike svakog stupca. Kada se
raspoređivanje svede na jedan redak ili jedan stupac ne mogu se računati
razlike, ali se zato raspoređivanje obavlja po poljima preostalog stupca ili
retka zavisno od vrijednosti
c
ij
.
Za kontrolu zbroj jedinica po recima mora biti jednak ponudi pojedinog
ishodišta i zbroj jedinica po stupcima potražnji pojedinih odredišta.
Vrijednost funkcije kriterija
Z
predstavlja zbroj umnožaka
c
ij
x
ij
za
x
ij
≠ 0,
gdje
i
= 1, … ,
m
i
j
= 1,…,
n
.
5
