PENERAPAN ALGORITMA COST SCALING PADA PERMASALAHAN MINIMUM COST FLOW DAN IMPLEMENTASINYA PADA PROGRAM Fajar Prabowo Universitas Negeri Malang E-mail:
[email protected] Pembimbing: (I) Dra. Sapti Wahyuningsih, M.si, (II) Dra. Mimiep S. Madja, M. Kom Abstrak: Tujuan penulisanartikel ini adalah mengkaji penerapan algoritma cost scaling dalam permasalahan minimum cost flow dan mengaplikasikannya dalam program. Penelitian dilakukan dengan mengkaji penerapan algoritma cost scaling dalam penyelesaian masalah minimum cost flow, dan membandingkan hasil penyelesaian tersebut dengan menggunakan algoritma lintasan terpendek berulang.Kemudian dibuat sebuah program dengan bantuan Delphi 7. Hasil yang diperoleh adalah penyelesaian masalah minimum cost flow dengan menggunakan algoritma cost scaling sama dengan penyelesaian menggunakan algoritma lintasan terpendek berulang. Sedangkan hasil penyelesaian masalah minimum cost flow menggunakan bantuan program cost scaling, adalah sama dengan hasil yang diperoleh menggunakan program Giden. Kata Kunci : minimum cost flow, algoritma cost scaling, program Abstract: The purpose of this article is to examine the implementation of the cost scaling algorithm in the minimum cost flow problem, and apply it in the program. The study was conducted by reviewing the implementation of the cost scaling algorithm in solving the minimum cost flow problem, and compare the results of the settlement by using the sucsecive shortest path algorithm. Then created a program with the help of Delphi 7. The result is a minimum cost flow problem solving using cost scaling algorithm with completion using the shortest path algorithm repeatedly. While the results of the completion of the minimum cost flow problem using the help of the program cost scaling, is the same as the results obtained using the program Giden. Keywords:minimum cost flow, cost scaling algorithm, program
Permasalahanpencarian biaya minimum yang digunakan untuk mendistribusikan barang dari produsen menuju konsumen, di dalam teori graph dapat dimodelkan dengan minimum costflow.Salah satu algorima yang bisa digunakan untuk menyelesaikan permasalahan pada minimum cost flow adalah algoritma cost scaling. Algoritma cost scaling mengikuti kajian yang diadaptasi dari buku Network Flow yang ditulis oleh Ravindra K. Ahujja (1993). Salah satu keunggulan algoritma ini adalah mudah untuk diterapkan pada permasalahan minimum cost flow karena iterasinya mudah dipahami dan tidak terlalu banyak. Agar penyelesaian permasalahan minimum cost flow dengan menggunakan algoritma cost salling secara lebih efisien, akan dibuat program dengan bantuan program Delphi. Penulisan artikel ini secara khusus ditujukan untuk mengetahui langkah– langkah pencarian minimum cost flow dengan menggunakan algoritma cost scalling kemudianmenerapkannyauntuk menyelesaikan permasalahan minimum cost flow. Selain itu juga untuk mengetahui perbedaan hasil penyelesaian minimum cost flow antara algoritma cost scalling dengan algoritma lintasan terpendek berulang serta menyusun program untuk menyelesaikan minimum cost flow dengan algoritma cost scalling. Artikel
Halaman1
Untuk menunjang penulisan dibutuhkan beberapa kajian teori antara lain digraph berbobot, jaringan, minimum cost flow, dan algoritma cost scaling.Wilson (1989: 132) mendefinisikan, Suatu digraph , disebut sebuah digraph berbobot (weight graph), apabila terdapat sebuah fungsi bobot bernilai real pada himpunan , W: A R disebut bobot-bobot sisi , untuk semua anggota . Digraph berbobot tersebut dapat dinyatakan sebagai , , .
Digrap berbobot (weight digraph).
Jaringan (dilambangkan N) adalah digraph sederhana, berbobot, jika memenuhi: • Satu titik yang merupakan titik sumber, tidak memiliki sisi masuk • Satu titik yang merupakan titik tujuan, tidak memiliki sisi keluar Muatan sisi i,j disebut kapasitas sisi i,j , dilambangkan cij dengan cij adalah bilangan bulat non negatif. Minimum cost flow adalah suatu graph G V,E yang merupakan jaringan terhubung dengan himpunan titik V dan himpunan sisi berarah E yang masingmasing sisi (i,j) ∈ E mempunyai costcijdan kapasitas muatan uij ≥ 0. Misal n = V dan m = E (Rosen : 630). Algoritma cost scaling memperlakukan ε sebagai parameter dan secara iterasi diproses untuk memperoleh ε-optimal flow untuk nilai yang lebih kecil dari ε. Awalnya, ε = C dan setiap aliran feasibel adalah ε-optimal. Algoritma kemudian melakukan fase cost scalingsecara berulang kali dengan menerapkanprosedur improve-approximation yang mengubah aliran ε-optimal menjadi -optimal flow. Setelah melakukan 1 + log (nC) tahap l cost scaling, dan kemudian algoritmaberakhir dengan aliran yang optimal (Ahuja : 364). Hasil yang Diharapkan Pada tahap ini dapat mengkaji beberapa prosedur inti yang digunakan untuk menyelesaikan minimum costflowdiantaranya adalah prosedur improveapproximation dan prosedur push/relabel sehingga dapat diterapkan dalam contoh permasalahan minimum costflow.Selanjutnya dapat mengkaji perbedaan penyelesaian minimum costflowdengan menggunakan algoritma cost scaling dan menggunakan algritma lintasan terpendek berulang. Untuk mempermudah menyelesaikan permasalahan minimum cost fow dengan menggunakan algoritma cost scaling, selanjutnya cukup disebut program cost scaling, dibuat program dengan bantuan program Borland Delphi 7. Pada tahap ini disusun syntax program dan penyusunan flowchart. Artikel
Halaman2
Pembahasan Untuk menyelesaikan permasalahan minimum cost flow dengan algoritma cost scaling diperlukan langkah-langkah berikut. Inisialisasi yaitu langkah yang menggambarkan keadaan awal dalam bentuk jaringan berarah. Penggambaran keadaan awal dimulai dengan menggambarkan banyaknya titik yang terdapat di dalam permasalahan. Masing-masing sisi dihubungkan dengan sisi berarah , yang menunjukkan adanya jalan untuk aliran dari titik i ke titik j. Setiap sisi , yang merupakan biaya yang mempunyai dua bobot yang disimbolkan diperlukan untuk mengalirkan suplai dari titik i ke titik j dan ! adalah batas maksimum suplai yang dapat dialirkan dari titik i ke titik j. Menuliskan bobot/suplai masing-masing titik yang disimbolkan dengan b(i) dengan ketentuan apabila b(i) > 0 maka titik i adalah titik pengirim, apabila b(i) = 0 maka titik i adalah titik perantara, dan apabila b(i) < 0 maka titik i adalah titik penerima. Setelah proses inisialisasi selesai, tentukan nilai ε yang diperoleh dari biaya terbesar yang terdapat pada permasalahan awal. Menentukannode imbalance/titik kesetimbangan dari masing-masing titik yang disimbolkan dengan dengan ketentuan " # ∑& : , ' (,() * % + ∑& : , ' (,() * % , " adalahsuplai dari titik i.Pada algoritma cost scaling nilai awal %) , 0, maka " dan ! ,/ , ' . . Menentukan biaya tereduksi ( 0 + 1 # 1 ) pada masing-masing sisi pada digraph G. Karena pada algoritma cost scaling nilai awal 1 0, 0 0 / ' , sehingga , / , ' . Kemudian menuliskan , . pada setiap sisi di G. Pilih titik aktif yang terdapat pada jaringan sisa. Titik i dikatakan titik aktif apabila e(i) > 0. Menentukan sisi admisibel yang berpangkal pada titik aktif yang telah dipilih. Sisi admisibel ditentukan dengan mengecek setiap sisi pada jaringan sisa yang berpangkal pada titik aktif yang telah dipilih, yaitu sisi yang memiliki 2 biaya tereduksi dan memenuhi kondisi + 3 0 0, / , ' . Apabila pada jaringan sisa tidak terdapat sisi admisibel yang berpangkal pada titik aktif yang telah dipilih, lakukan pelabelan nilai potensial titik pada titik 2 aktif tersebut dengan ketentuan 1 5678 1 96:6 # . Lakukan pelabelan biaya tereduksi pada sisi yang berpangkal pada titik aktif yang telah dipilih. Lakukan langkah 6 apabila sisi admisibel masih belum diperoleh. Setelah sisi admisibel yang berpangkal pada titik aktif diperoleh, tentukan nilai δ dengan cara δ = Min{e(i), rij}. Lakukan proses pengiriman suplai sebanyak δ unit pada sisi admisibel, misalkan sisi admisibel yang dipilih adalah sisi (i,j), yaitu dengan cara e(i)baru = e(i)lama – δ, e(j)baru = e(j)lama + δ. Mengganti sisi (i,j) dengan dua sisi (i,j) dan sisi (j,i) dengan bobot masing-masing sisi adalah sebagai berikut : sisi (i,j) Artikel
Halaman3
0 memiliki bobot 0 dan rij = rij – δ, sedangkan sisi (j,i) memiliki bobot 0 0 + dan rji = δ Hapus sisi yang memiliki kapasitas sisa sama dengan nol (rij=0). Lakukan pengulangan pada langkah 10 sampai diperoleh e(i) = 0, / ' . Menggambarkan digraph solusi optimum dengan aliran dan % . , serta mencari ; ∑ % . Perbedaan langkah-langkah algoritma cost scaling dengan algoritma lintasan terpendek berulang terdapat pada penentuan nilai titik potensial dan penentuan suplai yang akan dialirkan dalam jaringan. Nilai titik potensial (π) pada 2 algoritma cost scaling ditentukan dengan cara 1 1 # sedangkan suplai (δ) yang akan dialirkan dalam jaringan ditentukan dengan cara < = >& ,. . Nilai titik potensial (π) pada algoritma lintasan terpendek berulangditentukan dengan cara 1 1 + ? # ? @ sedangkan suplai (δ) yang akan dialirkan dalam jaringan ditentukan dengan cara < min& C , + @ , minD. , , ' EF*. Implementasi program penyelesaian permasalahan minimum cost flow dengan menggunakan algoritma cost scaling dibuat dengan bantuan program Delphi 7 dan mengikuti syntax algoritma sebagai berikut: algorithm cost scaling; begin π : = 0 andε : = C; let x be any feasible flow; while G do begin improve-approximation(ε, x, π);
2
;
end; x is an optimal flow for the minimum cost flow problem; end; procedure improve-approximation(ε, x, π); begin for every arc (i, j) ∊ A do if 0 K 0 then % : = 0 else if 0 0 then % , ! ; compute node imbalances; while the network contains an active node do begin select an active node i; push/relabel (i ); end; end; procedure push/relabel(i); begin if G(x) contains an admissible arc (i, j) then Artikel
Halaman4
push δ : = min{e(i), . } units of flow from node i to node j; 2 else π(i) : = π(i) + ; end; (Williamson, 2007: 14) Tampilan dari program cost scaling yang dihasilkan adalah seperti berikut :
Simulasi penyelesaian masalah minimum cost flow dikerjakan dengan menggunakan program cost scaling dan program Giden. Dalam simulasi tersebut diperoleh hasil yang sama. Penutup Berdasarkan pembahasan sebelumnya, beberapa kesimpulan yang diperoleh diantaranya adalah proses penyelesaian masalah minimum cost flow dengan algoritma cost scalling dilakukan melalui beberapa prosedur inti yaitu prosedur improve-approximation dan prosedur push/relabel.Nilai titik potensial (π) pada 2 algoritma cost scaling ditentukan dengan cara 1 1 # sedangkan suplai (δ) yang akan dialirkan dalam jaringan ditentukan dengan cara < = >& ,. . Nilai titik potensial (π) pada algoritma lintasan terpendek berulangditentukan dengan cara 1 1 + ? # ? @ sedangkan suplai (δ) yang akan dialirkan dalam jaringan ditentukan dengan cara < min& C , + @ , minD. , , ' E*.Simulasi penyelesaian masalah minimum cost flow dikerjakan dengan menggunakan program cost scaling dan program Giden. Dalam simulasi tersebut diperoleh hasil yang sama. Dari pembahasandi atas, pembaca diharapkanmenganalisis penerapan algoritma cost scalling pada permasalahan minimum cot flowapabila terdapat lebih dari satu sisi admisibel dan bangun suatu teorema. Kemudian untuk penulisan berikutnya adanya pembuktian beberapa teorema yang mendukung keeksistensian algoritma cost scalling pada permasalahan minimum cost flow.
Artikel
Halaman5
Daftar Rujukan Ahuja, Ravindra, dkk. 1993. Network Flows Theory, Algoritmhs, and Applications. New Jersey : Prentice-Hall, Inc. Rosen, H., Kenneth. Handbook of Discrete and Combinatorial Mathematics. Washington, DC: CRC Press. Willson, Robin J. 1990. Graph An Introduction Approach. Canada : Wiley. Williamson, David. 2007. Lecture 14: Network Flow. Jurnal online diakses tanggal 23 Maret 2012.
Artikel
Halaman6
