ALGORITMA CAPACITY SCALING DALAM MENYELESAIKAN MINIMUM COST FLOW PROBLEM DAN IMPLEMENTASI PROGRAMNYA Reni Dian Saputri, Sapti Wahyuningsih*), Darmawan Satyananda*) Universitas Negeri Malang E-mail:
[email protected] ABSTRAK: Minimum cost flow problem adalah permasalahan menentukan biaya minimum yang digunakan untuk mendistribusikan barang dari produsen atau distributor ke konsumen. Algoritma capacity scaling merupakan salah satu algoritma yang dapat digunakan dalam menyelesaikan permasalahan minimum cost flow. Ide dari algoritma capacity scaling ini adalah dengan menambahkan aliran sepanjang lintasan yang memiliki kapasitas sisa cukup besar yang telah ditetapkan. Untuk mengatasi permasalahan jaringan yang memiliki banyak titik, maka dibuat program algoritma capacity scaling menggunakan Delphi 7. Program tersebut dapat menentukan biaya minimum yang diperlukan secara cepat dan mudah. Kata Kunci: minimum cost flow, capacity scaling, algoritma capacity scaling
Banyak sekali manfaat yang didapatkan jika mempelajari teori graph, terutama untuk kehidupan sehari-hari. Salah satu model yang banyak dipakai dalam menyelesaikan masalah dalam kehidupan sehari-hari adalah network flow. Pada dasarnya network flow membahas optimasi yaitu usaha untuk memaksimumkan atau meminimumkan suatu jaringan dengan syarat-syarat tertentu. Pada permasalahan minimum cost flow ini, jaringan akan meminimumkan biaya pendistribusian barang pada suatu jaringan. Pada salah satu jurnal berjudul “A Capacity Scaling for The Constrained Maximum Flow Problem” yang ditulis oleh Ahuja dan Orlin (1993) menyebutkan bahwa algoritma capacity scaling dapat digunakan dalam menyelesaikan permasalahan maximum flow. Berdasarkan dari jurnal tersebut, maka algoritma capacity scaling akan dikembangkan pada penyelesaian permasalahan minimum cost flow. Untuk mengatasi permasalahan jaringan yang memiliki banyak titik, maka dibuat program algoritma capacity scaling menggunakan Delphi 7. Program tersebut dapat menentukan biaya minimum yang diperlukan secara cepat dan mudah. HASIL YANG DIHARAPKAN Hasil yang diharapkan pada penulisan ini adalah (1) mendeskripsikan langkah-langkah algoritma capacity scaling pada permasalahan minimum cost flow, (2) menganalisa hasil perbandingan algoritma capacity scaling dengan algoritma penghapusan sikel dan algoritma lintasan terpendek berulang, (3) mengimplementasikan algoritma capacity scaling ke dalam program Delphi 7, serta (4) membandingkan hasil program algoritma capacity scaling dengan algoritma penghapusan sikel dan algoritma lintasan terpendek berulang.
Reni Dian Saputri adalah mahasiswa Universitas Negeri Malang. Sapti Wahyuningsih dan Darmawan Satyananda adalah dosen Jurusan Matematika FMIPA Universitas Negeri Malang
PEMBAHASAN Algoritma Capacity Scaling Algoritma capacity scaling ini pertama kali ditemukan oleh Gabow pada tahun 1985, dan kemudian disempurnakan oleh Ahuja dan Orlin pada tahun 1991. Pada salah satu jurnal berjudul “A Capacity Scaling for The Constrained Maximum Flow Problem” yang ditulis oleh Ahuja dan Orlin (1993) menyebutkan bahwa algoritma capacity scaling dapat digunakan dalam menyelesaikan permasalahan maximum flow. Ide pokok yang mendasari algoritma capacity scaling ini adalah menambahkan aliran sepanjang lintasan yang memiliki kapasitas sisa cukup besar. algoritma capacity scaling ini baik digunakan untuk jaringan yang memiliki kapasitas sisi cukup besar. Adapun langkah-langkah yang terdapat dalam buku Netwok Flow (Ahuja, Magnanti, dan Orlin, 1993) yang harus dilakukan dalam algoritma capacity scaling ini adalah sebagai berikut: Input: suatu network N yang telah diketahui bobot masing-masing titik ( ), biaya dari suatu titik ke titik yang lain , dan kapasitas pengiriman dari suatu titik ke titik lain . 1. Menentukan jaringan sisa, dengan mengalirkan aliran setiap sisinya =0 dan potensial setiap titiknya adalah ( ) = 0. Sehingga dari jaringan sisa tersebut akan didapatkan ketakseimbangan titik ( ), biaya sisa , dan kapasitas sisa . 2. Tentukan nilai ∆ = 2 . ∆ nantinya akan menjadi banyaknya unit yang dilirkan pada setiap lintasan yang terpilih. Jika ∆≥ 1 maka lanjut ke langkah 3, jika ∆< 1 maka algoritma berhenti. 3. Apabila kapasitas sisa lebih dari atau sama dengan ∆ ( ≥ ∆) dan biaya sisa kurang dari 0 ( < 0) maka alirkan sebanyak dan update ketakseimbangan titik ( ), aliran , dan kapasitas sisa dan lanjut ke langkah 4. Apabila tidak terjadi kasus tersebut, maka langsung ke langkah 4. 4. Tentukan (∆) dan (∆) dengan: (∆) merupakan himpunan titik yang mempunyai ketakseimbangan titik sebanyak lebih dari atau sama dengan ∆ atau merupakan himpunan titik pengirim. Sedangkan (∆) merupakan himpunan titik yang memiliki ketakseimbangan titik sebanyak kurang dari atau sama dengan −∆ atau merupakan himpunan titik penerima. (∆) = { ∈ : ( ) ≥ ∆} (∆) = { ∈ : ( ) ≤ −∆} Apabila (∆) ≠ ∅ dan (∆) ≠ ∅ maka lanjut ke langkah 5. Apabila (∆) = ∅ dan (∆) = ∅ maka langsung ke langkah 7. 5. Ketika (∆) ≠ ∅ dan (∆) ≠ ∅ maka lakukan langkah berikut: Pilih ∈ (∆) dan ∈ (∆). Update biaya sisa = − ( ) + ( ). Update jarak ( ) = ( ) + . Pilih yang merupakan lintasan terpendek dari titik ke titik pada jaringan sisa-∆. Pemilihan lintasan dilakukan dengan cara melihat ( ), yaitu dengan mencari lintasan dengan biaya sisa minimum yang sama dengan ( ).
Update potensial titik ( ) = ( ) − ( ). Alirkan sebanyak ∆ pada lintasan terpilih . Update ketakseimbangan titik ( ) = ( ) + ∑ − ∑ . Update kapasitas sisa = − ∆. Apabila pada lintasan ada sisi ( , ), maka = +∆ Update = + ∆. Apabila pada lintasan ada sisi ( , ), maka = − ∆. Lakukan langkah 5 sampai (∆) terpilih semua. Apabila (∆) sudah terpilih semua, update ∆ dengan ∆= ∆/2. Kembali ke langkah 3 Output: jumlah dari aliran yang masing-masing dikalikan dengan biaya sisinya , ∀( , ) ∈ .
6. 7. 8. 9.
Analisa Contoh Penerapan Algoritma Capacity Scaling, Algoritma Penghapusan Sikel, dan Algoritma Lintasan Terpendek Berulang Salah satu contoh permasalahan minimum cost flow yang terdapat pada kehidupan sehari-hari adalah permasalahan pengiriman barang. Dalam melakukan pengiriman, distributor pasti mengharapkan mengeluarkan biaya seminimal mungkin. Berikut ini akan diberikan suatu permasalahan minimum cost flow yang telah diubah ke dalam bentuk jaringan seperti terlihat pada Gambar 1. Permasalahan tersebut diselesaikan dengan menggunakan algoritma capacity scaling, algoritma penghapusan sikel, dan algoritma lintasaan terpendek berulang.
Gambar 1 : jaringan awal dari permasalahan
Dari contoh permasalahan pengiriman di atas terihat bahwa titik 1 harus mengirimkan barang kepada titik yang lain sesuai dengan permintaan titik tersebut. Contoh permasalah di atas telah diselesaikan dengan menggunakan algoritma capacity scaling, algoritma penghapusan sikel, dan algoritma lintasaan terpendek berulang, dan diperoleh hasil yang ditampilkan pada tabel berikut:
Tabel Analisis Perbandingan Algoritma
Algoritma capacity scaling Algoritma ini dimulai dengan menginisialisasi aliran awal dan potensial titik ( ) dengan 0. Kemudian dilakukan penghitungan nilai ∆ yang berguna untuk jaringan sisa dengan kapasitas sebesar ∆, dengan ∆ = 2 . Setelah itu menentukan (∆) yang merupakan himpunan titik pengirim dan (∆) Proses yang merupakan himpunan titik penerima. Algoritma akan mengimkan aliran sebanyak ∆ dari titik yang berada pada (∆) menuju setiap titik yang ada pada (∆). Apabila titik yang berada pada (∆) sudah terpilih semua maka algoritma akan mengupdate nilai ∆ ∆ menjadi . Lakukan sampai (∆) = ∅. Aliran fisibel awal dimisalkan dengan nol. Kemudian untuk Menentu banyaknya aliran kan aliran selanjutnya yang dialirkan pada jaringan fisibel sisa akan bergantung pada nilai ∆. Menentu kan jaringan sisa
Jaringan sisa pada algoritma ini ditentukan setelah menginisialisasi aliran
Algoritma Penghapusan Sikel Algoritma ini dimulai dengan menentukan aliran fisibel yang memenuhi 0 ≤ ≤ dan mengalirkannya pada jaringan. Kemudian menentukan jaringan sisa dari jaringan yang telah diberi aliran fisibel sebelumnya. Algoritma akan memilih sikel yang berharga negatif yang ada pada jaringan sisa. Menentukan nilai dan menambahkannya pada sisi yang berlawanan dengan sikel negatif yang terpilih sebelumnya. kemudian update kembali jaringan sisa. Lakukan sampai tidak terdapat sikel yang berharga negatif.
Algoritma Lintasan Terpendek Berulang Algoritma ini dimulai dengan menginisialisasi aliran awal dan potensial titik dengan nol. Kemudian menentukan yang merupakan himpunan titik pengirim dan yang merupakan himpunan titik penerima. Menentukan lintasan dari titik yang ada pada menuju titik yang ada pada . Kemudian tentukan nilai dengan = min{ ( ), − ( ), min }}. Alirkan sepanjang lintasan terpilih. Lakukan sampai = ∅.
Aliran fisibel awal ditentukan dengan ketentuan 0 ≤ ≤ . Dan untuk aliran yang dialirkan selanjutnya bergantung pada aliran fisibel awal tersebut. Jaringan sisa ditentukan setelah mengalirkan aliran fisibel pada jaringan.
Aliran fisibel awal dimisalkan dengan nol. Kemudian untuk banyaknya aliran selanjutnya yang dialirkan pada jaringan sisa akan bergantung pada nilai . Jaringan sisa pada algoritma ini diperoleh setelah mingisialisasi aliran
dengan 0 dan berhubungan dengan . Algoritma akan menghapus sisi pada jaringan yang memuat kapasitas sisa kurang dari dan akan menampilkannya lagi ketika memenuhi . Sama dengan Hasil algoritma yang lain. Terdapat Algoritma Dijkstra yang berfungsi untuk Algoritm menentukan lintasan a lain terpendek yang dilalui yang ketika mengirimkan mempeng aliran dari titik yang aruhi ada pada menuju titik yang ada pada .
dengan 0.
Sama dengan algoritma yang lain. Tidak terdapat lagoritma lain yang mempengaruhi.
Sama dengan algoritma yang lain. Terdapat Algoritma Dijkstra yang berfungsi untuk menentukan lintasan terpendek yang dilalui ketika mengirimkan aliran dari titik yang ada pada menuju titik yang ada pada .
Program Algoritma Capacity Scaling dengan Delphi 7 Pemecahan permasalahan minimum cost flow menggunakan algoritma capacity scaling yang memiliki banyak titik memerlukan suatu cara untuk mempercepat pencarian biaya minimumnya. Salah satu caranya adalah dengan membuat implementasi program algoritma capacity scaling menggunakan Delphi 7. Berikut ini adalah flowchart program algoritma capacity scaling.
1
2
3
4
5
1
2
3
4
5
Gambar 2. Flowchart program algoritma capacity scaling
Setelah membuat rancangan flowchart program dan dari studi literatur dari modul Struktur Data (Satyananda, 2010) maka langkah selanjutnya adalah membuat rancangan tampilan program. Dalam program algoritma capacity scaling terdapat beberapa button, yaitu button input titik, input suplai, input biaya, input kapasitas, hasil, gambar hasil, proses, buka, simpan, reset, dan keluar. Button input titik digunakan untuk menampilkan halaman yang digunakan untuk menggambarkan titik-titik yang manjadi permasalahan. Button input suplai digunakan untuk menginputkan bobot pada setiap titik. Button input biaya digunakan untuk menginputkan biaya pada sisi yang ada pada permasalahan. Button input kapasitas digunakan untuk menginputkan kapasitas pada sisi yang ada pada permasalahan. Button proses ini digunakan untuk memproses data yang telah diinputkan. Button hasil digunakan utuk menampilkan hasil iterasi yang berupa memo. Button Gambar Hasil ini digunakan untuk menampilkan bagaimana gambar dan bobot sisi setelah terjadi proses. Button Simpan ini digunakan untuk menyimpan data yang telah diinputkan. Button Buka digunakan untuk membuka data yang telah tersimpan sebelumnya. Button Reset digunakan untuk me-reset apa yang telah dilakukan. Selanjutnya akan dicoba menyelesaikan contoh jaringan pada Gambar 1 menggunakan program algoritma capacity scaling. Langkah-langkahnya adalah sebagai berikut: 1. Inputkan data-data yang diperlukan seperti titik, bobot titik (suplai), bobot biaya, serta bobot kapasitas denngan menekan button yang sesuai. 2. Langkah senjutnya adalah menekan button proses yang terdapat pada program. 3. Tekan button hasil untuk mengetahui berapa biaya minimum yang dihasilkan dari proses pencarian tersebut. dan tekan button gambar hasil untuk mengetahui gambar dengan aliran yang melalui setiap sisinya. 4. Data yang telah diinputkan pada program dapat disimpan dan suatu saat memerlukan data yang sama maka akan dapat dibuka kembali. 5. Untuk keluar dari program, silahkan menekan button keluar.
Dari contoh yang telah dikerjakan, dapat dilihat bahwa biaya minimum yang dihasilkan dari program Algoritma capacity scaling dan algoritma pembandingnya adalah sama. Sehingga Algoritma capacity scaling ini dapat dijadikan alternatif dalam menyelesaika permasalahan minimum cost flow. Algoritma capacity scaling baik digunakan pada jaringan yang memuat kapasitas sisi yang cukup besar (Ahuja, 1993: 360). Namun, proses pengerjaannya lebih panjang, sehingga apabila dikerjakan dengan cara manual akan membutuhkan waktu yang sedikit lebih lama. Oleh karena itu, implementasi program yang telah dibuat ini dapat membantu dalam mendapatkan biaya minimum yang diharapkan secara cepat. Hanya dengan menekan satu tombol yang terdapat pada program, maka program langsung dapat menampilkan jumlah biaaya minimum dari jaringan yang telah diinputkan. PENUTUP Beberapa kesimpulan yang dapat diambil dari permasalahan minimum cost flow dengan menggunakan Algoritma Capacity Scaling adalah sebagai berikut: 1. Langkah kerja dari Algoritma Capacity Scaling ini secara singkat dapat dipahami sebagai berikut: Algoritma Capacity Scaling ini dimulai dengan inisialisasi potensial titik ( ( )), bobot titik ( ), biaya sisa ( ), jumlah aliran ( ), dan kapasitas sisa ⌋ ( ). Lalu dilanjutkan dengan pencarian ∆ dengan rumus ∆= 2⌊ , dengan merupakan kapasitas terbesar pada jaringan. Jika dari perhitungan tersebut didapatkan nilai ∆≥ 1, maka dapat dilanjutkan ke langkah selanjutnya yaitu pencarian lintasan terpendek dan mengalirkan sebanyak ∆ unit pada lintasan tersebut. Namun, jika hasil perhitungan ∆ menunjukkan nilai ∆< 1, maka algoritma akan berhenti. 2. Baik Algoritma Capacity Scaling maupun Algoritma Penghapusan Sikel dan Algoritma Lintasan Terpendek Berulang menghasilkan biaya minimum yang sama, namun terdapat perbedaan dalam prosesnya. Untuk Algoritma Capacity Scaling dan Algoritma Lintasan Terpendek Berulang, penambahan aliran dilakukan sepanjang lintasan yang terpilih. Pada Algoritma Penghapusan Sikel adalah dengan menghapus sikel yang berharga negatif sehingga jaringan akan optimum jika sudah tidak memuat sikel negatif. Dalam menentukan lintasan terpendek pada Algoritma Capacity Scaling dan Algoritma Lintasan Terpendek Berulang ditentukan dengan menggunakan Algoritma Dijkstra. Namun perbedaan mendasar pada Algoritma Capacity Scaling dan Algoritma Lintasan Terpendek Berulang terletak pada penskalaan kapasitas sisinya, sehingga Algoritma Cpacity Scaling dapat digunakan pada jaringan yang memuat kapasitas sisi cukup besar. 3. Implementasi program dari Algoritma Capacity Scaling ini menggunakan bahasa pemrograman Delphi. Untuk data yang harus diinputkan untuk menjalankan program adalah input titik, input kapasitas ( ), input biaya ( ), serta input permintaan ( ( )). Dan hasil yang diperoleh setelah menjalankan program adalah biaya minimum untuk mengirimkan unit aliran pada jaringan tersebut. 4. Biaya minimum yang dihasilkan oleh program Algoritma Capacity Scaling sama dengan biaya minimum yang dihasilkan oleh Algoritma Penghapusan Sikel dan Algoritma penghapusan Sikel yang terdapat pada alat bantu Giden
V4a, sehingga Algoritma Capacity Scaling tersebut dapat dijadikan alternatif dalam menyelesaikan permasalahan minimum cost flow. DAFTAR PUSTAKA Ahuja, R.K., T. L. Magnanti, dan J. B. Orlin. 1993. Network Flows Theory, Algoritmhs, and Applications. New Jersey : Prentice-Hall, Inc. Ahuja, R.K. dan J. B. Orlin.. 1993. A Capacity Scaling Algorithm for The Constrained Maximum Flow Problem. Rossen, K.H. 2000. Discreate Mathematics and Its Aplications. NewYork: Mc Graw Hill, Inc. Satyananda, Darmawan. 2010. Struktur Data. Malang: UniversitasNegeri Malang. Wilson, R. J dan J.J.Watkins. 1990. Graph An Introductory Approach a First Course in Discrete Mathematics. Canada: John Willey and Sons, Inc.
Malang, Mei 2013 Penulis
Pembimbing 1
Dra. Sapti Wahyuningsih, M.Si NIP 19621211 198812 2 001
Pembimbing 2
Darmawan Satyananda, S.T, M.T NIP. 19730724 199903 1 001
Mahasiswa
Reni Dian Saputri NIM. 908312408018
