PENYELESAIAN MASALAH DESAIN NETWORK TAKBERKAPASITAS DENGAN DEKOMPOSISI BENDERS DAN METODE BRANCH-ANDBOUND
PUTI PARAMITA ROSLIYANTI
DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2007
PENYELESAIAN MASALAH DESAIN NETWORK TAKBERKAPASITAS DENGAN DEKOMPOSISI BENDERS DAN METODE BRANCH-ANDBOUND
PUTI PARAMITA ROSLIYANTI G54103008
DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2007
ABSTRACT PUTI PARAMITA ROSLIYANTI. Solving the Uncapacitated Network Design Problem by Benders Decomposition and Branch-and-Bound Method. Under the direction of FARIDA HANUM and AGAH DRAJAT GARNADI. Design network problem is a multicommodity minimum cost network flow problem. Its applications appear in many fields, include planning in telecommunication network, transportation network, water resource, computer networking, vehicle fleet, and product distribution. This problem is generally divided into capacitated and uncapacitated network design problems. The main purpose of uncapacitated network design problem is to design or improve a network configuration by choosing certain arcs to be included in the network, in order to reach minimum value of total cost, with assumption that the number of commodity flow which can be sended along those arcs is unrestricted (uncapacitated). There are several methods have been developed to find a solution of this model, two of them are Benders decomposition and branch-and-bound. The basic concept of Benders decomposition is to solve a primal linear programming (LP) problem by considering one of its variable vectors has a fixed value, so that for any iteration of this algorithm, the problems that contain one of these variable vectors can be solved. The basic principle of branch-and-bound method is to split a feasible region of LP-relaxation by constructing subproblems. Benders decomposition gives a lower bound for optimal value of uncapacitated network design problem and solves it through repeated iterative steps so that an optimal feasible solution is found. Solving this problem by branch-and-bound method is carried out using software LINGO 8.0 and hypothetic data randomly generated, resulting the minimum total cost, the arcs used in the network, and optimal shipping routes for every commodity flow.
ABSTRAK PUTI PARAMITA ROSLIYANTI. Penyelesaian Masalah Desain Network Takberkapasitas dengan Dekomposisi Benders dan Metode Branch-and-Bound. Dibimbing oleh FARIDA HANUM dan AGAH DRAJAT GARNADI. Masalah desain network merupakan suatu masalah aliran network (network flow) biaya minimum untuk lebih dari satu komoditas. Aplikasinya banyak muncul dalam perencanaan jaringan telekomunikasi, transportasi, sumberdaya air, komunikasi komputer (computer networking), maupun perencanaan armada kendaraan dan distribusi barang. Secara garis besar, masalah ini dapat dikelompokkan ke dalam dua jenis, yakni masalah desain network berkapasitas dan takberkapasitas. Permasalahan pokok dari masalah desain network takberkapasitas adalah mendesain atau menyempurnakan suatu konfigurasi network dengan memilih sisi-sisi berarah tertentu untuk berada di dalamnya sedemikian sehingga biaya totalnya menjadi minimum, dengan asumsi bahwa banyaknya flow komoditas yang dapat melewati sisi-sisi berarah tersebut tidak dibatasi (takberkapasitas). Ada beberapa metode yang dikembangkan untuk mencari solusi model masalah ini, dua di antaranya adalah dekomposisi Benders dan metode branch-and-bound. Konsep dasar dekomposisi Benders adalah menyelesaikan masalah pemrograman linear primal dengan menganggap salah satu vektor variabelnya bernilai tetap sedemikian sehingga untuk sembarang iterasi dari algoritme ini nantinya masalah-masalah yang memuat salah satu vektor variabel, namun tidak seluruhnya, dapat diselesaikan. Prinsip dasar metode branch-and-bound adalah memecah daerah fisibel suatu masalah pemrograman linear relaksasi dengan membuat subproblem-subproblem. Dekomposisi Benders memberikan suatu batas bawah bagi nilai optimal masalah desain network takberkapasitas dan menyelesaikannya melalui langkah-langkah iteratif yang dilakukan secara berulang hingga ditemukan suatu solusi fisibel optimal. Penyelesaian masalah ini dengan metode branch-and-bound dilakukan dengan menggunakan software LINGO 8.0 dan data-data hipotetik yang dibangkitkan secara acak, yang menghasilkan nilai optimal berupa biaya total minimum berikut sisi-sisi berarah yang digunakan dalam network terkait dan rute pengangkutan untuk setiap flow komoditas.
PENYELESAIAN MASALAH DESAIN NETWORK TAKBERKAPASITAS DENGAN DEKOMPOSISI BENDERS DAN METODE BRANCH-ANDBOUND
Skripsi sebagai salah satu syarat untuk memperoleh gelar Sarjana Sains pada Departemen Matematika
PUTI PARAMITA ROSLIYANTI G54103008
DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR 2007
Judul Nama NIM
: Penyelesaian Masalah Desain Network Takberkapasitas dengan Dekomposisi Benders dan Metode Branch-and-Bound : Puti Paramita Rosliyanti : G54103008
Menyetujui,
Pembimbing I
Pembimbing II
Dra. Farida Hanum, M.Si. NIP 131 956 709
Drs. Agah D. Garnadi, Grad. Dipl. Sc. NIP 131 804 648
Mengetahui,
Dekan Fakultas Matematika dan Ilmu Pengetahuan Alam Institut Pertanian Bogor
Prof. Dr. Ir. Yonny Koesmaryono, MS. NIP. 131 473 999
Tanggal Lulus :
KATA PENGANTAR Puji dan syukur penulis panjatkan ke hadirat Allah SWT atas segala nikmat, karunia, izin, dan pertolongan-Nya sehingga penulisan skripsi ini berhasil diselesaikan. Tema yang dipilih adalah Riset Operasi dengan judul Penyelesaian Masalah Desain Network Takberkapasitas dengan Dekomposisi Benders dan Metode Branch-and-Bound. Skripsi ini merupakan syarat untuk menyelesaikan studi pada Departemen Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam, Institut Pertanian Bogor. Terima kasih penulis ucapkan kepada : 1. Ibu Dra. Farida Hanum M.Si dan Bapak Drs. Agah D. Garnadi, Grad. Dipl. Sc. selaku dosen pembimbing, atas segala kesabaran dan masukannya selama membimbing penulis; tak lupa kepada Bapak Dr. Toni Bakhtiar selaku penguji; 2. ibu kandungku tercinta, (alm.) Puti Rosmeiliza B. S., yang telah melahirkan, mendidik, dan membesarkan penulis hingga usia 17 tahun; bapak dan bundaku tercinta, Sumaryanto dan Anggraini Sukmawati, atas segala dukungan, motivasi, pembelajaran, masukan, dan segala kasih sayang yang diberikan kepada penulis; juga adik-adikku tersayang, Arif dan Ajeng, atas segala kasih sayang dan keceriaannya; 3. keluarga besar Zagloel Dt. Moeroen, terutama Mama Ade dan Ibu Riri; keluarga besar (alm.) Atmosoekarto, terutama Bulik Nuning dan Bulik Kris; keluarga besar H. Munawar, terutama eyang putri; 4. sahabat-sahabatku tersayang, Nay dan Dara, atas segala tawa dan tangis, manis dan pahit, suka dan duka dalam empat tahun persahabatan kita; sahabatku-sahabatku, Baidhuri dan Ilma, atas doa-doa dan dukungannya; 5. teman-teman mahasiswa matematika angkatan 40: Septi, Ifni, Tiwi, Indah, Icha, Vina, Ami, Achie, Mika, Uli, Mayang, Metha, Elis, Marlin, Sri, Ulfa, Nchie, Yuda, Dwi, Nisa, Walidah, Agatha, Herni, Rama, Yudi, Abdillah, Ari, Jayu, Prima, Mufti, Azis, Berri, Abay, Dimas, Kafi, Rusli, Sawa, Aam, Lili, Putra, Yusuf, Manto, Ali, Demi, Anton, Febri, atas segenap dukungan, suka-duka dan keceriaan selama penulis menempuh studi di Departemen Matematika IPB; 6. kakak-kakak mahasiswa matematika angkatan 39, terutama kak Arie Wijayanto, atas segala bantuannya; adik-adik mahasiswa matematika angkatan 41, terutama Dian dan Diah yang telah bersedia menjadi pembahas; adik-adik mahasiswa matematika angkatan 42; seluruh pengajar, pegawai, dan staf Departemen Matematika IPB; 7. keluarga besar BEM FMIPA IPB angkatan 2005-2006: kakakku Fajri Ma’rifatullah (atas segala doa, dukungan, motivasi, dan masukan bagi penulis dalam berbagai hal), Uli, Ari, kak Riana Safaat, Cheri, Fariz, Rina, Ajeng, Tresna, Jayadin, Marwan, Pras, Tiwi, Agita, Achie, Maul, Dyna, Lewe, Rizal, Awit, Asih, Great, Haristinah, Astrid, Yuyun, Arul, Ihsan, Putri, Halida, Haris, Lia, Isran, Ayu, Nenny, Agung Seno, Deny Kurniawan, Bayu, Chandra, Lutfi, Utami Rahayu, dan (alm.) Rachma Ruly Maharatri, atas segenap dukungan, doa, dorongan semangat, dan warna-warni dalam setahun kebersamaan kita; 8. keluarga besar pengurus GUMATIKA IPB periode 2004-2005; pengurus BEM FMIPA 2004-2005, terutama Mbak Henny Yulanda, yang telah memberikan banyak inspirasi; pengurus BEM FMIPA IPB 2006-2007; 9. staf dan pengajar Lembaga Pendidikan Primagama Cimanggu dan Sukasari, terutama Mas Mulyadi, Mas Wildan, dan Mbak Ari; 10. teman-teman penghuni Lorong 10 Gedung A2 Asrama TPB IPB 2003-2004, terutama Silvi, Rahma, Lita, Puji, Pujay, Tila, Natalia; Fajar Faizal dan Dwi Budi H, atas doa dan bantuannya; Aried Ardhina dan Bian Adiantoro, atas dukungan dan dorongan semangat selama penyusunan skripsi ini; Novan A. Pratama dan kru Centium, atas bantuannya dalam hal print dan perbanyakan draft skripsi; juga pihak-pihak lain yang telah membantu penyusunan skripsi ini, yang tidak dapat disebutkan satu persatu. Penulis menyadari bahwa dalam tulisan ini masih terdapat kekurangan dan jauh dari kesempurnaan, oleh karena itu dibutuhkan kritik dan saran yang membangun dari pembaca. Semoga tulisan ini dapat bermanfaat. Bogor, Oktober 2007 Puti Paramita Rosliyanti
RIWAYAT HIDUP Penulis dilahirkan di Bandung pada tanggal 20 Oktober 1985 dari pasangan Ir. Sumaryanto, MS dan (alm) Ir. Puti Rosmeiliza Budi Savitri. Penulis merupakan anak pertama dari tiga bersaudara. Pada tahun 2003 penulis lulus dari SMU Negeri 1 Bogor dan pada tahun yang sama lulus seleksi masuk IPB melalui jalur Undangan Seleksi Masuk IPB. Penulis memilih Program Studi Matematika, Departemen Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam. Selama mengikuti perkuliahan, penulis aktif dalam kegiatan kemahasiswaan, di antaranya pada tahun 2004-2005 menjabat sebagai bendahara umum Gugus Mahasiswa Matematika (GUMATIKA) IPB periode 2004-2005 dan pada tahun 2005-2006 sebagai staf Departemen Sains Badan Eksekutif Mahasiswa Fakultas Matematika dan Ilmu Pengetahuan Alam (BEM FMIPA) IPB, serta mengikuti kepanitiaan dari beberapa kegiatan selama rentang waktu 2004-2006. Pada tahun 2006 penulis bersama dua orang rekan memperoleh insentif dari Dirjen DIKTI dalam Program Kreativitas Mahasiswa Bidang Penulisan Ilmiah. Pada tahun 2005 penulis pernah menjadi staf pengajar matematika pada Lembaga Bimbingan Belajar AMPUH dan tahun 2007 menjadi staf pengajar matematika pada Lembaga Pendidikan Primagama Bogor.
DAFTAR ISI Halaman DAFTAR TABEL .......................................................................................................................... viii DAFTAR GAMBAR ..................................................................................................................... viii DAFTAR LAMPIRAN................................................................................................................... viii 1 PENDAHULUAN Latar Belakang ............................................................................................................................ 1 Tujuan .......................................................................................................................................... 2 2 LANDASAN TEORI Fungsi Linear dan Pertidaksamaan Linear ................................................................................. Pemrograman Linear ................................................................................................................... Dualitas Pemrograman Linear .................................................................................................... Integer Programming .................................................................................................................. Pemrograman Linear Relaksasi .................................................................................................. Graf............................................................................................................................................... Network Flow ............................................................................................................................... Metode Branch-and-Bound ........................................................................................................
2 2 4 5 6 6 8 9
3 DEKOMPOSISI BENDERS........................................................................................................ 12 4 DESKRIPSI DAN FORMULASI MASALAH DESAIN NETWORK TAKBERKAPASITAS ................................................................................................................ 14 5 PENYELESAIAN MASALAH DESAIN NETWORK TAKBERKAPASITAS DENGAN DEKOMPOSISI BENDERS...................................................................................... 15 6 PENYELESAIAN MASALAH DESAIN NETWORK TAKBERKAPASITAS DENGAN METODE BRANCH-AND-BOUND ......................................................................... 18 7 SIMPULAN DAN SARAN Simpulan ................................................................................................................................... 20 Saran .......................................................................................................................................... 20 DAFTAR PUSTAKA ...................................................................................................................... 21 LAMPIRAN ...................................................................................................................................... 22
vii
DAFTAR TABEL Halaman 1 Hubungan antara variabel-variabel dan kendala-kendala pada masalah primal dan masalah dual ............................................................................................................... 5 2 Sisi-sisi berarah yang digunakan dalam network ....................................................................... 19 3 Rute pengangkutan flow optimal untuk setiap komoditas ......................................................... 19 4 Data titik asal dan titik tujuan untuk setiap komoditas .............................................................. 30 5 Biaya tetap ( f ij ) untuk setiap sisi berarah (i, j ) ...................................................................... 31 6 Biaya pengangkutan (cijk ) untuk setiap komoditas k pada sisi berarah (i, j ) .......................... 32
DAFTAR GAMBAR Halaman
1 2 3 4 5 6 7 8 9 10
Ilustrasi himpunan konveks dan yang bukan himpunan konveks ............................................... 4 Graf G = (V , E ) ............................................................................................................................ 6 Graf G ' = (V , A) ........................................................................................................................... 6 Sisi berarah menjauhi atau mendekati, suksesor, dan predesesor ............................................... 7 Graf berbobot G ' = (V , A) ............................................................................................................ 7 Network, source, dan sink.............................................................................................................. 7 Flow dan kapasitas sisi berarah .................................................................................................... 8 Daerah fisibel untuk PL-relaksasi dari IP (2.10) ....................................................................... 10 Daerah fisibel untuk subproblem 2 dan subproblem 3 dari IP (2.10) ....................................... 10 Seluruh pencabangan pada metode branch-and-bound untuk menyelesaikan IP (2.10) ...................................................................................................................................... 11 11 Ilustrasi network optimal yang dihasilkan berdasarkan Tabel 2 dan Tabel 3 ............................ 20
DAFTAR LAMPIRAN Halaman
1 Bukti-Bukti Teorema dan Akibat pada Titik Ekstrem dan Dualitas Pemrograman Linear .................................................................................................................. 2 Syntax Program LINDO 6.1 untuk Menyelesaikan Masalah Pemrograman Linear dengan Metode Branch-and-Bound Beserta Hasil yang Diperoleh ............................... 3 Syntax Program LINDO 6.1 untuk Menyelesaikan Masalah Pemrograman Linear dengan Metode Dekomposisi Benders Beserta Hasil yang Diperoleh ........................... 4 Pembangkitan Data-data Biaya Pengangkutan dan Biaya Tetap dengan Mathematica 5.2 Beserta Syntax Inputnya ................................................................................ 5 Data-data Hipotetik untuk Implementasi Penyelesaian Masalah Desain Network Takberkapasitas dengan Metode Branch-and-Bound ................................................. 6 Syntax Program LINGO 8.0 untuk Masalah Desain Network Takberkapasitas ........................................................................................................................... 7 Hasil Komputasi Program pada LINGO 8.0 untuk Masalah Desain Network Takberkapasitas ...........................................................................................................................
23 25 27 29 30 36 37
viii
