I PENDAHULUAN 1.1 Latar Belakang Bencana alam merupakan interupsi signifikan terhadap kegiatan operasional sehari-hari yang bersifat normal dan berkesinambungan. Interupsi ini dapat menyebabkan entitas yang tertimpa bencana kehilangan sumber-sumber daya sehingga mengalami disfungsi. Kondisi seperti ini tentunya akan menumbuhkan permintaan terhadap bantuan yang ditujukan kepada masyarakat di luar wilayah bencana. Dengan demikian, diperlukan sistem distribusi barang bantuan penanggulangan bencana yang sangat mendukung. Distribusi barang bantuan penanggulangan bencana alam berkaitan dengan masalah pengiriman barang bantuan dari pusat-pusat penampungan barang bantuan ke pusat-pusat penerimaan atau tujuan, dalam kasus ini adalah titik tempat terjadinya bencana.
Karya ilmiah ini merupakan pengkajian dari masalah yang berhubungan dengan bencana alam yaitu pendistribusian logistik dan pengalokasian kendaraan untuk mendistribusikan logistik tersebut. Masalah ini telah dikaji oleh Ozdamar, Ekinci dan Kucukyazici. 2004 dalam jurnalnya yang berjudul Emergency logistic planning in natural disasters. Dalam karya ilmiah ini akan menentukan solusi optimal dari banyaknya permintaan yang tidak terpenuhi di suatu daerah yang terkena bencana alam dengan menggunakan bantuan software LINGO 8.0. 1.2 Tujuan Penulisan karya ilmiah ini bertujuan untuk memodelkan masalah yang berkaitan dengan pendistribusian logistik bencana alam dan menyelesaikan masalah tersebut. .
II LANDASAN TEORI Metode pemecahan yang digunakan dalam masalah pendistribusian logistik bencana alam memerlukan definisi-definisi berikut ini.
2.1 Linear Programming Linear programming adalah kegiatan merencanakan untuk mendapatkan hasil yang optimal. Model linear programming (LP) meliputi pengoptimuman suatu fungsi linear terhadap kendala linear. (Nash & Sofer 1996) Suatu LP mempunyai bentuk standar seperti yang didefinisikan sebagai berikut: Definisi 1 (Bentuk Standar suatu LP) Suatu linear progamming dikatakan berbentuk standar jika dapat dituliskan sebagai: Minimumkan z = cTx terhadap Ax = b x ≥0 (1) dengan x dan c berupa vektor berukuran n, vektor b berukuran m, sedangkan A berupa matriks berukuran m n, yang disebut juga sebagai matriks kendala. (Nash & Sofer 1996) Sebagai catatan, yang dimaksud dengan vektor
berukuran n adalah vektor yang memiliki dimensi (ukuran) n × 1. 2.1.1 Solusi suatu Linear Programming Untuk menyelesaikan suatu masalah linear programming (LP), metode simpleks merupakan salah satu metode yang dapat menghasilkan solusi optimum. Metode ini mulai dikembangkan oleh Dantzig tahun 1947. Dalam perkembangannya, metode ini adalah metode paling umum digunakan untuk menyelesaikan LP, yaitu berupa metode iteratif untuk menyelesaikan masalah LP dalam bentuk standar. Pada LP (1), vektor x yang memenuhi kendala Ax=b disebut sebagai solusi dari LP (1). Misalkan matriks A dapat dinyatakan sebagai A= (B N), dengan B adalah matriks yang elemennya berupa koefisien variabel basis dan N merupakan matriks yang elemennya berupa koefisien variabel nonbasis pada matriks kendala. Matriks B disebut matriks basis untuk LP (1). Jika vektor x dapat dinyatakan sebagai vektor x=
B N
, dengan xB adalah vektor
variabel basis dan xN adalah vektor variabel nonbasis, maka Ax=b dapat dinyatakan sebagai:
2
Ax= (2) =BxB+NxN =b. Karena B adalah matriks taksingular, maka B memiliki invers, sehingga dari (2) xB dapat dinyatakan sebagai: (3) xB=B−1b − B−1NxN Definisi 2 (Solusi basis) Solusi dari suatu LP disebut solusi basis jika: 1. solusi tersebut memenuhi kendala pada LP, 2.
kolom-kolom dari matriks koefisien yang berpadanan dengan komponen taknol adalah bebas linear. (Nash & Sofer 1996)
Definisi 3 (Solusi basis fisibel) Vektor x disebut solusi basis fisibel jika x merupakan solusi basis dan x . Salah satu cara menentukan solusi basis fisibel awal . adalah dengan membuat xN (Nash & Sofer 1996) Ilustrasi solusi basis dan solusi basis fisibel dapat dilihat dalam contoh berikut: Contoh 1 Misalkan diberikan linear programming berikut: Minimumkan z= − 2x1 − 3x2 terhadap − 2x1 + x2+ x3 = 4 − x1+ 2x2+ x4=11 x1+ x5 = 5 (4) x1, x2, x3, x4, x5 0 Dari LP tersebut didapatkan: A=
4 2 1 1 0 0 1 2 0 1 0 , b= 11 . 1 0 0 0 1 5
Misalkan dipilih xB=(x3 x4 x5)T dan xN =(x1 x2)T maka matriks basisnya adalah 1 0 0 B= 0 1 0 . 0 0 1 Dengan menggunakan mariks basis tersebut diperoleh: (5) xN=(0 0)T, xB=B−1b=(4 11 5)T
Solusi (5) merupakan solusi basis, karena solusi tersebut memenuhi kendala LP (4) dan kolom-kolom pada matriks kendala yang berpadanan dengan komponen taknol dari (5), yaitu B adalah bebas linear, yaitu kolom yang satu bukan merupakan kelipatan dari kolom yang lain. Solusi (5) juga merupakan solusi basis fisibel, karena nilai-nilai variabelnya lebih dari atau sama dengan nol. Definisi 4 (Daerah fisibel) Daerah fisibel suatu LP adalah himpunan semua titik yang memenuhi semua kendala dan pembatasan tanda pada LP tersebut. (Winston 2004) Definisi 5 (Solusi optimal) Untuk masalah maksimisasi, solusi optimal suatu LP adalah suatu titik dalam daerah fisibel dengan nilai fungsi objektif terbesar. Untuk masalah minimisasi, solusi optimal suatu LP adalah suatu titik dalam daerah fisibel dengan nilai fungsi objektif terkecil. (Winston 2004) 2.2 Integer Programming Integer programming (IP) adalah suatu model linear programming dengan variabel yang digunakan berupa bilangan bulat (integer). Jika semua variabel harus berupa integer, maka masalah tersebut disebut pure integer programming. Jika hanya sebagian yang yang harus integer maka disebut mixed integer programming. IP dengan semua variabelnya harus bernilai 0 atau 1 disebut 0−1 IP. (Garfinkel & Nemhauser 1972) Definisi 6 (Linear programming relaksasi) LP-relaksasi merupakan masalah linear programming yang diperoleh dari suatu IP dengan menghilangkan kendala integer atau kendala 0−1 pada setiap variabelnya. (Winston 1995) Untuk masalah maksimisasi, nilai fungsi objektif yang optimal di LP-relaksasi lebih besar atau sama dengan nilai fungsi objektif optimal dari IP, sedangkan untuk masalah minimisasi nilai fungsi objektif yang optimal di LP-relaksasi lebih kecil atau sama dengan nilai optimal fungsi objektif IP. 2.3 Metode Branch and Bound Masalah integer programming dapat dipecahkan dengan metode branch and bound. Prinsip dasar metode branch and bound adalah
3
membagi daerah fisibel dari masalah LPrelaksasi dengan cara membuat subproblemsubproblem baru sehingga masalah integer programming terpecahkan. Daerah fisibel suatu linear programming adalah daerah yang memuat titik-titik yang memenuhi kendala linear masalah linear programming. Berikut ini adalah langkah-langkah dalam penyelesaian metode branch and bound untuk masalah maksimisasi: • Langkah 0 Didefinisikan z sebagai batas bawah dari solusi IP yang optimum. Pada awalnya tetapkan z = −∞ dan i = 0. • Langkah 1 Subproblem LP(i) dipilih sebagai bagian masalah berikutnya untuk diteliti. Subproblem LP(i) diselesaikan dan diukur dengan kondisi yang sesuai. 1. Jika LPi terukur, batas bawah z diperbarui jika solusi IP yang lebih baik ditemukan. Jika tidak, bagian masalah (subproblem) baru i dipilih dan langkah 1 diulangi. Jika semua subproblem telah diteliti, maka proses dihentikan. 2. Jika LPi tidak terukur, lanjutkan ke Langkah 2 untuk melakukan pencabangan LPi. Menurut Winston (2004) LPi dikatakan terukur jika terdapat kondisi sebagai berikut: 1. Subproblem menghasilkan solusi takfisibel, sehingga tidak dapat menghasilkan solusi optimal bagi IP 2. Subproblem tersebut menghasilkan suatu solusi optimal dengan semua variabelnya bernilai integer. Jika solusi optimal ini mempunyai nilai fungsi objektif yang lebih baik daripada solusi fisibel yang diperoleh sebelumnya, maka solusi ini menjadi kandidat solusi optimal dan nilai fungsi objektifnya menjadi batas bawah nilai fungsi objektif optimal bagi masalah IP pada saat itu. Bisa jadi subproblem menghasilkan solusi optimal untuk masalah IP. 3. Nilai fungsi objektif optimal untuk subproblem tersebut tidak melebihi (untuk masalah maksimisasi) batas bawah saat itu, maka subproblem ini dapat dieliminasi. • Langkah 2 Pilih satu variabel xj yang nilai optimumnya, yaitu xj*, tidak memenuhi batasan integer dalam solusi LPi. Singkirkan bidang [xj*] < xj < [xj*]+1 dengan membuat dua bagian masalah LP yang berkaitan menjadi
dua batasan yang tidak dapat dipenuhi secara bersamaan yaitu: xj ≤ [xj*] dan xj ≥ [xj*]+1 dengan [xj*] didefinisikan sebagai integer terbesar yang kurang dari atau sama dengan xj*. Kembali ke Langkah 1. (Taha 1996) Untuk memudahkan pemahaman mengenai metode branch and bound diberikan contoh sebagai berikut: Contoh 1: Misalkan diberikan IP sebagai berikut: Maksimumkan z = 5x1 + 4x2 terhadap x1 + x2 ≤ 5 (6) 10x1 + 6x2 ≤ 45 x1, x2 ≥ 0 dan integer Solusi optimal PL-relaksasi dari masalah IP (6) adalah x1=3.75, x2=1.25, dan z =23.75 (lihat Lampiran 1). Jadi batas atas nilai optimal fungsi objektif masalah IP (6) adalah z= 23.75. Daerah fisibel PL-relaksasi masalah (6) ditunjukkan pada Gambar 1 (daerah yang diarsir) sedangkan titik-titik merupakan solusi fisibel masalah IP (6).
x2
x1
Gambar 1 Daerah fisibel untuk PL-relaksasi dari IP (6).
Langkah berikutnya adalah memartisi daerah fisibel PL-relaksasi menjadi dua bagian berdasarkan variabel yang bernilai pecahan (noninteger). Karena x1= 3.75 dan x2=1.25 variabel bernilai pecahan maka dipilih salah satu variabel, misalkan x1, sebagai dasar pencabangan. Jika masalah PL-relaksasi dari IP (6) diberi nama Subproblem 1 dan Subproblem 1 dicabangkan atas x1, maka pencabangan tersebut menghasilkan 2 subproblem, yaitu: • Subproblem 2: Subproblem 1 ditambah kendala x1 ≤ 3 • Subproblem 3: Subproblem 1 ditambah kendala x1 ≥ 4.
4
Daerah fisibel untuk kedua subproblem di atas diilustrasikan secara grafis pada Gambar 2. x2
Subproblem 2
Subproblem 3
x1
Gambar 2 Daerah fisibel untuk Subproblem 2 (x1 ≤ 3) dan Subproblem 3 (x1≥4). Setiap titik (solusi) fisibel dari IP (6) termuat dalam daerah fisibel Subproblem 2 atau Subproblem 3. Setiap subproblem ini saling lepas. Sekarang dipilih subproblem yang belum diselesaikan, misalkan dipilih Subproblem 3. Solusi optimal untuk Subproblem 3 ini adalah x1 = 4, x2 = 0.8333 dan z = 23.333, (lihat Lampiran 1 bagian Subproblem 3). Karena solusi optimal yang dihasilkan Subproblem 3 bukan solusi integer, maka Subproblem 3 dicabangkan atas x2 sehingga diperoleh dua subproblem lagi, yakni: • Subproblem 4: Subproblem 3 ditambah kendala x2 ≥ 1; • Subproblem 5: Subproblem 3 ditambah kendala x2 ≤ 0. Saat ini subproblem yang belum diselesaikan adalah Subproblem 2, 4 dan 5. Salah satu subproblem dipilih, misalnya dengan aturan LIFO (last in first out). Dengan aturan ini berarti dipilih Subproblem 4 atau Subproblem 5. Subproblem 4 takfisibel (lihat Lampiran 1 bagian Subproblem 4) maka
subproblem ini tidak dapat menghasilkan solusi optimal, yang tersisa adalah Subproblem 2 dan Subproblem 5. Karena aturan LIFO, dipilih Subproblem 5, yang kemudian menghasilkan solusi optimal x1=4.5, x2=0 dan z=22.5 (lihat Lampiran 1 bagian Subproblem 5). Karena x1=4.5 bukan integer, maka dilakukan kembali pencabangan atas x1, sehingga diperoleh: • Subproblem 6: Subproblem 5 ditambah kendala x1≥5 ; • Subproblem 7: Subproblem 5 ditambah kendala x1≤4. Misalkan dipilih Subproblem 6. Ternyata Subproblem 6 ini juga takfisibel (lihat Lampiran 1 bagian Subproblem 6), sehingga tidak dapat menghasilkan solusi optimal. Dengan demikian subproblem-subproblem yang belum diselesaikan adalah Subproblem 2 dan Subproblem 7. Karena aturan LIFO, dipilih Subproblem 7. Subproblem ini kemudian menghasilkan solusi opimal x1=4, x2= 0, dan z= 20 (lihat Lampiran 1 bagian Subproblem 7). Dapat dilihat bahwa solusi optimal subproblem ini semuanya berupa integer, sehingga merupakan kandidat solusi untuk IP (6). Nilai z pada kandidat solusi ini merupakan batas bawah bagi nilai optimal IP. Penyelesaian Subproblem 2 menghasilkan solusi optimal x1= 3, x2= 2 dan z= 23 (lihat Lampiran 1 bagian 2). Batas bawah yang ditetapkan dari solusi optimal Subproblem 7 tidak lebih baik dari nilai solusi optimal yang dihasilkan Subproblem 2. Dengan demikian, nilai solusi optimal Subproblem 2, yakni z = 23 menjadi batas bawah yang baru. Semua solusi optimal telah berupa integer dan tidak perlu dilakukan pencabangan kembali, sehingga solusi optimal dari Subproblem 2 merupakan solusi optimal IP (6), yakni x1= 3, x2= 2 dan z= 23. Pohon pencabangan yang menunjukkan proses penyelesaian masalah IP (6) secara keseluruhan ditunjukkan pada Gambar 3.
5
t=1
Subproblem 1 x1=3.75, x2=1.25, dan z = 23.75 x1 ≤ 3
x1 ≥ 4 Subproblem 3 x1=4, x2=0.8333, dan z = 23.333
t=2
x2≤ 0
x2≥1 t=3
Subproblem 2 x1=3, x2=2, dan z = 23 batas bawah bagi IP( 6) atau Solusi Optimal
t=7
Subproblem 4 Solusi takfisibel
Subproblem 5 x1=4.5, x2=0, dan z = 22.5
t=4 x1≤4
x1≥5 t=5
Subproblem 6 Solusi takfisibel
Subproblem 7 x1=4, x2=0, dan z = 20 batas bawah, Kandidat Solusi Optimal
t=6
Gambar 3 Pencabangan yang dilakukan metode branch and bound untuk menentukan solusi IP dengan t menyatakan urutan penyelesaian subproblem.
2.4 Graf Definisi 7 (Graf) Suatu graf G adalah pasangan terurut (V, E), dengan V himpunan takkosong dan berhingga dan E adalah himpunan takterurut yang menghubungkan elemen-elemen V, dinotasikan dengan G = (V, E). Elemen V dinamakan simpul atau vertex dan elemen E dinamakan sisi (edge), dinotasikan dengan {i, j} , yakni sisi yang menghubungkan simpul i dengan simpul j, dengan i, j ∈V . (Foulds 1992) Graf seperti pada Definisi 7 disebut juga graf takberarah. Ilustrasi graf takberarah dapat dilihat pada Gambar 4. G
1
2
Definisi 8 (Digraf) Graf berarah (directed graph/digraph) adalah pasangan terurut (V, A) dengan V himpunan takkosong dan berhingga, dan A adalah himpungan pasangan terurut dari elemen-elemen di V. Elemen-elemen dari A disebut arc (sisi berarah) dan dituliskan sebagai ( i , j ) , dengan i, j ∈V . (Foulds 1992) Ilustrasi graf berarah dapat dilihat pada gambar pada Gambar 5. G’
1
2
4
3
5 4
3
5
Gambar 4 Graf G = (V, E). Graf pada Gambar 4 mempunyai himpunan simpul V = {1,2,3,4,5} dan himpunan sisi E = {{1,2},{1,4},{2,3},{3,4},{2,4},{3,5},{4,5}}.
Gambar 5 Graf G’= (V,A). Graf pada Gambar 5 memiliki himpunan simpul V ={1,2,3,4,5} dan himpunan sisi berarah A={(1,4),(1,2),(4,2),(2,3),(4,3),(3,5),(5,4)}
6
Definisi 9 (Graf Berbobot) Suatu graf G = (V,E) atau graf berarah D = (V,A) dikatakan berbobot jika terdapat fungsi w : E → ℜ atau l : A → ℜ (dengan ℜ himpunan bilangan real) yang memberikan bobot pada setiap elemen E atau A. (Foulds 1992) D:
6
1
Gambar 6 Digraf berbobot D=(V,A).
Fungsi w : A → ℜ untuk digraf berbobot D = (V, A) pada Gambar 6, dengan: w(1,2)=2; w(1,3)=4; w(2,3)=1; w(2,4)=4; w(2,5)=2; w(3,5)=3; w(5,4)=3; w(4,6)=2; w(5,6)=2 merupakan fungsi bobot pada digraf D. 2.5 Frekuensi pengiriman barang Frekuensi pengiriman barang (f) adalah ukuran banyaknya putaran ulang pengiriman barang dalam selang periode waktu (t) yang diberikan. Secara matematis rumus mencari , dengan kata lain frekuensi adalah f = misalnya bila waktu pengiriman barang dua periode maka frekuensi pengiriman adalah setengah. (Tipler 2001)
III DESKRIPSI DAN FORMULASI MASALAH 3.1 Deskripsi Masalah Terjadinya bencana alam akan menyebabkan entitas yang tertimpa bencana kehilangan sumber-sumber daya sehingga mengalami disfungsi. Kondisi seperti ini tentunya akan menimbulkan permintaan terhadap bantuan yang ditujukan kepada masyarakat di luar wilayah bencana. Untuk masyarakat di luar wilayah bencana, bencana alam akan menumbuhkan rasa simpati dan keinginan memberikan bantuan kepada korban bencana alam. Di dalam pendistribusian barang bantuan diperlukan sarana transportasi untuk mendistribusikan barang bantuan tersebut, sarana transportasi yang digunakan dapat berupa: transportasi darat, laut, udara dan kereta api. Banyaknya sarana transportasi yang tersedia di titik pasokan maupun di titik permintaan adalah berbeda. Selain itu kapasitas muat setiap sarana transportasi juga berbeda. Struktur model distribusi barang bantuan penanggulangan bencana alam terdiri atas beberapa komponen yang terlibat, yaitu titik pemasok, titik persinggahan, titik permintaan atau titik tujuan, dan titik tunggu. Deskripsi untuk setiap titik yang terlibat adalah sebagai berikut: 1. Titik pasokan adalah titik penampungan barang bantuan di titik tersebut maupun titik penampungan dari titik pasokan yang lain atau titik yang memiliki komoditas barang bantuan yang diperlukan dan kemudian akan didistribusikan dengan menggunakan sarana transportasi yang
tersedia di titik pasokan maupun titik permintaan. 2. Titik permintaan atau titik tujuan, yaitu titik yang memiliki sejumlah permintaan atau kebutuhan barang bantuan, yang akan dikirim oleh titik pasokan maupun titik persinggahan. 3. Titik persinggahan yaitu titik permintaan yang juga sekaligus berperan sebagai titik pasokan. Bila titik persinggahan dipasok sejumlah barang yang jumlahnya lebih besar dari jumlah kebutuhan, maka akan terdapat sejumlah kelebihan barang yang selanjutnya dapat dikirimkan ke titik permintaan yang lainnya. 4. Titik tunggu yaitu titik yang digunakan seolah-olah untuk menampung sementara komoditas yang dikirim lebih dari satu periode. Misalnya bila pengiriman barang memerlukan waktu selama tiga periode, maka di akhir periode t permintaan belum terpenuhi dan baru terpenuhi setelah pada periode t+3. Dalam proses penghitungan yang dilakukan, barang pasokan tersebut seolah-olah ditampung sementara di titik tunggu, dan akan menunggu di titik tunggu tersebut sampai tiga periode kemudian. 3.2 Formulasi Masalah Model di kasus ini melibatkan beberapa tempat yang berfungsi sebagai titik pasokan dan titik permintaan. Misalkan tempat A, B dan C terkena bencana alam sehingga membutuhkan barang bantuan dengan kata lain sebagai titik permintaan, sedangkan D, E, F
