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
1
I PENDAHULUAN 1.1 Latar Belakang Berbagai permasalahan dalam dunia nyata terkait dengan jaringan, misalnya jaringan telekomunikasi, lalu lintas, transportasi, maupun distribusi produk. Dalam matematika, permasalahan-permasalahan tersebut dapat dirumuskan ke dalam suatu model optimisasi yang disebut model optimisasi network, yang menggunakan representasi graf. Model ini bermacam-macam, salah satunya adalah model masalah desain network. Masalah desain network merupakan suatu masalah aliran network (network flow) biaya minimum untuk lebih dari satu komoditas (multicommodity) dengan biaya tetap pada sisi berarahnya. Masalah ini tergolong ke dalam pemrograman integer campuran (mixed integer programming). Aplikasi masalah ini amat beragam, di antaranya adalah konstruksi jalan-jalan baru dalam suatu jaringan lalu lintas, konstruksi sambungan-sambungan (links) baru dalam jaringan transportasi, desain topologi jaringan komunikasi komputer, desain jaringan telekomunikasi, maupun perencanaan armada kendaraan yang terkait dengan keputusan dalam hal pelayanan dan berbagai bidang lainnya yang menyangkut perencanaan distribusi dan transportasi. Istilah komoditas dalam masalah desain network misalnya dapat berupa barang-barang dalam jaringan transportasi atau sinyal-sinyal data dalam jaringan komputer. Secara garis besar, masalah desain network dapat dikelompokkan ke dalam dua bagian, yakni masalah desain network berkapasitas (capacitated network design problem) dan masalah desain network takberkapasitas (uncapacitated network design problem). Yang membedakan keduanya adalah ada atau tidaknya batasan komoditas yang dapat melalui suatu sisi berarah (arc) dalam network, yang disebut kapasitas sisi berarah. Seringkali dalam persoalan nyata kapasitas sisi berarah dalam suatu network sangat besar, sehingga kapasitas tersebut dapat diabaikan atau dianggap takberkapasitas. Hal ini misalnya muncul dalam penggunaan serat optik pada jaringan telekomunikasi. Fokus desain network takberkapasitas pada dasarnya adalah pemilihan sisi berarah yang dikehendaki untuk berada di dalam suatu konfigurasi network yang meminimumkan biaya total pada network tersebut. Yang dimaksud dengan konfigurasi suatu network adalah wujud atau bentuk dari network tersebut terkait dengan simpul-simpul maupun
sisi-sisi berarah yang terdapat di dalamnya. Kasus khusus dalam masalah ini meliputi masalah network biaya tetap (fixed charge network problem) yang hanya melibatkan satu komoditas, simple plant location problem (SPLP), travelling salesman problem (TSP), dan masalah Steiner Tree. Secara spesifik, penerapan masalah ini mencakup masalahmasalah dalam perencanaan komunikasi, transportasi, dan sumber daya air, serta representasi keputusan yang menyangkut lokasi fasilitas, misalnya penempatan gudang pabrik, fasilitas darurat, maupun jaringan komputer (computer networking). Ada beberapa metode yang telah dikembangkan untuk mencari solusi model optimisasi ini, di antaranya adalah metode dekomposisi Benders (Magnanti et al., 1986), metode dual ascent (Balakrishnan et al., 1989), dekomposisi dan relaksasi Lagrange dengan pertidaksamaan valid (Holmberg & Migdalas, 1991), metode branch-and-bound berbasis pemrograman linear standar, metode simpleks yang dimodifikasi, dekomposisi silang, yang dikembangkan oleh Van Roy pada tahun 1983 dan diaplikasikan pada masalah ini oleh Holmberg pada tahun 1990, mean value cross decomposition (Holmberg, 1992), serta heuristik Lagrange (Holmberg & Hellstrand, 1998). Dalam karya ilmiah ini akan dibahas metode dekomposisi Benders, suatu metode solusi yang dikembangkan oleh J.F. Benders pada tahun 1962. Metode ini telah digunakan pada masalah dengan variabel-variabel kontinu berjumlah besar, variabel integer relatif sedikit, dan kendala-kendalanya memiliki struktur khusus (Magnanti et al., 1986). Metode ini terbukti sangat berguna untuk beberapa konteks masalah yang meliputi desain sistem distribusi (Geoffrion & Graves, 1974), aircraft routing (Richardson, 1976), dan penjadwalan mesin kereta api (Florian et al., 1976). Dekomposisi Benders dalam karya ilmiah ini digunakan untuk mencari suatu batas bawah nilai fungsi objektif optimal dan menyelesaikan masalah desain network takberkapasitas. Selain itu akan ditunjukkan pula penyelesaian masalah ini dengan menggunakan metode branch-and-bound dengan bantuan software LINGO 8.0. Untuk menyederhanakan model ini digunakan asumsi bahwa asal dan tujuan tunggal (single origin and destination) untuk setiap komoditas.
2
1.2 Tujuan Tujuan dari karya ilmiah ini meliputi: 1. mempelajari model masalah desain network takberkapasitas dengan asal (origin) dan tujuan (destination) tunggal untuk setiap komoditas;
2. mencari batas bawah nilai optimal fungsi objektif dan menyelesaikan masalah desain network takberkapasitas dengan menggunakan dekomposisi Benders; 3. menyelesaikan masalah desain network takberkapasitas dengan menggunakan metode branch-and-bound.
II LANDASAN TEORI Untuk memahami masalah desain network takberkapasitas dan teknik-teknik pemecahan yang digunakan dalam karya tulis ini diperlukan pengertian 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) Misalkan f ( x1 , x 2 ,..., x n ) menyatakan suatu fungsi dalam variabel-variabel x1 , x 2 ,..., x n . Fungsi f ( x1 , x 2 ,..., x n ) dikatakan linear jika dan hanya jika untuk suatu c1 , c 2 ,..., c n , himpunan konstanta f ( x1 , x 2 ,..., x n ) = c1 x1 + c 2 x 2 + ... + c n x n . (Winston, 2004) Sebagai gambaran, f ( x1 , x 2 ) = 2 x1 + x 2 merupakan fungsi linear, sementara f ( x1 , x 2 ) = x12 x 2 bukan fungsi linear. Misalkan b sembarang bilangan, suatu persamaan f ( x1 , x 2 ,..., x n ) = b merupakan persamaan linear. Definisi 2 (Pertidaksamaan Linear) Untuk sembarang fungsi linear f ( x1 , x 2 ,..., x n ) dan sembarang bilangan b, f ( x1 , x 2 ,..., x n ) ≤ b dan pertidaksamaan f ( x1 , x 2 ,..., x n ) ≥ b adalah pertidaksamaan linear. (Winston, 2004) Pemrograman Linear Menurut Winston (2004), pemrograman linear (PL) atau linear programming 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 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 xi harus taknegatif ( xi ≥ 0) atau tidak dibatasi tandanya (unrestricted in sign). Suatu PL mempunyai bentuk standar seperti yang didefinisikan sebagai berikut. Definisi 3 (Bentuk Standar PL) Pemrograman linear min z = cT x (2.1) terhadap Ax = b x≥0 dikatakan PL dalam bentuk standar, dengan x dan c vektor-vektor berukuran n, vektor b berukuran m, dan A matriks berukuran m × n yang disebut sebagai matriks kendala, dengan m ≤ n. (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.
3
Pada masalah PL (2.1), vektor x yang memenuhi kendala Ax = b disebut solusi PL (2.1). Misalkan matriks A dapat 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). Definisi 4 (Matriks Basis) Matriks B disebut matriks basis untuk PL (2.1) jika B adalah matriks taksingular, yaitu matriks yang determinannya tidak sama dengan nol. (Garfinkel & Nemhauser, 1972)
Misalkan x dapat dinyatakan sebagai ⎛x ⎞ vektor x = ⎜ B ⎟ , dengan x B adalah vektor ⎝ xN ⎠ variabel basis dan x N adalah vektor variabel nonbasis, maka Ax = b dapat dinyatakan ⎛x ⎞ sebagai Ax = ( B N ) ⎜ B ⎟ ⎝ xN ⎠ = BxB + Nx N = b. (2.2) Karena matriks B adalah matriks taksingular, maka B memiliki invers, sehingga dari (2.2) x B dapat dinyatakan sebagai:
xB = B -1b - B -1 Nx N .
(2.3)
Definisi 5 (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) Menurut Garfinkel & Nemhauser (1972), solusi dari suatu PL disebut solusi basis jika memenuhi xB = B -1b, x N = 0. Definisi 6 (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 = −2 x1 − 3x2 terhadap
− 2 x1 + x2 + x3 = 4 − x1 + 2 x2 + x4 = 11
(2.4)
x1 + x5 = 5 x1 , x2 , x3 , x4 , x5 ≥ 0, dari PL (2.4) diperoleh: ⎛ −2 1 1 0 0 ⎞ ⎛4⎞ ⎜ ⎟ ⎜ ⎟ A = ⎜ −1 2 0 1 0 ⎟ , b = ⎜ 11⎟ . ⎜ 1 0 0 0 1⎟ ⎜5⎟ ⎝ ⎠ ⎝ ⎠ Misalkan dipilih xB = ( x3
x4
x5 ) dan x N = ( x1 T
x2 ) , T
maka matriks basisnya adalah ⎛1 0 0⎞ ⎜ ⎟ B = ⎜0 1 0⎟ . ⎜0 0 1⎟ ⎝ ⎠ Dengan menggunakan matriks basis di atas didapatkan T T x N = ( 0 0 ) , x B = B −1b = ( 4 11 5 ) . (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. PL (2.1) dapat dinyatakan dalam bentuk x B dan x N sebagai berikut min z = cTB xB + cTN x N terhadap Bx B + Nx N = b
(2.6)
x ≥ 0, dengan c B vektor koefisien variabel basis pada fungsi objektif dan c N vektor koefisien variabel nonbasis pada fungsi objektif. Jika persamaan (2.3) disubstitusikan ke dalam fungsi objektif PL (2.6) maka akan didapat z = cTB (B −1b − B −1 Nx N ) + cTN x N
= cTB B −1b + (cTN − cBT B −1 N) x N .
Definisi 7 (Vektor Pengali Simpleks) Jika didefinisikan y = (c TB B −1 ) T = B − T c B , maka z dapat ditulis sebagai z = y T b + (c TN − y T N) x N . (2.7) Vektor y disebut vektor pengali simpleks. (Nash & Sofer, 1996)
4
Untuk suatu solusi basis x N = 0 dan x B = bˆ = B −1 b, maka zˆ = c TB B −1 b, dengan zˆ menyatakan nilai optimal untuk z.
Pada Gambar 1, lingkaran (i) dan persegi panjang (ii) merupakan himpunan konveks, sedangkan bidang (iii) dan cincin (iv) bukan himpunan konveks.
Definisi 8 (Reduced Cost) Misalkan cˆ j menyatakan elemen vektor
Definisi 12 (Titik Ekstrem) Untuk sembarang himpunan konveks S, titik P anggota S dikatakan sebagai suatu titik ekstrem jika untuk setiap segmen garis yang seluruhnya terletak dalam S dan memuat titik P, titik P merupakan titik ujung dari segmen garis tersebut. (Winston, 2004)
cˆ TN ≡ (c TN − c TB B −1 N) yang bersesuaian dengan variabel x j , koefisien cˆ j disebut reduced cost dari x j . Reduced cost adalah penambahan nilai fungsi objektif jika suatu variabel nonbasis dijadikan variabel basis (artinya menjadi solusi taknol) pada suatu PL. (Nash & Sofer, 1996) Hal yang juga penting dalam konsep pemrograman linear adalah daerah fisibel, solusi optimal, himpunan konveks, dan titik ekstrem, yang didefinisikan sebagai berikut.
Definisi 9 (Daerah Fisibel) Daerah fisibel suatu PL adalah himpunan semua titik yang memenuhi semua kendala dan pembatasan tanda pada PL tersebut. (Winston, 2004) Definisi 10 (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) Definisi 11 (Himpunan Konveks) Misalkan S menyatakan himpunan titik. S adalah himpunan konveks jika segmen garis yang menghubungkan sembarang titik-titik dalam S seluruhnya termuat dalam S. (Winston, 2004) Ilustrasi himpunan konveks dan yang bukan himpunan konveks diberikan pada gambar di bawah ini.
(i)
(iii)
(ii)
(iv)
Gambar 1 Ilustrasi himpunan konveks dan yang bukan himpunan konveks.
Menurut Nash & Sofer (1996), suatu titik x ∈ S disebut titik ekstrem dari suatu himpunan konveks S jika titik tersebut tidak dapat dinyatakan dalam bentuk x = αy + (1 − α ) z , dengan y, z ∈ S , 0 < α < 1 dan y, z ≠ x. Berdasarkan Gambar 1, seluruh titik yang berada pada keliling lingkaran (i) merupakan titik ekstrem, demikian pula titik-titik ujung (sudut) persegi panjang (ii). Optimalitas titik ekstrem pada suatu masalah pemrograman linear ditunjukkan pada terorema berikut ini.
Teorema 1 (Optimalitas Titik Ekstrem) Solusi optimal suatu masalah PL dicapai pada suatu titik ekstrem atau himpunan titiktitik ekstrem. Bukti teorema ini dapat dilihat pada Lampiran 1. (Hazell & Norton, 1986) Dualitas Pemrograman Linear Menurut Nemhauser & Wolsey (1999), dualitas pemrograman linear berkaitan dengan sepasang masalah PL dan hubungan antarsolusi keduanya. Salah satu dari sepasang masalah PL ini disebut masalah primal dan lainnya disebut masalah dual. Masalah dual dan primal berkaitan sangat erat sedemikian sehingga solusi optimal dari salah satu masalah akan secara otomatis menghasilkan solusi optimal bagi masalah lainnya. Masalah dual adalah sebuah masalah PL yang diturunkan dari sebuah masalah PL primal dengan mengikuti kaidah-kaidah berikut: 1. untuk setiap kendala masalah primal terdapat suatu variabel masalah dual; 2. untuk setiap variabel masalah primal terdapat suatu kendala masalah dual;
5
3. koefisien dari sebuah variabel pada kendala masalah primal membentuk koefisien yang terdapat pada ruas kiri kendala masalah dual yang bersesuaian dan koefisien fungsi objektif dari variabel terkait menjadi ruas kanan kendala masalah dual. (Taha, 1996) Secara ringkas, hubungan antara variabelvariabel kendala pada masalah primal dan masalah dual diberikan dalam tabel berikut Tabel 1 Hubungan antara variabel-variabel dan kendala-kendala pada masalah primal dan masalah dual PRIMAL DUAL Minimisasi Maksimisasi ≥ bi ≥0 ≤ bi ≤0 Kendala tandanya Variabel = bi tidak dibatasi ≤ cj ≥0
≥ cj
≤0 Kendala tandanya = c tidak j dibatasi Keterangan : bi dan c j menyatakan suatu Variabel
nilai. Misalkan suatu masalah PL primal dinyatakan sebagai berikut min z = cT x (P) terhadap Ax ≥ b x ≥ 0, maka dual dari masalah di atas adalah max w = b T y (D) terhadap A T y ≤ c y ≥ 0, dengan c dan x vektor-vektor berukuran n, b dan y vektor-vektor berukuran m, dan A matriks berukuran m × n. Keterkaitan antara solusi masalah primal dan solusi masalah dual dijabarkan dalam teorema-teorema berikut ini. Teorema 2 (Dualitas Lemah) Misalkan x adalah solusi fisibel masalah primal (P) dan y adalah solusi fisibel masalah dual (D), maka z = cT x ≥ b T y = w.
Bukti teorema ini dapat dilihat pada Lampiran 1. (Nash & Sofer, 1996) Teorema 2 ini berlaku untuk masalah primal yang berbentuk minimisasi dan dualnya, sementara untuk masalah primal berupa maksimisasi dan dualnya, nilai fungsi objektif masalah primal ≤ nilai fungsi objektif masalah dual. Hal mendasar dari dualitas pemrograman linear adalah bahwa jika kedua masalah primal dan dual ini fisibel maka nilainilai optimalnya sama, yang diperjelas oleh teorema berikut. Teorema 3 (Dualitas Kuat) Misalkan diberikan sepasang masalah PL primal dan dual. Jika salah satu masalah memiliki solusi optimal demikian pula yang lain dan nilai objektif kedua masalah ini sama. Bukti teorema ini dapat dilihat pada Lampiran 1. (Nash & Sofer, 1996)
Contoh dualitas pemrograman linear diberikan sebagai berikut. Contoh 2 (Dualitas Pemrograman Linear) Misalkan masalah primal (P) z = 7 x1 + 2 x2 min terhadap − x1 + 2 x2 ≥ 4 5 x1 + x2 ≥ 20
(P)
− 2 x1 − 2 x2 ≥ −7 x1 , x2 ≥ 0, maka dual dari masalah di atas adalah max w = 4 y1 + 20 y2 − 7 y3 terhadap − y1 + 5 y2 − 2 y3 ≤ 7 2 y1 + y2 − 2 y3 ≤ 2
(D)
y1 , y2 , y3 ≥ 0.
Integer Programming (Pemrograman Integer) 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. IP dengan semua variabelnya harus bernilai 0 atau 1 disebut 0-1 IP. (Garfinkel & Nemhauser, 1972)
6
Pemrograman Linear Relaksasi Konsep pemrograman linear relaksasi atau PL-relaksasi diberikan dalam definisi berikut ini. Definisi 13 (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) Graf Konsep graf yang digunakan dalam karya ilmiah ini meliputi definisi-definisi berikut ini. Definisi 14 (Graf) Suatu graf G adalah pasangan terurut (V , E ), dengan V himpunan takkosong dan berhingga dan E adalah himpunan takterurut yang menghubungkan elemen-elemen di 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 disebutkan pada definisi di atas disebut juga graf takberarah. Ilustrasi graf takberarah dapat dilihat pada Gambar 2 berikut G:
1 4 2 5 3
Gambar 2 Graf G = (V , E ). Pada Gambar 2 di atas diperlihatkan bahwa V = {1, 2,3, 4,5} dan E = {{1, 2},{1,3},{1, 4},{2,3},{3, 4},{3,5}}.
Definisi 15 (Graf Berarah) Graf berarah (directed graph/digraph) G ' adalah pasangan terurut (V , A) dengan V himpunan takkosong dan berhingga, dan A adalah himpungan pasangan terurut yang menghubungkan elemen-elemen di V, dinotasikan dengan G ' = (V , A). Elemenelemen 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': 1 4 2 5 3
Gambar 3 Graf G ' = (V , A). Pada Gambar 3 diperlihatkan bahwa V = {1, 2,3, 4,5} dan A = {(1, 2), (1, 3), (1, 4), (2,1), (3, 2), (3, 5), (4, 3)}. Definisi 16 (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 . Walk tersebut menghubungkan simpul v1 dengan simpul vn . (Foulds, 1992) Definisi 17 (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 2, salah satu contoh walk adalah 1, 2,3, 4,3,5 , sedangkan 1, 2,3,5 adalah salah satu contoh path. Definisi 18 (Walk Berarah) Walk berarah pada suatu graf berarah G ' = (V , A) adalah suatu barisan terurut
7
simpul dan sisi pada G ' yang berbentuk v 0 , a1 , v1 ,..., a n , v n , dengan setiap sisi
G' :
berarah ai menghubungkan simpul-simpul vi −1 dan vi secara berurutan. (Foulds, 1992) Definisi 19 (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 3, contoh walk berarah adalah 1,3, 2,1, 4,3,5 . Contoh path berarah
adalah
2,1, 4,3,5 ,
sementara
bukan path berarah, karena tidak
1, 2,3,5
ada sisi berarah dari simpul 2 ke simpul 3. Definisi 20 (Sisi Berarah Menjauhi atau Mendekati, Suksesor, dan Predesesor) Misalkan diberikan graf berarah G ' = (V , A) . Jika a = (vi , v j ) ∈ A maka sisi
berarah ini dikatakan menjauhi vi dan mendekati v j . Simpul vi disebut predesesor bagi simpul v j , dan simpul v j
disebut
suksesor bagi simpul vi . (Foulds, 1992) Ilustrasinya diberikan dalam gambar berikut. vi
vj
Gambar 4 Sisi berarah menjauhi atau mendekati, suksesor, dan predesesor. Definisi 21 (Graf Berbobot) Suatu graf G = (V , E ) atau graf berarah G ' = (V , A) dikatakan berbobot jika terdapat fungsi w : E → ℜ atau A : A → ℜ (dengan ℜ himpunan bilangan real) yang memberikan bobot pada setiap elemen E atau A. (Foulds, 1992)
Ilustrasi graf berbobot diberikan dalam Gambar 5.
2
1 1
4
0 3
2 -2
3
5 0
Gambar 5 Graf berbobot G ' = (V , A). Misalkan diberikan A : A → ℜ untuk graf berbobot G ' = (V , A) pada Gambar 5, maka A((4,3)) = 3 atau dapat pula ditulis A 4,3 = 3; A 2,1 = 1; A1,3 = A 3,5 = 0; A 3,2 = −2; A1,4 = 2.
Terdapat kasus khusus dari graf berbobot, yaitu network. Untuk memahami konsep network diperlukan definisi-definisi source dan sink berikut ini. Definisi 22 (Source) Source adalah suatu simpul dengan tidak ada sisi berarah yang mendekati simpul tersebut. (Foulds, 1992) Definisi 23 (Sink) Sink adalah suatu simpul sehingga tidak ada sisi berarah yang menjauhi simpul tersebut. (Foulds, 1992) Definisi 24 (Network) Network adalah suatu graf berarah yang mempunyai tepat satu source dan satu sink. (Foulds, 1992)
Ilustrasi network, source, diberikan dalam Gambar 6. G:
dan
sink
1 4 2 5 3
Gambar 6 Network, source, dan sink. Pada Gambar 6, graf berarah G merupakan network dengan simpul 1 sebagai source dan simpul 5 sebagai sink. Pengertian network yang lebih sederhana diberikan oleh Ahuja et al. (1993),
8
Balakrishnan (1997), dan Bertsimas & Tsitsiklis (1997), yakni bahwa network adalah suatu graf yang simpul-simpul dan sisi-sisi berarahnya memiliki informasi numerik (suatu nilai). Ada kalanya suatu network memiliki lebih dari satu source maupun sink, sebagaimana yang akan digunakan dalam karya ilmiah ini. Network Flow Terkait dengan bahasan network flow, terlebih dahulu perlu dipahami konsep flow dalam suatu network yang diberikan pada definisi berikut ini.
Definisi 25 (Flow) Suatu flow, misalnya dinotasikan dengan f, adalah suatu fungsi bernilai integer yang didefinisikan pada himpunan sisi berarah pada suatu network sedemikian sehingga 0 ≤ f (e) ≤ c(e) untuk setiap sisi berarah e,
dengan c(e) = c(i, j ) menyatakan kapasitas sisi berarah, bernilai taknegatif, dan f (e) suatu integer yang menyatakan flow sepanjang sisi berarah e. (Balakrishnan, 1997) Ilustrasi flow pada suatu network diberikan pada Gambar 7 berikut 1
0, 4
2
Misalkan biaya pengangkutan (shipping) setiap unit flow komoditas pada sisi berarah (i, j ) ∈ A dinyatakan dengan cij , banyaknya unit flow komoditas yang melalui sisi berarah (i, j ) untuk setiap (i, j ) ∈ A dinotasikan dengan xij , batas bawah dan batas atas banyaknya flow komoditas yang diangkut melalui sisi berarah (i, j ) untuk setiap (i, j ) ∈ A berturut-turut dinyatakan dengan lij dan uij , dan bi menyatakan supply/demand pada simpul i ∈ N . Formulasi umum suatu masalah network flow diberikan sebagai berikut: min ∑ cij xij ( i , j )∈ A
terhadap
∑
j :( i , j )∈ A
xij −
∑
j :( i , j )∈ A
x ji = bi ∀i ∈ N
(2.8)
lij ≤ xij ≤ uij ∀(i, j ) ∈ A, (2.9)
dengan N menyatakan himpunan simpul dalam suatu network dan A menyatakan himpunan sisi berarah dalam network tersebut. Jika bi > 0 , bi disebut supply pada simpul i dan simpul i disebut simpul supply. Jika bi < 0 , bi disebut demand pada simpul i dan simpul i disebut simpul demand. Jika bi = 0 , simpul i disebut simpul transshipment. Batas atas, uij , disebut juga kapasitas sisi berarah
Berdasarkan Gambar 7 di atas, pada setiap sisi berarah terdapat dua buah integer yang dipisahkan oleh tanda koma. Integer pertama menyatakan flow sepanjang sisi berarah yang terkait dan integer kedua menyatakan kapasitas sisi berarah tersebut.
(i, j ) . Persamaan (2.8) menyatakan kendala konservasi flow dan pertidaksamaan (2.9) menyatakan kendala pembatasan 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 pembatasan flow merupakan suatu kendala yang membatasi banyaknya flow yang dapat melewati suatu sisi berarah. (Ahuja et al., 1993)
Network flow merupakan suatu kasus dalam PL yang memiliki struktur khusus dan menggunakan representasi graf. Bentuk dasar suatu masalah network flow dikenal dengan sebutan 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 pembatasan flow.
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.
3, 5
3, 8 3
3, 3
4
Gambar 7 Flow dan kapasitas sisi berarah.
9
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 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 LP( i ) dipilih sebagai bagian masalah berikutnya untuk diteliti. Subproblem LP(i ) diselesaikan dan diukur dengan kondisi yang sesuai. a) Jika LP( 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. LP(i ) tidak terukur, proses b) Jika dilanjutkan ke langkah 2 melakukan pencabangan LP( i ) .
untuk
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 LPi . Bidang [ x *j ] < x j < [ x *j ] + 1
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 ,
10
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 3 (Metode Branch-and-Bound) Misalkan diberikan pemrograman integer (IP) berikut max z = 5 x1 + 4 x2 x1 + x2 ≤ 5 terhadap 10 x1 + 6 x2 ≤ 45 (2.10) x1 , x2 ≥ 0 x1 , x2 integer.
Solusi optimal PL-relaksasi dari masalah IP (2.10) adalah x1 = 3.75, x2 = 1.25, dan z = 23.75 (lihat pada Lampiran 2). Batas atas nilai optimal fungsi objektif masalah ini adalah z = 23.75. Daerah fisibel masalah (2.10) ditunjukkan pada Gambar 8.
Gambar 8 Daerah fisibel untuk PL-relaksasi dari IP (2.10). Keterangan : = solusi optimal PL-relaksasi IP (2.10) = titik-titik fisibel bagi IP (2.10) Langkah berikutnya adalah memartisi daerah fisibel PL-relaksasi menjadi dua bagian berdasarkan variabel yang berbentuk pecahan (non-integer). Karena nilai dari kedua variabel yang diperoleh bukan integer, maka dipilih salah satu variabel untuk dasar pencabangan. Misalkan dipilih x1 sebagai dasar pencabangan. Jika masalah PL-relaksasi diberi nama subproblem 1, maka pencabangan tersebut menghasilkan 2 subproblem, yaitu:
•
subproblem 2: subproblem 1 ditambah kendala x1 ≥ 4; • subproblem 3: subproblem 1 ditambah kendala x1 ≤ 3. Hal ini dilustrasikan secara grafis pada Gambar 9.
Gambar 9 Daerah fisibel untuk subproblem 2 dan subproblem 3 dari IP (2.10). Setiap titik (solusi) fisibel dari IP (2.10) termuat dalam daerah fisibel subproblem 2 atau subproblem 3. Setiap subproblem ini saling lepas. Subproblem 2 dan subproblem 3 dikatakan dicabangkan oleh x1 . Sekarang dipilih subproblem yang belum diselesaikan. Misalkan dipilih subproblem 2, kemudian diselesaikan. Solusi optimal untuk subproblem 2 ini adalah x1 = 4, x2 = 0.83, dan z = 23.33 (lihat Lampiran 2). Karena nilai fungsi objektif yang diperoleh dari subproblem 1 lebih baik (lebih besar) dari pada nilai fungsi objektif yang diperoleh dari subproblem 2, maka batas atas bagi masalah ini adalah z = 23.75. Karena solusi optimal yang dihasilkan subproblem 2 bukan solusi integer, maka dipilih pencabangan pada subproblem 2 atas x2 , sehingga diperoleh dua subproblem lagi, yakni: • subproblem 4: subproblem 2 ditambah kendala x2 ≥ 1; • subproblem 5: subproblem 2 ditambah kendala x2 ≤ 0. 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. Karena subproblem 4 takfisibel (lihat pada Lampiran 2), maka subproblem ini tidak dapat menghasilkan solusi optimal, yang tersisa adalah subproblem 3 dan subproblem 5.
11
Karena aturan LIFO, dipilih subproblem 5, yang kemudian menghasilkan solusi optimal x1 = 4.5, x2 = 0, dan z = 22.5 (lihat pada Lampiran 2). Batas atas bagi masalah ini adalah z = 23.75, karena nilai ini lebih baik daripada nilai objektif yang diperoleh dari subproblem 5. x1 = 4.5 bukan integer, maka Karena 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 ini juga takfisibel (lihat pada Lampiran 2), sehingga tidak dapat menghasilkan solusi optimal. Dengan demikian subproblem-subproblem yang belum diselesaikan adalah subproblem 3 dan subproblem 7. Karena aturan LIFO, dipilih subproblem 7. Subproblem ini kemudian menghasilkan solusi optimal x1 = 4, x2 = 0,
t=1
dan z = 20 (lihat pada Lampiran 2). Dapat dilihat bahwa solusi optimal subproblem ini semuanya berupa integer, sehingga merupakan kandidat solusi untuk IP (2.10). Nilai z pada kandidat solusi ini merupakan batas bawah bagi nilai optimal IP. Penyelesaian subproblem 3 menghasilkan solusi optimal x1 = 3, x2 = 2, dan z = 23 (lihat pada Lampiran 2). Batas bawah yang ditetapkan dari solusi optimal subproblem 7 terlalu lemah dan tidak lebih baik dari nilai solusi optimal yang dihasilkan oleh subproblem 3. Dengan demikian, nilai solusi optimal subproblem 3, yakni z = 23 menjadi batas bawah yang baru. Semua solusi optimal telah berupa integer dan tidak perlu lagi dilakukan pencabangan, sehingga solusi optimal dari subproblem 3 merupakan solusi optimal IP (2.10), yakni x1 = 3, x2 = 2, dan z = 23. Pohon pencabangan yang menunjukkan penyelesaian masalah IP (2.10) secara keseluruhan ditunjukkan pada Gambar 10.
Subproblem 1 x1 = 3.75, x2 = 1.25, z = 23.75 Batas atas = 23.75 x1 ≤ 3
x1 ≥ 4
t=2
Subproblem 2 x1 = 4, x2 = 0.83, z = 23.33 Batas atas = 23.75 x2 ≥ 1
t=3
t=7
x2 ≤ 0
Subproblem 4 takfisibel
Subproblem 5 x1 = 4.5, x2 = 0, z = 22.5 Batas atas = 23.75 x1 ≥ 5
t=5
Subproblem 6 takfisibel
Subproblem 3 x1 = 3, x2 = 2, z = 23 Batas bawah = 23 Solusi Optimal
t=4
x1 ≤ 4
t=6
Subproblem 7 x1 = 4, x2 = 0, z = 20 Batas bawah = 20 Kandidat Solusi
Gambar 10 Seluruh pencabangan pada metode branch-and-bound untuk menyelesaikan IP (2.10).
12
III DEKOMPOSISI BENDERS Dekomposisi Benders (Benders, 1962) merupakan metode yang digunakan pada masalah yang memiliki variabel-variabel kontinu dalam jumlah besar, variabel integer relatif sedikit, dan struktur khusus pada kendala-kendalanya. Prosedur Dekomposisi Benders Prosedur metode dekomposisi Benders menyelesaikan masalah pemrograman linear primal (P) berikut dengan menganggap salah satu vektor variabel pada masalah tersebut, dalam hal ini Y, bernilai tetap sedemikian sehingga untuk sembarang iterasi dari algoritme ini nantinya masalah-masalah yang memuat salah satu vektor variabel, namun tidak keduanya, dapat diselesaikan.
Misalkan diberikan masalah primal max z = CX + DY terhadap AX + EY ≤ b (P) X≥0 Y≥0 dengan X dan Y vektor-vektor berukuran n, C dan D vektor-vektor 1 × n, A dan E matriksmatriks m × n, dan b vektor m × 1. Misalkan vektor Y dianggap tetap pada suatu nilai yang diberikan, dengan Y ≥ 0, maka masalah (P) di atas dapat direduksi menjadi bentuk berikut v = CX + DY max (PX) terhadap AX ≤ b − EY X ≥ 0. Misalkan u adalah vektor dual, maka dual dari masalah (PX) adalah min w = u(b − EY) (D1) terhadap uA ≥ C u ≥ 0. Taha (1975) menyebutkan bahwa masalah (D1) di atas memiliki dua sifat penting, yakni: i) daerah solusi fisibelnya adalah R = {u uA ≥ C, u ≥ 0} yang bebas dari pemilihan Y; ii) minimumnya terjadi pada titik ekstrem u k dari daerah fisibel R (hal ini didasarkan pada teorema optimalitas titik ekstrem). Jika R takterbatas maka perlu ditambahkan kendala
m
∑u i =1
M > 0 sangat besar.
i
≤ M , dengan
Kedua sifat ini menunjukkan bahwa (D1) dapat dituliskan sebagai min uk {u k (b − EY) u k ≥ 0, k = 1,..., K }, (D2) dengan u k vektor yang menyatakan titik ekstrem ke-k pada R. Diasumsikan (D1) fisibel dan misalkan mempunyai suatu nilai optimal berhingga, maka dengan menggunakan (D2), masalah (P) dapat dituliskan dalam bentuk max z = DY + min uk {u k (b − EY)} terhadap u k ≥ 0,
k = 1,..., K
(P*)
Y ≥ 0. Berdasarkan teorema dualitas kuat, jika (D1) memiliki solusi optimal, demikian pula dengan (PX), dan nilai fungsi objektif keduanya sama. Misalkan solusi optimal pada
(D1) diberikan oleh ( w, u k ), maka nilai z pada (P*) sama dengan nilai v pada (PX). Dengan demikian, masalah (P*) ekuivalen dengan masalah (PX). Karena (PX) ekuivalen dengan (P), maka masalah (P*) ekuivalen pula dengan masalah (P). Misalkan diberikan masalah max z terhadap z ≤ DY + u k (b − EY)
(P r )
u k ≥ 0, Y ≥ 0. dengan k = 1,..., r , 1 ≤ r ≤ K .
Kendala z ≤ DY + u k (b − EY) di atas disebut potongan Benders (Benders’ cut). Master problem Benders adalah suatu masalah dalam variabel y yang memuat penambahan potongan-potongan Benders. Dalam hal ini, (P r ) merupakan master problem Benders. Metode dekomposisi Benders akan konvergen ke suatu bilangan berhingga jika subproblem dan master problemnya diselesaikan secara eksak (Holmberg & Hellstrand, 1998). Konvergensi algoritme dekomposisi Benders ini dijamin oleh adanya fakta bahwa R memiliki sejumlah berhingga titik-titik ekstrem (Taha, 1975). Gagasan umum dari algoritme dekomposisi Benders adalah membuat atau menentukan batas atas dan batas bawah pada nilai optimal masalah asli (P). Berikut ini akan ditunjukkan prosedur pencarian batas bawah, z , dan batas atas, z , dengan z ≤ z∗ ≤ z , dan z ∗ adalah nilai optimal masalah asli (P). Misalkan z r menyatakan nilai fungsi objektif optimal pada masalah ( P r ) .
13
Langkah-langkah untuk mencari batas atas z dan batas bawah z adalah sebagai berikut. • Langkah 0 Misalkan u (0) sembarang solusi fisibel di (D1), u (0) tidak harus titik ekstrem. Ditetapkan r = 1 dan dilanjutkan ke langkah 1. • Langkah 1 Masalah (P r ) diselesaikan dalam z dan Y, yakni dengan menggunakan max z
Contoh 4. (Dekomposisi Benders) Misalkan masalah primal (P) min z = 3x1 + 3x2 + (10 − y2 ) x1 − x2 + y1 − 0.4 y2 ≥ 0.7
terhadap
x1 , x2 ≥ 0 y1 , y2 ∈ {0,1}, (PX) dan (D1) masalah di atas diberikan oleh v = 3 x1 + 3 x2 + (10 − y2 ) min x1 − x2 ≥ 0.7 − y1 + 0.4 y2
terhadap
x1 , x2 ≥ 0
terhadap z ≤ DY + u (b − EY ) (k )
u ( k ) ≥ 0, Y ≥ 0, k = 0,1,..., r − 1.
Misalkan
solusi
optimalnya
( z (r ) , Y(r ) ) .
Ditetapkan z = z ( r ) . • Langkah 2 Diberikan Y = Y(r ) , masalah (D1) menjadi min w = u(b − EY r ) terhadap uA ≥ C u ≥ 0. Masalah (D1) di atas diselesaikan dan misalkan u ( r ) solusi optimalnya, batas bawah z diberikan oleh z = DY ( r ) + u ( r ) (b − EY ( r ) ). Jika kendala uA ≥ C takterbatas, kendala m
∑u
i
y1 , y2 ∈ {0,1},
dan
≤ M ditambahkan pada masalah (D1) di
i=1
atas. • Langkah 3 Jika z = z , Y ( r ) optimal untuk (P) dan prosedur dilanjutkan ke langkah 4. Selainnya, ditetapkan r = r + 1 dan kembali ke langkah 1. • Langkah 4 Dengan menggunakan Y = Y ( r ) , masalah (PX) diselesaikan. Misalkan X( r ) adalah solusi optimalnya, maka solusi optimal untuk masalah (P) adalah X = X ( r ) , Y = Y ( r ) , dan z∗ = z = z . Prosedur dihentikan. (Taha, 1975) Untuk masalah primal berupa minimisasi, prosedurnya serupa, hanya saja batas atas pada masalah maksimisasi menjadi batas bawah untuk masalah minimisasi, yakni z = z ( r ) , dan sebaliknya batas bawah menjadi batas atas, yaitu z = DY ( r ) + u ( r ) (b − EY ( r ) ). Sebagai ilustrasi, diberikan contoh 4 berikut
w = u (0.7 − y1 + 0.4 y2 )
max terhadap
-3 ≤ u ≤ 3 u ≥ 0,
sementara (P r ) dari masalah (P) adalah min z terhadap z ≥ (10 − y2 ) + u ( k ) (0.7 − y1 + 0.4 y2 ) u(k ) ≥ 0 y1 , y2 ∈ {0,1},
untuk k = 0,1,..., r − 1 . Misalkan u (0) = 1 , maka (P1 ) menjadi min z terhadap z ≥ (10 − y2 ) + (0.7 − y1 + 0.4 y2 ) = 10.7 − y1 − 0.6 y2 y1 , y2 ∈ {0,1}, yang menghasilkan y1(1) = y2(1) = 1 dan z (1) = 9.1 = z (lihat pada Lampiran 3). Dengan memasukkan nilai ( y1(1) , y2(1) ) = (1,1) ke dalam (D1) diperoleh max w = 0.1u terhadap 0 ≤ u ≤ 3.
Agar w maksimum, maka haruslah u (1) = 3. Nilai-nilai ( y1(1) , y2(1) ) = (1,1) dan u (1) = 3 ini disubstitusi ke dalam batas atas z = (10 − y2( r ) ) + u ( r ) (0.7 − y1( r ) + 0.4 y2( r ) ), dengan r = 1, maka didapat
z = (10 − y2(1) ) + u (1) (0.7 − y1(1) + 0.4 y2(1) ) = (10 − 1) + 3(0.7 − 1 + 0.4) = 9 + (3)(0.1) = 9 + (0.3) = 9.3. Karena z < z , iterasi dilanjutkan. (P 2 ) diberikan oleh
14
min
z
terhadap
z ≥ (10 − y2 ) + u (0) (0.7 − y1 + 0.4 y2 ) u (0) ≥ 0 z ≥ (10 − y2 ) + u (1) (0.7 − y1 + 0.4 y2 ) u (1) ≥ 0 y1 , y2 ∈ {0,1},
yakni min terhadap
z z ≥ 10.7 − y1 − 0.6 y2 z ≥ (10 − y2 ) + (3)(0.7 − y1 + 0.4 y2 ) = 12.1 − 3 y1 + 0.2 y2 y1 , y2 ∈ {0,1}.
Ini menghasilkan solusi y1(2) = 1, y2(2) = 1, dan z (2) = 9.3 = z (lihat pada Lampiran 3). Karena z = z = 9.3, maka ( y1(2) , y2(2) ) = (1,1) merupakan solusi optimalnya. Masalah (PX) diselesaikan dalam ( x1 , x2 ) setelah menyubstitusi nilai ( y1(2) , y2(2) ) = (1,1) ke dalam (PX). Solusi optimal ini kemudian menghasilkan x1 = 0.1 dan x2 = 0 (lihat pada Lampiran 3). Secara keseluruhan, solusi optimal masalah (P) adalah ( y1 , y2 ) = (1,1), ( x1 , x2 ) = (0.1, 0), dan z = 9.3.
IV DESKRIPSI DAN FORMULASI MASALAH DESAIN NETWORK TAKBERKAPASITAS Sebagaimana disebutkan sebelumnya, 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 rupa sehingga biaya totalnya menjadi minimum. Ada dua macam komponen biaya yang dikenakan, yakni: 1. biaya pengangkutan (shipping cost) flow komoditas pada sisi berarah yang digunakan; 2. biaya tetap (fixed cost), yakni biaya yang harus dibayar setiap kali sisi berarah yang bersangkutan digunakan. Asumsi-asumsi yang digunakan dalam masalah ini antara lain: 1. biaya pengangkutan meningkat secara linear terhadap banyaknya komoditas yang diangkut melalui sisi berarah terkait; 2. banyaknya flow komoditas yang melewati suatu sisi berarah tidak dibatasi (takberkapasitas), untuk setiap sisi berarah yang terdapat dalam network; 3. setiap komoditas memiliki titik asal dan titik tujuan tunggal; 4. komoditas yang sama diangkut melalui path yang sama pula. Misalkan untuk setiap komoditas k didefinisikan sebuah simpul asal o(k) dan simpul tujuan d(k). Misalkan rk menyatakan banyaknya flow komoditas k yang diangkut dari o(k) ke d(k). Semua rk unit komoditas k diangkut melalui path yang sama, maka masalah ini dapat direduksi dengan cara membagi banyaknya komoditas k yang
diangkut dengan rk. Dengan demikian, inti dari masalah ini adalah mengirimkan atau mengangkut satu unit flow komoditas k dari titik asal ke titik tujuannya untuk setiap komoditas dengan biaya minimum. Ada dua variabel keputusan yang digunakan dalam model masalah ini, meliputi: 1. variabel desain network yang terkait dengan satu unit flow komoditas yang diangkut; 2. variabel desain network yang terkait dengan penentuan sisi berarah yang digunakan. Kendala-kendala dan pembatasan tanda yang digunakan dalam masalah ini mencakup: 1. kendala konservasi flow, yang merupakan bentuk dasar kendala masalah network flow secara umum (penjelasannya dapat dilihat pada landasan teori); 2. biaya tetap pada suatu sisi berarah harus dibayar setiap kali sisi berarah tersebut digunakan untuk mengangkut flow komoditas; 3. banyaknya flow komoditas yang melintasi suatu sisi berarah harus berupa bilangan positif; 4. variabel keputusan penentuan flow sisi berarah bernilai biner, artinya hanya mungkin bernilai 0 atau 1. Masalah desain network takberkapasitas dapat dimodelkan sebagai berikut. Misalkan C = himpunan komoditas N = himpunan simpul pada network A = himpunan sisi berarah pada network
15
⎧1, jika sisi berarah (i, j ) digunakan yij = ⎨ ⎩ 0, selainnya
cijk = biaya pengangkutan (shipping) satu unit
flow komoditas k pada sisi berarah (i, j ) f ij = biaya tetap yang harus dibayar jika sisi
⎧ 1, jika i = o(k ) ⎪ b = ⎨−1, jika i = d (k ) ⎪ 0,selainnya ⎩
berarah (i, j ) digunakan
k i
xijk = banyaknya flow komoditas k pada sisi berarah (i, j )
Model masalah desain network takberkapasitas (MDNT)
min
∑∑
k ∈C ( i , j )∈ A
terhadap
∑
j :( i , j )∈ A
cijk xijk +
xijk −
∑
∑
( i , j )∈ A
j :( i , j )∈ A
f ij yij
x kji = bik
∀i ∈ N , ∀k ∈ C
xijk ≤ yij
∀(i, j ) ∈ A, ∀k ∈ C (4.2)
x ≥0
∀(i, j ) ∈ A, ∀k ∈ C
k ij
(4.1)
yij ∈ {0,1} ∀(i, j ) ∈ A
Diasumsikan semua koefisien adalah integer. Kendala (4.1) menunjukkan persamaan konservasi network flow yang mengandung pengertian bahwa banyaknya flow yang masuk ke suatu simpul haruslah sama dengan banyaknya flow yang keluar dari simpul tersebut jika bukan berupa simpul asal o(k) ataupun simpul tujuan d(k), dalam hal ini xijk − x kji = 0 . Akan tetapi jika
∑
j:(i , j )∈A
∑
j:(i , j )∈A
simpul tersebut adalah simpul asal o(k), maka hanya ada flow yang keluar dari simpul tersebut dan persamaan di atas bernilai 1. Sebaliknya, jika simpul yang bersangkutan adalah simpul tujuan d(k), maka persamaan di atas akan bernilai −1 karena hanya ada flow yang memasuki simpul tersebut. Kendala (4.2) memberikan persyaratan bahwa tidak ada flow yang boleh melintasi sisi berarah (i, j ) kecuali jika biaya tetap fij
dibayarkan. Penjelasannya, jika suatu flow melintasi sisi berarah (i, j ) berarti sisi berarah tersebut digunakan dan terdapat dalam network (yij bernilai 1), artinya biaya tetap fij haruslah dibayarkan. Dalam hal ini total flow yang melintasi suatu sisi berarah paling banyak satu unit untuk tiap komoditas. Sementara jika yij bernilai 0 berarti sisi berarah (i, j ) tidak terdapat dalam network (tidak digunakan) atau dengan kata lain tidak ada flow yang melintasi sisi berarah ini, sehingga biaya tetap fij tidak perlu dibayarkan. Dalam model ini, masalah desain network takberkapasitas adalah masalah pemrograman integer campuran, dengan variabel integer sebanyak |A| dan variabel kontinu sebanyak |A||C|.
V PENYELESAIAN MASALAH DESAIN NETWORK TAKBERKAPASITAS DENGAN DEKOMPOSISI BENDERS Dekomposisi Benders secara khusus memberikan penyederhanaan bentuk ketika diterapkan pada masalah desain network takberkapasitas. Algoritme ini secara bergantian menyelesaikan suatu konfigurasi network yang bersifat sementara dalam variabel integer y dan masalah routing atau shipping dalam variabel kontinu x. Untuk menyelesaikan masalah desain network takberkapasitas dengan dekomposisi Benders,
variabel y ditentukan bernilai tetap. Ini menghasilkan suatu himpunan tetap sisi-sisi berarah yang digunakan dalam konfigurasi network. Dalam hal, ini variabel keputusan y ditetapkan bernilai 1, yang mengandung pengertian bahwa sisi-sisi berarah yang bersangkutan digunakan dalam network. Untuk suatu variabel y yang bernilai tetap, model masalah (MDNT) terdekomposisi menjadi sekumpulan masalah path terpendek
16
(routing) untuk setiap komoditas k. Banyaknya masalah-masalah path terpendek ini adalah C , sesuai dengan banyaknya
dengan A menyatakan himpunan sisi berarah yang terdapat dalam network tersebut, N menyatakan himpunan simpul dalam network tersebut, dan C menyatakan himpunan komoditas. Menurut Magnanti et al. (1986), mekanisme dekomposisi Benders untuk satu komoditas maupun banyak komoditas sama saja, sehingga indeks k dapat ditinggalkan dan diasumsikan hanya ada satu komoditas. Dengan demikian hanya satu subproblem routing untuk sembarang nilai tetap y. Misalkan subproblem routing untuk satu komoditas dinotasikan dengan S(y) dan R(y) menyatakan nilai optimal S(y), dengan mengabaikan biaya-biaya tetap. Misalkan pula simpul 1 adalah simpul asal untuk komoditas tunggal ini dan simpul n adalah simpul tujuannya. Kendala (4.1) pada masalah (MDNT) dapat dijabarkan dengan memasukkan simpul 1 sebagai simpul asal (o(k)) dan simpul n sebagai simpul tujuan (d(k)). Dengan mengabaikan indeks k, subproblem routing S(y) dapat dituliskan sebagai berikut.
komoditas. Misalkan diberikan y ∈ Y , model masalah (MDNT) terdekomposisi untuk komoditas-komoditas yang ada menjadi bentuk berikut min z terhadap z ≥ ∑ Rk ( y ) + k ∈C
∑
( i , j )∈ A
fij yij
yij ∈ {0,1}
y ∈Y ,
(i, j ) ∈ A,
dengan Rk ( y ) menyatakan biaya routing komoditas k dalam network yang ditetapkan oleh k, yakni Rk ( y ) = min ∑ cijk xijk ( i , j )∈ A
terhadap
∑
j :( i , j )∈ A
xijk −
∑
j :( i , j )∈ A
x kji = bik ∀i ∈ N , k ∈ C
xijk ≤ yij
(i, j ) ∈ A, k ∈ C
x ≥0
(i, j ) ∈ A, k ∈ C ,
k ij
( S ( y ))
R ( y ) = min
∑
( i , j )∈ A
terhadap
cijk xij
∑
xijk −
∑
xijk −
∑
xijk −
j :( i , j )∈ A
j :( i , j )∈ A
j :( i , j )∈ A
∑
x kji = 1, i = 1
(5.1)
∑
x kji = −1, i = n
(5.2)
∑
x kji = 0, i ≠ 1, i ≠ n (5.3)
j :( i , j )∈ A
j :( i , j )∈ A
j :( i , j )∈ A
− xijk ≥ − yij (i, j ) ∈ A (5.4) xijk ≥ 0
Misalkan ui menyatakan variabel-variabel dual yang bersesuaian dengan kendala (5.1), (5.2), dan (5.3), dan vij menyatakan variabelvariabel dual yang bersesuaian dengan kendala (5.4). Masalah dual dari subproblem S(y) dapat dituliskan sebagai berikut max u1 − un − ∑ vij yij ( i , j )∈ A (DR) terhadap ui - u j − vij ≤ cijk ∀(i, j ) ∈ A. Berdasarkan teorema dualitas lemah, untuk sembarang nilai tetap y, nilai fungsi objektif dari solusi fisibel masalah primal (minimisasi) ≥ nilai fungsi objektif dari solusi fisibel masalah dual (maksimisasi). Dalam hal ini, subproblem S(y) merupakan masalah primal yang berupa minimisasi. Dengan demikian, nilai fungsi objektif dari solusi fisibel masalah (DR), yang dalam hal ini
(i, j ) ∈ A.
adalah dual dari subproblem S(y), merupakan batas bawah R(y), yakni R( y ) ≥ u1 − un − ∑ vij yij . (5.5) ( i , j )∈ A
Pertidaksamaan (5.5) dipenuhi sebagai suatu persamaan (ruas kiri = ruas kanan) jika ui dan vij adalah solusi optimal masalah dual (DR). Dengan demikian, dapat dituliskan R( y ) = min w terhadap w ≥ u1 − un −
∑
( i , j )∈ A
vij yij
(5.6)
∀(u, v) ∈ D, dengan w menyatakan nilai optimal masalah dual, u = (u i ) dan v = (vij ) menyatakan
vektor-vektor dari variabel-variabel masalah dual, dan D menyatakan daerah solusi fisibel masalah dual (DR), dengan variabel vij dalam D taknegatif .
17
terpendek yang didefinisikan oleh y ′ atau reformulasi masalah (5.6) dengan y = y ′. Jika variabel-variabel dual yang menghasilkan solusi optimal, dinyatakan sebagai (u ' , v' ) , memenuhi kendala (5.7), dalam hal ini z ′ ≥ ∑ fij yij′ + u1′ − un′ − ∑ vij′ yij′ , (5.8)
Misalkan nilai optimal masalah (MDNT) dinotasikan dengan p*. Karena p* adalah minimum dari jumlah biaya tetap f ij y ij
∑
( i , j )∈A
dan biaya pengangkutan (yang dalam hal ini merupakan nilai optimal subproblem S(y), direpresentasikan dengan R(y)) pada semua konfigurasi network yang dihasilkan oleh solusi fisibel masalah ini, maka didefinisikan masalah (MP) (MP) p∗ = min z terhadap z≥
∑
( i , j )∈ A
f ij yij + u1 − un −
∑
( i , j )∈ A
( i , j )∈ A
( i , j )∈ A
maka masalah (MP) dipenuhi untuk setiap (u, v) ∈ D dan dengan demikian p∗ = p ′ dan y ′ adalah solusi optimal (Magnanti et al., 1986). Jika tidak, potongan Benders (5.7) di atas ditambahkan ke dalam master problem (MP) dan prosedur diulangi kembali. Untuk beberapa nilai y, misalnya y , subproblem routing ini mungkin takfisibel, yakni jika network yang didefinisikan oleh y tidak memuat path apapun dari titik asal komoditas ke titik tujuannya. Dalam kasus ini harus ada suatu himpunan B yang memisahkan asal dan tujuan tersebut dari titik-titik asal dan tujuan lainnya, yakni dengan y ij = 0 untuk setiap (i, j ) ∉ B.
(vij ) yij (5.7)
∀(u, v) ∈ D y ∈ Y dan yij ∈ {0,1} ∀(i, j ) ∈ A.
Masalah (MP) di atas merupakan master problem, dengan A menyatakan himpunan sisi berarah pada network tersebut dan Y menyatakan himpunan konfigurasi network yang dihasilkan solusi fisibel y, dalam hal ini jika routing fisibel ada. Kendala (5.7) pada masalah di atas merupakan potongan Benders. Dekomposisi ini menyelesaikan master problem dengan merelaksasi kendala (5.7) pada z untuk paling banyak (u, v) ∈ D dan menggantinya dengan sejumlah berhingga kendala yang didapat dari pembatasan (u, v) ke dalam beberapa himpunan D ′ ⊆ D. Misalkan p′ menyatakan nilai fungsi objektif dari master problem dengan (u, v) ∈ D ′ ⊆ D, Karena kendala (5.7) tersebut direlaksasikan, maka p ′ merupakan suatu batas bawah untuk p* (Magnanti et al., 1986). Algoritme dekomposisi Benders ini menyelesaikan subproblem routing S(y) untuk mengecek apakah solusi p ′ = z ′ dan y ' = ( yij′ ) pada master problem terelaksasi
Dengan demikian, perlu ditambahkan potongan fisibilitas (feasibility cut), yakni y ij ≥ 1 , pada master problem terelaksasi
∑
( i , j )∈B
dan diproses sebagaimana sebelumnya, dengan catatan bahwa master problem takterelaksasi tidak memuat potongan ini. Untuk lebih dari satu komoditas, misalkan S k ( yˆ ) menyatakan subproblem routing untuk komoditas k pada suatu nilai tetap yˆ , Rk ( yˆ ) menyatakan nilai objektif optimalnya, dan R( yˆ ) = ∑ Rk ( yˆ ). Subproblem routing S k ( yˆ ) k ∈C
dapat dituliskan sebagai berikut.
bersifat fisibel dalam masalah aslinya (master problem yang belum terelaksasi), yakni dengan menyelesaikan masalah path ( S k ( yˆ )) Rk ( yˆ ) = min ∑ cijk xij ( i , j )∈ A
terhadap
∑
xijk −
∑
xijk −
∑
xijk −
j :( i , j )∈ A
j :( i , j )∈ A
j :( i , j )∈ A
∑
x kji = 1,
i = o(k ), k ∈ C
(5.9)
∑
x kji = −1, i = d (k ), k ∈ C
(5.10)
∑
x kji = 0, i ≠ o(k ), i ≠ d ( k ), k ∈ C
(5.11)
j :( i , j )∈ A
j :( i , j )∈ A
j :( i , j )∈ A
− xijk ≥ − yij (i, j ) ∈ A, k ∈ C x ≥0 k ij
(i, j ) ∈ A.
(5.12)
18
Misalkan u k = (uik ) menyatakan variabel dual untuk subproblem ke-k yang bersesuaian dengan kendala-kendala (5.9), (5.10), dan (5.11), dan v k = (vijk ) menyatakan variabel dual untuk subproblem ke-k yang bersesuaian dengan kendala (5.12), maka dual dari subproblem routing S k ( yˆ ) dapat dituliskan sebagai berikut. max uok( k ) − udk ( k ) − ∑ vijk yij ( i , j )∈ A
terhadap u - u − v ≤ cijk
(DS)
(i, j ) ∈ A. Untuk semua (u,v) fisibel bagi (DS), Rk ( yˆ ) ≥ uok( k ) − udk ( k ) − ∑ vijk yij .
(5.13)
k i
k j
k ij
Dengan demikian, potongan Benders (5.7) menjadi pertidaksamaan (5.14) berikut z ≥ ∑ f ij yij ( i , j )∈ A (5.14) + ∑ [(uok( k ) − udk ( k ) ) − ∑ vijk yij ] . k ∈C
( i , j )∈ A
Ruas kanan pada pertidaksamaan (5.14) di atas merupakan batas bawah biaya total z. Batas bawah ini dapat diinterpretasikan sebagai penjumlahan biaya-biaya tetap dan nilai fungsi objektif masalah dual dari subproblem routing yang terkait dengan masalah (MDNT). Master problem dari masalah desain network takberkapasitas secara umum berbentuk
( i , j )∈ A
(MPk ) min z terhadap z ≥
∑
( i , j )∈ A
f ij yij + ∑ [uok( k ) − udk ( k ) − k ∈C
y ∈ Y dan yij ∈ {0,1}
Secara garis besar, dekomposisi Benders untuk menyelesaikan masalah desain network takberkapasitas dilakukan melalui langkahlangkah berikut ini. 1. Master problem diselesaikan untuk memperoleh solusi (z, y). 2. Subproblem routing S k ( yˆ ) untuk setiap komoditas k ∈ C dalam network yang ditetapkan oleh y diselesaikan. 3. Jika beberapa subproblem tidak fisibel ( y ∉ Y ) , dibentuk potongan-potongan fisibilitas. 4. Masalah dual (DS) diselesaikan. Jika variabel-variabel (u,v) yang menghasilkan solusi optimal masalah ini memenuhi pertidaksamaan (5.14), maka nilai z dan
∑
( i , j )∈ A
(vijk ) yij ] ∀(u , v) ∈ D ∀(i, j ) ∈ A.
y yang dihasilkan dari master problem adalah optimal. Jika tidak, potonganpotongan Benders ditambahkan ke dalam master problem. Langkah-langkah tersebut dilakukan secara berulang hingga ditemukan suatu vektor solusi fisibel optimal (z, y). Magnanti et al. (1986) menyebutkan bahwa metode dekomposisi Benders untuk menyelesaikan masalah desain network takberkapasitas dapat disempurnakan dengan potongan-potongan Benders yang dikuatkan dan potongan-potongan Benders yang pareto optimal. Dapat juga dilakukan suatu preprocessing untuk mereduksi ukuran masalah.
VI PENYELESAIAN MASALAH DESAIN NETWORK TAKBERKAPASITAS DENGAN METODE BRANCH-AND-BOUND Penyelesaian masalah desain network takberkapasitas dengan metode branch-andbound pada karya ilmiah ini dilakukan dengan memanfaatkan software LINGO 8.0, yakni sebuah software pemrograman yang didesain untuk membangun suatu model masalah pemrograman linear, pemrograman taklinear, dan optimisasi integer serta menentukan solusinya dengan prinsip pemecahan yang didasarkan pada metode branch-and-bound. Dengan software ini, pemecahan dan penentuan solusi masalah desain network
takberkapasitas dapat dilakukan secara lebih cepat, mudah, dan efisien. Untuk mengimplementasikan metode branch-and-bound dalam penyelesaian masalah desain network takberkapasitas ini digunakan data hipotetik dengan 13 simpul, 156 sisi berarah, dan 26 komoditas. Data-data biaya tetap (fixed cost) dan biaya pengangkutan (shipping cost) untuk setiap komoditas pada setiap pasangan simpul yang dihubungkan oleh sisi berarah dibangkitkan secara acak dengan menggunakan software Mathematica 5.2, dengan input berupa tipe
19
bilangan yang akan dibangkitkan (integer), nilai minimum yang diinginkan, nilai maksimum yang diinginkan, dan banyaknya bilangan yang diinginkan. Outputnya berupa bilangan-bilangan bertipe integer yang nilainilainya berada pada range antara nilai minimum dan maksimum yang dimasukkan sebagai input, dan banyaknya sesuai yang diinginkan. Pembangkitan data-data ini beserta syntax inputnya dicantumkan pada Lampiran 4. Titik asal dan titik tujuan untuk setiap komoditas ditentukan oleh penulis (dapat dilihat pada Tabel 4). Data-data selengkapnya diberikan dalam Lampiran 5. Syntax program dalam LINGO 8.0 untuk memroses penyelesaian masalah ini dicantumkan dalam Lampiran 6, sementara beberapa hasil komputasi program ini ditampilkan pada Lampiran 7. Waktu komputasi yang dibutuhkan software LINGO 8.0 untuk menyelesaikan program ini adalah selama 40 detik. Solusi yang didapat adalah solusi optimal dengan nilai optimal fungsi objektifnya 12516 dan diperoleh pada iterasi ke-56191. Adapun ringkasan hasil komputasinya, yang berupa sisi-sisi berarah yang digunakan dalam network terkait beserta rute untuk tiap komoditas diberikan dalam tabel-tabel berikut. Tabel 2 Sisi-sisi berarah yang digunakan dalam network Sisi-sisi Berarah yang Digunakan (E,Q) (F,P) (G,H) (H,P) (H,W) (L,H) (L,M) (M,O) (O,T) (P,O) (P,R) (Q,L) (R,F) (R,S) (S,H) (T,W)
(W,E) (W,G) Tabel 3 Rute pengangkutan flow optimal untuk setiap komoditas Komoditas Rute Pengangkutan Flow 1 P,R 2 H,W 3 L,H,P,R,F 4 E,Q,L,H,P,R,S 5 G,H,W,E,Q,L,M 6 O,T,W,G,H 7 R,S,H,W,E 8 M,O,T 9 F,P 10 W,E,Q,L 11 S,H,W,G 12 T,W,E,Q 13 Q,L,M,O 14 E,Q,L,M 15 P,O,T,W 16 F,P,R,S,H 17 R,F,P,O,T 18 G,H,W,E 19 Q,L,H,P,R,S 20 H,P,R,F 21 W,G,H,P,R 22 L,M,O 23 S,H,W,E,Q 24 M,O,T,W,E,Q,L 25 T,W,G,H,P 26 O,T,W,G Sisi-sisi berarah yang digunakan dalam network sebagaimana tercantum dalam Tabel 2 diperoleh dari variabel keputusan yij yang bernilai 1, sementara rute pengangkutan flow optimal yang terdapat dalam Tabel 3 diperoleh dari variabel keputusan xijk yang bernilai 1. Berdasarkan hasil yang tertera pada Tabel 2 dan Tabel 3 tersebut, konfigurasi network optimal yang dihasilkan diilustrasikan pada Gambar 11.
20
T
R S E
W
F
H O P G
Q L
M
Gambar 11 Ilustrasi network optimal yang dihasilkan berdasarkan Tabel 2 dan Tabel 3. Pada Gambar 11 di atas, seluruh tanda panah menyatakan sisi-sisi berarah yang digunakan dalam network. Rute pengangkutan flow optimal tidak ditampilkan untuk setiap komoditas, dalam hal ini yang digambarkan hanya rute untuk komoditas 1, 5, dan 17. Panah dengan garis putus-putus (dari simpul P
ke simpul R) merupakan rute pengangkutan untuk flow komoditas 1. Rute pengangkutan untuk flow komoditas 5 dilambangkan dengan tanda panah putus-putus berbentuk bulat, sementara rute pengangkutan flow komoditas 17 dinotasikan dengan tanda panah putusputus berbentuk kotak.
VII SIMPULAN DAN SARAN 7.1 Simpulan Masalah desain network takberkapasitas bertujuan meminimumkan biaya total yang terdiri atas biaya pengangkutan untuk setiap komoditas dan biaya tetap yang terkait dengan penggunaan sisi-sisi berarah dalam network, dengan asumsi bahwa banyaknya flow komoditas yang dapat melewati sisi-sisi berarah tersebut tidak dibatasi. Kendalakendalanya meliputi kendala konservasi flow dan keharusan dibayarkannya biaya tetap setiap penggunaan suatu sisi berarah untuk mengangkut komoditas. Masalah ini dapat diselesaikan dengan berbagai metode, 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. Metode ini memberikan suatu batas bawah bagi nilai optimal untuk masalah desain network takberkapasitas, yakni penjumlahan dari biaya-biaya tetap dan nilai fungsi objektif dari masalah dual yang bersesuaian, dan menyelesaikannya melalui langkah-langkah
iteratif yang dilakukan secara berulang, yakni dengan menyelesaikan master problem, subproblem routing, dan masalah dual yang bersesuaian secara bergantian, hingga ditemukan suatu solusi fisibel optimal. Prinsip dasar metode branch-and-bound adalah memecah daerah fisibel suatu masalah PL-relaksasi dengan membuat subproblemsubproblem. Penyelesaian masalah desain network takberkapasitas dengan metode ini dilakukan dengan menggunakan software LINGO 8.0 dan data-data hipotetik yang dibangkitkan secara acak, yang menghasilkan biaya total minimum berikut sisi-sisi berarah yang digunakan dalam network dan rute pengangkutan untuk setiap flow komoditas.
7.2 Saran Pada karya ilmiah ini telah dibahas penyelesaian masalah desain network takberkapasitas dengan dekomposisi Benders yang belum disempurnakan dan metode branch-and-bound. Penulis menyarankan untuk selanjutnya dilakukan pembahasan mengenai penyelesaian masalah ini dengan metode dekomposisi Benders yang telah disempurnakan dan reprocessing masalah serta implementasinya dengan menggunakan software yang kompatibel.
21
DAFTAR PUSTAKA Ahuja, R.K., T.L. Magnanti, J.B. Orlin. 1993. Network Flows: Theory, Algorithms, and Applications. Prentice Hall, New Jersey. Balakrishnan, V.K. 1997. Schaum’s Outlines: Graph Theory. McGraw-Hill, New York. Balakrishnan, A., T.L. Magnanti, R.T. Wong. 1989. A Dual Ascent Procedure for Large-Scale Uncapacitated Network Design. Opns. Res. 37: 716-740. Benders, J.F. 1962. Partitioning Procedures for Solving Mixed-Variables Programming Problems. Numerische Matematik 4: 238-252. Bertsimas, D & J. Tsitsiklis. 1997. Introduction to Linear Optimization. Athena Scientific, Massachussets. Dantzig, G.B. 1963. Linear Programming and Extensions. Princeton University Press, New Jersey. Florian, M., G. Guerin, G. Bushel. 1976. The Engine Scheduling Problem in A Railway Network. INFOR Journal 14: 121-138.
Holmberg, K & J. Hellstrand. 1998. Solving the Uncapacitated Network Design Problem by A Lagrangean Heuristic and Branch-and-Bound. Operations Research 46. No. 2: 247-259. Holmberg, K & A. Migdalas. 1991. Solution Methods for the Discrete Choice Network Design Problem Combining Lagrangean Relaxation and Decomposition with Generation of Valid Inequalities. Working Paper LiTH-MAT/OPT-WP-1991. Optimization. Linköping Institute of Technology, Sweden. Magnanti, T.L., R.T. Wong, P. Mireault. 1986. Tailoring Benders Decomposition for Uncapacitated Network Design. Mathematical Programming Study 26: 112-154. Nash, S.G & A. Sofer. 1996. Linear and Nonlinear Programming. McGraw-Hill, New York. Nemhauser, G & L. Wolsey. 1999. Integer and Combinatorial Optimization. John Wiley & Sons, New York.
Foulds, L.R. 1992. Graph Theory Applications. Springer-Verlag, New York.
Richardson, R. 1976. An Optimization Approach to Routing Aircraft. Transportation Science 10: 52-71.
Garfinkel, R.S & G.L. Nemhauser. 1972. Integer Programming. John Wiley & Sons, New York.
Taha, H.A. 1975. Integer Programming: Theory, Applications, and Computations. Academic Press, New York.
Geoffrion, A.M & G. Graves. 1974. Multicommodity Distribution System Design by Benders Decomposition. Management Science 5: 822-844.
Taha, H.A. 1996. Pengantar Riset Operasi. Alih Bahasa: Drs. Daniel Wirajaya. Binarupa Aksara, Jakarta. Terjemahan dari: Operations Research.
Hazell, P.B.R & R.D. Norton. 1986. Mathematical Programming for Economic Analysis in Agriculture. MacMillan, New York.
Van Roy, T.J. 1983. Cross Decomposition for Mixed Integer Programming. Math. Programming 25: 46-63.
Holmberg, K. 1990. On the Convergence of Cross Decomposition. Math. Programming 47: 269-296. Holmberg, K. 1992. Linear Mean Value Cross Decomposition: A Generalization of the Kornai-Liptak Method. European Journal Opnl. Res. 62: 55-73.
Winston, W.L. 1995. Introduction to Mathematical Programming 2nd ed. Duxbury, New York. Winston, W.L. 2004. Operations Research Applications and Algorithms 4th ed. Duxbury, New York.
22
LAMPIRAN
23
Lampiran 1 Bukti-Bukti Teorema dan Akibat pada Titik Ekstrem dan Dualitas Pemrograman Linear Teorema 1 (Optimalitas Titik Ekstrem) Solusi optimal suatu masalah PL dicapai pada suatu titik ekstrem atau himpunan titiktitik ekstrem.
adalah suatu kombinasi konveks dari titik-titik ekstrem.
Bukti: Misalkan x sembarang titik yang bukan titik ekstrem. Titik x ini dapat dinyatakan sebagai kombinasi linear titik-titik ekstrem xk. Dipilih suatu nilai minimum dari titik-titik ekstrem yang diperlukan untuk menentukan x sedemikian sehingga tidak ada titik ekstrem yang bernilai 0. Harus ada paling sedikit dua titik ekstrem taknol ini, maka x dapat dituliskan sebagai x= d k x k , d k > 0, d k = 1, (A.1)
Teorema 2 (Dualitas Lemah) Misalkan x adalah solusi fisibel masalah primal (P) dan y adalah solusi fisibel masalah dual (D), maka z = c T x ≥ b T y = w.
∑
∑ k
(Hazell & Norton, 1986)
Bukti: Kendala pada masalah dual (D) menunjukkan bahwa c T ≥ y T A. Karena x ≥ 0, maka z = c T x ≥ y T Ax = y T b = b T y = w.
dengan dk suatu konstanta. Misalkan c suatu vektor koefisien nilai fungsi objektif, maka cTx = cT ( d k xk ) = d k (c T x k ). (A.2)
∑ k
∑ k
Untuk semua titik ekstrem xk, dipilih salah satu titik yang memaksimumkan c T x k (dalam hal ini masalah PL berupa maksimisasi). Misalkan nilai maksimum ini dinyatakan dengan v. Jika v disubstitusikan untuk setiap c T x k pada (A.2), maka ruas kanan persamaan di atas tidak dapat direduksi dan mungkin saja justru meningkat. Dengan demikian, (A.3) c T x ≤ v. Ada dua kemungkinan hasil (A.2), yakni: 1. nilai maksimum v pada c T x k tidak tercapai pada semua titik ekstrem yang digunakan untuk menentukan x, maka c T x k < v untuk beberapa k dan dengan demikian c T x < v . Ini berarti x bukan merupakan suatu nilai maksimum (dalam hal ini x adalah suatu titik batas (boundary point) yang bukan kombinasi linear dari titik-titik ekstrem optimal), 2. nilai maksimum v pada c T x k dicapai pada semua titik ekstrem sedemikian sehingga c T x = v. Dengan demikian, jika x optimal, demikian pula semua titik ekstrem (dan semua kombinasi linearnya). Berdasarkan dua kemungkinan di atas, tidak ada titik dalam himpunan fisibel, kecuali titik ekstrem, yang optimal kecuali titik tersebut
(Nash & Sofer, 1996) Teorema di atas memiliki implikasi yang dituliskan dalam akibat berikut ini. Akibat 1 Jika x ∗ adalah suatu solusi fisibel masalah primal (P), y ∗ solusi fisibel masalah dual (D), dan c T x∗ = b T y∗, maka x ∗ adalah solusi optimal masalah primal (P) dan y ∗ solusi optimal masalah dual (D). Bukti: Berdasarkan Teorema 2, untuk sembarang solusi x, c T x ≥ b T y ∗ dan cT x ≥ b T y∗ = cT x∗, maka c T x ≥ c T x ∗ untuk
sembarang
x ∈{x Ax ≥ b, x ≥ 0}.
Dengan
demikian, x ∗ merupakan solusi optimal masalah primal (P). Secara serupa, terbukti pula bahwa y ∗ merupakan solusi optimal masalah dual (D). (Nash & Sofer, 1996) Teorema 3 (Dualitas Kuat) Perhatikan sepasang masalah PL primal dan dual. Jika salah satu masalah memiliki solusi optimal demikian pula yang lain dan nilai objektif kedua masalah ini sama. Bukti: Misalnya diasumsikan: (a) masalah primal memiliki suatu solusi optimal; (b) masalah primal dalam bentuk standar; (c) xˆ , solusi
24
masalah primal, adalah suatu solusi basis fisibel. Dengan menyusun kembali variabelvariabelnya, vektor xˆ dapat dituliskan dalam bentuk variabel-variabel basis dan nonbasis: ⎛x ⎞ xˆ = ⎜ B ⎟ . ⎝ xN ⎠ Secara bersesuaian dapat dituliskan pula ⎛c ⎞ A = (B N ) dan c = ⎜ B ⎟ . ⎝ cN ⎠ Dengan demikian x B = B −1 b. Jika x B optimal, reduced memenuhi
c TN − c TB B −1 N ≥ 0 atau c TB B −1 N ≤ c TN . Misalkan
costnya
dapat
yˆ suatu ditulis pula vektor yang bersesuaian dengan solusi fisibel basis ini, yˆ = B − T c B atau yˆ T = cTB B −1 . Akan ditunjukkan yˆ fisibel untuk masalah dual dan b T yˆ = c T xˆ .
Akan ditunjukkan pula dari
Akibat 1 bahwa yˆ optimal untuk masalah dual. Pertama-tama perlu dicek fisibilitasnya. yˆ T A = cTB B −1 ( B N ) =
(c
T B
cTB B −1 N ) ≤ ( cTB
cTN ) = cT ,
maka A T yˆ ≤ c dan y memenuhi kendalakendala masalah dual. Kemudian nilai-nilai objektif untuk masalah primal dan dual dihitung: z = cT x = cTB xB = cBT B −1b w = b T y = y T b = cTB B −1b = z. Dapat dilihat bahwa yˆ fisibel untuk masalah dual dan nilai fungsi objektif dualnya sama dengan nilai optimal masalah primal. Dengan demikian, berdasarkan Akibat 1, yˆ optimal untuk masalah dual.
(Nash & Sofer, 1996)
25
Lampiran 2
Syntax Program LINDO 6.1 untuk Menyelesaikan Masalah Pemrograman Linear dengan Metode Branch-and-Bound Beserta Hasil yang Diperoleh 1) PL-relaksasi masalah (2.10) max z = 5 x1 + 4 x2 terhadap x1 + x2 ≤ 5 10 x1 + 6 x2 ≤ 45 x1 , x2 ≥ 0
Syntax program pada LINDO 6.1: max 5x1 + 4x2 subject to x1 + x2 <= 5 10x1 + 6x2 <= 45 x1 >= 0 x2 >= 0 Hasil yang diperoleh: LP OPTIMUM FOUND AT STEP 2 OBJECTIVE FUNCTION VALUE 1) 23.75000 VARIABLE VALUE REDUCED COST X1 3.750000 0.000000 X2 1.250000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 2.500000 3) 0.000000 0.250000 4) 3.750000 0.000000 5) 1.250000 0.000000 NO. ITERATIONS= 2 2) Subproblem 2 max z = 5 x1 + 4 x2 terhadap x1 + x2 ≤ 5 10 x1 + 6 x2 ≤ 45 x1 ≥ 4, x2 ≥ 0
Syntax program pada LINDO 6.1: max 5x1 + 4x2 subject to x1 + x2 <= 5 10x1 + 6x2 <= 45 x1 >= 4 x2 >= 0 Hasil yang diperoleh: LP OPTIMUM FOUND AT STEP 2 OBJECTIVE FUNCTION VALUE 1) 23.33333 VARIABLE VALUE REDUCED COST X1 4.000000 0.000000 X2 0.833333 0.000000
ROW SLACK OR SURPLUS DUAL PRICES 2) 0.166667 0.000000 3) 0.000000 0.666667 4) 0.000000 -1.666667 5) 0.833333 0.000000 NO. ITERATIONS= 2 3) Subproblem 4 max z = 5 x1 + 4 x2 terhadap x1 + x2 ≤ 5 10 x1 + 6 x2 ≤ 45 x1 ≥ 4, x2 ≥ 1
Syntax program pada LINDO 6.1: max 5x1 + 4x2 subject to x1 + x2 <= 5 10x1 + 6x2 <= 45 x1 >= 4 x2 >= 1 Hasil yang diperoleh: takfisibel, sebagaimana ditunjukkan di bawah ini
4) Subproblem 5 max z = 5 x1 + 4 x2 terhadap x1 + x2 ≤ 5 10 x1 + 6 x2 ≤ 45 x1 ≥ 4, x2 ≤ 0
Syntax program pada LINDO 6.1: max 5x1 + 4x2 subject to x1 + x2 <= 5 10x1 + 6x2 <= 45 x1 >= 4 x2 <= 0 Hasil yang diperoleh: LP OPTIMUM FOUND AT STEP 2 OBJECTIVE FUNCTION VALUE 1) 22.50000
26
VARIABLE VALUE REDUCED COST X1 4.500000 0.000000 X2 0.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.500000 0.000000 3) 0.000000 0.500000 4) 0.500000 0.000000 5) 0.000000 1.000000 NO. ITERATIONS= 2 5) Subproblem 6 max z = 5 x1 + 4 x2 terhadap x1 + x2 ≤ 5 10 x1 + 6 x2 ≤ 45 x1 ≥ 5, x2 ≤ 0
Syntax program pada LINDO 6.1: max 5x1 + 4x2 subject to x1 + x2 <= 5 10x1 + 6x2 <= 45 x1 >= 5 x2 <= 0 Hasil yang diperoleh: takfisibel, sebagaimana ditunjukkan di bawah ini
6) Subproblem 7 max z = 5 x1 + 4 x2 terhadap x1 + x2 ≤ 5 10 x1 + 6 x2 ≤ 45 x1 ≤ 4, x2 ≤ 0
Syntax program pada LINDO 6.1: max 5x1 + 4x2 subject to x1 + x2 <= 5 10x1 + 6x2 <= 45
x1 <= 4 x2 <= 0 Hasil yang diperoleh: LP OPTIMUM FOUND AT STEP 2 OBJECTIVE FUNCTION VALUE 1) 20.00000 VARIABLE VALUE REDUCED COST X1 4.000000 0.000000 X2 0.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 1.000000 0.000000 3) 5.000000 0.000000 4) 0.000000 5.000000 5) 0.000000 4.000000 NO. ITERATIONS= 2 7) Subproblem 3 max z = 5 x1 + 4 x2 terhadap x1 + x2 ≤ 5 10 x1 + 6 x2 ≤ 45 x1 ≤ 3, x2 ≥ 0
Syntax program pada LINDO 6.1: max 5x1 + 4x2 subject to x1 + x2 <= 5 10x1 + 6x2 <= 45 x1 <= 3 x2 >= 0 Hasil yang diperoleh: LP OPTIMUM FOUND AT STEP 2 OBJECTIVE FUNCTION VALUE 1) 23.00000 VARIABLE VALUE REDUCED COST X1 3.000000 0.000000 X2 2.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 4.000000 3) 3.000000 0.000000 4) 0.000000 1.000000 5) 2.000000 0.000000 NO. ITERATIONS= 2
27
Lampiran 3
Syntax Program LINDO 6.1 untuk Menyelesaikan Masalah Pemrograman Linear dengan Metode Dekomposisi Benders Beserta Hasil yang Diperoleh 1) Masalah (P1 ) dengan u 0 = 1 min z terhadap z ≥ (10 − y2 ) + (0.7 − y1 + 0.4 y2 ) = 10.7 − y1 − 0.6 y2 y1 , y2 ∈ {0,1}
Syntax program pada LINDO 6.1: min z subject to z + y1 + 0.6y2 >= 10.7 end int y1 int y2 Hasil yang diperoleh: LP OPTIMUM FOUND AT STEP 3 OBJECTIVE VALUE = 9.10000038 FIX ALL VARS.( 2) WITH RC > 0.600000 NEW INTEGER SOLUTION OF 9.10000038 AT BRANCH 0 PIVOT 3 BOUND ON OPTIMUM: 9.100000 ENUMERATION COMPLETE. BRANCHES= 0 PIVOTS= 3 LAST INTEGER SOLUTION IS THE BEST FOUND RE-INSTALLING BEST SOLUTION... OBJECTIVE FUNCTION VALUE 1) 9.100000 VARIABLE VALUE REDUCED COST Y1 1.000000 -1.000000 Y2 1.000000 -0.600000 Z 9.100000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 -1.000000 NO. ITERATIONS= 3 BRANCHES= 0 DETERM.= 1.000E 0 2) Masalah (D1), dengan ( y1 , y2 ) = (1,1) max w = 0.1u terhadap 0 ≤ u ≤ 3
Syntax program LINDO 6.1: max 0.1u subject to u >= 0 u <= 3
Hasil yang diperoleh: LP OPTIMUM FOUND AT STEP 1 OBJECTIVE FUNCTION VALUE 1) 0.3000000 VARIABLE VALUE REDUCED COST U 3.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 3.000000 0.000000 3) 0.000000 0.100000 NO. ITERATIONS= 1 RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE U 0.100000 INFINITY 0.100000 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 0.000000 3.000000 INFINITY 3 3.000000 INFINITY 3.000000 3) Masalah (P 2 ) min z terhadap z ≥ 10.7 − y1 − 0.6 y2 z ≥ (10 − y2 ) + (3)(0.7 − y1 + 0.4 y2 ) = 12.1 − 3 y1 + 0.2 y2 y1 , y2 ∈ {0,1}
Syntax program LINDO 6.1: min z subject to z + y1 + 0.6y2 >= 10.7 z + 3y1 - 0.2y2 >= 12.1 end int y1 int y2 Hasil yang diperoleh: LP OPTIMUM FOUND AT STEP 4 OBJECTIVE VALUE = 9.25000000 FIX ALL VARS.( 1) WITH RC > 2.50000
28
SET Y2 TO <= 0 AT 1, BND= 9.700 TWIN= -9.300 9 NEW INTEGER SOLUTION OF 9.69999981 AT BRANCH 1 PIVOT 9 BOUND ON OPTIMUM: 9.300000 FLIP Y2 TO >= 1 AT 1 WITH BND= -9.3000002 NEW INTEGER SOLUTION OF 9.30000019 AT BRANCH 1 PIVOT 9 BOUND ON OPTIMUM: 9.300000 DELETE Y2 AT LEVEL 1 ENUMERATION COMPLETE. BRANCHES= 1 PIVOTS= 9 LAST INTEGER SOLUTION IS THE BEST FOUND RE-INSTALLING BEST SOLUTION... OBJECTIVE FUNCTION VALUE 1) 9.300000 VARIABLE VALUE REDUCED COST Y1 1.000000 -3.000000 Y2 1.000000 0.200000 Z 9.300000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.200000 0.000000 3) 0.000000 -1.000000 NO. ITERATIONS= 9 BRANCHES= 1 DETERM.= 1.000E 0 4) Masalah (PX), dengan ( y1 , y2 ) = (1,1) min v = 3 x1 + 3x2 + (10 − 1) terhadap x1 − x2 ≥ 0.7 − 1 + 0.4 x1 , x2 ≥ 0
Syntax program LINDO 6.1: min 3x1 + 3x2 + y subject to x1 - x2 >= 0.1 x1 >= 0 x2 >= 0 y=9
Hasil yang diperoleh: LP OPTIMUM FOUND AT STEP 2 OBJECTIVE FUNCTION VALUE 1) 9.300000 VARIABLE VALUE REDUCED COST X1 0.100000 0.000000 X2 0.000000 6.000000 Y 9.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 -3.000000 3) 0.100000 0.000000 4) 0.000000 0.000000 5) 0.000000 -1.000000 NO. ITERATIONS= 2 RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 3.000000 INFINITY 3.000000 X2 3.000000 INFINITY 6.000000 Y 1.000000 INFINITY INFINITY RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 0.100000 INFINITY 0.100000 3 0.000000 0.100000 INFINITY 4 0.000000 0.000000 INFINITY 5 9.000000 INFINITY 9.000000
29
Lampiran 4 Pembangkitan Data-data Biaya Pengangkutan dan Biaya Tetap dengan Mathematica 5.2 Beserta Syntax Inputnya Input yang dimasukkan ke dalam halaman notebook software Mathematica 5.2 mempunyai struktur sebagai berikut: nama daftar (list) = Table[Random[tipe bilangan yang ingin dibangkitkan, {nilai minimum, nilai maksimum},{banyaknya bilangan yang ingin dibangkitkan}]. Perintah “Table” merupakan perintah untuk mengkonstruksi suatu list yang berisikan entri-entri sesuai input yang dimasukkan. Struktur paling sederhana dari perintah ini dituliskan dalam bentuk Table[expr, {imax }], yang membangkitkan suatu list berisikan “expr” sebanyak imax . Perintah “Random” merupakan suatu perintah untuk membangkitkan bilangan secara acak sesuai
dengan tipe bilangan yang ingin dibangkitkan dan nilai-nilainya berada pada range antara nilai minimum dan nilai maksimum yang dimasukkan oleh pengguna (user). Banyaknya bilangan yang ingin dibangkitkan dapat ditentukan pula oleh user sebagaimana yang terdapat dalam karya ilmiah ini. Berikut ini diberikan syntax pembangkitan data biaya tetap untuk setiap sisi berarah (i, j ), fij, dengan i ≠ j :
fixed_cost=Table[Random[Integer,{100,5000}],{156}]. Ekspresi “fixed_cost” merupakan nama untuk list yang ingin dihasilkan, “integer” adalah tipe bilangan yang ingin dibangkitkan, “100” adalah nilai minimum bilangan yang ingin dibangkitkan, ekspresi “5000” adalah nilai maksimumnya, dan “156” adalah banyaknya bilangan yang ingin dibangkitkan. Output dari syntax di atas berupa suatu list bilangan bertipe integer yang nilai-nilainya berada di antara 100 dan 5000 sebanyak 156 buah. Untuk sisi-sisi berarah (i, j ) dengan i = j , misalnya sisi berarah (F, F), biaya tetapnya
bernilai 0. Output ini beserta nilai-nilai 0 kemudian dimasukkan secara berurutan ke dalam worksheet Microsoft Excell sebagai entri-entri data biaya tetap pada setiap sisi berarah (i, j ) , sebagaimana dicantumkan pada Tabel 5 (Lampiran 5). Adapun syntax pembangkitan data biaya pengangkutan setiap komoditas pada setiap sisi berarah (i, j ), cijk, dengan i ≠ j diberikan sebagai berikut:
shipping_cost=Table[Random[Integer,{1,90}],{4056}]. Keterangan syntax ini serupa dengan keterangan syntax pembangkitan data biaya tetap sebagaimana telah disebutkan di atas. Output dari syntax ini adalah list bilangan bertipe integer yang nilai-nilainya berada pada selang [1,90] sebanyak 4056 buah. Seperti halnya pada biaya tetap, biaya pengangkutan setiap komoditas pada sisi-sisi berarah (i, j ) dengan i = j bernilai 0. Output syntax ini bersama dengan nilai-nilai 0
sebagaimana telah disebutkan kemudian dimasukkan pula ke dalam worksheet Microsoft Excell sebagai entri-entri biaya pengangkutan, dapat dilihat pada Tabel 6 (Lampiran 5). Data-data pada worksheet ini dibaca oleh program LINGO 8.0 melalui perintah “@OLE” untuk kemudian diproses (syntax program LINGO 8.0 untuk masalah ini dapat dilihat pada Lampiran 6).
30
Lampiran 5 Data-data Hipotetik untuk Implementasi Penyelesaian Masalah Desain Network Takberkapasitas dengan Metode Branch-and-Bound Tabel 4 Data titik asal dan titik tujuan untuk setiap komoditas Komoditas 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
Titik Asal (Origin) P H L E G O R M F W S T Q E P F R G Q H W L S M T O
Titik Tujuan (Destination) R W F S M H E T P L G Q O M W H T E S F R O Q L P G
31
Tabel 5 Biaya tetap (fij) untuk setiap sisi berarah (i, j ) Simpul E F G H L M O P Q R S T W
E 0 3473 4563 818 4261 909 1533 3914 3218 4082 626 2909 215
F 1593 0 1681 4310 3555 749 3018 2733 1246 552 1405 4313 2291
G 2270 3311 0 4116 1668 1933 3731 4964 3495 1657 1415 2188 477
H 2933 3933 267 0 272 1502 3594 1072 3371 973 389 4442 1905
L 916 498 2250 2668 0 1257 3531 4551 491 1481 2823 2930 3128
M 4268 4675 3095 1262 1090 0 4575 3823 4484 2459 3798 2767 3717
O 1240 2257 2539 1056 756 112 0 198 2957 4183 1034 1583 1734
P 2695 282 4907 146 3335 2885 2831 0 2923 3508 2916 2176 611
Q 1062 2341 3095 2588 2173 3261 2800 1110 0 4495 2435 3640 1339
R 2730 372 661 2521 3858 2270 3330 511 4190 0 1397 4209 3036
S 2960 3792 1090 843 3140 2306 3737 3395 2391 197 0 3105 3948
T 3580 3088 2917 3401 4700 1593 1161 531 323 3736 1789 0 4095
W 2806 2401 4292 506 2476 2728 3734 4321 2224 2018 2620 534 0
31
32
Tabel 6 Biaya pengangkutan (cijk) untuk setiap komoditas k pada setiap sisi berarah (i, j ) Sisi Berarah 1 0 (E,E) (E,F) 64 (E,G) 74 (E,H) 33 5 (E,L) (E,M) 60 (E,O) 7 (E,P) 26 (E,Q) 23 (E,R) 80 (E,S) 20 (E,T) 75 (E,W) 19 1 (F,E) 0 (F,F) (F,G) 30 (F,H) 61 (F,L) 39 (F,M) 6 (F,O) 67 (F,P) 84 (F,Q) 27 (F,R) 40 (F,S) 26 (F,T) 87 (F,W) 63 (G,E) 44 (G,F) 30 (G,G) 0 (G,H) 12 (G,L) 15 (G,M) 20 (G,O) 74 (G,P) 24 (G,Q) 28 (G,R) 25 (G,S) 33 (G,T) 47 (G,W) 76 (H,E) 61 (H,F) 3 (H,G) 73 (H,H) 0 (H,L) 57 (H,M) 39 (H,O) 76 (H,P) 20 (H,Q) 36
2 0 21 84 38 80 40 58 72 24 9 67 38 83 43 0 65 29 48 87 45 21 58 1 35 46 57 22 33 0 30 3 36 51 66 71 43 49 21 68 8 71 87 0 81 74 50 74 57
3 0 47 23 33 78 58 23 65 11 34 3 57 4 47 0 10 24 37 84 73 8 53 2 78 14 74 90 65 0 66 28 53 63 75 18 7 21 15 6 16 55 78 0 45 58 24 20 52
4 0 57 72 18 10 8 78 3 62 59 3 33 43 65 0 81 23 72 31 11 79 14 8 49 81 77 18 36 0 54 90 51 49 35 69 64 35 84 26 23 5 8 0 77 6 31 79 45
5 0 88 13 67 36 30 25 48 67 22 61 42 75 8 0 15 40 27 74 78 38 53 89 69 20 70 49 19 0 7 36 90 59 72 83 3 36 64 20 5 48 22 0 51 88 89 11 90
6 0 9 82 6 24 72 33 23 83 86 24 21 55 59 0 35 33 76 80 59 59 11 14 4 24 2 22 10 0 79 70 86 29 87 42 70 53 68 38 11 83 64 0 10 21 66 13 79
7 0 15 65 78 25 5 61 57 64 10 8 46 45 82 0 55 27 62 39 88 21 3 19 21 48 27 9 89 0 32 11 24 27 54 25 34 8 6 68 76 76 8 0 16 34 32 53 69
8 0 27 69 51 16 68 68 35 82 38 73 13 62 37 0 87 22 4 46 35 42 18 21 53 61 82 80 57 0 4 40 57 57 45 7 70 6 26 20 68 13 5 0 69 48 46 54 64
9 0 89 62 13 61 85 12 9 87 6 60 47 36 5 0 23 66 47 8 85 81 11 51 57 8 9 75 32 0 11 81 32 27 36 50 25 61 74 64 6 82 27 0 83 79 58 76 56
10 0 70 30 33 33 17 11 40 36 19 67 42 86 24 0 69 42 88 70 31 2 36 12 2 23 17 44 21 0 7 83 33 8 42 5 25 15 29 60 26 60 82 0 81 38 15 38 77
11 0 31 12 27 13 83 88 55 87 59 3 60 1 13 0 60 85 61 49 68 31 87 2 28 76 70 80 53 0 27 25 79 24 38 62 81 57 47 67 20 76 20 0 72 66 41 68 13
Komoditas 12 13 14 15 0 0 0 0 78 36 2 70 30 61 14 45 1 5 89 40 76 50 81 54 84 88 55 60 13 36 25 56 57 64 6 23 29 12 6 32 89 36 66 68 67 9 48 54 48 58 26 23 29 83 75 60 56 88 45 90 0 0 0 0 29 51 22 45 29 30 70 40 14 45 66 55 87 12 77 40 26 7 19 75 58 16 48 57 1 14 41 69 12 5 10 55 59 20 37 63 78 13 45 81 41 21 24 8 31 72 55 13 59 9 58 88 0 0 0 0 88 87 6 53 71 52 80 48 53 78 23 65 79 79 74 38 44 55 4 49 69 27 9 19 10 58 79 23 10 59 89 19 40 89 79 27 84 64 86 70 38 68 20 64 46 75 89 32 5 76 76 56 0 0 0 0 64 77 46 10 17 51 66 61 83 22 42 79 24 44 12 80 71 48 35 34
16 0 44 18 42 65 68 52 62 60 3 46 29 75 40 0 79 70 74 9 29 42 1 76 48 59 84 63 29 0 69 85 33 18 38 12 65 76 40 51 60 36 51 0 71 70 28 36 40
17 0 32 89 89 11 86 80 60 74 53 43 44 40 63 0 4 36 76 28 32 82 58 46 30 81 45 36 58 0 78 72 70 1 82 82 44 40 32 50 67 88 33 0 11 45 31 50 17
18 0 57 62 11 27 52 56 72 49 1 38 78 20 2 0 73 21 53 42 42 69 31 73 56 33 14 28 61 0 38 58 79 64 59 5 32 19 2 32 84 74 31 0 17 2 21 45 5
19 0 62 41 46 21 65 80 13 86 67 66 31 11 19 0 82 58 76 20 18 89 36 74 77 8 1 7 23 0 53 69 8 17 49 25 20 38 69 68 64 43 58 0 58 44 83 15 61
20 0 20 38 69 8 41 69 42 47 58 24 27 38 59 0 56 9 34 45 86 42 36 20 27 70 35 89 32 0 45 45 25 90 49 13 86 68 83 5 86 76 72 0 30 12 47 12 81
21 0 60 10 52 20 78 42 79 22 88 18 37 51 54 0 58 47 58 89 18 36 81 39 54 69 7 20 21 0 40 36 35 61 68 90 60 1 61 3 70 67 56 0 30 87 14 58 16
22 0 70 74 18 44 2 84 24 32 31 2 70 70 77 0 82 26 11 14 87 74 18 68 42 22 60 65 66 0 75 85 37 90 82 52 63 55 8 71 51 28 12 0 76 74 22 36 74
23 0 53 33 20 90 76 18 82 52 60 28 70 4 89 0 47 74 46 13 33 52 59 33 86 46 52 5 11 0 33 10 40 61 25 54 20 26 16 55 50 27 84 0 46 69 41 67 77
24 0 48 66 3 60 51 71 78 36 37 51 28 11 17 0 10 56 24 40 13 46 52 70 23 12 61 7 38 0 19 69 36 90 75 89 64 65 23 5 32 10 9 0 56 71 51 71 39
25 0 9 24 31 81 37 74 37 57 86 67 11 88 29 0 10 59 37 54 53 22 34 42 57 15 22 53 1 0 85 40 13 34 16 65 14 79 5 48 68 18 61 0 68 32 74 13 28
26 0 85 34 13 64 63 13 10 85 18 63 45 16 14 0 52 18 17 5 60 18 29 77 53 79 15 60 25 0 52 45 33 2 80 38 82 63 11 83 5 61 8 0 51 55 85 88 56
33
(H,R) (H,S) (H,T) (H,W) (L,E) (L,F) (L,G) (L,H) (L,L) (L,M) (L,O) (L,P) (L,Q) (L,R) (L,S) (L,T) (L,W) (M,E) (M,F) (M,G) (M,H) (M,L) (M,M) (M,O) (M,P) (M,Q) (M,R) (M,S) (M,T) (M,W) (O,E) (O,F) (O,G) (O,H) (O,L) (O,M) (O,O) (O,P) (O,Q) (O,R) (O,S) (O,T) (O,W) (P,E) (P,F) (P,G) (P,H) (P,L) (P,M) (P,O) (P,P) (P,Q) (P,R)
80 84 40 6 64 76 59 74 0 72 77 48 46 61 17 53 83 31 43 72 60 42 0 30 13 11 53 90 19 7 5 67 52 9 56 18 0 46 26 1 22 43 54 23 73 37 89 64 4 73 0 85 46
8 69 17 72 82 2 18 28 0 19 73 20 58 59 61 48 17 61 30 39 69 1 0 63 48 90 64 71 16 24 5 87 55 53 44 2 0 64 70 14 88 34 58 72 4 88 36 70 78 34 0 38 7
34 88 11 65 74 67 84 22 0 89 3 87 54 20 52 16 62 23 87 35 26 51 0 86 68 1 27 71 84 32 38 53 81 50 16 73 0 77 49 7 36 55 72 66 8 74 75 25 6 21 0 6 84
14 71 47 30 3 76 23 48 0 82 11 38 58 62 33 75 50 29 75 59 31 53 0 53 59 25 48 71 34 67 29 78 39 3 41 81 0 55 2 76 44 7 19 12 86 13 32 21 21 64 0 68 19
64 10 17 7 15 71 39 66 0 71 15 87 42 54 13 15 43 43 73 3 79 72 0 14 58 16 42 5 73 56 27 49 61 22 37 69 0 1 70 66 31 52 18 20 1 19 59 76 20 63 0 30 66
51 52 83 12 80 6 8 77 0 51 10 60 35 49 56 38 50 18 85 22 29 57 0 88 11 1 86 36 35 90 75 62 10 87 32 26 0 14 53 65 44 32 67 53 74 71 63 10 20 50 0 7 33
63 56 19 7 55 35 19 13 0 29 6 48 53 49 10 60 50 42 56 28 47 29 0 39 89 49 57 12 83 34 90 4 88 49 74 6 0 26 77 46 16 39 38 19 70 21 5 75 88 59 0 88 52
72 33 44 52 2 62 80 16 0 74 43 56 39 79 82 85 79 46 44 72 20 10 0 56 13 13 52 53 35 64 17 52 59 1 51 30 0 32 13 8 32 50 18 24 29 88 38 54 19 77 0 83 69
74 45 77 26 52 41 19 88 0 14 21 20 13 62 13 78 51 26 75 54 29 8 0 7 35 19 80 4 71 15 62 33 78 6 39 46 0 31 65 80 22 5 2 10 15 70 80 38 82 36 0 31 39
51 62 88 44 59 81 75 65 0 66 77 33 26 42 41 1 23 39 13 40 65 83 0 57 14 38 88 53 21 60 60 29 42 23 25 66 0 85 15 59 11 83 64 88 35 45 33 67 33 77 0 64 78
23 43 53 34 27 86 26 83 0 83 54 59 41 41 19 50 18 37 89 34 65 68 0 61 76 84 30 59 40 35 61 32 57 60 24 3 0 3 85 11 22 28 70 56 16 2 51 3 83 28 0 53 28
46 43 39 22 77 61 1 89 0 48 65 57 45 18 13 85 40 58 48 73 88 64 0 7 65 27 87 25 44 12 32 39 81 16 24 19 0 32 64 89 83 90 87 72 16 8 78 49 5 89 0 6 55
19 16 44 27 44 80 73 89 0 34 45 4 30 66 41 69 54 34 47 31 76 22 0 42 4 68 66 25 56 32 63 29 27 39 65 84 0 24 71 34 71 17 34 42 15 77 8 16 24 11 0 60 35
48 50 55 70 24 12 37 54 0 6 79 45 57 39 54 21 14 74 50 9 83 30 0 71 16 43 70 67 44 82 75 59 69 67 88 5 0 29 51 86 79 42 77 61 68 41 26 59 61 22 0 89 7
14 7 44 77 26 80 56 19 0 17 22 17 61 55 50 63 13 1 60 49 70 63 0 79 90 22 4 10 48 58 31 47 5 80 87 50 0 87 3 79 34 70 50 76 45 63 80 67 17 30 0 22 13
50 38 36 33 40 59 64 89 0 37 53 66 79 25 45 37 4 78 35 57 5 86 0 22 71 63 26 12 43 59 65 11 82 7 22 35 0 60 28 50 79 34 16 52 22 10 84 57 5 21 0 31 17
31 43 38 65 76 25 37 80 0 38 13 40 86 15 46 60 85 35 67 52 54 53 0 9 35 66 59 42 35 46 85 11 85 39 68 88 0 6 45 85 86 70 19 47 8 54 2 81 64 38 0 34 20
63 65 86 87 84 90 32 8 0 79 50 77 84 36 4 41 13 39 50 59 49 72 0 53 44 58 6 66 59 85 18 41 30 17 21 35 0 41 65 80 78 34 1 82 52 30 68 5 4 32 0 3 34
45 34 45 45 46 51 65 86 0 44 62 39 55 52 22 74 41 61 90 41 58 57 0 77 84 82 79 49 65 32 75 19 41 30 15 48 0 71 67 37 1 10 45 39 89 33 23 16 62 65 0 34 24
3 6 12 83 22 59 33 3 0 89 45 74 50 83 50 21 70 58 13 28 37 29 0 64 18 47 18 37 37 90 42 80 20 60 82 17 0 22 35 24 48 70 60 89 16 20 61 75 55 24 0 65 62
54 50 41 1 53 77 34 12 0 17 76 48 29 64 61 54 77 29 87 63 64 10 0 3 12 41 41 61 79 46 35 80 46 58 18 11 0 54 63 49 42 36 63 32 80 33 6 38 36 1 0 29 74
75 42 22 26 40 68 85 77 0 1 70 36 88 90 90 5 11 69 29 5 56 8 0 51 18 14 59 52 37 57 35 45 90 51 38 13 0 50 9 8 90 15 6 39 71 85 83 15 74 48 0 55 2
7 72 4 43 13 14 53 51 0 24 89 42 40 21 10 57 83 72 56 48 48 83 0 73 46 90 61 48 55 33 65 86 88 9 74 90 0 42 57 5 16 79 48 13 13 57 30 83 22 15 0 18 10
47 77 40 19 73 70 21 38 0 53 4 58 58 74 7 18 28 83 40 83 13 68 0 85 66 47 44 30 30 78 72 45 87 8 80 61 0 52 33 83 74 35 72 56 90 65 25 58 70 36 0 53 31
46 61 60 56 4 81 56 78 0 2 79 46 83 54 48 56 50 66 55 51 52 64 0 89 24 18 81 1 76 6 47 63 72 17 35 84 0 59 30 42 32 8 62 46 78 23 32 19 35 26 0 48 90
12 75 30 78 25 9 32 49 0 8 79 5 73 36 28 29 20 16 51 46 73 22 0 59 23 10 42 51 89 12 80 71 29 89 86 22 0 59 33 81 3 41 12 33 40 77 17 86 65 85 0 73 70
34
(P,S) (P,T) (P,W) (Q,E) (Q,F) (Q,G) (Q,H) (Q,L) (Q,M) (Q,O) (Q,P) (Q,Q) (Q,R) (Q,S) (Q,T) (Q,W) (R,E) (R,F) (R,G) (R,H) (R,L) (R,M) (R,O) (R,P) (R,Q) (R,R) (R,S) (R,T) (R,W) (S,E) (S,F) (S,G) (S,H) (S,L) (S,M) (S,O) (S,P) (S,Q) (S,R) (S,S) (S,T) (S,W) (T,E) (T,F) (T,G) (T,H) (T,L) (T,M) (T,O) (T,P) (T,Q) (T,R) (T,S)
60 63 89 43 20 51 40 61 20 81 76 0 34 18 69 14 39 48 45 6 38 83 52 12 82 0 15 2 75 10 21 45 84 25 23 68 16 84 47 0 37 42 57 59 19 58 33 36 80 49 7 74 85
73 63 85 57 18 68 48 67 1 6 8 0 29 55 48 45 76 46 38 32 29 82 5 5 47 0 17 78 53 84 38 82 45 90 54 45 71 59 5 0 62 17 58 41 79 63 17 74 80 64 55 77 81
42 22 19 70 58 86 64 81 18 51 10 0 44 79 33 17 52 70 9 28 4 41 85 5 88 0 85 81 49 40 64 33 36 24 83 83 70 62 68 0 49 4 23 61 83 10 37 60 44 4 40 83 78
3 52 87 85 86 67 9 70 49 80 73 0 27 59 44 6 62 53 3 74 72 9 17 41 15 0 81 45 5 31 63 37 5 6 78 32 72 46 60 0 67 90 82 21 25 15 25 46 79 20 89 62 10
54 59 43 23 50 27 52 13 13 4 9 0 32 45 78 67 66 45 67 57 69 63 19 6 33 0 25 29 9 9 70 6 55 47 28 18 52 88 73 0 47 4 44 89 18 47 58 76 2 77 60 31 22
3 1 83 8 16 17 61 53 7 23 69 0 73 30 66 68 66 9 1 68 48 71 73 44 49 0 80 60 31 8 36 80 87 75 65 76 67 83 64 0 62 19 21 74 21 30 71 71 37 35 82 38 90
83 7 79 67 80 13 36 37 84 50 45 0 12 81 79 51 27 82 63 21 84 29 13 23 13 0 16 51 8 13 58 25 3 83 80 52 47 18 35 0 33 61 22 81 1 61 80 82 36 80 16 76 83
6 74 43 11 49 45 9 54 7 1 32 0 36 12 49 87 26 82 28 40 11 26 56 38 78 0 16 12 47 88 53 10 8 26 28 32 56 1 22 0 71 65 63 3 45 40 85 76 71 58 2 71 52
49 17 63 87 19 41 18 71 47 50 35 0 74 86 26 69 57 33 50 60 68 42 72 7 31 0 60 48 8 9 77 4 36 44 18 37 6 22 19 0 1 87 71 45 56 19 20 75 82 78 11 73 79
15 326 52 35 69 24 72 23 22 30 10 0 57 44 39 8 71 28 89 74 44 76 3 68 76 0 82 75 28 50 25 39 30 41 36 54 12 49 11 0 82 26 65 81 85 24 43 49 62 39 83 10 10
18 85 65 59 69 76 39 70 88 17 9 0 56 33 74 74 6 2 14 17 66 81 26 89 66 0 2 79 36 79 28 83 85 40 6 53 48 58 64 0 41 88 6 65 2 38 62 60 19 49 25 78 25
5 65 74 15 88 1 53 51 14 76 9 0 62 89 19 31 67 73 15 15 48 41 16 36 9 0 24 30 89 41 63 25 80 57 27 86 43 33 67 0 50 74 58 35 36 15 2 80 37 84 21 85 44
27 65 16 72 71 70 11 43 52 56 60 0 72 24 59 45 3 90 35 29 51 14 12 68 11 0 65 5 23 42 86 45 22 37 84 80 9 68 78 0 48 85 1 54 1 73 75 22 33 86 19 32 39
71 50 10 60 86 21 15 77 3 26 6 0 3 1 77 62 13 75 73 36 21 68 42 54 64 0 79 67 23 11 58 76 2 71 56 19 47 16 35 0 73 61 41 45 63 87 21 11 3 61 12 72 28
87 88 33 16 84 17 7 57 1 65 47 0 31 68 65 60 48 76 5 85 17 75 61 64 73 0 81 49 39 7 80 85 82 37 27 42 62 89 85 0 57 25 84 17 7 89 37 16 41 60 88 73 24
4 30 26 31 21 35 57 2 69 77 72 0 71 44 84 77 39 82 81 61 55 42 42 10 17 0 88 13 58 51 28 27 82 71 26 61 15 53 53 0 67 61 76 47 21 87 6 79 41 56 77 21 80
3 71 69 64 55 80 31 6 39 58 4 0 58 59 18 9 1 70 13 38 44 15 36 47 61 0 49 78 60 68 72 32 69 18 82 34 89 26 1 0 48 71 59 90 44 22 31 34 56 11 31 39 23
37 47 25 16 77 25 55 38 35 1 18 0 19 81 25 31 53 49 27 82 47 56 66 62 67 0 60 54 12 83 37 76 2 84 1 45 13 88 46 0 5 8 89 4 43 32 64 45 40 27 72 2 17
74 46 33 35 62 76 3 48 26 90 37 0 1 80 49 45 31 72 54 34 19 43 38 53 82 0 44 14 37 55 18 59 81 30 84 63 49 61 23 0 4 83 23 48 6 65 75 18 77 54 50 1 28
74 35 22 89 89 78 59 12 56 56 6 0 31 14 79 32 28 44 70 82 45 62 40 73 77 0 75 72 52 88 8 3 57 71 27 72 83 12 25 0 62 16 74 63 17 77 16 79 2 32 79 6 88
37 19 17 78 28 1 21 31 18 66 41 0 87 75 15 87 36 47 30 25 46 57 90 61 68 0 67 12 73 70 17 80 23 33 19 80 13 11 90 0 88 36 3 71 49 39 81 46 68 22 79 77 49
42 65 2 52 85 75 5 87 49 5 39 0 22 57 25 3 78 6 22 31 86 50 85 87 33 0 53 2 3 64 55 67 84 81 85 71 1 59 69 0 41 87 1 5 53 75 38 39 64 29 77 18 78
24 37 28 17 68 11 22 32 3 67 46 0 80 9 79 72 11 36 69 54 4 32 12 87 43 0 69 64 43 69 80 34 54 63 36 84 29 29 2 0 43 90 58 12 51 38 56 78 41 86 47 67 64
27 81 63 54 63 77 11 12 6 15 66 0 38 8 41 55 25 37 61 55 25 34 73 47 69 0 79 17 13 48 67 21 84 69 56 55 13 77 74 0 6 42 25 31 43 33 28 27 1 57 76 81 70
26 63 73 82 15 24 76 3 79 40 31 0 3 66 63 13 83 16 42 57 35 23 39 2 16 0 7 4 17 70 7 31 52 9 66 13 56 5 73 0 72 63 5 7 30 12 43 69 87 23 32 2 45
27 68 38 90 83 79 1 17 55 3 37 0 6 75 47 74 14 16 13 57 62 82 87 2 52 0 85 29 39 65 9 69 84 38 54 15 41 79 57 0 10 71 5 55 83 61 74 38 62 54 60 34 7
35
(T,T) (T,W) (W,E) (W,F) (W,G) (W,H) (W,L) (W,M) (W,O) (W,P) (W,Q) (W,R) (W,S) (W,T) (W,W)
0 60 61 20 20 80 33 22 34 4 1 6 81 70 0
0 13 32 66 11 27 41 49 63 4 12 40 61 28 0
0 31 46 28 49 4 58 12 73 1 44 56 42 49 0
0 56 73 5 81 70 86 61 32 55 3 2 72 5 0
0 34 58 88 40 30 34 7 43 89 30 88 11 13 0
0 79 33 69 45 23 26 87 27 86 27 57 5 37 0
0 73 11 19 90 77 44 8 53 61 56 34 26 7 0
0 43 22 70 89 2 35 47 36 3 64 18 5 48 0
0 13 80 16 58 6 68 68 41 24 82 56 19 5 0
0 1 45 37 52 55 67 74 71 51 58 87 18 82 0
0 35 88 82 85 89 13 11 74 21 50 63 61 37 0
0 8 16 75 7 22 77 36 42 88 11 58 4 26 0
0 10 64 29 83 30 17 85 62 88 27 3 20 9 0
0 75 39 88 46 7 37 87 88 38 2 49 78 76 0
0 48 81 80 65 51 51 43 68 86 68 27 82 90 0
0 37 15 45 59 27 18 80 50 71 10 88 1 13 0
0 14 23 53 9 72 78 83 31 17 58 18 16 21 0
0 67 78 87 90 62 38 21 5 56 15 47 45 21 0
0 81 25 34 4 29 85 20 3 29 13 4 73 55 0
0 47 12 22 57 18 61 14 85 22 89 30 29 76 0
0 32 42 36 55 75 1 32 48 62 72 64 59 53 0
0 49 43 63 6 23 84 9 5 70 6 21 32 68 0
0 78 71 42 43 71 48 1 4 29 22 81 83 13 0
0 6 10 10 28 88 83 1 81 63 84 7 86 49 0
0 36 88 87 20 90 10 29 15 53 19 54 82 82 0
0 63 21 78 14 42 12 80 57 15 60 6 59 13 0
36
Lampiran 6
Syntax Program LINGO 8.0 untuk Masalah Desain Network Takberkapasitas model : sets: node1; node2; commodity; arcs(node1,node2):fixed_cost,arc_usage; conservation(node1,commodity):supply; links(node1,node2,commodity):shipping_cost,flow; endsets !fungsi obyektif; min=@sum(links(i,j,k):shipping_cost(i,j,k)*flow(i,j,k))+@sum(arcs( i,j):fixed_cost(i,j)*arc_usage(i,j)); !kendala; !1)konservasi flow; @for(conservation(i,k):@sum(links(i,j,k):flow(i,j,k))@sum(links(j,i,k):flow(j,i,k))=supply(i,k)); !2)restriksi flow; @for(links(i,j,k):flow(i,j,k) <= arc_usage(i,j)); !3)flow harus positif; @for(links(i,j,k):flow(i,j,k) >= 0); !4)arc_usage merupakan integer biner; @for(arcs(i,j):@bin(arc_usage(i,j))); data: node1, node2, commodity, supply, fixed_cost, shipping_cost = @ole('F:\Skripsi\Draft\ImplementasiData.xls'); enddata end
37
Lampiran 7 Hasil Komputasi Program pada LINGO 8.0 untuk Masalah Desain Network Takberkapasitas
Global optimal solution found at iteration: Objective value:
Variable Value FIXED_COST( E, E) 0.000000 FIXED_COST( E, F) 1593.000 …………………………………………………………… FIXED_COST( W, T) 4095.000 ARC_USAGE( E, Q) 1.000000 ARC_USAGE( F, P) 1.000000 ARC_USAGE( G, H) 1.000000 ARC_USAGE( H, P) 1.000000 ARC_USAGE( H, W) 1.000000 ARC_USAGE( L, H) 1.000000 ARC_USAGE( L, M) 1.000000 ARC_USAGE( M, O) 1.000000 ARC_USAGE( O, T) 1.000000 ARC_USAGE( P, O) 1.000000 ARC_USAGE( P, R) 1.000000 1.000000 ARC_USAGE( Q, L) ARC_USAGE( R, F) 1.000000 ARC_USAGE( R, S) 1.000000 ARC_USAGE( S, H) 1.000000 ARC_USAGE( T, W) 1.000000 ARC_USAGE( W, E) 1.000000 ARC_USAGE( W, G) 1.000000 SUPPLY( E, 4) 1.000000 SUPPLY( E, 7) -1.000000 SUPPLY( E, 14) 1.000000 SUPPLY( E, 18) -1.000000 SUPPLY( F, 3) -1.000000 SUPPLY( F, 9) 1.000000 SUPPLY( F, 16) 1.000000 SUPPLY( F, 20) -1.000000 SUPPLY( G, 5) 1.000000 SUPPLY( G, 11) -1.000000 SUPPLY( G, 18) 1.000000 SUPPLY( G, 26) -1.000000 SUPPLY( H, 2) 1.000000 SUPPLY( H, 6) -1.000000 SUPPLY( H, 16) -1.000000 SUPPLY( H, 20) 1.000000 SUPPLY( L, 3) 1.000000 SUPPLY( L, 10) -1.000000 SUPPLY( L, 22) 1.000000 SUPPLY( L, 24) -1.000000 SUPPLY( M, 5) -1.000000 SUPPLY( M, 8) 1.000000 SUPPLY( M, 14) -1.000000 SUPPLY( M, 24) 1.000000 SUPPLY( O, 6) 1.000000 SUPPLY( O, 13) -1.000000
56191 12516.00
Reduced Cost 0.000000 0.000000 0.000000 1062.000 282.0000 267.0000 146.0000 506.0000 272.0000 1090.000 112.0000 1161.000 198.0000 511.0000 491.0000 552.0000 197.0000 389.0000 534.0000 215.0000 477.0000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000
38
SUPPLY( O, 22) -1.000000 SUPPLY( O, 26) 1.000000 SUPPLY( P, 1) 1.000000 SUPPLY( P, 9) -1.000000 SUPPLY( P, 15) 1.000000 SUPPLY( P, 25) -1.000000 SUPPLY( Q, 12) -1.000000 SUPPLY( Q, 13) 1.000000 SUPPLY( Q, 19) 1.000000 SUPPLY( Q, 23) -1.000000 SUPPLY( R, 1) -1.000000 SUPPLY( R, 7) 1.000000 SUPPLY( R, 17) 1.000000 SUPPLY( R, 21) -1.000000 SUPPLY( S, 4) -1.000000 SUPPLY( S, 11) 1.000000 SUPPLY( S, 19) -1.000000 SUPPLY( S, 23) 1.000000 SUPPLY( T, 8) -1.000000 SUPPLY( T, 12) 1.000000 SUPPLY( T, 17) -1.000000 SUPPLY( T, 25) 1.000000 SUPPLY( W, 2) -1.000000 SUPPLY( W, 10) 1.000000 SUPPLY( W, 15) -1.000000 SUPPLY( W, 21) 1.000000 SHIPPING_COST( E, F, 1) 64.00000 ………………………………………………………… SHIPPING_COST( W, T, 26) 13.00000 FLOW( E, Q, 4) 1.000000 FLOW( E, Q, 5) 1.000000 FLOW( E, Q, 10) 1.000000 FLOW( E, Q, 12) 1.000000 FLOW( E, Q, 14) 1.000000 FLOW( E, Q, 23) 1.000000 FLOW( E, Q, 24) 1.000000 FLOW( F, P, 9) 1.000000 FLOW( F, P, 16) 1.000000 FLOW( F, P, 17) 1.000000 FLOW( G, H, 5) 1.000000 FLOW( G, H, 6) 1.000000 FLOW( G, H, 18) 1.000000 FLOW( G, H, 21) 1.000000 FLOW( G, H, 25) 1.000000 FLOW( H, P, 3) 1.000000 FLOW( H, P, 4) 1.000000 FLOW( H, P, 19) 1.000000 FLOW( H, P, 20) 1.000000 FLOW( H, P, 21) 1.000000 FLOW( H, P, 25) 1.000000 FLOW( H, W, 2) 1.000000 FLOW( H, W, 5) 1.000000 FLOW( H, W, 7) 1.000000 FLOW( H, W, 11) 1.000000 FLOW( H, W, 18) 1.000000 FLOW( H, W, 23) 1.000000 FLOW( L, H, 3) 1.000000 FLOW( L, H, 4) 1.000000 FLOW( L, H, 19) 1.000000
0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000
39
FLOW( L, M, 5) FLOW( L, M, 13) FLOW( L, M, 14) FLOW( L, M, 22) FLOW( M, O, 8) FLOW( M, O, 13) FLOW( M, O, 22) FLOW( M, O, 24) FLOW( O, T, 6) FLOW( O, T, 8) FLOW( O, T, 15) FLOW( O, T, 17) FLOW( O, T, 24) FLOW( O, T, 26) FLOW( P, O, 15) FLOW( P, O, 17) FLOW( P, R, 1) FLOW( P, R, 3) FLOW( P, R, 4) FLOW( P, R, 16) FLOW( P, R, 19) FLOW( P, R, 20) FLOW( P, R, 21) FLOW( Q, L, 4) FLOW( Q, L, 5) FLOW( Q, L, 10) FLOW( Q, L, 13) FLOW( Q, L, 14) FLOW( Q, L, 19) FLOW( Q, L, 24) FLOW( R, F, 3) FLOW( R, F, 17) FLOW( R, F, 20) FLOW( R, S, 4) FLOW( R, S, 7) FLOW( R, S, 16) FLOW( R, S, 19) FLOW( S, H, 7) FLOW( S, H, 11) FLOW( S, H, 16) FLOW( S, H, 23) FLOW( T, W, 6) FLOW( T, W, 12) FLOW( T, W, 15) FLOW( T, W, 24) FLOW( T, W, 25) FLOW( T, W, 26) FLOW( W, E, 5) FLOW( W, E, 7) FLOW( W, E, 10) FLOW( W, E, 12) FLOW( W, E, 18) FLOW( W, E, 23) FLOW( W, E, 24) FLOW( W, G, 6) FLOW( W, G, 11) FLOW( W, G, 21) FLOW( W, G, 25) FLOW( W, G, 26)
1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000 1.000000
0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000
40
Row Slack or Surplus 1 12516.00 2 0.000000 3 0.000000 4 0.000000 5 0.000000 6 0.000000 7 0.000000 8 0.000000 9 0.000000 10 0.000000 11 0.000000 12 0.000000 13 0.000000 14 0.000000 15 0.000000 16 0.000000 17 0.000000 18 0.000000 19 0.000000 20 0.000000 21 0.000000 22 0.000000 23 0.000000 24 0.000000 25 0.000000 26 0.000000 27 0.000000 28 0.000000 29 0.000000 30 0.000000 31 0.000000 32 0.000000 ……………………………………………… 9105 0.000000 9106 0.000000 9107 0.000000 9108 0.000000 9109 0.000000 9110 0.000000 9111 0.000000 9112 0.000000 9113 0.000000 9114 0.000000 9115 0.000000 9116 0.000000 9117 0.000000 9118 0.000000 9119 0.000000 9120 0.000000 9121 0.000000 9122 0.000000 9123 0.000000 9124 0.000000 9125 0.000000 9126 0.000000 9127 0.000000
Dual Price -1.000000 1.000000 -12.00000 19.00000 -204.0000 72.00000 124.0000 33.00000 16.00000 0.000000 45.00000 -20.00000 -2.000000 9.000000 -6.000000 -77.00000 0.000000 23.00000 124.0000 8.000000 -23.00000 -75.00000 -35.00000 68.00000 23.00000 -6.000000 16.00000 8.000000 -13.00000 138.0000 -19.00000 64.00000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000
