ALGORITMA DOUBLE SCALING UNTUK MENYELESAIKAN PERMASALAHAN MINIMUM COST FLOW DAN IMPLEMENTASINYA PADA PROGRAM KOMPUTER Agustina Ardhini 1, Sapti Wahyuningsih 2, Darmawan Satyananda 3 Jurusan Matematika, Universitas Negeri Malang Email :
[email protected] ABSTRAK : Penelitian ini bertujuan mengetahui penerapan algoritma double scaling untuk menyelesaikan permasalahan minimum cost flow dan implementasinya pada program komputer. Algoritma double scaling mengadopsi langkah-langkah pada algoritma cost scaling dengan mengganti prosedur improve approximation awal dengan prosedur baru yang memuat fase -scaling yang merupakan bagian dari algoritma capacity scaling . Perbedaan algoritma double scaling dengan algoritma cost scaling terletak pada fase improve approximation. Adapun perbedaan algoritma double scaling dengan algoritma capacity scaling terletak pada prosedur pemilihan lintasan yang akan dialiri flow pada fase -scaling. Pada penelitian ini dibuat program Delphi untuk mengimplementasikan prosedur pencarian solusi minimum cost flow yang memuat prosedur retreat dan advance untuk menentukan lintasan admissible. Program yang dikembangkan hanya dapat digunakan untuk menyelesaikan permasalahan minimum cost flow hingga 79 titik. Adapun untuk permasalahan minimum cost flow dengan jumlah titik lebih dari 79, tidak dapat diselesaikan dengan menggunakan program ini. Kata Kunci: Algoritma double scaling, minimum cost flow, lintasan admissible ABSTRACT : This study aims to determine application of double scaling algorithm to solve minimum cost flow problem and its implementation in a computer program. Double scaling algorithm adopts cost scaling algorithm steps by replacing improve approximation procedure with a new procedure that includes Δ-scaling phase, which is part of the capacity scaling algorithm. Differences of double scaling algorithm with cost scaling algorithm lies in the improve approximation phase and difference of double scaling algorithm with capacity scaling algorithm lies in the path selection procedure P which will be fed flow on Δ-scaling phase. In this thesis it was made Delphi program to implement procedures of searching solution of minimum cost flow problem that includes retreat and advance procedures for determining the admissible path. The program was simulated on example until 79 points. However, for the minimum cost flow problem with the number of points over 79, can not be solved by using this program. Key Words: Double scaling algorithm, minimum cost flow, admissible path
Permasalahan minimum cost flow merupakan salah satu contoh aplikasi permasalahan network flow dalam kehidupan sehari-hari. Permasalahan minimum cost flow merupakan permasalahan untuk mencari biaya minimum dalam mengirimkan suatu barang/objek dari suatu titik yang disebut dengan titik supply (sumber) ke titik lain yang disebut dengan titik demand (tujuan). Menurut Ahuja 1. Mahasiswa Jurusan Matematika FMIPA Universitas Negeri Malang 2. Dosen Jurusan Matematika FMIPA Universitas Negeri Malang 3. Dosen Jurusan Matematika FMIPA Universitas Negeri Malang
1
(1993), terdapat beberapa algoritma untuk menyelesaikan permasalahan minimum cost flow diantaranya adalah algoritma penghapusan sikel, algoritma lintasan terpendek berulang, algoritma jaringan simpleks, algoritma out of kilter, algoritma primal dual, algoritma relaksasi, algoritma cost scaling, algoritma capacity scaling, algoritma repeated capacity scaling, algoritma enhanced capacity scaling, dan algoritma double scaling. Beberapa penelitian yang telah membahas permasalahan minimum cost flow diantaranya yaitu “ Penerapan Algoritma Cost Scaling pada Permasalahan Minimum Cost Flow dan Implementasinya pada Program” oleh Prabowo (2012) dan “Algoritma Capacity Scaling dalam Menyelesaikan Minimum Cost Flow Problem dan Implementasi Programnya” oleh Saputri (2013). Pada algoritma cost scaling pencarian solusi dilakukan dengan melakukan pencarian sisi admissible dari titik dengan imbalance lebih dari nol ke titik lain pada jaringan sedangkan pada algoritma capacity scaling pencarian solusi dilakukan dengan melakukan pencarian lintasan terpendek dari titik dengan imbalance lebih dari atau sama dengan ke titik dengan imbalance kurang dari . Seperti disebutkan sebelumnya, untuk menyelesaikan permasalahan minimum cost flow juga dapat menggunakan algoritma double scaling. Algoritma double scaling merupakan perpaduan dari algoritma cost scaling dan algoritma capacity scaling. Algoritma double scaling pada minimum cost flow melakukan pencarian lintasan admissible pada jaringan kemudian mengirimkan supply sebesar pada lintasan tersebut. Algoritma double scaling dapat menghasilkan solusi optimum karena pengiriman supply sebesar dan pereduksian dengan faktor 2 mengakibatkan ketika nilai terkecil sama dengan 1 akan dicapai kondisi optimum. Di sisi lain, penyelesaian permasalahan minimum cost flow dengan algoritma double scaling bila dikerjakan secara manual memuat langkah-langkah yang berulang-ulang dengan langkah yang sama. Sehingga untuk mempermudah proses tersebut dibutuhkan alat bantu berupa program. HASIL YANG DIHARAPKAN Hasil yang diharapkan pada penelitian ini adalah untuk mengetahui (1) penerapan algoritma double scaling untuk menyelesaikan permasalahan minimum cost flow , (2) analisa proses dan hasil penyelesaian minimum cost flow dengan algoritma double scaling dan algoritma pembanding, (3) implementasi program untuk menyelesaikan permasalahan minimum cost flow dengan algoritma double scaling . PEMBAHASAN Pada penulisan ini definisi yang berhubungan dengan digraph, jalan, lintasan, digraph terhubung, digraph berbobot, dan jaringan diambil dari Rosen (2000) dan Wilson (1990). Definisi-definisi tersebut menunjang pembahasan penyelesaian minimum cost flow dengan algoritma double scaling. Algoritma double scaling menggabungkan algoritma cost scaling dengan algoritma capacity scaling. Algoritma double scaling mengadopsi langkahlangkah pada algoritma cost scaling dengan mengganti prosedur improve approximation awal dengan prosedur baru yang memuat fase -scaling yang merupakan bagian dari algoritma capacity scaling . Pada fase -scaling dilakukan
2
identifikasi lintasan admissible dari titik dengan nilai node imbalances kurang dari atau sama dengan ke titik dengan nilai node imbalances kurang dari nol, serta mengalirkan supply sebesar unit ke lintasan tersebut. Ketika nilai node imbalances semua titik pada digraph kurang dari , maka lama direduksi dengan faktor 2 menjadi dan memulai fase -scaling yang baru. Langkah-langkah penyelesaian permasalahan minimum cost flow dengan algoritma double scaling diperlukan langkah-langkah berikut : 1. Fase Inisialisasi Langkah-langkah yang dilakukan pada fase inisialisasi yaitu menggambarkan keadaan awal dalam bentuk jaringan berarah. Langkah-langkahnya yaitu sebagai berikut . - Menggambarkan keadaan awal dengan menggambarkan beberapa titik yang terdapat pada permasalahan. Masing-masing titik dihubungkan dengan dengan sisi berarah (i,j) yang menunjukkan adanya jalan untuk aliran dari titik i ke titik j. Setiap sisi (i,j) mempunyai dua bobot yang dinotasikan dengan dan . - Menuliskan dari masing-masing titik dengan dengan ketentuan . Karena pada algoritma double scaling nilai awal , maka - Menuliskan dan untuk masing-masing sisi di G. Karena pada algoritma double scaling nilai awal dan nilai awal , maka . Selanjutnya menuliskan pada setiap sisi G. - Menentukan nilai . Periksa apakah , jika memenuhi lanjut ke langkah
-
2. -
-
selanjutnya, jika tidak direduksi menjadi kemudian lakukan pemeriksaan kembali. Menentukan dan . Selanjutnya memperbarui nilai dengan ketentuan dan memperbarui untuk setiap titik yang terhubung langsung dengan titik j. Selanjutnya menuliskan kembali pada pada setiap sisi G. Menentukan . Menentukan titik aktif. Jika pada digraph terdapat titik aktif maka lakukan langkah 2, jika pada digraph tidak terdapat titik aktif, iterasi berhenti. Fase -scaling : penentuan lintasan admissible . Menentukan yaitu himpunan titik dengan . Jika , direduksi menjadi dan kembali menentukan Jika lanjut menentukan lintasan admissible . Menentukan lintasan admissible Pilih titik , tentukan lintasan admissible P dari titik ke titik dengan . Jika titik mempunyai sisi admissible ,lakukan prosedur advance (i) , jika titik tidak memiliki sisi admissible lakukan prosedur retreat (i). Advance (i) Jika titik i memiliki sisi admissible, tambahkan sisi ke P , lanjutkan menentukan sisi admissible dari titik sampai .
3
Retreat (i) Jika titik tidak memiliki sisi admissible , perbarui nilai menjadi . Jika hapus sisi dari P (jika maka ) dan lanjutkan menentukan sisi admissible dari titik . - Jika telah diperoleh lintasan admissible P, lakukan pengiriman sebanyak unit ke lintasan P. Selanjutnya perbarui jaringan sisa dengan mengganti sisi dengan dua sisi dan dengan bobot masing-masing sisi yaitu sisi memiliki bobot dan , sisi memiliki bobot dan . Serta perbarui untuk setiap sisi pada lintasan P dengan ketentuan dan . 3. Fase Perulangan Pada fase ini dillakukan perulangan langkah 2 di atas hingga semua titik teraliri flow. Jika nilai node imbalance semua titik sama dengan nol, maka perulangan dinyatakan selesai dan lanjut ke langkah 4. 4. Fase Solusi Optimum Jika nilai node imbalance semua titik pada jaringan sisa sama dengan nol, maka langkah selanjutnya adalah menggambarkan digraph solusi optimum dengan bobot masing-masing sisinya adalah dengan . Selanjutnya menghitung nilai dengan ketentuan . Nilai yang diperoleh merupakan total biaya minimum dari permasalahan awal. Pada penulisan ini, algoritma double scaling diterapkan pada beberapa contoh permasalahan minimum cost flow diantaranya yaitu pada contoh dengan empat titik, lima titik, enam titik, dan delapan titik. Solusi yang diperoleh kemudian dibandingkan dengan solusi yang diperoleh dengan algoritma cost scaling dan algoritma capacity scaling. Dari perbandingan tersebut diperoleh bahwa algoritma double scaling, algoritma cost scaling, dan algoritma capacity scaling menghasilkan biaya total minimum dan rute pengiriman supply yang sama Adapun perbedaan algoritma double scaling dengan algoritma cost scaling terletak pada fase improve approximation. Fase improve approximation pada algoritma cost scaling menggunakan fase push relabel dengan pengiriman flow ke sisi admissible sebesar minimum dari node imbalance titik dan kapasitas sisa sisi sedangkan fase improve approximation pada algoritma double scaling menggunakan fase -scaling dengan pengiriman flow ke sisi-sisi admissible sebesar Adapun perbedaan algoritma double scaling dengan algoritma capacity scaling terletak pada prosedur pemilihan lintasan yang akan dialiri flow pada fase -scaling. Pada algoritma capacity scaling, prosedur pemilihan lintasan menggunakan algoritma-algoritma pada shortest path, sedangkan pada algoritma double scaling menggunakan konsep lintasan admissible, yaitu lintasan yang terdiri dari sisi-sisi admissible.. Implementasi program untuk menyelesaikan permasalahan minimum cost flow dengan menggunakan algoritma double scaling dibuat dengan bantuan program Delphi 7 dengan mengikuti algoritma sebagai berikut (Ahuja,1993:374).
4
Begin π :=0 and ε := C let x any feasible flow while ε do begin Improve approximation *) ε:= ; end; x is optimal flow end; *) Procedur Improve approximation Begin Set x:=0 and compute node imbalances; π (j):= π (j)+ ε , ; While network contains an active node do begin S( )= While S( ) do begin (scaling phase) Select a node k from S( ); Determine an admissible path P from node k to some node l with e(l) < 0 ; augment units of flow on path P and update x and ; end; end; end; Adapun prosedur untuk mengidentifikasi lintasan admissible adalah sebagai berikut (Ahuja, 1993 : 374) . Advance (i). If the residual network contains an admissible arc (i,j), add to P and set pred (j):= i. If stop. Retreat (i). If the residual network does not contains an admissible arc (i,j), update to . If , remove the arc from P so that becomes its new tip. Solusi permasalahan minimum cost flow dengan algoritma double scaling dengan bantuan program yang dikembangkan ditunjukkan pada gambar berikut.
5
Program yang dikembangkan, selain disimulasikan pada empat titik, lima titik, enam titik dan delapan titik, juga dapat digunakan untuk menyelesaikan permasalahan minimum cost flow pada 40 titik, 50 titik, 60 titik, 70 titik, 75 titik, 78 titik dan 79 titik. Sedangkan untuk permasalahan minimum cost flow pada jaringan dengan banyak titik lebih dari 79, permasalahan tersebut tidak dapat diselesaikan dengan program ini. KESIMPULAN 1. Dalam mencari solusi minimum cost flow, algoritma double scaling melakukan pencarian lintasan yang disebut dengan lintasan admissible. Lintasan admissible, yaitu lintasan yang semua sisinya merupakan sisi admissible . Sisi admissible merupakan sisi dengan yang memenuhi kondisi . Penerapan algoritma double scaling pada permasalahan minimum cost flow diterapkan pada beberapa contoh yaitu contoh pada empat titik, contoh pada lima titik, contoh pada enam titik, dan contoh pada delapan titik. Setelah permasalahan tersebut diselesaikan dengan algoritma double scaling diperoleh solusi dengan biaya optimum dan rute yang sama dengan penyelesaian menggunakan algoritma pembanding. 2. Algoritma double scaling menggabungkan algoritma cost scaling dengan algoritma capacity scaling. Algoritma double scaling mengadopsi langkahlangkah pada algoritma cost scaling dengan mengganti prosedur improve approximation awal dengan prosedur baru yang memuat fase -scaling yang merupakan bagian dari algoritma capacity scaling . Perbedaan algoritma double scaling dengan algoritma cost scaling terletak pada fase improve approximation. Adapun perbedaan algoritma double scaling dengan algoritma capacity scaling terletak pada prosedur pemilihan lintasan yang akan dialiri flow pada fase -scaling. 3. Pencarian minimum cost flow dapat dilakukan dengan menggunakan program program Delphi dengan mengimplementasikan prosedur pencarian solusi minimum cost flow yang memuat prosedur retreat dan advance untuk menentukan lintasan admissible. Program yang dikembangkan, selain disimulasikan pada empat titik, lima titik, enam titik dan delapan titik, juga
6
dapat digunakan untuk menyelesaikan permasalahan minimum cost flow pada 40 titik, 50 titik, 60 titik, 70 titik, 75 titik, 78 titik dan 79 titik. Adapun untuk permasalahan minimum cost flow dengan jumlah titik lebih dari 79, tidak dapat diselesaikan dengan menggunakan program ini. DAFTAR RUJUKAN Ahuja, Ravindra, dkk. 1993. Network Flows Theory, Algorithms, and Applications. New Jersey : Prentice-Hall, Inc. Prabowo, Fajar. 2012. Penerapan Algoritma Cost Scaling pada Permasalahan Minimum Cost Flow dan Implementasinya pada Program. Skripsi tidak diterbitkan. Malang: Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Negeri Malang. Rosen, H., Kenneth.2000. Handbook of Discrete and Combinatorial Mathematics. Washington, DC: CRC Press. Saputri, Reni Dian. 2013. Algoritma Capacity Scaling dalam Menyelesaikan Minimum Cost Flow dan Aplikasi Programnya. Skripsi tidak diterbitkan. Malang: Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Negeri Malang. Wilson, Robin J. 1990. Graph An Introduction Approach. Canada : Wiley.
7
