ISSN : 1693 – 1173 Penyelesaian Masalah Transportasi Dengan Metoda Primal-Dual Wawan Laksito YS 4) Abstrak Masalah Transportasi merupakan permasalahan pendistribuian suatu produk homogen dari beberapa sumber ke beberapa tujuan dengan cara yang paling optimal. Metoda Primal-Dual merupakan penyelesaian masalah transportasi dari model matematika dengan ide dapat ditentukan suatu solusi fisibel dari primal dan solusi fisibel dari dual sedemikian hingga kondisi complementary slackness dipenuhi, maka permasalahan transportasi terselesaikan. 1. Permasalahan Suatu masalah transportasi melibatkan m sumber daya (resources), dimana masing-masing tersedia ai (i = 1,2,..,m) unit suatu produk homogen, dan n tempat tujuan (destination) yang masing-masing membutuhkan bj (j = 1,2,..,n) unit produk. Bilangan-bilangan aI dan bj adalah bulat non negatif. Keuntungan (benefit) wij (atau biaya cij ) dengan mentransformasikan suatu unit produk dari sumber I ke tujuan j diketahui untuk tiap-tiap I dan j. Objektifnya adalah menyusun suatu skedul transportasi bilangan bulat (satuan produk boleh berbentuk pecahan ) yang memenuhi semua permintaan dari daftar barang-barang pada saat ini sehingga menghasilkan keuntungan yang maksimum (atau biaya yang mininimum).Dianggap bahwa total penawaran sama dengan total permintaan. Masalah transportasi tersebut dapat dimodelkan sebagai berikut: Diberikan bilangan-bilangan bulat non negatif a1, a2, .., am dan b1, b2, .., bn sedemikian hingga
m
n
i 1
j 1
ai b j r dan bilangan-bilangan wij atau cij
, i = 1,2,..,m; j = 1,2,..,n. Akan dicari xij 0 sedemikian hingga n
x j 1
4)
ij
ai , i 1,2,..., m ;
m
x i 1
ij
bi , i 1,2,..., n
Staf Pengajar STMIK Sinar Nusantara Surakarta Jurnal Ilmiah SINUS…………….29
m
dan
n
wij xij maksimum atau i 1 j 1
m
n
c i 1 j 1
ij
xij minimum
Masalah ini dapat digambarkan sebagai suatu network sebagai berikut :
Vertex – vertex sumber
ai
s1
t1
si
ti
sm
tn
bj
Vertex – vertex target
ai = arus masuk pada vertex si ; bj arus keluar pada vertex tj Pada tiap edge (si, tj) diberikan suatu bilangan wij atau cij. Permasalahannya adalah bagaimana menentukan (mentransport) arus x ij m
dari si ke tj sedemikian sehingga
n
w i 1 j 1
m
ij
xij
maksimum atau
n
c i 1 j 1
ij
xij minimum.
2. Tujuan Bagaimana menentukan kombinasi transportasi dari sumber ke tujuan dengan menggunakan metoda primal-dual. 3. Metoda Primal Dual Dipandang bentuk Primal sebagai berikut : m
Maksimalkan
n
w
ij
i 1 j 1 n
Dengan kendala :
x j 1
ij
ai , i 1,2,..., m
ij
bi , i 1,2,..., n
m
x i 1
xij
xij 0 30…………….Jurnal Ilmiah SINUS
Bentuk dual dari primal di atas adalah m
n
i 1
j 1
ai y i b j z j
Minimumkan Dengan kendala
yi z j wij dimana yi , zj bebas dalam tanda.
Primal mempunyai penyelesaian optimum bila dan hanya bila Dual mempunyai optimum dan dalam hal ini maksimum objektif primal sama dengan minimum objektif pada dual. Analisa Complementary Slackness n
x ij ai , i 1,2,..., m ,
Jika xij 0 ,
j 1
yi z j wij ekuivalen dengan
m
n
(w i 1 j 1
ij
m
m
x i 1
ij
bi , i 1,2,..., n dan
n
w i 1 j 1
ij
m
xij =
n
( y i 1 j 1
i
z j ) xij
yi z j ) xij 0
(wij yi z j ) xij 0 sehingga didapat : xij 0 atau wij yi z j ; i=1.2,.., m ; j=1,2,..,n Dari analisa dualitas, complementary slackness dan dualitas masalah transportasi di atas dapat dipandang sebagai berikut : Dapat ditentukan suatu solusi fisibel dari primal dan solusi fisibel dari dual sedemikian hinngga kondisi complementary slackness dipenuhi, maka permasalahan terselesaikan (diperoleh xij yang merupakan solusi optimum). 4. Algoritma Metoda Primal-Dual Untuk Masalah Transportasi Step 0 : (inisialisasi vertex berlabel) 1. Susun yi= maksimum wij (i=1,2,..,m) zj=0, (j=1,0,..,n) 2. Konstruksikan suatu network G(V,E) V S T {s, t} dimana S= himpunan vertex-vertex sumber = (s1, s2, .., sm) T=himpunan vertex-vertex target = (t1, t2, .., tn) s=source ; t= target
Jurnal Ilmiah SINUS…………….31
E={(s,si), si S} {(t j , t ), t j T } J dengan J {{si , t j ) / yi z j wij } 3. Susun arus xij=0, edge (si,tj) J. Step 1. : (arus maksimum) Dimulai dari arus yang diberikan, cari arus maksimum dari network G. Ambil L adalah himpunan dari vertex-vertex berlabel. Kapasitas dari : (s,si)n=ai, (tj,t)=bj, (si,tj)= ,i, j Ambil xij sebagai arus pada edge-edge (si,tj) dan v adalah besar arus. Jika v=r : STOP, Xij adalah solusi masalah, jika tidak, go to step 2. 1 Step 2. : Hitung minimum (yi+zj-wij) 2 (si , t j ); si L, t j L ’
Susun untuk si L : yi=yi- t i L : zi=zi- si L ‘: yi=yi+ t i L : zi=zi+ Hapus (si, tj) dari J jika si L ‘, tj L Tambahkan (si,tj) ke J jika si L, tj L’ dan yi+zj=wij, Ulangi step 1. Contoh Permasalahan : Perusahaan X yang memasarkan suatu komoditi tertentu mempunyai 4 pabrik dimana masing-masing pabrik mampu memproduksi sejumlah ai barang per harinya (i=1,2,3,4). Pemesan barang-barang tersebut terdapat di 3 kota, dimana masing-masing pemesan perharinya mampu membeli sejumlah bj barang (j=1,2,3). Dalam hal ini diasumsikan jumlah semua barang yang dapat diproduksi dari ke-4 pabrik perhari sama dengan jumlah semua barang yang mungkin dibeli oleh pemesan-pemesan di 3 kota tersebut. Keuntungan yang diterima oleh perusahaan dengan mengirim barang dari pabrik I ke pemesan di kota j sebesar wij rupiah ditabel kan sebagai berikut :
32…………….Jurnal Ilmiah SINUS
ai \ bj 2 2 3 3
2 2 3 3 4
3 4 1 2 3
5 1 1 2 4
Diperlukan cara pendistribusian barang-barang agar semua produksinya terjual dan diperoleh keuntungan maksimum. Penyelesaian : Jika jumlah barang yang didistribusikan dari pabrik I ke kota j adalah xij (dengan xij 0), maka masalah transportasi di atas dapat disajikan sebagai berikut : 4
3
w
Maksimalkan
ij
i 1 j 1
4
x
Dengan kendala :
j 1
ij
xij
ai ;
3
x i 1
ij
bi
xij 0
dalam hal ini
m
n
i 1
j 1
ai b j r 10
Dicari yidan zj yang memenuhi solusi fisibel dari dual sebagai berikut : Netwoknya : s1 2 s2 v
2 s
3
s3
3 s4
,0 ai ,0 ai ,0
ai ,0 ai ,0 ai
t1 2 t2
3 s
v
5 t3
Jurnal Ilmiah SINUS…………….33
Iterasi 1 : Mencari arus Maksimum s1 2,2 s2 2,2 s
V=7
3,0
s3
3,3
L’ , 0
L
t1 2,2
, 2 , L0 , 0 L’
L’
L
t2
3,2 V=7
s 5,3
L’ t3 , 3 V=7 r=10 perlu diadakan perubahan untuk harga-harga yi dan zj dan semua (si,tj) dengan si L , tj L’. =1/2. Harga baru yi’ dan zj’ terlihat pada tabel berikut : s4
ai \ bj 2 2 3 3
2 2 3 3 4 0 0.5
3 4 1 2 3 0 -0.5
5 1 1 2 4 0 -0.5
4 3 3 4 zj\yi z j’
4.5 2.5 3.5 4.5 yi’
Iterasi 2 : Mencari arus Maksimum untuk network yang baru s1
t1
2
2,2
2,2 s2
2
2,2 s V=10
3,3
0 1
s3 2
34…………….Jurnal Ilmiah SINUS
3,3 s 5,5
3,3 s4
t2
t3
L’ 3
V=10
Karena besar arus maksimum v=r=10, maka STOP. Distribusi barangnya adalah :
xij i\ j 1 2 3 4
1 0 2 0 0
2 2 0 1 0
3 0 0 2 3
wij i\ j 1 2 3 4
1 2 3 3 4
2 4 1 2 3
3 1 1 2 4
4
3
Keuntungan Maksimum = wij xij i 1 j 1
= 4.2 + 3.2 + 2.1 + 2.2 + 4.3 =32 5. Kesimpulan Masalah transportasi dapat diselesaikan dengan ide dari metoda primal dual, yaitu menyelesaikan masalah arus maksimum pada network G(V,E,U) dengan V={s,t,S,T} dengan S={s1, s2, .., sm}, T={t1, t2, .., tn} s = vertex sumber, t = vertex target. E = {(s,si), (si, tj), (tj,t)} ; u = ai, pada edge-edge (s,si), u=bj, pada edge-edge (tj,t), u= , pada edge-edge (si,tj) Besar arus v pada (si,t) =xij a. Jika dicapai besar arus v=r, maka masalah terselesaikan, diperoleh solusi optimum. b. Jika v
Jurnal Ilmiah SINUS…………….35
Pustaka 1. Chvatal, Vasek, ”Linear Programming”, W.H Freeman and Company, new York, 1993. 2. Taha, Hamdy A., Operatios Research : An Introduction, 4rd ed, Macmillan Publishing Co. Inc, New York, 1992 3. Jensen ,Poul Q, Operation research Model & Metode, Mathematical techniques of operation research http://www.londonexternal.ac.uk (akses 2007) 4. Network Flow Programming http://www.me.utexas.edu (akses 2007) 5. Jensen ,Poul Q, Mathematical techniques of operation research http://www.londonexternal.ac.uk (akses 2007)
36…………….Jurnal Ilmiah SINUS
