Transportni problem

Transportni problem je jedan od problema sa polja operacionih istraživanja‎. Zadatak je da se za date spiskove dobavljača i poručilaca neke robe organizuje transport tako da njegove cene budu optimalne.

Opis rešenja

Elementi matrice transportnog problema

Prvo treba sastaviti matricu transportnog problema. To je matrica tipa m × n, gde je m broj dostavljača a n broj kupaca. Svako polje (i,j) je namenjeno beleženju trgovine između i-tog dostavljača i j-tog kupca. Pored toga, svako polje matrice takođe ima i jedno potpolje u kojem se nalazi cena transporta jedne jedinice trgovine. Vrednosti a₁, ..., a_m predstavljaju redom raspoložive kapacitete dostavljača, a b₁, ..., b_n potrebe poručilaca. Neka cena transporta za polje (i,j) bude C_i,j, a količina isporučene robe X_i,j.

Sledeći korak je raspodela transporta tako da svi mogući transporti budu napravljeni tj. da zbir isporučenih jedinica robe bude maksimalan.

$\sum _{i=1}^{m}{\sum _{j=1}^{n}{X_{(i,j)}}}=max$

Ovaj početni raspored ne mora biti optimalan. Dva postupka za dobijanje ovih rasporeda su metod najmanjih cena i metod severozapadnog ugla.

Nakon ovoga sledi iterativni postupak optimizacije ukupne cene transporta. U matrici se traži ciklus koji sadrži tačno jedno prazno polje i neparan broj popunjenih polja. Pravilo za formiranje ciklusa je da se sledeći element može samo tražiti po vertikali ili po horizontali. Ukoliko je, počev od nepopunjenog polja, zbir cena transporta izabranih polja sa neparnim indeksom manji nego kod polja sa parnim indeksom prelazi se na sledeći korak, u suprotnom se traži novi ciklus.

Po nalaženju jednog ciklusa koji odgovara gorenavedenom pravilu o sumama vrednosti svojih članova, izabire se minimalna vrednost svih polja sa parnim indeksom koja ciklus uključuje. Ova vrednost se potom oduzima od svih polja sa parnim indeksom u ciklusu a dodaje se svakom polju sa neparnim indeksom. Ovo poređenje se takođe može vršiti sumom svih elemenata niza, s tim što znak za svaki sledeći element alternira. Da bi uslov bio ispunjen, suma mora biti manja od nule. Kao što je već pomenuto, nepopunjeno polje ima indeks broj 1, a smer daljeg numerisanja nije bitan jer je broj izabranih polja uvek paran.

Kad se količina isporučene robe u nekom polju anulira, u tom polju ostaje broj nula i ono se ne računa kao nepopunjeno. Proces traženja ciklusa i modifikovanja brojeva u njemu se ponavlja dokle god postoje ciklusi koji zadovoljavaju navedene uslove.

Ukupna cena transporta u svakom momentu je suma proizvoda vrednosti isporučene robe i cene transporta svakog polja.

$\sum _{i=1}^{m}{\sum _{j=1}^{n}{X_{(i,j)}\cdot C_{(i,j)}}}$

Primer

Recimo da su data tri dostavljača, koji redom raspolažu sa 8, 5 i 6 pošiljki, i četiri poručioca sa potražnjama za 6, 4, 5 i 4 pošiljke. Ovo je optimalan slučaj kada je potražnja jednaka poundi. U praksi se češće sreću tržište orijentisano ka kupcima, gde je ponuda veća od potražnje i tržište orijentisano ka prodavcima, gde je potražnja veća od ponude.

Uz to je poznata i matrica sa cenama transporta:

$C={\begin{bmatrix}4&1&2&1\\1&3&5&1\\1&1&3&2\\\end{bmatrix}}$

Tada će matrica transportnog problema, pre početne raspodele, izgledati ovako:	A nakon raspodele po metodi severozapadnog ugla, ovako:

Nakon raspodele metodom severozapadnog ugla uglavnom je do konačnog rešenja potrebno više iteracija nego nakon raspodele metodom najmanjih cena. Ovde je izabran metod severozapadnog ugla da bi se problem kroz veći broj iteracija što bolje predstavio.

Sledeći korak je traganje za ciklusom koji odgovara navedenom uslovu. Jedan takav je označen na slici ispod. Pošto je δ = 1 - 4 + 1 - 3 < 0, u ovom ciklusu će se u svakom „negativnom“ polju od isporučene robe oduzeti minimalna vrednost (u ovom slučaju min{2, 6} = 2), a „pozitivnom“ polju ista dodati.

Nađeni ciklus C21-C11-C12-C22:	Rezultat je sledeći:

Iterativno se opet traži ciklus koji zadovoljava uslove. Na slici ispod je obeležen ciklus kod koga je opet δ = 2 - 5 + 1 - 4 < 0, a minimalna vrednost min{3, 4} = 3:

Nađeni ciklus C13-C23-C21-C11:	Rezultat:

Sledi iterativno nalaženje daljih ciklusa i njihova optimizacija:

Ciklus C31-C33-C13-C11 δ = 1 - 3 + 2 - 4 < 0 min{1,2} = 1:	Ciklus C32-C33-C13-C12 δ = 1 - 3 + 2 - 1 < 0 min{1,4} = 1:

Ciklus C14-C12-C32-C34 δ = 1 - 1 + 1 - 2 < 0 min{3,4} = 3:	Ciklus C24-C21-C31-C34 δ = 1 - 1 + 1 - 2 < 0 min{5,1} = 1:

Konačni rezultat

Može se primetiti da se kroz iteracije isporuke gomilaju oko polja gde je cena transporta najmanja, što je signifikator optimizacije. U ovom slučaju algoritam je od početne ukupne cene transporta C₁ = 6·4 + 2·1 + 2·3 + 3·5 + 2·3 + 4·2 = 61 došao do cene C₂ = 5·2 + 3·1 + 4·1 + 1·1 + 2·1 + 4·1 = 24.

Specijalni slučajevi

U praksi se može javiti i par dodatnih uslova koji donekle menjaju tok rešavanja.

• Dostavka od prodavca i do naručioca j nije moguća: Postavi se da cena dostavke C_i,j bude ∞ i na to polje se ne raspoređuje nikakva dostavka pri početnom raspoređivanju.
• Prodavac i mora sve da proda: Potreba za ovim uslovom se javlja kad je ponuda veća od potražnje. Rešenje je da se definiše još jedan naručilac kome treba tačna razlika između ponude i potražnje, s tim da su cene dostavke njemu od svih dostavljača, sem dostavljača i jednake nuli, a cena dostavke od dostavljača i do ovog naručioca ∞.
• Naručilac j treba da bude namiren: Analogno prethodnom slučaju, definiše se još jedan prodavac, koji nudi razliku između potražnje i ponude i postavi se da su cene transporta od njega do svih ostalih naručilaca jednake nuli, a do j-og ∞.