PENDAHULUAN Latar Belakang Masalah pengiriman barang hasil produksi bagi suatu perusahaan kepada para pelanggannya merupakan masalah yang sangat penting, karena hal itu berkaitan dengan kepuasan pelanggan akan pelayanan. Untuk memenuhi permintaan pelanggan akan suatu produk, suatu perusahaan diharuskan mengirim produk tersebut dengan sebaik mungkin. Di pihak lain, perusahaan tentu menginginkan keuntungan yang besar, karena itu, biaya pengiriman haruslah seminimum mungkin. Banyaknya rute pengiriman yang mungkin dari pabrik ke pelanggan serta ketersediaan terminal sebagai tempat transit tentu menjadi masalah yang sangat rumit bagi pihak manajemen. Oleh sebab itu, perusahaan harus dapat menentukan rute dan terminal yang tepat sehingga biaya pengiriman yang dikeluarkan minimum. Masalah penentuan kombinasi terminal dan rute kapal dapat pula dimodelkan sebagai masalah pemrograman bilangan bulat campuran/mixed integer programming (MIP).
MIP adalah masalah optimisasi dengan fungsi objektif dan kendala yang linear yang beberapa variabelnya diharuskan integer dan selainnya bisa integer atau tidak. Karya ilmiah ini merupakan penyederhanaan dari permasalahan yang dihadapi oleh salah satu supplier pasar pulp terbesar di dunia, Sodra Cell AB, yang telah dibahas oleh Gunnarsson, H. RÖnnqvist, M. Carlsson, D. (2006) dalam jurnal yang berjudul A combined terminal location and ship routing problem. Dalam karya ilmiah ini akan ditunjukkan solusi optimal dari masalah penentuan kombinasi terminal dan rute kapal dengan menggunakan bantuan software LINGO 8.0. Tujuan Tujuan penulisan karya ilmiah ini adalah menunjukkan peranan MIP (mixed integer programming) dalam menentukan kombinasi terminal dan rute kapal.
LANDASAN TEORI Untuk memahami masalah penentuan kombinasi terminal dan rute kapal serta teknik pemecahan yang digunakan dalam karya tulis ini, diperlukan definisi dari beberapa konsep berikut ini. Fungsi Linear dan Pertidaksamaan Linear Fungsi linear dan pertidaksamaan linear merupakan salah satu konsep dasar yang harus dipahami terkait dengan konsep pemrograman linear. Definisi 1 (Fungsi Linear) f ( x1 , x 2 ,..., x n ) Suatu fungsi
dalam
variabel-variabel x1 , x2 ,..., xn adalah suatu fungsi linear jika dan hanya jika untuk suatu himpunan konstanta c1 , c2 ,..., cn ,
f ( x1 , x 2 ,..., x n ) = c1 x1 + c 2 x 2 + ... + c n x n . (Winston, 2004) Sebagai gambaran, f ( x1 , x2 ) = 2 x1 + 3 x2 merupakan fungsi linear, sementara f ( x1 , x2 ) = x12 x 22 bukan fungsi linear.
Definisi 2 (Pertidaksamaan dan Persamaan Linear) Untuk sembarang fungsi linear f ( x1 , x 2 ,..., x n ) dan sembarang bilangan b ,
f ( x1 , x 2 ,..., x n ) ≤ b dan f ( x1 , x 2 ,..., x n ) ≥ b adalah pertidaksamaan linear. Misalkan b sembarang bilangan, suatu persamaan f ( x1 , x 2 ,..., x n ) = b merupakan persamaan linear. (Winston, 2004)
pertidaksamaan
Pemrograman Linear Pemrograman linear (PL) atau linear programming (LP) adalah suatu masalah optimisasi yang memenuhi ketentuanketentuan sebagai berikut: a) Tujuan masalah tersebut adalah memaksimumkan atau meminimumkan suatu fungsi linear dari sejumlah variabel keputusan. Fungsi yang akan dimaksimumkan atau diminimumkan ini disebut fungsi objektif. b) Nilai variabel-variabel keputusannya harus memenuhi suatu himpunan kendala. Setiap
2
kendala harus berupa persamaan linear atau pertidaksamaan linear. c) Ada pembatasan tanda untuk setiap variabel dalam masalah ini. Untuk sembarang variabel x i , pembatasan tanda menentukan x i harus taknegatif ( x i ≥ 0) atau tidak dibatasi tandanya (unrestricted in sign). (Winston, 2004) Suatu PL mempunyai bentuk standar seperti yang didefinisikan sebagai berikut.
Misalkan x dinyatakan sebagai vektor x x = B , dengan xB adalah vektor variabel xN basis dan x N adalah vektor variabel nonbasis, maka Ax = b dapat dinyatakan sebagai x Ax = ( B N ) B xN (2.2) = Bx B + Nx N = b. Karena matriks B adalah matriks taksingular, maka B memiliki invers, sehingga dari (2.2) x B dapat dinyatakan sebagai: x B = B -1b - B -1 Nx N .
Definisi 3 (Bentuk Standar PL) Suatu pemrograman linear didefinisikan mempunyai bentuk standar: maks z = cT x terhadap Ax = b (2.1) x≤0 dengan x dan c berupa vektor berukuran n, vektor b berukuran m, sedangkan A berupa matriks berukuran m × n yang disebut juga matriks kendala. [Nash & Sofer, 1996] Sebagai catatan, yang dimaksud dengan vektor berukuran n adalah vektor yang memiliki dimensi (ukuran) n × 1. Solusi Pemrograman Linear Suatu masalah PL dapat diselesaikan dalam berbagai teknik, salah satunya adalah metode simpleks. Metode ini dapat menghasilkan suatu solusi optimal bagi masalah PL dan telah dikembangkan oleh Dantzig sejak tahun 1947, dan dalam perkembangannya merupakan metode yang paling umum digunakan untuk menyelesaikan PL. Metode ini berupa metode iteratif untuk menyelesaikan PL berbentuk standar.
Pada masalah PL (2.1), vektor x yang memenuhi kendala Ax = b disebut solusi PL (2.1). Misalkan matriks A dinyatakan sebagai A = ( B N ) , dengan B adalah matriks berukuran m × m yang elemennya berupa koefisien variabel basis dan N merupakan matriks berukuran m × (n − m) yang elemenelemennya berupa koefisien variabel nonbasis pada matriks kendala. Dalam hal ini matriks B disebut matriks basis untuk PL (2.1).
(2.3)
Definisi 4 (Solusi Basis) Solusi dari suatu PL disebut solusi basis jika memenuhi syarat berikut: i. solusi tersebut memenuhi kendala pada PL; ii. kolom-kolom dari matriks kendala yang berpadanan dengan komponen taknol dari solusi tersebut adalah bebas linear. (Nash & Sofer, 1996) Definisi 5 (Solusi Basis Fisibel) Vektor x disebut solusi basis fisibel jika x merupakan solusi basis dan x ≥ 0. (Nash & Sofer, 1996)
Ilustrasi solusi basis dan solusi basis fisibel diberikan dalam Contoh 1. Contoh 1 Misalkan diberikan PL (2.4) berikut: min z = −x1 − 2x2
terhadap
− 2x1 + x2 + x3 = 2 − x1 + 2x2 + x4 = 7
(2.4)
x1 + x5 = 5 x1, x2 , x3 , x4 , x5 ≥ 0, dari PL (2.4) diperoleh: −2 1 1 0 0 2 A = −1 2 0 1 0 , b = 7 . 1 0 0 0 1 5 Misalkan dipilih
xB = ( x3 x4 x5 ) dan x N = ( x1 x2 ) , maka matriks basisnya adalah 1 0 0 B = 0 1 0 0 0 1 . Dengan menggunakan matriks basis di atas didapatkan T
T
3
x N = ( 0 0 ) , xB = B−1b = ( 2 7 5) . (2.5) Solusi (2.5) merupakan solusi basis, karena memenuhi kendala pada PL (2.4) dan kolomkolom pada matriks kendala yang berpadanan dengan komponen taknol dari (2.5), yaitu B bebas linear (kolom yang satu bukan merupakan kelipatan dari kolom yang lain). Solusi (2.5) juga merupakan solusi basis fisibel, karena nilai-nilai variabelnya lebih dari atau sama dengan nol. Hal yang juga penting dalam konsep pemrograman linear untuk model ini adalah daerah fisibel dan solusi optimal yang didefinisikan sebagai berikut. T
T
Definisi 6 (Daerah Fisibel) Daerah fisibel suatu PL adalah himpunan semua titik yang memenuhi semua kendala dan pembatasan tanda pada PL tersebut. (Winston, 2004) Definisi 7 (Solusi Optimal) Untuk masalah maksimisasi, solusi optimal suatu PL adalah suatu titik dalam daerah fisibel dengan nilai fungsi objektif terbesar. Untuk masalah minimisasi, solusi optimal suatu PL adalah suatu titik dalam daerah fisibel dengan nilai fungsi objektif terkecil. (Winston, 2004) Integer Programming Integer programming (IP) atau pemrograman integer adalah suatu model pemrograman linear dengan variabel yang digunakan berupa bilangan bulat (integer). Jika semua variabel harus berupa integer, maka masalah tersebut dinamakan pure integer programming. Jika hanya sebagian yang harus berupa integer, maka disebut mixed integer programming (MIP). IP dengan semua variabelnya harus bernilai 0 atau 1 disebut 0-1 IP. (Garfinkel & Nemhauser, 1972) Definisi 8 (Pemrograman Linear Relaksasi) Pemrograman linear relaksasi atau sering disebut PL-relaksasi merupakan suatu pemrograman linear yang diperoleh dari suatu IP dengan menghilangkan kendala integer atau kendala 0-1 pada setiap variabelnya. Untuk masalah maksimisasi, nilai optimal fungsi objektif PL-relaksasi lebih besar atau sama dengan nilai optimal fungsi objektif IP, sedangkan untuk masalah minimisasi, nilai optimal fungsi objektif PL-relaksasi lebih
kecil atau sama dengan nilai optimal fungsi objektif IP. (Winston, 1995)
Metode Branch-and-Bound Pemecahan masalah pemrograman integer dapat dilakukan dengan metode branch-andbound. Prinsip dasar metode ini adalah memecah daerah fisibel suatu masalah PLrelaksasi dengan membuat subproblemsubproblem. Ada dua konsep dasar dalam algoritme branch-and-bound. • Cabang (Branch) Membuat partisi daerah solusi dari masalah utama (PL-relaksasi) dengan membentuk subproblem-subproblem, tujuannya untuk menghapus daerah solusi yang tidak fisibel. Hal ini dicapai dengan menentukan kendala yang penting untuk menghasilkan solusi IP, secara tidak langsung titik integer yang tidak fisibel terhapus. Dengan kata lain, hasil pengumpulan lengkap dari subproblemsubproblem ini menunjukkan setiap titik integer yang fisibel dalam masalah asli. Karena sifat partisi tersebut, maka prosedur ini dinamakan pencabangan (branching). • Batas (Bound) Misalkan masalah utamanya berupa masalah maksimisasi, nilai objektif yang optimal untuk setiap subproblem dibuat dengan membatasi pencabangan dengan batas atas dari nilai objektif yang dihubungkan dengan sembarang nilai integer yang fisibel. Hal ini sangat penting untuk mengatur dan menempatkan solusi optimal. Operasi pembatasan ini dinamakan pembatasan (bounding). (Taha, 1975) Metode branch-and-bound diawali dari menyelesaikan PL-relaksasi dari suatu integer programming. Jika semua nilai variabel keputusan solusi optimal sudah berupa integer, maka solusi tersebut merupakan solusi optimal IP. Jika tidak, dilakukan pencabangan dan penambahan batasan pada PL-relaksasinya kemudian diselesaikan. Winston (2004) menyebutkan bahwa nilai fungsi objektif optimal untuk IP ≤ nilai fungsi objektif optimal untuk PL-relaksasi (masalah maksimisasi), sehingga nilai fungsi objektif optimal PL-relaksasi merupakan batas atas bagi nilai fungsi objektif optimal untuk masalah IP. Diungkapkan pula oleh Winston (2004) bahwa nilai fungsi objektif optimal untuk suatu kandidat solusi merupakan batas bawah nilai fungsi objektif optimal untuk masalah IP asalnya. Suatu kandidat solusi
4
diperoleh jika solusi dari suatu subproblem sudah memenuhi kendala integer pada masalah IP, artinya fungsi objektif dan semua variabelnya sudah bernilai integer. Berikut ini adalah langkah-langkah penyelesaian suatu masalah maksimisasi dengan metode branch-and-bound. • Langkah 0 Didefinisikan z sebagai batas bawah dari nilai fungsi objektif (solusi) IP yang optimal. Pada awalnya ditetapkan z = −∞ dan i = 0. • Langkah 1 Subproblem PL(i ) dipilih sebagai bagian masalah berikutnya untuk diteliti. Subproblem PL(i ) diselesaikan dan diukur dengan kondisi yang sesuai. a) Jika PL(i ) 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. b) Jika tidak terukur, proses PL(i ) dilanjutkan ke langkah 2 untuk melakukan pencabangan PL(i ) . Menurut Winston (2004), suatu subproblem dikatakan terukur (fathomed) jika terdapat situasi sebagai berikut. 1. Subproblem tersebut takfisibel, sehingga tidak dapat menghasilkan solusi optimal untuk 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 ini 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 Dipilih salah satu variabel x j yang nilai optimalnya adalah x *j yang tidak memenuhi batasan integer dalam solusi
[ x *j ] <
x j < [ x *j ] + 1
PLi . Bidang
disingkirkan
dengan
membuat dua subproblem PL yang berkaitan
menjadi dua subproblem yang tidak dapat dipenuhi secara bersamaan, yaitu
x j ≤ [ x*j ] dan x j ≥ [ x*j ] + 1 , dengan [ x *j ] didefinisikan sebagai integer terbesar yang kurang dari atau sama dengan x *j . Kembali ke langkah 1. (Taha, 1996) Untuk memudahkan pemahaman metode branch-and-bound diberikan contoh sebagai berikut. Contoh 2 (Metode Branch-and-Bound) Misalkan diberikan pemrograman integer (IP) berikut max z = 2 x1 + 3 x2 terhadap
x1 + 2 x2 ≤ 10 3 x1 + 4 x2 ≤ 25
x1 , x2 ≥ 0; (2.6) x1 , x2 integer. Solusi optimal PL-relaksasi dari masalah IP (2.6) adalah x1 = 5 , x2 = 2.5 , dan z = 17.5 (lihat pada Lampiran 1). Batas atas nilai optimal fungsi objektif masalah ini adalah z = 17.5 . Daerah fisibel PL-relaksasi masalah (2.6) ditunjukkan pada Gambar 1 (daerah yang diarsir) sedangkan titik-titik merupakan solusi fisibel masalah IP (2.6).
Gambar 1 Daerah fisibel untuk PL-relaksasi dari IP (2.6).
Langkah berikutnya adalah memartisi daerah fisibel PL-relaksasi menjadi dua bagian berdasarkan variabel yang berbentuk pecahan (non-integer). Misalkan dipilih x2 sebagai dasar pencabangan. Jika masalah PL-relaksasi diberi nama Subproblem 1, maka pencabangan tersebut menghasilkan 2 subproblem, yaitu: • Subproblem 2: Subproblem 1 ditambah kendala x2 ≤ 2. • Subproblem 3: Subproblem 1 ditambah kendala x2 ≥ 3 ;
5
Hal ini diilustrasikan secara grafis pada Gambar 2.
dari Subproblem 4. Nilai z baru merupakan batas bawah baru bagi nilai optimal IP (2.6). Karena aturan LIFO, dipilih Subproblem 5, yang kemudian menghasilkan solusi optimal x1 = 6, x2 = 1.75 , z = 17.25 (lihat Lampiran 1). Karena x2 = 1.75 bukan integer, maka
Gambar 2 Daerah fisibel untuk Subproblem 2 dan Subproblem 3.
Setiap titik (solusi) fisibel dari IP (2.6) termuat dalam daerah fisibel Subproblem 2 atau Subproblem 3. Setiap subproblem ini saling lepas. Subproblem 2 dan Subproblem 3 dikatakan dicabangkan oleh x2 . Sekarang dipilih subproblem yang belum diselesaikan. Misalkan dipilih Subproblem 2, kemudian diselesaikan. Solusi optimal untuk Subproblem 2 ini adalah x1 = 5.67, x2 = 2 , dan z = 17.33 (lihat Lampiran 1). Karena solusi optimal yang dihasilkan Subproblem 2 bukan solusi integer, maka dipilih pencabangan pada Subproblem 2 atas x1 , sehingga diperoleh dua subproblem lagi, yakni: • Subproblem 4: Subproblem 2 ditambah kendala x1 ≤ 5 ; • Subproblem 5: Subproblem 2 ditambah kendala x1 ≥ 6 . Saat ini subproblem yang belum diselesaikan adalah Subproblem 3, 4, dan 5. Salah satu subproblem dipilih, misalnya dengan aturan LIFO (Last In First Out). Dengan adanya aturan ini berarti dipilih Subproblem 4 atau Subproblem 5. Subproblem 4 menghasilkan solusi optimal x1 = 5, x2 = 2 , dan z = 16 yang berupa integer (lihat Lampiran 1). Diperoleh kandidat solusi optimal yang baru
dilakukan kembali pencabangan atas x2 , sehingga diperoleh: • Subproblem 6: Subproblem 5 ditambah kendala x2 ≤ 1 ; • Subproblem 7: Subproblem 5 ditambah kendala x2 ≥ 2 . Selanjutnya berdasarkan aturan LIFO, dipilih Subproblem 6. Subproblem yang dipilih menghasilkan solusi optimal yang berupa integer, dengan x1 = 1 , x2 = 7 , dan z = 17 (lihat Lampiran 1). Diperoleh kandidat solusi optimal yang baru dari Subproblem 6. Karena nilai z baru pada Subproblem 6 lebih baik daripada nilai z pada Subproblem 4, maka nilai z pada Subproblem 6 merupakan batas bawah baru bagi nilai optimal IP (2.6). Tersisa dua buah subproblem yaitu, Subproblem 3 dan Subproblem 7. Misalkan dengan aturan LIFO dipilih Subproblem 7. Karena Subproblem 7 takfisibel (lihat Lampiran 1), maka subproblem ini tidak dapat menghasilkan solusi optimal, yang tersisa hanya Subproblem 3. Subproblem 3 menghasilkan solusi optimal yang berupa integer, dengan x1 = 4 , x2 = 3 , dan z = 17 (lihat Lampiran 1). Batas bawah yang ditetapkan dari solusi optimal Subproblem 6 dan 3 bernilai sama. Semua solusi optimal dari Subproblem 6 dan 3 telah berupa integer dan tidak perlu lagi dilakukan pencabangan, sehingga terdapat 2 solusi optimal dari Subproblem 6 dan 3. Pohon pencabangan yang menunjukkan penyelesaian masalah IP (2.6) secara keseluruhan ditunjukkan pada Gambar 3.
6
Gambar 3 Seluruh pencabangan pada metode Branch-and-Bound untuk menentukan solusi optimal dari IP (2.6).
Graf Konsep graf yang digunakan dalam karya ilmiah ini meliputi definisi-definisi berikut. Definisi 9 (Graf) Suatu graf 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 (vertex/node) 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 takberarah.
ini
disebut
juga
graf
Pada Gambar 4 V = {1, 2,3, 4,5} dan E = {{1, 2},{1, 4},{2,3},{3, 4},{2, 4},{3,5},{4, 5}}. Definisi 10 (Graf Berarah/Digraph) 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 berikut.
G' : Ilustrasi graf takberarah dapat dilihat pada gambar berikut. G
Gambar 5 Graf G ' = (V , A) . Gambar 4 Graf G = (V, E).
Pada Gambar 5 di atas V = {1, 2,3, 4,5} dan A = {(1, 4), (1, 2), (4, 2), (2,3),(4,3), (3,5),(5, 4)}.
7
mendekati v j . Simpul vi disebut predesesor Definisi 11 (Walk) Suatu walk pada graf G = (V, E) adalah suatu barisan simpul dan sisi dari G dengan bentuk : v1 , {v1 , v2 } , v2 , {v2 , v3 } ,..., {vn −1 , vn } , vn , atau ditulis dengan ringkas : v1 , v2 ,..., vn atau v1 , v2 ,..., vn .
bagi simpul v j , dan simpul v j
disebut
suksesor bagi simpul vi . (Foulds, 1992) Ilustrasinya diberikan dalam gambar berikut.
Walk tersebut menghubungkan simpul v1 dengan vn . (Foulds, 1992)
Gambar 6 Sisi berarah menjauhi atau mendekati, suksesor, dan predesesor.
Definisi 12 (Path) Path pada suatu graf G adalah suatu walk dengan semua simpulnya berbeda. (Foulds, 1992) Ilustrasi walk dan path diberikan sebagai berikut. Pada graf G yang terdapat dalam Gambar 4, salah satu contoh walk adalah 1, 2, 3, 2, 4, 5 , sedangkan 1, 4, 2, 3,5 adalah
Definisi 16 (Graf Berbobot) Suatu graf G = (V, E) atau graf berarah D = (V , A) dikatakan berbobot jika terdapat fungsi w : E → ℜ atau ℓ : A → ℜ (dengan ℜ himpunan bilangan real) yang memberikan bobot pada setiap elemen E atau A. (Foulds, 1992)
salah satu contoh path.
Ilustrasinya berikut:
Definisi 13 (Walk Berarah) Walk berarah pada suatu graf berarah G ' = (V , A) adalah suatu barisan terurut simpul dan sisi pada G ' berbentuk v 0 , a1 , v1 ,..., a n , v n , dengan setiap sisi
diberikan
dalam
gambar
G:
berarah a i menghubungkan simpul-simpul
vi −1 dan v i secara berurutan. (Foulds, 1992) Definisi 14 (Path Berarah) Path berarah pada graf berarah G ' adalah suatu walk berarah yang semua simpulnya berbeda. (Foulds, 1992) Ilustrasi walk dan path berarah diberikan sebagai berikut. Pada graf berarah G ' yang terdapat dalam Gambar 5, contoh walk berarah adalah 1, 2, 3, 5, 4, 2, 3, 5 . Contoh path berarah adalah 1, 2, 3, 5, 4 , sementara yang bukan path berarah adalah 1, 2, 4, 3,5 , karena tidak ada sisi berarah dari simpul 2 ke simpul 4. Definisi 15 (Sisi Berarah Menjauhi atau Mendekati, Suksesor, dan Predesesor) Misalkan diberikan graf berarah D = (V , A) . Jika a = (vi , v j ) ∈ A maka sisi berarah ini dikatakan menjauhi
vi
dan
Gambar 7 Graf berbobot G = (V , A) .
Misalkan diberikan fungsi w : A → ℜ untuk graf berbobot G = (V , A) pada Gambar 7, maka 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. Terdapat kasus khusus dari graf berbobot, yaitu network. Untuk memahami konsep network diperlukan definisi-definisi source dan sink berikut ini. Definisi 17 (Source) Source adalah suatu simpul dengan tidak ada sisi berarah yang mendekati simpul tersebut. (Foulds, 1992) Definisi 18 (Sink) Sink adalah suatu simpul sehingga tidak ada sisi berarah yang menjauhi simpul tersebut. (Foulds, 1992)
8
Definisi 19 (Network) Network adalah suatu digraph yang mempunyai tepat satu source dan satu sink. (Foulds, 1992) Ilustrasi network, source, diberikan dalam gambar berikut.
dan
sink
G:
Gambar 8 Network, source, dan sink.
Pada Gambar 8, graf berarah G merupakan suatu network dengan simpul 1 sebagai source dan simpul 6 sebagai sink. Pengertian suatu network N menurut Chartrand & Oellermann (1993), adalah suatu digraph D dengan source s, sink t, dan fungsi bernilai bilangan bulat taknegatif c yang didefinisikan di setiap sisi pada E(D). Digraph D dikatakan underlying digraph dari N dan fungsi c dinamakan fungsi kapasitas dari N. Ada kalanya suatu network memiliki lebih dari satu source maupun sink, sebagaimana yang akan digunakan dalam karya ilmiah ini. Definisi 20 (Lingkungan-luar & lingkungandalam) Dalam digraph D, didefinisikan: • Lingkungan luar (out-neighborhood) dari verteks x di D adalah N + ( x) = { y ∈ V ( D ) | ( x, y ) ∈ E ( D )} , • Lingkungan dalam (in-neighborhood) dari verteks x di D adalah N − ( x) = { y ∈ V ( D ) | ( y, x) ∈ E ( D )} . (Chartrand & Oellermann, 1993) Definisi 21 (Arus/Flow) Misalkan diberikan network N dengan underlying digraph D, source s, sink t, dan fungsi kapasitas c. Arus/flow di N adalah fungsi bernilai bilangan bulat taknegatif f pada E(D) sehingga berlaku (2.7) 0 ≤ f ( a) ≤ c( a), untuk setiap a ∈ E ( D ) , dan
∑
y∈N + ( x )
f ( x, y ) =
∑
f ( y , x)
Network Flow Network flow merupakan suatu kasus dalam PL yang memiliki struktur khusus dan menggunakan representasi graf. Bentuk umum suatu masalah network flow dikenal dengan masalah network flow biaya minimum (minimum cost network flow problem). Pada masalah ini, fungsi objektifnya berupa minimisasi biaya yang terkait dengan suatu sisi berarah dengan kendala-kendala yang meliputi kendala konservasi flow dan kendala restriksi flow. Kendala konservasi flow merupakan suatu kendala yang menjaga keseimbangan flow pada suatu simpul, yang menyatakan bahwa banyaknya flow yang masuk ke suatu simpul harus sama dengan banyaknya flow yang keluar dari simpul tersebut. Kendala restriksi flow merupakan suatu kendala yang membatasi banyaknya flow yang dapat melewati suatu sisi berarah. Misalkan N menyatakan himpunan simpul dalam suatu network dan A menyatakan himpunan sisi berarah dalam network tersebut. Misalkan pula biaya pengangkutan (shipping) setiap unit flow komoditas pada sisi berarah (i, j ) ∈ A dinyatakan sebagai cij , unit flow komoditas yang melalui sisi berarah (i , j ) untuk setiap (i, j ) ∈ A dinotasikan dengan xij , lij dan uij berturut-turut menyatakan batas bawah dan batas atas flow komoditas yang harus diangkut melalui sisi berarah (i , j )
untuk setiap (i, j ) ∈ A , dan bi menyatakan supply/demand pada simpul i ∈ N . Variabel bi disebut supply pada simpul i jika bi > 0 dan simpul i disebut simpul supply. Variabel bi disebut demand pada simpul i jika bi < 0 dan simpul i disebut simpul demand. Jika bi = 0 , simpul i disebut sebagai simpul transshipment. Formulasi umum suatu masalah network flow diberikan sebagai berikut: min cij xij
∑
(i , j )∈A
terhadap
∑
j:( i , j )∈ A
(2.8)
y∈ N − ( x )
untuk setiap x ∈ V ( D ) − {s, t} . (Chartrand & Oellermann 1993)
xij −
∑
j:( i , j )∈ A
x ji = bi , ∀i ∈ N
lij ≤ xij ≤ uij , ∀(i, j ) ∈ A
(2.9) (2.10).
Persamaan (2.9) menyatakan kendala konservasi flow dan pertidaksamaan (2.10) menyatakan kendala restriksi flow. (Ahuja et al. 1993)
9
Masalah Path Terpendek (The Shortest Path Problem) Masalah path terpendek merupakan kasus khusus dalam masalah network flow biaya minimum. Didefinisikan panjang untuk sembarang path berarah dalam suatu network
sebagai jumlah biaya semua sisi berarah dalam path tersebut. Dalam masalah ini akan dicari suatu path terpendek, yakni path berarah dari suatu simpul asal ke simpul tujuan dengan panjang terkecil.
DESKRIPSI DAN FORMULASI MASALAH Suatu perusahaan yang memproduksi pulp harus mengirimkan beberapa produknya pada para pelanggan yang ada di dalam negeri maupun diekspor ke luar negeri. Pengiriman dalam negeri dapat dilakukan dengan menggunakan truk atau kereta, dan pengiriman ke luar negeri dapat dilakukan dengan kapal pengangkut (shipping vessels) ke terminalterminal dan dilanjutkan dengan truk atau kereta sampai kepada para pelanggan. Terdapat dua jenis terminal, yaitu terminal pelabuhan dan terminal inland. Terminal inland adalah suatu terminal berukuran lebih kecil daripada terminal pelabuhan dan terdapat di pesisir sungai. Terminal inland dapat dicapai dari terminal pelabuhan dengan menggunakan kapal yang berukuran lebih kecil daripada kapal pengangkut, truk, atau kereta. Setelah menurunkan semua muatan di terminal pelabuhan, kapal yang telah kosong tersebut diharuskan kembali ke pabrik untuk pengiriman produk selanjutnya.
Pengiriman produk dari pabrik ke pelanggan membutuhkan biaya yang besar, dan besarnya biaya tersebut dipengaruhi oleh jarak yang ditempuh dari pabrik pulp (pulpmill) ke pelanggan, baik dalam negeri maupun luar negeri. Selain itu, terdapat pula biaya tetap untuk penggunaan terminal, kereta, truk, dan kapal. Setiap produk yang masuk ke terminal dikenai biaya cukai per tonnya. Rute pengiriman dari pabrik ke terminalterminal ditunjukkan oleh Gambar 9. Terdapat dua tipe rute, yaitu rute sederhana yang ditunjukkan dengan rute-A dan rute gabungan yang ditunjukkan dengan rute-B. Rute-A dimulai dari satu pabrik pulp dan menuju satu terminal untuk pembongkaran. Sedangkan untuk pemuatan rute-B dimulai dari satu pabrik pulp dan berkunjung ke satu atau beberapa pabrik pulp atau terminal dan berakhir pada satu terminal. Beberapa contoh rute ditunjukkan pada Tabel 1.
Gambar 9 Ilustrasi lokasi pabrik, terminal, dan pelanggan.