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)

Suatu fungsi ),...,,( 21 nxxxf dalam

variabel-variabel 1 2, ,..., nx x x adalah suatu

fungsi linear jika dan hanya jika untuk suatu himpunan konstanta 1 2, ,..., nc c c ,

....),...,,( 221121 nnn xcxcxcxxxf +++=

(Winston, 2004)

Sebagai gambaran, 1 2 1 2( , ) 2 3f x x x x= +

merupakan fungsi linear, sementara 2 2

1 2 1 2( , )f x x x x= bukan fungsi linear.

Definisi 2 (Pertidaksamaan dan Persamaan Linear)

Untuk sembarang fungsi linear ),...,,( 21 nxxxf dan sembarang bilangan ,b

pertidaksamaan bxxxf n ≤),...,,( 21 dan

bxxxf n ≥),...,,( 21 adalah pertidaksamaan

linear. Misalkan b sembarang bilangan, suatu

persamaan bxxxf n =),...,,( 21 merupakan

persamaan linear. (Winston, 2004)

Pemrograman Linear

Pemrograman linear (PL) atau linear programming (LP) adalah suatu masalah optimisasi yang memenuhi ketentuan-ketentuan 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 ix , pembatasan tanda

menentukan ix harus taknegatif )0( ≥ix

atau tidak dibatasi tandanya (unrestricted in sign).

(Winston, 2004) Suatu PL mempunyai bentuk standar seperti yang didefinisikan sebagai berikut.

Definisi 3 (Bentuk Standar PL) Suatu pemrograman linear didefinisikan

mempunyai bentuk standar: maks Tz = c 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 elemen-

elemennya berupa koefisien variabel nonbasis pada matriks kendala. Dalam hal ini matriks B disebut matriks basis untuk PL (2.1).

Misalkan x dinyatakan sebagai vektor

=

B

N

xx

x, dengan Bx adalah vektor variabel

basis dan Nx adalah vektor variabel nonbasis,

maka =Ax b dapat dinyatakan sebagai

( ) =

B

N

xAx B N

x

.= =B NBx + Nx b (2.2)

Karena matriks B adalah matriks taksingular, maka B memiliki invers, sehingga dari (2.2)

Bx dapat dinyatakan sebagai:

- .= -1 -1B Nx B b B Nx (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 .0x ≥

(Nash & Sofer, 1996)

Ilustrasi solusi basis dan solusi basis fisibel diberikan dalam Contoh 1.

Contoh 1

Misalkan diberikan PL (2.4) berikut:

1 2

1 2 3

1 2 4

1 5

1 2 3 4 5

min 2

terhadap 2 2

2 7

5

, , , , 0,

z x x

x x x

x x x

x x

x x x x x

= − −− + + =

− + + =+ =

≥

(2.4)

dari PL (2.4) diperoleh: 2 1 1 0 0 2

1 2 0 1 0 , 7

1 0 0 0 1 5

− = − =

A b .

Misalkan dipilih

( ) ( )3 4 5 1 2 dan ,x x x x x= =T T

B Nx x

maka matriks basisnya adalah 1 0 0

0 1 0

0 0 1

=

B

. Dengan menggunakan matriks basis di atas didapatkan

3

( ) ( )0 0 , 2 7 5 .−= = =T T1N Bx x B b (2.5)

Solusi (2.5) merupakan solusi basis, karena memenuhi kendala pada PL (2.4) dan kolom-kolom 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.

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-and-bound. Prinsip dasar metode ini adalah memecah daerah fisibel suatu masalah PL-relaksasi dengan membuat subproblem-subproblem. 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 subproblem-subproblem 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 .0=i • Langkah 1 Subproblem ( )iPL dipilih sebagai bagian

masalah berikutnya untuk diteliti. Subproblem

( )iPL diselesaikan dan diukur dengan kondisi

yang sesuai. a) Jika ( )iPL 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 ( )iPL tidak terukur, proses

dilanjutkan ke langkah 2 untuk melakukan pencabangan ( )iPL .

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 jx yang nilai

optimalnya adalah *jx yang tidak memenuhi

batasan integer dalam solusi iPL . Bidang

1][][ ** +<< jjj xxx disingkirkan dengan

membuat dua subproblem PL yang berkaitan

menjadi dua subproblem yang tidak dapat dipenuhi secara bersamaan, yaitu

*[ ]j jx x≤ dan *[ ] 1j jx x≥ + ,

dengan ][ *jx didefinisikan sebagai integer

terbesar yang kurang dari atau sama dengan

.*jx 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 1 2

2 3z x x= +

terhadap

1 2

1 2

1 2

2 10

3 4 25

, 0;

x x

x x

x x

+ ≤

+ ≤

≥ (2.6)

1 2,x x integer.

Solusi optimal PL-relaksasi dari masalah

IP (2.6) adalah 1 5x = , 2 2.5x = , dan 17.5z =

(lihat pada Lampiran 1). Batas atas nilai optimal fungsi objektif masalah ini adalah

17.5z = . 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 2x sebagai

dasar pencabangan. Jika masalah PL-relaksasi diberi nama Subproblem 1, maka pencabangan tersebut menghasilkan 2 subproblem, yaitu: • Subproblem 2: Subproblem 1 ditambah

kendala 2 2.x ≤

• Subproblem 3: Subproblem 1 ditambah kendala

23x ≥ ;

5

Hal ini diilustrasikan secara grafis pada Gambar 2.

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 2.x

Sekarang dipilih subproblem yang belum diselesaikan. Misalkan dipilih Subproblem 2, kemudian diselesaikan. Solusi optimal untuk Subproblem 2 ini adalah 1 5.67,x = 2 2x = ,

dan 17.33z = (lihat Lampiran 1). Karena solusi optimal yang dihasilkan

Subproblem 2 bukan solusi integer, maka dipilih pencabangan pada Subproblem 2 atas

1,x sehingga diperoleh dua subproblem lagi,

yakni: • Subproblem 4: Subproblem 2 ditambah

kendala 1 5x ≤ ;

• Subproblem 5: Subproblem 2 ditambah kendala 1 6x ≥ .

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 1 25, 2x x= = , dan 16z=

yang berupa integer (lihat Lampiran 1). Diperoleh kandidat solusi optimal yang baru

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

1 26, 1.75x x= = , 17.25z= (lihat Lampiran 1). Karena 2 1.75x = bukan integer, maka

dilakukan kembali pencabangan atas 2x ,

sehingga diperoleh: • Subproblem 6: Subproblem 5 ditambah

kendala 2 1x ≤ ;

• Subproblem 7: Subproblem 5 ditambah kendala 2 2x ≥ .

Selanjutnya berdasarkan aturan LIFO, dipilih Subproblem 6. Subproblem yang dipilih menghasilkan solusi optimal yang berupa integer, dengan 1 1x = , 2 7x = , dan

17z = (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 1 4x = , 2 3x = ,

dan 17z = (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

G

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 ini disebut juga graf

takberarah. Ilustrasi graf takberarah dapat dilihat pada

gambar berikut.

Gambar 4 Graf G = (V, E).

Pada Gambar 4

{1,2,3,4,5}V = dan

{{1,2},{1,4},{2,3},{3,4},{2,4},{3,5},{4, 5}}.E = 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.

Gambar 5 Graf ' ( , )G V A= .

Pada Gambar 5 di atas {1,2,3,4,5}V = dan

{(1,4), (1,2), (4,2), (2,3),(4,3), (3,5),(5,4)}.A =

'G :

7

Definisi 11 (Walk)

Suatu walk pada graf G = (V, E) adalah suatu barisan simpul dan sisi dari G dengan bentuk :

{ } { } { }1 1 2 2 2 3 1, , , , , ,..., , , ,n n nv v v v v v v v v−

atau ditulis dengan ringkas :

1 2, ,..., nv v v atau 1 2, ,..., .nv v v

Walk tersebut menghubungkan simpul 1v

dengan .nv

(Foulds, 1992)

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

salah satu contoh path.

Definisi 13 (Walk Berarah) Walk berarah pada suatu graf berarah

' ( , )G V A= adalah suatu barisan terurut

simpul dan sisi pada 'G berbentuk ,,,...,,, 110 nn vavav dengan setiap sisi

berarah ia menghubungkan simpul-simpul

1−iv dan iv 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 ( , )i ja v v A= ∈ maka sisi

berarah ini dikatakan menjauhi iv dan

mendekati jv . Simpul iv disebut predesesor

bagi simpul jv , dan simpul jv disebut

suksesor bagi simpul iv .

(Foulds, 1992)

Ilustrasinya diberikan dalam gambar berikut.

Gambar 6 Sisi berarah menjauhi atau mendekati, suksesor, dan predesesor.

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) Ilustrasinya diberikan dalam gambar

berikut:

Gambar 7 Graf berbobot ( , )G V A= .

Misalkan diberikan fungsi :w A→ ℜ

untuk graf berbobot ( , )G V A= pada Gambar

7, maka (1,2) 2; (1,3) 4; (2,3) 1;

(2,4) 4; (2,5) 2; (3,5) 3;

(5,4) 3; (4,6) 2; (5,6) 2.

w w w

w w w

w w w

= = == = == = =

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)

G:

8

Definisi 19 (Network) Network adalah suatu digraph yang

mempunyai tepat satu source dan satu sink. (Foulds, 1992)

Ilustrasi network, source, dan sink

diberikan dalam gambar berikut.

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 & lingkungan-dalam)

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

0 ( ) ( ),f a c a≤ ≤ (2.7)

untuk setiap ( )a E D∈ , dan

( ) ( )

( , ) ( , )y N x y N x

f x y f y x+ −∈ ∈

=∑ ∑ (2.8)

untuk setiap ( ) { , }x V D s t∈ − . (Chartrand & Oellermann 1993)

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 ijc , unit flow

komoditas yang melalui sisi berarah ( , )i j

untuk setiap ( , )i j A∈ dinotasikan dengan ijx ,

ijl dan iju berturut-turut menyatakan batas

bawah dan batas atas flow komoditas yang harus diangkut melalui sisi berarah ( , )i j

untuk setiap ( , )i j A∈ , dan ib menyatakan

supply/demand pada simpul .i N∈ Variabel

ib disebut supply pada simpul i jika 0ib >

dan simpul i disebut simpul supply. Variabel ib disebut demand pada simpul i jika 0ib <

dan simpul i disebut simpul demand. Jika 0ib = , simpul i disebut sebagai simpul

transshipment. Formulasi umum suatu masalah network

flow diberikan sebagai berikut:

:( , ) :( , )

( , )

.

min

terhadap

(2.9)

(2.10)

,

, ( , )

ij ji ij i j A j i j A

ij ij ij

ij iji j A

x x b i N

l x u i j A

c x

∈ ∈

∈

− = ∀ ∈

≤ ≤ ∀ ∈

∑ ∑

∑

Persamaan (2.9) menyatakan kendala konservasi flow dan pertidaksamaan (2.10) menyatakan kendala restriksi flow.

(Ahuja et al. 1993)

G:

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 terminal-terminal 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 terminal-terminal 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.