OPTIMASI ARUS MAKSIMUM PADA JARINGAN

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

OPTIMASI ARUS MAKSIMUM PADA JARINGAN

SKRIPSI Diajukan untuk memenuhi Salah Satu Syarat Memperoleh Gelar Sarjana Program Studi Matematika

Disusun oleh : NAMA

: MARIA AGUSTINA AMELIA

NIM

: 023114005

FAKULTAS MATEMATIKA DAN PENGETAHUAN ALAM PROGRAM STUDI MATEMATIKA UNIVERSITAS SANATA DHARMA YOGYAKARTA 2007

i


ii


iii


Persembahan

Skripsi ini kupersembahkan untuk :

Mamaku yang terhebat di dunia, Ch. Yuni Hastuti. Makasi ya ma dah mau ikutan gila-gilaan sama Lia selama ini. I luv U sooooo Much!!!!!!!!!!!!!! Papaku: R.B. Sutoyo. I`m sorry that I can`t be your perfect daughter… Eyang ti dan Mbah Kung, matur nuwun atas segala doa, nasehat dan contoh nyata dalam menjalani hidup ini. Adik-adikku : Dira, Ayu, Dian. Sumber segala kekacauan, masalah, pengertian dan cinta di rumah. Let`s rock the world, sist!!!!!! Me Amo : Bon-bon, thanks dah menyadarkanku waktu aku masih bodoh. Ayo kita jalanin program-program KKN kita yang belum slesai. Romo Iwan: yang membantu memberikan inspirasi dan penguatan dalam fase hidupku yang kelam. Hehehe….dad I`ve made it but I can`t let him go.

iv


Motto

Love is patient Love is kind It does not envy It does not boast It is not proud It is not rude It is not self-seeking It is not easily anggered It keeps no record of wrongs Love does not delight in evil but rejoices with the truth it always protects always trust always hope always perserves

v


Pernyataan Keaslian Karya

Saya menyatakan dengan sesungguhnya bahwa skripsi yang saya tulis ini tidak memuat karya atau bagian karya orang lain, kecuali yang telah disebutkan dalam daftar pustaka, sebagaimana layaknya karya ilmiah.

Yogyakarta, 20 Maret 2007 Penulis

Maria Agustina Amelia

vi


ABSTRAK Suatu jaringan dapat menghasilkan sebuah gambaran atau model yang membantu memberi pengertian dalam menunjukkan hubungan antar komponen dalam berbagai permasalahan. Dalam penulisan ini akan dibahas masalah optimasi pada jaringan, yaitu masalah arus maksimum. Penyelesaian masalah arus maksimum yang akan dibahas lebih lanjut dalam penulisan ini adalah penyelesaian menggunakan proses pelabelan Ford Fulkerson dan metode max flow-min cut. Dalam penggunaan proses pelabelan Ford Fulkerson, pertama kali ubah jaringan menjadi bentuk matriks. Kemudian lakukan proses pelabelan dan perhitungan kembali nilai arus. Proses berulang kembali ke proses pelabelan, jika sudah tidak dapat ditemukan lagi flow augmenting path pada matriks, proses dihentikan karena arus maksimum sudak didapat. Dalam penyelesaian menggunakan metode max flow-min cut mula-mula perlu dicari jalur yang menghubungkan simpul awal dan simpul akhir pada jaringan. Kemudian hitung nilai slack pada masing-masing busur dan dilakukan perhitungan kembali arus. Proses berulang kembali ke pencarian jalur pada jaringan. Jika tidak dapat ditemukan jalur yang menghubungkan simpul awal ke simpul akhir maka simpul-simpul pada jaringan terpartisi menjadi dua buah himpunan yaitu himpunan yang memuat simpul awal dan yang memuat simpul akhir. Hitung kapasitas masing-masing busur yang menghubungkan simpulsimpul dari himpunan yang memuat simpul awal ke himpunan yang memuat simpul akhir. Nilai kapasitas tersebut akan sama dengan arus maksimum. Metode max flow-min cut dapat dihentikan. Dalam menyelesaikan masalah arus maksimum, dengan proses pelabelan Ford Fulkerson jaringan harus diubah dahulu ke dalam bentuk matriks. Dalam bentuk tersebut proses pelabelan lebih mudah dijalankan karena lebih ringkas. Sedangkan dalam pengerjaan tentang metode max flow min cut dibutuhkan ketelitian karena pada setiap iterasi dilakukan dalam bentuk jaringan dan harus memperhatikan arah arus yang mengalir pada jaringan tersebut. Namun jika iterasi sudah berhenti dan ditemukan nilai kapasitas dari potongan pada jaringan dapat diperiksa kebenarannya dengan menggunakan teorema max flow-min cut.

vii


ABSTRACT Network can give a representation or models that can help for giving sense to show relation between components in various problems. This writing will discuss about maximum network flow optimization. Maximum flow problem solving that will discuss further in this writing is using Ford-Fulkerson method and max flow-min cut method. To use Ford-Fulkerson method, first change the network into the matrix form. Then do the labeling process and find flow-augmenting path to get the new value of the flow. That process return to the labeling process again. If there is no flow-augmenting path, we stop the process, and get the maximum flow. To use max flow-min cut method, first find a path that connected source and sink on the network. Then find slack value for each arc to get the new value of the flow. This process returns to find the flow augmenting steps. If the path that connected source and sink cannot found, divide the set of nodes on the network into two subsets that contain the source and the sink, respectively. Count each arcs capacity that connected nodes from the sets that contain the source to the sets that contain the sink. That capacity will equal to the maximum flow and the process of max flow-min cut end. For solving maximum flow problem with Ford-Fulkerson method, the network must changed into matrix. It makes the labeling process easier because it is simpler. Even though max flow-min cut method, need more accuracy and must care about direction of the flow. However, if the iteration end and the capacity of the cut found we get the maximum flow.

viii


KATA PENGANTAR

Syukur kepada Tuhan YME, atas segala berkat yang diberikan kepada saya hingga saya dapat menyelesaikan penulisan skripsi dengan judul Optimasi Arus Maksimum pada Jaringan ini. Terimakasih saya sampaikan pula kepada ibu Lusia Krismiyati Budiasih, S.Si, M.Si yang telah meluangkan banyak kesempatan untuk membimbing dan mengkoreksi hasil tulisan saya. Dalam penulisan ini banyak sekali bantuan, dukungan dan berbagai masukan dari berbagai pihak. Karena itu saya juga mengucapkan terimakasih sebanyak-banyaknya kepada : 1.

Bapak Y. G. Hartono selaku ketua prodi Matematika yang telah membantu pada awal pengerjaan tulisan ini hingga selesai.

2.

Bapak Ir. Ign. Aris Dwiatmoko, M.Sc sebagai pembimbing akademik angkatan 2002 yang telah banyak memberikan inspirasi dan semangat selama saya dan teman-teman menjalani pendidikan di Sanata Dharma.

3.

Bapak Drs. B. Susanta dan Dr. Frans Susilo, SJ yang telah memberikan kuliah dengan suasana yang berbeda dan menyenangkan.

4.

Ibu Dra. Maria Agustiani, M.Si dan Ibu M.V. Any Herawati, S.Si, M.Si yang mengajarkan untuk berpikir secara runut dan logis.

5.

Ibu Prof. Dra. Moeharti Hadiwidjojo, M.A, Bapak Prof. Drs. R. Soemantri dan Bapak Drs. A. Tutoyo yang telah membantu menyampaikan dasar pada ilmu yang saya pelajari.

6.

Ibu Ch. L. Suwarni dan Bapak Z. Tukija yang selalu direpotkan dengan urusan kesekretariatan di FMIPA.

7.

Pimpinan Perpustakaan dan Staff yang sangat membantu memberi kenyamanan dalam mencari bahan untuk penulisan ini.

8.

Keluargaku: Mbah kakung, padhe Sigit dan budhe Yani, MbaÒpi, MbaÀik, Paòyo dan budhe Ulis, Mas Ilham, TeÌs dan Om Anwar, Aga, Edo, TeÌk dan Om Bas, Ajeng, Iqbal. Terima kasih banyak…

ix


9.

Eyang Bani Putri dan Eyang Bani kakung di Baturetno, Suster Diana dan Bulik Nia. Terimakasih atas semua dukungan semangat dan doanya.

10.

Teman-teman angkatan 2002, teman seperjuanganku. Ijup my best friend, Lenta, Debby, Priska, Lili, Ika, Vida, Archi, Retno, Sari, Padhe Galih, Aan, Tato, Markus, Bani, Taim, Felix, ayo.. perjuangan belum berakhir…!!!!!!! Serta teman-teman yang sudah melanjutkan fase hidup yang baru Cia, Aning, Palma, Rita, Asih, Desy, Dani, Wuri, Deon, Nunung, kalian hebat….!!!!

11.

Keluarga Glodogan Bapak Jaka dan Ibu Lilik, Yoga, Ivan, Mbah Mul putri Mbah Mul Kakung, Wawan, Ruri, Yani dan seluruh warga pedukuhan Glodogan yang sangat membantu waktu pelaksanaan KKN angkatan XXXI.

12.

Bapak Drs. Severinus Domi, M.Si selaku DPL KKN serta saudara-saudara KKN:

Mami`Dewi`,

Tante`Dianing`,

Kakak`Tubruk`,

Sari,

Elli,

Dedek`Gusti`, Pak Leo, Eyang kakung, Babas. 13.

Guru-guruku yang telah membimbing dan mempersiapkanku dalam menghadapi dunia. Jasa ibu dan bapak tidak akan pernah kulupakan.

14.

Teman-teman geng Steceku: Tyas, Vedel, Karin, Elsa.

15.

Dan banyak pihak yang telah banyak membantu yang tidak dapat saya sebutkan satu persatu. Terima kasih….

Yogyakarta, 28 Maret 2007

Penulis

x


DAFTAR ISI

HALAMAN JUDUL…………………………………………………………… i HALAMAN PERSETUJUAN PEMBIMBING …………………………….... ii HALAMAN PENGESAHAN…………………………………………………. iii HALAMAN PERSEMBAHAN………………………………………….…… iv HALAMAN MOTTO………………………………………………………… iv HALAMAN PERNYATAAN KEASLIAN KARYA……………...………… vi HALAMAN ABSTRAK……………………………………………...……… vii HALAMAN ABSTRACT…………………………………………...……… viii KATA PENGANTAR………………………………………………...………. ix DAFTAR ISI………………………………………………………………….. xi BAB I PENDAHULUAN…………………………………...……………...… 1 A. Latar Belakang Masalah……………………………...……………. 1 B. Perumusan Masalah……………………………...………………… 5 C. Pembatasan Masalah………………………………...…………….. 5 D. Tujuan Penulisan……………………………………...………….... 5 E. Metode Penulisan……………………………………...…………... 5 F. Manfaat Penulisan…………………………………...…………..… 6 G. Sistematika Penulisan……………………………...………………. 6 BAB II BEBERAPA MASALAH DALAM JARINGAN…………..………... 8 A. Jaringan……………………………...…………………………….. 8 B. Jaringan Planar……………………...…………………………..... 17 C. Masalah jalur terpendek (Shortest path problem)……………...… 21 BAB III MASALAH ARUS MAKSIMUM……………………………….... 34 A. Metode Ford-Fulkerson………………………………………….. 40 B. Metode max flow-min cut…………………………………......….

63

C. Mencari potongan minimum menggunakan jarak terpendek........... 81 D. Aplikasi masalah arus maksimum…………………………...…… 94 BAB IV PENUTUP………………………………………………………..... 102 A. Kesimpulan …………………………………………………..…. 102 B. Saran ……………………………………………………….…… 104

xi


DAFTAR TABEL Tabel 2.3.1 Label awal pada tabel jalur terpendek ……………….……….... 25 Tabel 2.3.2 Bentuk matriks dari jaringan pada Gambar 2.3.1 ………...……. 28 Tabel 2.3.3 Tabel setelah iterasi pertama ………………………………..…. 29 Tabel 2.2.4 Tabel setelah iterasi kedua ………………………..…………… 30 Tabel 2.2.5 Tabel setelah iterasi ketiga …………………………….………. 31 Tabel 2.2.6 Tabel setelah iterasi ke empat ………………………….……… 32 Tabel 2.2.7 Tabel setelah algoritma Djikstra selesai …………………….….. 32 Tabel 3.1.1 Jaringan dalam bentuk matriks ………………………………… 50 Tabel 3.1.2 Pelabelan Ford Fulkerson pada Iterasi 1 ………………….…… 51 Tabel 3.1.3 Penelusuran jalur dan pemberian tanda pada Iterasi 1 …..…….. 52 Tabel 3.1.4 Pelabelan Ford Fulkerson pada Iterasi 2 …………………….… 54 Tabel 3.1.5 Penelusuran jalur dan pemberian tanda pada Iterasi 2 …….….. 55 Tabel 3.1.6 Pelabelan Ford Fulkerson pada Iterasi 3 …………………….… 57 Tabel 3.1.7 Penelusuran jalur dan pemberian tanda pada Iterasi 3 …..……. 58 Tabel 3.1.8 Pelabelan Ford Fulkerson pada Iterasi 4 …………………….… 59 Tabel 3.1.9 Penelusuran jalur dan pemberian tanda pada Iterasi 4 ………… 60 Tabel 3.1.10 Tabel iterasi 5 ……………………………………………….…. 62 Tabel 3.2.1 Contoh 3.1.1 dan 3.2.1 menggunakan program komputer ......... 80 Tabel 3.2.2 Banyak iterasi dan jalur yang dipilih pada program komputer ….. 81 Tabel 3.3.1 Matriks awal sebelum iterasi dengan algoritma Djikstra …....…. 89 Tabel 3.3.2 Matris setelah ditemukan nilai jalur terpendek ……………….… 89 Tabel 3.3.3 Jaringan primal dalam bentuk matriks ………………………..… 91 Tabel 3.3.4 Arus maksimum dengan metode Ford Fulkerson ………………. 91 Tabel 3.3.5 Contoh 3.3.1 menggunakan program komputer …………………. 92 Tabel 3.3.6 Banyak iterasi dan jalur yang dipilih pada program komputer....... 93 Tabel 3.4.1 Bentuk matriks dari Gambar 3.3.2 …………………………...…. 98 Tabel 3.4.2 Matriks setelah metode Ford Fulkerson ……………………...… 98 Tabel 3.4.3 Contoh 3.4.1 menggunakan program komputer …………….…. 100 Tabel 3.4.4 Banyak iterasi dan jalur yang dipilih pada program komputer ….. 101

xii


DAFTAR GAMBAR

Gambar 1.1

Graf dengan empat simpul dan tiga busur ……………….……. 1

Gambar 1.2

Penerbangan kota A ke kota B dimodelkan dengan jaringan….. 4

Gambar 2.1.1 Jaringan planar dengan lima buah simpul dan 9 buah busur .... 18 Gambar 2.3.1 Jaringan dengan 9 simpul dan 15 busur ………...………….... 28 Gambar 2.3.2 Pohon perentang pada jaringan …………………………….... 33 Gambar 2.3.3 Jalur terpendek pada jaringan ………………………………... 33 Gambar 3.1

Skema pengolahan bahan mentah menjadi bentuk energi …... 35

Gambar 3.1.1 Jaringan berarah G ……………………………………...……. 49 Gambar 3.2.1 Jaringan dengan 8 simpul dan 12 busur ………………………. 73 Gambar 3.2.2 Jaringan setelah iterasi pertama …………………………….…. 74 Gambar 3.2.3 Jaringan setelah iterasi kedua …………………………….…. 75 Gambar 3.2.4 Jaringan setelah iterasi ketiga ………………………………… 76 Gambar 3.2.5 Jaringan setelah iterasi keempat ………………………………. 77 Gambar 3.2.6 Jaringan setelah iterasi kelima ………………………………. 78 Gambar 3.3.1 Dual dari suatu jaringan planar ………………………..……. 82 Gambar 3.3.2 Jaringan planar dengan 8 simpul dan 15 busur ……………… 87 Gambar 3.3.3 Dual dari jaringan planar ………………………………….…. 88 Gambar 3.3.4 Jalur terpendek pada jaringan dual ………………………..…. 90 Gambar 3.4.1 Skema jalan yang dapat dilalui dari gudang ke toko ………….. 96 Gambar 3.4.2 Jaringan dengan simpul awal s dan simpul akhir t ………….. 97 Gambar 3.4.3 Jaringan setelah metode Ford Fulkerson ……………...…….. 99

xiii


BAB I PENDAHULUAN

A.

Latar Belakang Masalah Dalam bidang matematika terdapat sebuah subyek yang mengalami

perkembangan yang luar biasa, yaitu masalah jaringan. Masalah tentang jaringan tersebut dilatarbelakangi oleh teori graf yang pertama kali muncul pada tahun 1736 berkaitan dengan masalah jembatan konigsberg. Orang yang memunculkan masalah tersebut adalah orang berkebangsaan Swiss bernama Leonhart Euler. Suatu graf adalah kumpulan obyek yang terdiri dari himpunan simpulsimpul yang dihubungkan oleh himpunan busur. Berikut merupakan contoh suatu graf dengan empat simpul dan tiga busur.

Gambar 1.1 Graf dengan empat simpul dan tiga busur

1


Jika dua simpul dihubungkan dengan sebuah busur, maka simpul tersebut dikatakan berdampingan (adjacent). Dari Gambar 1.1 dapat dilihat bahwa simpul dua, tiga dan empat terhubung dengan simpul satu. Graf dapat dijumpai dalam kehidupan sehari-hari, misalnya simpul melambangkan lokasi dari kota-kota dan busur melambangkan jalan-jalan yang menghubungkan kota-kota tersebut, atau simpul melambangkan komponen listrik dan busur melambangkan kawat yang menghubungkan komponen-komponen yang berbeda. Juga jika simpul melambangkan atom-atom maka busur melambangkan ikatan kimia. Contoh-contoh tersebut adalah beberapa situasi yang dapat dimodelkan dengan graf. Jika sebuah busur menghubungkan simpul i ke simpul j, maka busur tersebut juga menghubungkan simpul j ke simpul i dan dinotasikan dengan busur (i,j) atau busur (j,i). Jaringan adalah graf yang busur-busurnya mempunyai nilai dan arah. Nilai pada busur tersebut biasanya berkaitan dengan biaya, kapasitas, penawaran atau permintaan. Masalah jaringan muncul dalam berbagai masalah terutama masalah transportasi, masalah listrik dan masalah komunikasi. Busur dalam jaringan yang mempunyai arah dan nilai biasa disebut arus. Masalah arus pada jaringan dikemukakan dan dianalisis secara sistematis oleh Gustav Kirchoff dan beberapa orang yang menekuni bidang teknik dan kelistrikan. Pekerjaan dari beberapa orang inilah yang memberi landasan untuk lebih mendalami teori tentang arus pada jaringan dan pembentukan jaringan yaitu dalam bentuk graf sebagai obyek matematika yang dapat digunakan untuk menggambarkan banyak sistem fisik.

2


Arus pada jaringan menyangkut banyak bidang, misalnya bidang matematika terapan, ilmu komputer, bidang teknik, manajemen dan bidang riset operasi. Dalam kenyataan, sebuah jaringan menghasilkan sebuah gambaran yang kuat dan membantu memberi pengertian dalam menunjukkan hubungan antar komponen dari suatu sistem yang banyak digunakan dalam bidang ilmu pengetahuan. Salah satu perkembangan tentang masalah jaringan yang menggembirakan beberapa tahun terakhir adalah perkembangan dalam bidang metodologi dan aplikasi untuk masalah optimasi arus pada jaringan. Masalah optimasi pada jaringan mulai dibicarakan pada akhir tahun 1940 hingga awal tahun 1950 ketika para peneliti dan para ahli secara terus-menerus mengembangkan masalah optimasi sebagai bidang yang berdiri sendiri. Pada saat dimulainya perkembangan komputer maka didapat sebuah alat yang digunakan untuk menampilkan perhitungan masalah optimasi tersebut secara lebih ilmiah. Masalah yang akan dibahas di sini adalah masalah optimasi arus pada jaringan. Jadi, selain akan dipelajari masalah arus pada jaringan juga akan ditunjukkan bagaimana optimasi arus pada jaringan tersebut. Sebagai contoh sebuah kejuaraan dunia baseball diadakan di kota B. Sebuah tim baseball dari kota A ikut berlomba dalam kejuaraan ini. Banyak penggemar dari kota A akan menggunakan layanan penerbangan menuju ke kota B. Jika jumlah kursi maksimum yang tersedia dalam masing-masing penerbangan diketahui, akan dicari jumlah penumpang maksimum yang akan diterbangkan dari kota A ke kota B dan rute penerbangan mana saja yang ditempuh. Rute penerbangan ini dapat dimodelkan dengan jaringan, seperti gambar berikut.

3


Gambar 1.2 Rute penerbangan dari kota A ke kota B dimodelkan dengan jaringan

Dalam jaringan G ini, kota A sebagai kota awal penerbangan disebut simpul awal dan kota B sebagai kota tujuan disebut simpul akhir. Simpul x, y dan z melambangkan bandara penghubung. Nilai-nilai pada setiap busur menyatakan kapasitas penumpang yang dapat diterbangkan dari satu tempat ke tempat lain. Secara umum optimasi arus pada jaringan dapat dijelaskan sebagai berikut. Misalkan diketahui jaringan dengan kapasitas tak negatif pada busur-busur. Untuk mendefinisikan masalah optimasi arus diperkenalkan dua buah simpul istimewa dalam jaringan tersebut, yaitu simpul awal s dan simpul akhir t. Akan dicari arus maksimum dari simpul awal s ke simpul akhir t yang sesuai dengan kapasitas dari busur dan memenuhi syarat tertentu. Untuk mencari penyelesaian dalam masalah arus maksimum, ada beberapa metode yang dapat digunakan antara lain metode Ford-Fulkerson, metode max flow-min cut atau menggunakan program komputer. Pada jaringan yang khusus masalah arus maksimum dapat diselesaikan menggunakan Algoritma jalur terpendek yaitu algoritma Djikstra.

4


B.

Perumusan Masalah

Permasalahan yang akan dibahas dalam skripsi ini adalah: 1.

Bagaimana cara mencari optimasi arus pada jaringan dengan metode FordFulkerson?

2.

Bagaimana cara mencari optimasi arus pada jaringan dengan metode max flow-min cut?

C. Pembatasan Masalah Masalah optimasi arus pada jaringan dalam skripsi ini hanya dibahas menggunakan dua metode saja, yaitu metode Ford-Fulkerson dan metode max flow-min cut.

D. Tujuan Penulisan Skripsi ini bertujuan untuk menambah pengetahuan dan memahami hal-hal yang berkaitan dengan optimasi arus pada jaringan.

E.

Metode Penulisan Penulisan skripsi ini menggunakan metode studi pustaka, yaitu

menggunakan buku-buku, jurnal-jurnal dan makalah-makalah yang telah dipublikasikan, sehingga tidak ditemukan hal baru.

5


F. Manfaat Penulisan Manfaat yang diharapkan dari penulisan skripsi ini adalah agar penulis lebih mengetahui tentang masalah jaringan terutama masalah optimasi arus maksimum pada jaringan.

G. Sistematika Penulisan Bab I

PENDAHULUAN Bab ini berisi tentang latar belakang penulisan tentang masalah optimasi

arus. Tentang bagaimana masalah optimasi arus, yaitu masalah arus maksimum dirumuskan dan juga pembatasan masalah dalam penulisan ini. Selain itu, terdapat tujuan penulisan, metode penulisan dan manfaat penulisan bagi penulis. Selanjutnya diberikan pula sistematika penulisan dalam masalah optimasi arus ini.

Bab II

BEBERAPA MASALAH DALAM JARINGAN Bab ini berisi tentang masalah jaringan, definisi-definisi dan teorema

yang berkaitan tentang masalah jaringan. Kemudian disinggung beberapa model jaringan yaitu jaringan planar dan jaringan dengan masalah jalur terpendek (shortest path problem).

6


Bab III

MASALAH ARUS MAKSIMUM Bab ini berisi pembahasan tentang jaringan dengan arus maksimum.

Bagaimana mencari arus maksimum menggunakan metode Ford-Fulkerson dan metode max flow-min cut. Selain itu dibahas pula bagaimana mencari arus maksimum pada jaringan yang khusus yaitu jaringan planar menggunakan algoritma untuk mencari jalur terpendek.

Bab IV

PENUTUP Bab ini berisi tentang kesimpulan dari penulisan tentang masalah

optimasi arus ini dan juga saran dari penulis bagi pembaca tulisan ini.

7


BAB II BEBERAPA MASALAH DALAM JARINGAN

A.

Jaringan Dalam kehidupan sehari-hari, masalah tentang jaringan selalu muncul.

Misalnya jaringan listrik yang memberi penerangan pada bangunan-bangunan dan jalan-jalan, jaringan telepon yang sangat membantu orang-orang untuk saling berkomunikasi tanpa susah payah, jaringan kereta api, sistem jalan raya dan jaringan yang melayani masalah penerbangan. Jaringan tersebut membantu pekerjaan sehari-hari dalam menempuh perjalanan dari satu tempat ke tempat lain dan memungkinkan seseorang untuk mengunjungi tempat-tempat baru dan menikmati pengalaman baru.

Definisi 2.1.1 Graf merupakan kumpulan obyek-obyek yang disebut simpul, bersama dengan himpunan busur. Jika dua buah simpul dihubungkan dengan sebuah busur maka simpul-simpul tersebut dikatakan berdampingan (adjacent).

Definisi 2.1.2 Digraf merupakan graf di mana setiap busur dari graf tersebut mempunyai arah. Pada sebuah digraf jika terdapat busur dari simpul i menuju simpul j, maka busur itu disebut busur maju (forward arc) untuk simpul i dan busur mundur (backward arc) untuk simpul j.

8


Definisi 2.1.3 Perjalanan (walk) pada suatu graf merupakan barisan yang terdiri dari himpunan simpul dan himpunan busur. Suatu sikel (cycle) merupakan perjalanan dari suatu simpul dan kembali ke simpul tersebut tanpa ada pengulangan busur dan simpul yang dilalui.

Definisi 2.1.4 Jalur (path) pada suatu graf merupakan perjalanan tanpa ada pengulangan pada simpul-simpul pada jaringan. Dipath (directed path) merupakan jalur yang mempunyai arah tertentu.

Definisi 2.1.5 Suatu pohon (tree) merupakan garaf terhubung yang tidak memuat sikel. Suatu pohon perentang (spanning tree) merupakan pohon dari suatu graf G yang memuat semua simpul.

Definisi 2.1.6 Simpul awal (source) pada sebuah digraf merupakan sebuah simpul di mana semua busur yang terhubung dengan simpul tersebut merupakan busur maju.

Definisi 2.1.7 Simpul akhir (sink) pada sebuah digraf merupakan sebuah simpul di mana semua busur yang terhubung dengan simpul tersebut merupakan busur mundur.

9


Definisi 2.1.8 Sebuah graf atau digraf dikatakan terhubung (connected) jika untuk setiap dua simpul pada graf tersebut terdapat sebuah jalur yang menghubungkan kedua simpul tersebut.

Definisi 2.1.9 Jaringan (network) merupakan digraf terhubung yang memiliki sebuah simpul awal dan sebuah simpul akhir.

Definisi 2.1.10 Kapasitas (capacity) sebuah busur merupakan arus maksimum dari suatu barang yang dapat melewati busur tersebut . Kapasitas arus dinotasikan dengan Cij yang merupakan bilangan bulat tak negatif. Nilai Cij = 0 jika simpul i dan j bukan merupakan dua buah simpul yang adjacent.

Definisi 2.1.11 Jaringan berarah merupakan graf berarah dimana busur-busurnya berkaitan dengan suatu nilai tertentu. Biasanya nilai tersebut berkaitan dengan biaya, kapasitas, permintaan, atau persediaan barang.

Definisi 2.1.12 Pada suatu jaringan berarah G:(N,A), suatu himpunan bagian dari jaringan G ini disebut rantai (chain) jika setiap unsur dalam himpunan bagian ini berhubungan.

10


Definisi 2.1.13 Digraf D:(N`,A`) disebut underlying digraf dari jaringan G:(N,A) jika digraf D tersebut mempunyai simpul awal s dan simpul akhir t serta kapasitas busur C yang berupa bilangan bulat tak negatif. Dengan N `N dan A`A

Definisi 2.1.14 Pada suatu jaringan G:(N,A), dengan simpul awal s, simpul akhir t dan kapasitas dari busur (i,j) adalah Cij , arus (flow) pada jaringan berarah merupakan fungsi yang mengawankan busur (i,j) ke sebuah nilai fij. Nilai fij inilah yang disebut besar arus pada jaringan. Nilai f ij tersebut harus memenuhi dua hal : 1. 0 ≤fij ≤Cij untuk semua i,j N dan 2.

f f ij

jN

ji

untuk setiap i N -{s,t}

(2.1) (2.2)

jN

Persamaan (2.1) menyatakan bahwa arus pada busur tidak pernah melampaui kapasitas busur dan persamaan tersebut disebut kendala kapasitas untuk masalah arus maksimum. Kondisi (2.2) menyatakan jika i bukan merupakan simpul awal s maupun simpul akhir t dari jaringan G:(N,A), maka selisih arus yang keluar dari i dan arus yang masuk ke i sama dengan nol. Kondisi ini didasarkan atas konservasi arus. Konservasi arus tersebut menyatakan bahwa tidak ada arus yang hilang pada setiap simpul pada jaringan.

11


Definisi 2.1.15 Jumlah total arus yang keluar dari simpul i dapat ditulis

f

ij

untuk setiap i N – {s,t}

jN

Jumlah total arus yang masuk ke simpul i dapat ditulis

f

ij

untuk setiap i N – {s,t}

jN

Untuk busur (i,j) pada jaringan G:(N,A), nilai fij disebut arus yang masuk ke busur (i,j) atau arus sepanjang busur (i,j) dan dapat dikatakan sebagai nilai dari bahan yang dapat dipindahkan oleh arus f sepanjang busur (i,j).

Perhatikan persamaan berikut

f

f ji

ij

i, jN

i , jN

f f

atau

ij

i , jN

0

ji

i , jN

Penjumlahan dilakukan pertama-tama terhadap j, kemudian terhadap i sehingga didapat



 f f  iN

jN

ij

ji

jN

 0  

Persamaan konservasi arus menyatakan hasil penjumlahan di dalam tanda kurung sama dengan nol kecuali pada simpul awal s atau simpul akhir t, maka



f f    

is , t

jN

ij

ji

jN

12

 0  


f f ij

ji

i s , tjN

f f sj

jN

0

i s , tjN

tj

jN

   fjs fjt   0 jN jN 

f f f f sj

js

j

Sehingga diperoleh

tj

j

jt

j

0

j

f f f f sj

j

js

j

jt

j

tj

j

Definisi 2.1.16 Misalkan terdapat jaringan berarah dengan simpul awal s, simpul akhir t dan himpunan simpul-simpul pada jaringan G:(N,A). Nilai dari arus F merupakan bilangan bulat dan didefinisikan sebagai val(F) =

f f sj

jN

js

jN

Atau menurut konservasi arus, ekivalen dengan val(F) =

f f jt

jN

tj

jN

Nilai arus merupakan selisih arus yang meninggalkan simpul awal dan arus yang memasuki simpul awal atau ekivalen dengan selisih arus yang memasuki simpul akhir dan arus yang meninggalkan simpul akhir.

13


Teorema 2.1.17 Pada jaringan berarah G:(N,A) dengan simpul awal s dan simpul akhir t dimana tidak ada arus yang masuk ke simpul awal s dan tidak ada arus yang keluar dari simpul akhir t maka berlaku bahwa

f f

val(F) =

sj

jt

jN

jN

Bukti Secara umum pada suatu jaringan G:(N,A) tidak ada arus yang masuk ke simpul awal s dan tidak ada arus yang keluar dari simpul akhir t, yaitu fjs = 0 = ftj untuk semua himpunan simpul-simpul N. Maka nilai dari arus val(F) adalah

f f

val(F) =

sj

jN

=

js

jN

f

sj

0

jN

=

f

sj

jN

atau ekivalen dengan val(F) =

f f jt

jN

=

jN

f

jt

jN

=

f jN

14

jt

0

tj


Dengan demikian nilai dari arus dapat ditulis sebagai berikut : val(F) =

f f sj

jN

jt

jN

Konstruksi arus pada jaringan Pertama-tama tempatkan sebuah jalur (path), namakan P, yang menghubungkan simpul awal s ke simpul akhir t. Arah jalur tersebut ditunjukkan dengan tanda panah pada busur. Didefinisikan arus pada jalur tersebut sebagai berikut: 1, jika (i, j ) P  f ij  0, jika (i, j )  P Arus yang didefinisikan tersebut disebut sebagai unit flow karena nilai dari arus pada busur adalah 1. Arus tersebut juga memenuhi konservasi arus.  Jika j merupakan simpul yang tidak terdapat pada P, maka semua busur yang memasuki dan keluar dari j mempunyai nilai arus sama dengan 0.  Jika j merupakan arus yang terdapat pada P, maka tepat satu busur memasuki simpul j yang mempunyai nilai arus tidak nol dan tepat satu busur meninggalkan simpul j.  Setiap busur pada jalur P tersebut masing-masing mempunyai nilai 1. Setelah ditemukan arus tersebut, konstruksi arus pada jaringan diteruskan dengan melakukan penambahan-penambahan arus pada jalur P. Penambahan arus tersebut sejumlah 1 hingga diperoleh nilai arus maksimum yang memenuhi kendala kapasitas arus pada busur yang terdapat pada jalur P dipenuhi.

15


Jika didapatkan kapasitas terkecil pada jalur P, maka dikatakan jalur P tersebut mempunyai busur jenuh (saturated arc), yaitu ada minimal satu busur yang memuat nilai arus sama dengan kapasitas busur tersebut. Jaringan dapat digunakan untuk memodelkan berbagai permasalahan dalam kehidupan sehari-hari. Contohnya jaringan dapat digunakan untuk memodelkan masalah sistem pendistribusian minyak. Model jaringan tersebut memuat sejumlah berhingga simpul-simpul dan busur-busur. Busur-busur yang menghubungkan antar simpul merepresentasikan pipa-pipa yang mengalirkan minyak dari simpul awal menuju ke simpul akhir. Simpul awal merepresentasikan daerah sumber minyak, simpul akhir merepresentasikan daerah tujuan atau tempat akhir pengiriman minyak. Sedangkan simpul-simpul lain selain simpul awal dan simpul akhir merepresentasikan daerah-daerah yang dilewati oleh pipa-pipa yang mengalirkan minyak tersebut. Berbagai masalah dalam kehidupan sehari-hari yang dapat diselesaikan menggunakan model jaringan antara lain: masalah jalur trayek angkutan perkotaan dapat dimodelkan menggunakan jaringan planar karena jalur tersebut diusahakan tidak sama agar tidak terjadi perebutan penumpang. Masalah jalur pengantaran surat dari kantor pos ke rumah-rumah dapat dimodelkan menjadi masalah jalur terpendek.

16


B.

Jaringan planar.

Definisi 2.2.1 Sebuah jaringan G:(N,A) disebut jaringan planar jika jaringan tersebut dapat digambarkan pada bidang datar sedemikian rupa sehingga tidak ada dua atau lebih busur yang saling memotong satu sama lain. Dengan kata lain busurbusur tersebut bertemu satu sama lain pada satu simpul , yaitu pada simpul-simpul pada jaringan.

Pada bagian ini akan dipelajari beberapa bagian dari jaringan planar dan mendeskripsikan algoritma yang dapat digunakan untuk menyelesaikan masalah arus maksimum pada jaringan planar. Jaringan yang akan dibahas pada bagian ini dibatasi pada jaringan tak berarah. Pada

jaringan

tak

berarah

busur

(i,j)

merupakan

busur

yang

menghubungkan simpul i dengan simpul j dan sebaliknya. Kapasitas Cij dari busur (i,j) menunjuk pada jumlah arus maksimum yang dapat dikirimkan dari simpul i ke simpul j atau dari simpul j ke simpul i.

Definisi 2.2.2 Misalkan G:(N,A) merupakan jaringan planar. Daerah (region), z dari jaringan G tersebut merupakan daerah dari bidang datar yang dibatasi oleh busur-busur yang memenuhi syarat bahwa untuk sebarang dua titik pada daerah tersebut dapat dihubungkan oleh suatu kurva tanpa memotong suatu simpul atau busur.

17


Definisi 2.2.3 Batas (boundary) dari daerah z merupakan himpunan dari semua busur-busur yang mengurung daerah z. Batas dari suatu daerah z membentuk suatu sikel.

Definisi 2.2.4 Suatu daerah disebut daerah terbatas (bounded region) jika daerah tersebut terbatas dan disebut daerah tak terbatas (unbounded region) jika daerah tersebut tak terbatas. Jaringan planar mempunyai tepat satu daerah tak terbatas.

Definisi 2.2.5 Misalkan setiap busur pada jaringan merupakan batas dari paling sedikit dua buah daerah. Daerah z1 dan z2 disebut berdampingan (adjacent) jika batas-batas dari daerah tersebut memuat busur-busur yang sama.

Gambar 2.1.1 Jaringan planar dengan lima buah simpul dan 9 buah busur

Jaringan di atas menunjukkan suatu jaringan planar yang mempunyai empat daerah. Daerah z1, z2, z3 berada pada daerah terbatas (bounded region) dan daerah z4 berada pada daerah tak terbatas (unbounded region). Daerah z1 dibatasi

18


oleh empat buah busur dan letaknya berdekatan dengan daerah z2 dan z4. Daerah z2 dibatasi oleh lima buah busur dan letaknya berdekatan dengan daerah z1, z3 dan z4.

Teorema 2.2.6 (Rumus Euler) Jika suatu jaringan planar G:(N,A) terhubung mempunyai n buah simpul, m buah busur dan f buah daerah maka berlaku f = m – n + 2.

Bukti Teorema di atas akan dibuktikan menggunakan induksi matematis terhadap banyaknya daerah. (i). Untuk jaringan dengan satu daerah, yaitu f = 1 maka

1 = m – n +2

atau

m= n–1

(2.3) Persamaan (2.3) bernilai benar karena suatu jaringan dengan satu daerah, yaitu daerah tak terbatas membentuk suatu pohon perentang. (ii). Diasumsikan bahwa Rumus Euler bernilai benar untuk setiap jaringan dengan banyaknya daerah k, yaitu f = k, maka berlaku k = m – n +2 (iii). Akan dibuktikan Rumus Euler bernilai benar untuk setiap jaringan dengan banyak daerah k + 1.

19


Misalkan ada suatu jaringan G:(N,A) dengan banyaknya daerah k + 1 dan banyaknya simpul n. Dipilih sebarang busur (i,j) yang merupakan batas dari dua daerah, yaitu z1 dan z2. Jika busur (i,j) tersebut dihapus dari jaringan G maka daerah z1 dan z2 akan bergabung membentuk sebuah daerah. Banyaknya daerah dan busur masingmasing berkurang satu sedangkan jumlah simpul tetap. Didapatkan jaringan G` dengan k buah daerah dan n simpul. Dari asumsi diketahui bahwa Rumus Euler berlaku pada jaringan G` tersebut, yaitu k = m – n +2 Selanjutnya jika busur (i,j) dimasukkan kembali pada jaringan G` didapatkan (k + 1) = (m + 1) – n +2 Rumus Euler tetap bernilai benar karena penambahan banyaknya busur dan daerah tidak mengubah nilai dari persamaan diatas . ■

Rumus Euler terbukti

Teorema 2.2.7 Pada jaringan planar, dengan m buah busur, n buah simpul dan f buah daerah. Berlaku m < 3n.

Bukti Teorema di atas akan dibuktikan menggunakan kontradiksi. Misalkan berlaku m ≥3n atau n ≤m/3

20

(2.4)


Selanjutnya akan dicari hubungan antara f dan m. Karena jaringan tidak memuat busur yang paralel maka batas dari tiap daerah memuat paling sedikit 3 buah busur. Pada jaringan dengan banyak daerah f, jika setiap daerah ditelusuri satu persatu, maka paling sedikit akan ditemukan sejumlah 3f busur-busur. Perhatikan bahwa pada penelusuran tersebut setiap busur akan dilewati paling banyak dua kali karena busur-busur tersebut merupakan batas untuk paling banyak dua buah daerah. Hal tersebut menunjukkan bahwa 3f ≤2m atau f ≤2m/3

(2.5)

Dari rumus Euler diketahui f = m – n + 2 atau f+n–m=2 Dari persamaan (2.4), (2.5) dan Rumus Euler didapatkan f + n – m ≤2m/3 + m/3 – m f + n – m ≤0

atau

Padahal menurut Rumus Euler diketahui bahwa f + n – m = 2. Terjadi kontradiksi, maka pengandaian bahwa m ≥3n atau n ≤m/3 salah. Jadi pada jaringan planar, dengan m buah busur, n buah simpul dan f buah daerah ■

Berlaku m < 3n.

C. Masalah jalur terpendek (Shortest path problem) Masalah penting lain yang muncul sebagai aplikasi dalam jaringan adalah menemukan jalur terpendek (shortest path) yang menghubungkan dua simpul pada suatu jaringan berarah. Contohnya suatu kantor pos ingin mengetahui jalan tercepat untuk mengirimkan paket dari suatu kota ke kota lain atau seorang

21


wisatawan akan merencanakan perjalanan lintas Negara dan ingin mengetahui jalanan mana yang dapat dilalui untuk mencapai daerah tujuan wisatanya dengan jarak tempuh terpendek. Selain contoh-contoh tersebut masih banyak masalah lain yang dapat dinyatakan sebagai masalah jalur terpendek yang akan dibahas pada bab ini. Dalam masalah jalur terpendek akan dicari suatu jalur (path) yang mempunyai jarak minimum dari suatu simpul awal s ke suatu simpul akhir t. Pada kenyataannya algoritma jalur terpendek sering digunakan pada algoritma matematika yang lain sebagai penyelesaian alternatif dalam masalah-masalah yang lebih rumit dengan daerah pembicaraan yang lain. Masalah jalur terpendek dapat dinyatakan sebagai berikut diberikan suatu jaringan berarah G:(N,A) akan dicari jalur terpendek dari suatu simpul awal yaitu simpul s ke suatu simpul akhir yaitu simpul t. Simpul-simpul tersebut dapat dibayangkan sebagai kota-kota pada suatu peta dan busur-busurnya merupakan jalan-jalan yang menghubungkan kota-kota tersebut. Nilai Uij pada busur (i,j) menyatakan panjang jalan yang menghubungkan kota i ke kota j. Masalah jalur terpendek dinyatakan sebagai masalah program linear. Misalkan xij sama dengan 1 jika (i,j) dimuat dalam jalur yang menghubungkan simpul s ke simpul t dan 0 jika sebaliknya. Panjang dari jalur merupakan jumlahan dari panjang busur-busur pada jalur yang dinyatakan dengan u Uij  x ij i , jN

Jumlahan pada ruas kanan persamaan ini diambil dari semua busur-busur (i,j) pada jaringan. Karena pada jalur tersebut harus ada satu busur yang keluar dari

22


simpul awal s maka dapat ditulis

x

sj

1 . Dengan cara yang sama, karena pada

jN

jalur tersebut berakhir pada simpul t dan hanya ada satu busur yang memasuki satu simpul t ini maka

x

it

1 .

iN

Untuk sebarang simpul-simpul i pada jaringan, jika busur yang berada

x

pada jalur memasuki simpul j, yaitu

ij

1 maka akan ada satu busur yang

iN

x

meninggalkan simpul j tersebut, yaitu

ji

1 . Dengan cara yang sama, jika

iN

tidak ada busur pada jalur yang memasuki simpul j, yaitu

x

ij

0 maka tidak

iN

ada busur pada jalur tersebut yang meninggalkan simpul, yaitu

x

ji

0 .

iN

Sehingga dapat disimpulkan bahwa pada simpul-simpul selain simpul awal dan simpul akhir, sebarang busur yang memasuki suatu simpul pasti akan meninggalkan simpul tersebut, atau

x x ij

jk

iN

untuk sebarang simpul j yang

kN

terletak antara simpul s dan simpul t. Maka dalam program linear, jika diketahui suatu jaringan berarah G:(N,A) dengan simpul awal s dan simpul akhir t, masalah jalur terpendek dari jaringan tersebut dapat dituliskan sebagai berikut :

Minimum u =

U

ij

xij

i , jN

Dengan kendala

x

sj

1

jN

x

1

it

iN

23


x

ij

i, jN

 xjk j , kN

dengan Uij = panjang busur yang menghubungkan simpul i dengan simpul j

Perhatikan bahwa variabel kendala pada persamaan di atas berupa bilangan bulat positif. Jika digabungkan dengan kendala yang lain berarti nilai dari semua variabel adalah 0 atau 1. Ketika didapatkan penyelesaian optimal dari masalah jalur terpendek, variabel-variabel yang bernilai 1 menentukan busurbusur yang termasuk dalam jalur sementara variabel-variabel yang bernilai 0 menentukan busur-busur yang tidak termasuk di dalam jalur. Misalkan d(j) menotasikan panjang jalur dari simpul awal ke simpul j, dengan j i dan d(s) = 0. Jika d(j*) merupakan jalur terpendek dari jaringan G:(N,A), maka d(j*) memenuhi d(j*) ≤d(i*) + Uij untuk semua (i,j) A

(2.2.1)

Pertidaksamaan di atas menyatakan bahwa untuk setiap busur (i,j) yang terletak pada jaringan, berlaku panjang dari jalur terpendek dari simpul awal ke simpul j tidak akan melebihi panjang dari jalur terpendek dari simpul awal ke simpul i ditambah panjang busur (i,j). Walaupun masalah jalur terpendek ini termasuk dalam masalah program linear, dalam mencari panyelesaian masalah akan tidak efektif jika digunakan metode simpleks karena banyak nilai 0 yang muncul pada tablo simpleks akan membuat komputasi yang tidak perlu dan memakan banyak waktu. Maka untuk menyelesaikan masalah jalur terpendek ini digunakan suatu cara yang disebut algoritma Dijkstra (Dijkstra algorithm).

24


Algoritma Djikstra ini berguna untuk mencari jarak suatu jalur dengan jumlah jarak terpendek dari simpul awal s ke simpul akhir t dalam suatu jaringan. Untuk menggunakan algoritma ini, pertama-tama ubah jaringan ke dalam bentuk matriks dengan aturan : 1) Pada diagonal utama matriks, tuliskan semua simpul pada jaringan. 2) Karena pada algoritma Djikstra diasumsikan bahwa jaringan yang digunakan tak berarah, maka masukkan semua panjang busur (i,j) pada jaringan tersebut. Elemen pada baris ke-i dan kolom ke-j. aij = aji = Uij dengan i, j simpul-simpul pada jaringan,dan i j Jika simpul 1 menghubungkan simpul 2, maka pada sel (1,2) tuliskan panjang busur (1,2), yakni a12 = a21 = U12 Setelah diperoleh suatu matriks yang merepresentasikan jaringan, maka algoritma Dijkstra dinyatakan sebagai berikut : 1. Berikan label pada setiap baris dan kolom yang menyatakan jalur terpendek dari simpul dari simpul awal ke simpul j. Label pada simpul awal adalah l1 = 0 sehingga didapatkan tabel sebagai berikut

0

0 1 2 ... ... n

Tabel 2.3.1 Label awal pada tabel jalur terpendek

25


2. Pada setiap sel (i*,j) dengan i* adalah baris berlabel dan j adalah kolom yang belum berlabel, berikan nilai d(j) yang merupakan jarak dari simpul awal ke simpul j, yakni d(j) = ai*j + li* 3. Tentukan lj = min {d(j)}, j N dan beri label pada kolom yang bersesuaian dengan simpul j tersebut. 4. Beberapa kemungkinan yang terjadi pada tabel (i).

Jika masih ada entri pada busur berlabel dan kolom yang tidak berlabel, kembali ke Langkah 2.

(ii). Jika semua kolom sudah mempunyai label, yang berarti semua simpul sudah mempunyai label, maka langkah dihentikan dan l(t) merupakan jalur terpendek dari simpul awal s ke simpul akhir t. (iii). Jika tidak semua kolom mempunyai label dan tidak ada entri pada baris berlabel dan kolom berlabel, maka langkah berhenti. Pada keadaan ini diperoleh graf tidak terhubung.

26


Diagram alir algoritma Djikstra

Tandai simpul awal dengan label l1 = 0

Hitung d(j) = ai*j + l i* dengan i * adalah baris berlabel

Hitung lj = min {d(j)} Tetapkan i * = j ya Apakah terdapat ai*j pada baris berlabel dan kolom tidak berlabel? tidak stop

27


Contoh 2.3.1 Tentukan jalur terpendek yang dapat ditempuh untuk menghubungkan simpul awal A hingga simpul akhir I pada jaringan berikut

Gambar 2.3.1 Jaringan dengan 9 simpul dan 15 busur

Penyelesaian

Pertama-tama bentuk jaringan akan diubah dalam bentuk matriks, yaitu : A 3 4

3 B 2 7 6

4 2 C 5 4

7 5 D 2 4 4

6 4 2 E 6 4

4 6 F 2 2 3

4 4 2 G 4 5

2 4 H 2

3 5 2 I

Tabel 2.3.2 Bentuk matriks dari jaringan pada Gambar 2.3.1

Iterasi 1 Langkah 1 Tetapkan label pada baris dan kolom 1, yakni l1 = 0

28


Langkah 2 Kolom yang belum berlabel pada baris 1 adalah kolom 2 dan 3, maka d(B) = a12 + l1 = 3 + 0 = 3 d(C) = a13 + l1 = 4 + 0 = 4 Langkah 3 Karena min {d(B), d(C)} = min {3, 4} = 3 maka diperoleh l 2 = 3. Tuliskan label tersebut pada baris dan kolom 2. Langkah 4 Dari baris 2, kolom yang belum berlabel adalah kolom 3,4, dan 5 dan didapatkan tabel baru yaitu:

0 3

0 A 3 4

3 33 B 2 7 6

44 2 C 5 4

7 5 D 2 4 4

6 4 2 E 6 4

4 6 F 2 2 3

4 4 2 G 4 5

2 4 H 2

3 5 2 I

Tabel 2.3.3 Tabel setelah iterasi pertama

Iterasi 2 Langkah 2 Kolom yang belum berlabel pada baris 2 adalah kolom 3, 4 dan 5, maka d(C) = a23 + l2 = 2 + 3 = 5 d(D) = a24 + l 2 = 7 + 3 = 10 d(E) = a25 + l2 = 6 + 3 = 9

29


Langkah 3 Karena min {d(C), d(D), d(E)} = min {5, 10, 9} = 5 maka diperoleh l 3 = 5. Tuliskan label tersebut pada baris dan kolom 3. Langkah 4 Dari baris 3, kolom yang belum berlabel adalah kolom 4 dan 5 dan didapatkan tabel baru yaitu:

0 3 4

0 A 3 4

3 33 B 2 7 6

4 44 25 C 5 4

710 5 D 2 4 4

69 4 2 E 6 4

4 6 F 2 2 3

4 4 2 G 4 5

2 4 H 2

3 5 2 I

Tabel 2.3.4 Tabel setelah iterasi kedua

Iterasi 3 Langkah 2 Kolom yang belum berlabel pada baris 3 adalah kolom 4 dan 5, maka d(D) = a34 + l 3 = 5 + 4 = 9 d(E) = a35 + l3 = 4 + 4 = 8 Langkah 3 Karena min {d(D), d(E)} = min {9, 8} = 8 maka diperoleh l 5 = 8. Tuliskan label tersebut pada baris dan kolom 5.

30


Langkah 4 Dari baris 5, kolom yang belum berlabel adalah kolom 4, 6 dan 7, dan didapatkan label baru yaitu:

0 3 4 8

0 A 3 4

3 33 B 2 7 6

4 44 25 C 5 4

8 710 59 D 2 4 4

69 48 2 E 6 4

4 6 F 2 2 3

4 4 2 G 4 5

2 4 H 2

3 5 2 I

Tabel 2.3.5 Tabel setelah iterasi ketiga

Iterasi 4 Langkah 2 Kolom yang belum berlabel pada baris 5 adalah kolom 4, 6 dan 7, maka d(D) = a54 + l 5 = 2 + 8 = 10 d(F) = a56 + l5 = 6 + 8 = 14 d(G) = a57 + l 5 = 4 + 8 = 12 Langkah 3 Karena min {d(D), d(F), d(G)} = min {10, 14, 12} = 10 maka diperoleh l 4 = 10. Tuliskan label tersebut pada baris dan kolom 4. Langkah 4 Dari baris 4, kolom yang belum berlabel adalah kolom 6 dan 7, dan didapatkan label baru yaitu:

31


0 3 4 9 8

0 A 3 4

3 33 B 2 7 6

4 44 25 C 5 4

9

8

710 59 D 210 4 4

69 48 2 E 6 4

4 614 F 2 2 3

4 412 2 G 4 5

2 4 H 2

3 5 2 I

Tabel 2.3.6 Tabel setelah iterasi ke empat

Lanjutkan iterasi dengan cara yang sama, maka pada iterasi ke 9 akan didapatkan tabel yang memuat jalur terpendek dari simpul A ke simpul I yaitu

0 3 4 9 8 13 12 15 16

0 A 3 4

3 33 B 2 7 6

4 44 25 C 5 4

9

8

710 59 D 210 4 4

69 48 2 E 6 4

13

12

15

16

413 614 F 2 2 3

413 412 2 G 4 5

215 416 H 2

316 517 217 I

Tabel 2.3.7 Tabel setelah algoritma Djikstra selesai

Label pada baris dan kolom 9 merupakan jumlah jalur terpendek yang dapat dilalui dari simpul A ke simpul I dengan jumlah jarak 16. Dari Tabel 2.3.6 dapat digambarkan pohon perentang yang menghubungkan simpul A ke simpul I dalam bentuk jaringan sebagai berikut

32


Gambar 2.3.2 Pohon perentang pada jaringan

jalur terpendek dari jaringan yang menghubungkan simpul awal, simpul A ke simpul akhir, simpul I adalah jalur P: {A, C, D, F, I} dengan panjang jalur adalah 16, seperti yang ditunjukkan pada gambar sebagai berikut

Gambar 2.3.3 jalur terpendek pada jaringan

33


BAB III MASALAH ARUS MAKSIMUM

Masalah jalur terpendek (shortest path problems) dan masalah arus maksimum (maximal flow problems) merupakan dua masalah khusus dan penting yang muncul sebagai masalah pada jaringan. Kedua masalah tersebut serupa dan saling melengkapi tetapi juga berbeda karena masalah tersebut memunculkan aspek yang berbeda dari suatu jaringan. Masalah jalur terpendek memunculkan masalah tentang jarak pada busur tanpa menyinggung tentang kapasitasnya. Sedangkan masalah arus maksimum memunculkan masalah tentang kapasitas busur tanpa menyinggung tentang jarak pada busur. Masalah arus maksimum bertujuan untuk mencari jumlah arus yang melewati jaringan, memenuhi syarat-syarat tertentu dan jumlahnya maksimum. Masalah arus maksimum merupakan salah satu persoalan yang sering kali muncul dalam suatu jaringan. Salah satu contoh masalah arus maksimum yang ditemukan dalam kehidupan sehari-hari adalah sebagai berikut. Sebagai bagian dari rencana pembangunan nasional suatu negara, kotakota dalam negara tersebut harus memutuskan sendiri penggunaan energinya. Misalkan pada suatu kota terdapat empat macam bahan mentah, yaitu minyak mentah, batubara, uranium dan tenaga air. Untuk menjalankan aktifitas seharihari, penduduk kota tersebut membutuhkan empat macam energi dasar, yaitu energi listrik, minyak tanah, petroleum, dan gas. Karena kota tersebut sudah

34


memiliki pusat teknologi dan infrastruktur sendiri maka dimungkinkan untuk mengolah bahan-bahan mentah tersebut menjadi bentuk-bentuk energi lain seperti yang dibutuhkan oleh penduduk. Misalnya minyak mentah dapat diolah menjadi minyak tanah atau petroleum. Batu bara dapat diubah menjadi energi listrik dan sebagainya seperti yang ditunjukkan pada gambar berikut Diolah menjadi Bentuk energi

Bahan mentah Minyak mentah

Energi listrik

Batu bara

Minyak tanah

Uranium

Petroleum

Tenaga air

Gas

Gambar 3.1 Skema pengolahan bahan-bahan mentah menjadi suatu bentuk energi

35


Keterangan gambar : s=

tambang atau tempat diambilnya bahan-bahan mentah tersebut.

t = rumah-rumah penduduk yang membutuhkan energi-energi tersebut untuk menjalankan aktifitas sehari-hari

Pada contoh di atas, yang menjadi permasalahan adalah bagaimana mencari hasil olahan dari bahan-bahan mentah tersebut dalam jumlah yang maksimum agar kebutuhan penduduk kota akan energi terpenuhi.

Misalkan terdapat sebuah jaringan G:(N,A) dengan kapasitas Cij tak negatif pada setiap busur (i,j)A. Masalah arus maksimum dari simpul awal s menuju simpul akhir t dapat ditulis sebagai Maksimumkan val(F) Dengan kendala val ( f )  f ij fji 0  jN jN val( f ) 

untuk i s i N {s, t } untuk i t

dan 0 fij Cij (i, j) A dengan fij adalah arus pada busur (i,j) dan Cij adalah kapasitas busur (i,j)

Berikut ini diberikan beberapa asumsi yang digunakan dalam mencari penyelesaian masalah arus maksimum dalam penulisan ini:

36


Asumsi 3.1 Jaringan yang digunakan untuk memodelkan suatu masalah adalah jaringan berarah.

Asumsi ini selalu dapat dipenuhi dengan mengubah jaringan tak berarah menjadi jaringan berarah. Sebuah busur tak berarah (i,j) dengan kapasitas Cij memindahkan arus dari simpul i ke simpul j atau dari simpul j ke simpul i. Maka pada masalah arus maksimum dengan model busur tak berarah adalah mempunyai kendala f ij ≤Cij atau fji ≤Cji.

Karena nilai dari Cij ≥0, pada beberapa masalah arus maksimum pada jaringan, diperoleh penyelesaian optimal, yakni salah satu dari fij dan f ji akan sama dengan nol. Penyelesaian semacam ini disebut non-over lapping. Pada pembahasan di sini busur tidak berarah yang menghubungkan simpul i dan j dinotasikan sebagai {i,j}. Diasumsikan arus pada busur {i,j} mempunyai batas bawah nol. Untuk mentransformasi busur tak berarah menjadi busur yang berarah, setiap busur tak berarah {i,j} diubah menjadi dua busur berarah (i,j) atau (j,i) yang masing-masing mempunyai nilai arus fij atau fji dan kapasitas busur Cij atau Cji. Untuk setiap arus non-overlapping pada jaringan mula-mula, yakni salah satu dari arus yang mengalir pada busur bernilai nol, akan berlaku sebagai berikut.

37


(i).

Jika busur tak berarah {i,j} mengalirkan αunit arus pada simpul i ke simpul j pada jaringan yang sudah ditransformasi maka ditulis arus fij = αdan arus f ji = 0.

(ii). Jika busur tak berarah {i,j} mengalirkan αunit arus pada simpul j ke simpul i pada jaringan yang sudah ditransformasi maka ditulis arus fij = 0 dan arus f ji = α. (iii). Jika f ij dan fji masing-masing adalah arus pada busur (i,j) dan (j,i) pada jaringan berarah, maka fij – fji atau fji – fij bersesuaian dengan arus pada busur {i,j} pada jaringan tak berarah dengan nilai yang positif yang dapat dinyatakan sebagai berikut. f ij fji  f i, j0 f ji fij 

jika fij f ji jika fij fji jika fji f ij

Asumsi 3.2 Semua kapasitas busur dalam jaringan adalah bilangan bulat tak negatif.

Pada kenyataannya asumsi tentang kapasitas busur yang berupa bilangan bulat ini tidak terlalu mengikat apabila digunakan penghitungan menggunakan komputer karena perhitungan tetap dapat dijalankan walaupun kapasitas busur merupakan bilangan rasional. Meskipun aturan tentang asumsi tersebut tidak terlalu mengikat pada beberapa proses perhitungan tetapi asumsi tentang kapasitas dari suatu busur yamg merupakan bilangan bulat penting bagi proses perhitungan lainnya.

38


Asumsi 3.3 Jaringan tidak memuat suatu jalur yang menghubungkan simpul awal s menuju simpul akhir t dengan busur-busur yang memiliki kapasitas tak terbatas.

Jika setiap busur pada jalur berarah P yang menghubungkan simpul s ke t mempunyai kapasitas tak hingga, maka nilai arus maksimum tak terbatas. Adanya kapasitas yang tak terbatas pada jalur dapat dideteksi menggunakan search algorithm. Namun dalam penulisan ini tidak akan dibahas tentang search algorithm lebih lanjut.

Asumsi 3.4 Jaringan tidak memuat busur paralel, yaitu dua atau lebih busur dengan ujung dan awal yang sama.

Dalam memodelkan suatu masalah menjadi bentuk jaringan ditentukan bahwa dua buah simpul dapat dihubungkan secara langsung hanya oleh satu busur. Busur tersebut menyatakan satu kegiatan dilakukan sebelum kegiatan lainnya. Namun kadang terjadi bahwa dua buah kegiatan dapat dilakukan bersamaan waktunya dan dalam jaringan akan memunculkan dua buah simpul dihubungkan lebih dari satu busur. Untuk mengatasi hal tersebut digunakan suatu kegiatan semu (dummy activities) diantara kedua simpul tersebut. Kegiatan semu tersebut merupakan kegiatan yang tidak sebenarnya terjadi pada busur yang terhubung dan ditetapkan nilainya sama dengan nol.

39


Beberapa metode yang digunakan dalam mencari penyelesaian arus maksimum diantaranya adalah metode Ford-Fulkerson dan metode max flow-min cut.

A. metode Ford-Fulkerson Definisi 3.1.1 Jika {u0, u1, ..., un } dan {a1, a2, ...., an} masing-masing merupakan simpul-simpul dan busur-busur pada jaringan G:(N,A) maka barisan berhingga dengan suku-suku yang berselang-seling antara simpul dan busur pada jaringan tersebut didefinisikan sebagai berikut Q: u0, a1, u1 , a2 , ......, un-1, an , un Barisan tersebut

diawali dengan simpul u0 dan berakhir dengan simpul un

sedemikian hingga tidak ada simpul-simpul yang berulang pada barisan Q. Busur ai = ( ui, ui-1 ) atau ai = ( ui-1, ui ) untuk i = 1, 2, ....., n merupakan busur-busur pada barisan Q.

Definisi 3.1.2 Misalkan f merupakan arus pada jaringan G:(N,A) dengan underlying digraf D dan fungsi kapasitas C. Jalur u0, a1, u 1, a2,....., u n-1, an, un pada D dikatakan mempunyai arus f tak jenuh ( f-unsaturated) jika untuk setiap 1≤i ≤n berlaku a.

ai = ( ui-1, ui ) dan f(ai) < C(ai) Dengan f(ai) merupakan arus pada busur ai dan C(ai) merupakan kapasitas pada busur ai .

40


b.

ai = ( ui , ui-1 ) dan f(ai) > 0 Jika kondisi (a) dipenuhi maka masih ada arus yang dapat dialirkan dari simpul ui-1 ke simpul ui. Jika kondisi (b) dipenuhi maka arus dari simpul ui ke simpul ui-1 dapat dialirkan kembali dari simpul ui-1 ke simpul ui .

Definisi 3.1.3 Jika Q mempunyai arus f tak jenuh pada jalur yang menghubungkan simpul awal ke simpul akhir dari jaringan G:(N,A) maka Q disebut flow augmenting path.

Definisi 3.1.4 Misalkan G:(N,A) merupakan jaringan dengan underlying digraf D, fungsi kapasitas C dan arus f. Jika f bukan merupakan arus maksimum maka D memuat flow augmenting path yang disimbolkan dengan Q yakni. Q: s = u0, a1 , u1, a2 , u2 , ......, un-1, an, un = t Kapasitas residual (residual capacities), (ai) pada D didefinisikan sebagai berikut ui 1, ui C (ai) f ( ai) jika ai  (ai)  jika ai  ui ,ui 1  f (ai) Misalkan = min { (ai ) | 1 ≤i ≤n} dan f* adalah arus baru yang ditentukan dari f , maka nilai dari f* dinyatakan sebagai berikut f ( a)  jika a (ui 1, ui ) untuk 1 i n  f * (a ) f ( a)  jika a (ui, ui 1) untuk 1 i n f ( a) jika a N (Q) 

41


Jika aj merupakan busur pada Q sedemikian hingga (aj ) = , maka f *(aj) = f(aj) + disebut busur jenuh (saturation arc). Dapat dikatakan bahwa nilai f * didapatkan dengan menjumlahkan nilai arus f dengan nilai kapasitas residual pada busur-busur yang terdapat di flow augmenting path.

Lemma 3.1.5 Semua kapasitas residual pada setiap iterasi merupakan bilangan bulat

Bukti Perhatikan kembali persamaan (3.4) untuk kapasitas residual, yakni ui 1, ui C (ai) f ( ai) jika ai  (ai)  jika ai  ui ,ui 1  f (ai) Pada iterasi pertama, lemma bernilai benar karena diasumsikan semua data tentang kapasitas dan arus berupa bilangan bulat. Kapasitas residual pada iterasi pertama berupa bilangan bulat. Diasumsikan bahwa lemma bernilai benar setelah k – 1 iterasi pertama. Perhatikan iterasi ke k sepanjang flow augmenting path P. Kapasitas residual (ai) yang dihitung dari jalur P tersebut merupakan nilai kapasitas residual minimum dari busur tak jenuh yang menyusun flow augmenting path. Karena diketahui bahwa pada iterasi ke k- 1 kapasitas residual berupa bilangan bulat maka data tentang kapasitas busur dan arus baru yang dihitung pada iterasi k-1 juga bernilai bilangan bulat. Dari situ dapat dilihat bahwa nilai kapasitas residual pada iterasi ke k juga akan berupa bilangan bulat.

42


Terbukti bahwa Semua kapasitas residual pada setiap iterasi merupakan bilangan ■

bulat

Untuk mendapatkan arus maksimum dengan menggunakan Metode Ford-Fulkerson, pertama cari

flow augmenting path yang menghubungkan

simpul awal dengan simpul akhir pada jaringan. Kemudian cari kapasitas residual pada masing-masing busur penyusun flow augmenting path tersebut. Dari masingmasing kapasitas resuidual, carilah nilai minimumnya, selanjutnya nilai minimum dari kapasitas residual digunakan untuk menambah arus yang mengalir untuk busur maju dan mengurangi arus untuk busur mundur pada jaringan. Setelah didapat nilai arus yang baru proses berulang kembali dengan mencari flow augmenting pada jaringan. Jika tidak dapat ditemukan flow augmenting tersebut maka proses mencari arus maksimum dengan metode Ford-Fulkerson dihentikan karena telah ditemukan arus maksimum.

Dalam melakukan metode Ford-Fulkerson akan lebih mudah jika jaringan berarah yang diketahui diubah menjadi bentuk matriks. Perubahan jaringan berarah G:(N,A) dengan jumlah simpul n buah menjadi bentuk matriks n x n dapat dilakukan sebagai berikut : 1. Pada diagonal utama matriks, tuliskan semua simpul pada jaringan. 2. Pada sudut kiri bawah matriks, yaitu pada sel (n,1) tuliskan kapasitas arus yang dapat masuk ke simpul akhir jaringan.

43


3. Pada sudut kanan atas matriks, yaitu pada sel (1,n) tuliskan angka nol dan nilai yang

berada

pada

entri

tersebut

merupakan

variabel

yang

akan

dimaksimumkan yaitu arus pada jaringan. 4. Untuk suatu busur (i,j), maka elemen pada sel (i,j) adalah aij = Cij Dengan C ij : besarnya kapasitas pada busur (i,j) Setelah matriks terbentuk, maka selanjutnya dilakukan metode FordFulkerson dengan ketentuan sebagai berikut : 1. Tandai simpul awal jaringan, yakni sel (1,1) dengan label m = 0. 2. Pilih salah satu sel (i, j), yaitu semua simpul yang dapat dilewati oleh busur yang berasal dari simpul awal dengan arus positif, yaitu Cij > 0. 3. Tandai sel (j, j) yang bersesuaian dengan Cij > 0 pada Langkah 2 dengan label m = m + 1. 4. Tentukan simpul j menjadi simpul pangkal busur, yaitu ibaru = j. Kemudian lanjutkan cara penandaan titik seperti Langkah 2 di atas. 5. Jika titik akhir (sink) dapat ditandai ikuti jalur dari titik akhir tersebut melalui titik-titik yang bertanda lebih kecil hingga mencapai titik awal. Jalur dari titik awal ke titik akhir tersebut dinamakan flow-augmenting. Jika proses penandaan titik-titik tersebut berhenti tanpa mencapai titik akhir , maka tidak ada jalur flow-augmenting dari titik awal ke titik akhir. Maka metode Ford Fulkerson berhenti. Jika jalur flow-augmenting ada, Hitung jumlah kapasitas residual dari setiap busur pada jalur tersebut dari titik awal ke titik akhir. Kembali ke Langkah 1.

44


Diagram alir dari metode Ford-Fulkerson.

Tandai sel (1,1) dengan label m=0

Untuk m = 1,2,...,n Pilih (i,j) dengan fij > 0 ?

Tandai sel (j,j) dengan label m = m + 1

tidak

Tentukan i = j j=n? dengan n = banyak simpul

ya Stop

45


Setelah melakukan proses pelabelan, maka selanjutnya perlu dilakukan proses perhitungan kembali terhadap nilai arus pada matriks dengan langkahlangkah sebagai berikut : 1) Lacak jalur P yang menghubungkan simpul awal hingga simpul akhir pada matriks dengan mengikuti label-label pada simpul. Jika terdapat flow augmenting path yang menghubungkan simpul awal ke simpul akhir maka sel (n,n) terhubung dengan sel (1,1). Perhatikan bahwa selsel yang berisi kapasitas arus dengan kendala kapasitas positif, merupakan arus maksimum yang dapat mengalir pada jalur. Tandai nilai-nilai tersebut dengan tanda minus, yakni Cij-. Juga sel (n,1) yang merupakan kapasitas busur yang masuk ke simpul akhir pada jaringan. 2) Tandai dengan tanda positif, sel-sel yang simetris dengan sel-sel yang sudah ditandai dengan tanda minus. Jika sel (i,j) diberi tanda minus maka sel (j,i) diberi tanda positif, dengan kata lain untuk suatu Cij - maka terdapat Cij+ 3) Cari nilai arus minimum yang dapat mengalir pada sel-sel dengan tanda minus, yakni min {(ai)}, untuk (i,j) P ui 1, ui C (ai) f ( ai) jika ai  dengan (ai)  jika ai  ui ,ui 1  f (ai) 4) Hitung nilai arus baru, yakni Cij -* = Cij- - min {(ai)} dan Cij +* = Cij+ + min {(ai)} 5) Didapatkan matriks baru, kembali ke metode Ford-Fulkerson.

46

(3.4)


Diagram alir proses penghitungan kembali nilai dari flow augmenting path (F.A.P) tidak

Jalur s-t F.A.P? ya

Beri tanda minus pada sel-sel dengan (ai ) > 0 dengan C( a i) f (a i) jika a i  ui 1,u i  (a i )  jika a i  ui ,u i 1 f ( a i)

Beri tanda positif sel-sel yang simetris dengan sel-sel bertanda negatif

Cari nilai minimum (ai) pada sel-sel bertanda negatif

Pada sel bertanda negatif, Cij-* = Cij – min {(ai)} Pada sel bertanda positif, Cj i+* = C ij + min {(ai )}

Buat matriks baru

Metode Ford -Fulkerson

47

stop


Teorema Banyaknya iterasi dari metode Ford-Fulkerson adalah berhingga.

Bukti Pada jaringan G:(N,A), kapasitas terkecil dari setiap busur penyusun flow augmenting path adalah satu. Dalam perhitungan kembali arus pada setiap iterasi, arus pada busur (s,j) akan berkurang sejumlah kapasitas residual minimum untuk setiap simpul j. Namun kapasitas residual yang sama tidak akan menambah arus pada busur (s,i) untuk setiap simpul i, dengan i j . Pada iterasi selanjutnya, jumlah kapasitas residual dari busur-busur yang keluar dari simpul awal s akan terus berkurang hingga pada suatu saat didapat kapasitas residual sama dengan nol.

48


Contoh 3.1.1 Carilah arus maksimum dari jaringan

berarah, G:(N,A) dengan

menggunakan metode Ford-Fulkerson.

Gambar 3.1.1 Jaringan berarah G

Penyelesaian Jaringan dengan 7 simpul diatas dapat ditulis kembali dalam bentuk matriks 7 x 7 yaitu :

49


s

8 a

2

9

0

6 b

6 c

4

6

4

d 5

3 e

2 f

17

8 t

Tabel 3.1.1 Jaringan dalam bentuk matriks

Iterasi 1 Proses pelabelan Ford-Fulkerson Langkah 1 Tandai sel (1,1) yang merupakan simpul awal pada jaringan dengan label 0. Tuliskan label tersebut sebagai indeks atas simpul s. Langkah 2 Dari baris 1, simpul s terhubung dengan simpul a, c dan e. kapasitas masing-masing busur tersebut busur (s,a) yaitu Csa = 8, busur (s,c) yaitu Csc = 2 dan busur (s,e) yaitu Cse = 9. Dipilih busur (s,a) dengan nilai arus Csa = 8. Pada sel (2,2), simpul a diberi label 1 dan ditulis sebagai indeks atas simpul.

50


Langkah 3 Dari baris 2, simpul a terhubung dengan simpul b. Nilai arus dari busur tersebut adalah Cab = 6. Pada sel (3,3), simpul b diberi label 2 dan ditulis sebagai indeks atas simpul. Langkah 4 Lanjutkan cara pelabelan seperti diatas. Akan didapatkan pada iterasi pertama pelabelan simpul akhir mendapat label 3 dan tidak dapat lagi ditemukan simpul dengan kapasitas residual positif. Langkah 5 Simpul akhir G sudah mendapat label. Proses pelabelan Ford Fulkerson pada iterasi pertama selesai, flow augmenting pada iterasi pertama ini adalah P 1 = {s,a,b,t}. Maka didapat tabel baru yaitu:

s0

8 a1

2

9

0

6 b2

C1 =

6 c

4

6

4

d 5

3 e

2 f

8 t3

17

Tabel 3.1.2 Pelabelan Ford Fulkerson pada Iterasi 1

51


Selanjutnya akan dihitung arus yang mengalir pada jalur tersebut dengan cara: Penghitungan nilai arus pada flow augmenting path

Langkah 1 Jalur yang menghubungkan simpul awal dan simpul akhir, yaitu P 1 = {s,a,b,t}. Tandai sel-sel yang berisi nilai arus pada flow augmenting path tersebut dengan tanda negatif, yakni pada sel (1,2), sel (2,3), sel (3,8) dan sel (8,1). Langkah 2 Berikan tanda positif pada sel-sel yang simetris dengan Cij , yakni sel (2,1), sel (3,2), sel (8,3) dan sel (1,8). Langkah 1 dan 2 dapat dilihat seperti pada tabel berikut:

s0

8-

+

a1

6-

+

b2

2

C1 =

0+

9

6c

4

6

4

d 5

3 e

2 f

17-

8 t3

+

Tabel 3.1.3 Penelusuran jalur dan pemberian tanda pada Iterasi 1

52


Langkah 3 Nilai minimum dari flow augmenting path adalah min {Csa , Cab , Cbt , Cts} = C ab = Cbt = 6 Langkah 4 Tentukan nilai arus yang baru (i)

Untuk sel-sel bertanda negatif Csa * = Csa – 6 = 8 – 6 = 2 Cab* = Cab – 6 = 6 – 6 = 0 Cbt * = Cbt – 6 = 6 – 6 = 0 Cts * = Cts – 6 = 17 – 6 = 11

(ii)

Untuk sel-sel bertanda positif Cas * = Cas + 6 = 0 + 6 = 6 Cba* = Cba + 6 = 0 + 6 = 6 Ctb * = Ctb + 6 = 0 + 6 = 6 Cst * = Cst + 6 = 0 + 6 = 6

Langkah 5 Proses penghitungan kembali nilai arus dari flow augmenting path selesai, maka didapatkan tabel baru. Lanjutkan kembali dengan poses pelabelan Ford Fulkerson.

53


Iterasi 2 Proses pelabelan Ford Fulkerson Dengan cara yang sama dengan langkah-langkah pelabelan Ford Fulkerson pada iterasi pertama diperoleh flow augmenting path

pada iterasi

kedua ini yaitu P2 = {s,e,d,t} maka didapatkan tabel baru yaitu : s0

2

2

a 6

2

9

6

b c

4

4

C2 = 6

d2 5

3 e1

2 f

11

8 t3

6


Selanjutnya akan dihitung arus yang mengalir pada jalur tersebut dengan cara: Penghitungan nilai arus pada flow augmenting path Langkah 1 Jalur yang menghubungkan simpul awal dan simpul akhir, yaitu P 2 = { s,e,d,t }. Tandai sel-sel yang berisi nilai arus pada flow augmenting path tersebut dengan tanda negatif, yakni pada sel (1,6), sel (6,5), sel (5,8) dan sel (8,1).

54


Langkah 2 Berikan tanda positif pada sel-sel yang simetris dengan Cij , yakni sel (6,1), sel (5,6), sel (8,5) dan sel (1,8). Langkah 1 dan 2 dapat dilihat seperti pada tabel berikut: s0

2

2

a

9-

2

6

6+

b c

C2 = 6 +

4

4

d2

+

5-

e1

32 f

11-

6

+

8 t3


Langkah 3 Nilai minimum dari flow augmenting path adalah min {Cse, Ced , Cdt, Cts} = Cdt = 3 Langkah 4 Tentukan nilai arus yang baru (i)

sel-sel bertanda negatif Cse* = Cse – 3 = 9 – 3 = 6 Ced * = Ced – 3 = 5 – 3 = 2

55


Cdt * = Cdt – 3 = 3 – 3 = 0 Cts * = Cts – 3 = 11 – 3 = 9 (ii)

Untuk sel-sel bertanda positif Ces * = Ces + 3 = 0 + 3 = 3 Cde* = Cde + 3 = 0 + 3 = 3 Ctd * = Ctd + 3 = 0 + 3 = 3 Cst * = Cst + 3 = 6 + 3 = 9

Langkah 5 Proses penghitungan kembali nilai arus dari flow augmenting path selesai, maka didapatkan tabel baru. Lanjutkan kembali dengan proses pelabelan Ford Fulkerson.

Iterasi 3 Proses pelabelan Ford Fulkerson Dengan cara yang sama dengan langkah-langkah pelabelan Ford Fulkerson pada iterasi pertama diperoleh flow augmenting path ketiga ini yaitu P3 = {s,e,f,t} maka didapatkan tabel baru yaitu :

56

pada iterasi


s0

2

2

a 6

2

9

b c 6

C3 =

6

3

4

4

d

3

2

e1

2 f2

9

6

3

8 t3


Selanjutnya akan dihitung arus yang mengalir pada jalur tersebut dengan cara: Penghitungan nilai arus pada flow augmenting path Langkah 1 Jalur yang menghubungkan simpul awal dan simpul akhir, yaitu P 3 = { s,e,f,t}. Tandai sel-sel yang berisi nilai arus pada flow augmenting path tersebut dengan tanda negatif, yakni pada sel (1,6), sel (6,7), sel (7,8) dan sel (8,1). Langkah 2 Berikan tanda positif pada sel-sel yang simetris dengan Cij , yakni sel (6,1), sel (7,6), sel (8,7) dan sel (1,8). Langkah 1 dan 2 dapat dilihat seperti pada tabel berikut:

57


s0

2

2

a 6

9+

b c

C3 = 6 3+

9-

6-

2

6

4

4

d

3

2

e1

2-

+

f2

8

+

t3

3


Langkah 3 Nilai minimum dari flow augmenting path adalah min {Cse, Cef , Cft, Cts} = C13 = Cef = 2 Langkah 4 Tentukan nilai arus yang baru (i)

Untuk sel-sel bertanda negatif Cse* = Cse – 2 = 6 – 2 = 4 Cef* = Cef – 2 = 2 – 2 = 0 Cft* = Cft – 2 = 8 – 2 = 6 Cts * = Cts – 2 = 9 – 2 = 7

(ii)

Untuk sel-sel bertanda positif Ces * = Ces + 2 = 3 + 2 = 5

58


Cfe* = Cfe + 2 = 0 + 2 = 2 Ctf* = Ctf + 2 = 0 + 2 = 2 Cst * = Cst + 2 = 9 + 2 = 11 Langkah 5 Proses penghitungan kembali nilai arus dari flow augmenting path selesai, maka didapatkan tabel baru. Lanjutkan kembali dengan proses pelabelan Ford Fulkerson.

Iterasi 4 Proses pelabelan Ford Fulkerson Dengan cara yang sama dengan langkah-langkah pelabelan Ford Fulkerson pada iterasi pertama diperoleh flow augmenting path keempat ini yaitu P4 = {s,c,f,t} maka didapatkan tabel baru yaitu :

s0

2

2

a 6

2

4

11

b c1

4

4

C4 = 6

3

2

e

5

d

2 7

6

3

f2

6 t3


59

pada iterasi


Selanjutnya akan dihitung arus yang mengalir pada jalur tersebut dengan cara: Penghitungan nilai arus pada flow augmenting path Langkah 1 Jalur yang menghubungkan simpul awal dan simpul akhir, yaitu P 4 = {s,c,f,t}. Tandai sel-sel yang berisi nilai arus pada flow augmenting path tersebut dengan tanda negatif, yakni pada sel (1,4), sel (4,7), sel (7,8) dan sel (8,1). Langkah 2 Berikan tanda positif pada sel-sel yang simetris dengan Cij , yakni sel (4,1), sel (7,4), sel (8,7) dan sel (1,8). Langkah 1 dan 2 dapat dilihat seperti pada tabel berikut: s0

2

2

a 6

2-

b c1

+ C4 =

4-

4

6

d

3

2

e

5 + 7-

11+

4

2

6

3

f2

6-

+

t3


60


Langkah 3 Nilai minimum dari flow augmenting path adalah min {Csc, Ccf, Cft,Cts } = Csc = 2 Langkah 4 Tentukan nilai arus yang baru (i)

Untuk sel-sel bertanda negatif Csc* = Csc – 2 = 2 – 2 = 0 Ccf * = Ccf – 2 = 4 – 2 = 2 Cft* = Cft – 2 = 6 – 2 = 4 Cts * = Cts – 2 = 7 – 2 = 5

(ii)

Untuk sel-sel bertanda positif Ccs* = Ccs + 2 = 0 + 2 = 2 Cfc * = Cfc + 2 = 0 + 2 = 2 Ctf* = Ctf + 2 = 0 + 2 = 2 Cst * = Cst + 2 = 11 + 2 = 13

Langkah 5 Proses penghitungan kembali nilai arus dari flow augmenting path selesai, maka didapatkan tabel baru.

61


Iterasi 5 s

2

2

a 6

C5 =

4

b

2

c

4

6 5

2

d

3

2

e

2 5

13

2

6

3

f

4

2

t

Tabel 3.1.10 Tabel iterasi 5

Pada iterasi ke 5 sudah tidak dapat ditemukan flow-augmenting path yang menghubungkan simpul s sebagai simpul awal ke simpul t sebagai simpul akhir. Pada sudut kanan atas nilai variabel yang akan dimaksimumkan terdapat nilai sebesar 13, maka dengan menggunakan metode Ford-Fulkerson didapat nilai arus maksimum adalah 13.

Selain menggunakan metode pelabelan Ford Fulkerson masih ada cara lain yang sering digunakan untuk mencari penyelesaian masalah arus maksimum pada jaringan yaitu metode max flow-min cut.

62


B. metode max flow-min cut

Definisi 3.2.1 Pada suatu jaringan G:(N,A), potongan (s,t) merupakan partisi dari simpul-simpul pada jaringan, yang membagi jaringan tersebut menjadi dua himpunan bagian tak kosong yang saling asing yaitu himpunan S dan T. Pada kedua himpunan tersebut berlaku bahwa simpul awal berada di himpunan S dan simpul akhir berada di himpunan T.

Definisi 3.2.2 Kapasitas dari potongan (s,t) ditulis sebagai cap(S,T) merupakan jumlahan kapasitas semua busur-busur pada potongan (s,t) dan ditulis sebagai. cap(S,T) =

C

ij

iS , jT

Setiap jalur (path) dari s ke t memuat busur yang menghubungkan simpul pada himpunan S ke simpul pada himpunan T. Jika setiap busur yang menghubungkan S ke T dipotong, maka tidak ada jalur yang menghubungkan s ke t. Dengan kata lain arus barang atau informasi dari s ke t dikatakan terpotong.

Teorema 3.2.1 Pada sebarang jaringan berarah, nilai dari arus (s,t) tidak akan pernah melampaui kapasitas dari sebarang potongan (s,t). Bukti

63


Misalkan F = {fij } merupakan sebarang arus-(s,t) dan {S,T} merupakan sebarang potongan (s,t). Konservasi arus menyatakan bahwa

f f ij

i , jN

0 untuk setiap iS, i s dan i t

ji

(3.2.1)

i , jN

Maka

f f

val(F) =

sj

js

jN

=

jN



 f f iS

ij

jN

ji

jN

   

Menurut konservasi arus, bagian yang berada dalam tanda kurung sama dengan nol kecuali untuk i = s, maka

f

val(F) =

ij

iS , jN

 f ji iS , jN

Karena {S,T} merupakan partisi dari simpul pada jaringan G:(N,A) maka persamaan di atas dapat ditulis val(F) =



fij 

iS , j S ,T 

=

f

ij

iS , jS

=

ji

   fij  f ji  fji     iS , jT iS , jS iS , jT  

f

 fji  f ij  f ji

f

 fji  fij fji 

ij

iS , jS

=

f

iS , j{S ,T }

ij

iS , jS

iS , jS

iS , jT

iS , jS

iS , jT

iS , jT

Dua suku pertama dari baris terakhir mempunyai jumlah yang sama, yakni

f

ij

iS , jS

 fji atau iS , jS

64

f

ij

iS , jS

 f ji = 0 iS , jS


Dengan demikian

val(F) = 0  fij f ji iS , jT

=

f f  ij

ji

iS , jT

Menurut definisi tentang arus pada jaringan, yakni fij ≤Cij dan fji ≥0 maka f ij – fji ≤Cij sehingga

f f  C ij

ji

iS , jT

Jadi

ij

iS , jT

val(F) ≤cap(S,T)

Terbukti bahwa pada sebarang jaringan berarah G:(N,A) berlaku nilai arus (s,t) tidak akan pernah melampaui kapasitas dari sebarang potongan (s,t) ■

Akibat 3.2.1 Jika F merupakan sebarang arus-(s,t)

dan {S,T} merupakan sebarang

potongan (s,t) maka val (F )  Cij cap( S ,T ) iS , jT

Akibat 3.2.2 Misalkan F merupakan arus-(s,t) dan {S,T} merupakan potongan (s,t) dengan nilai F sama dengan kapasitas dari {S,T}, maka F merupakan nilai arus maksimum dari sebarang arus-(s,t) dan cap(S,T) merupakan kapasitas minimum dari sebarang potongan (s,t) pada jaringan tersebut.

65


Bukti (1). Misalkan F 1 merupakan sebarang arus. Akan ditunjukkan bahwa F1 ≤F Teorema 3.2.1 menyatakan bahwa F1 ≤cap(S,T) Dari hipotesis diketahui bahwa cap(S,T) = F, maka F1 ≤F = cap(S,T) atau

F 1 ≤F

Jadi F merupakan nilai arus maksimum dari jaringan. (2). Misalkan cap(S`,T`) merupakan kapasitas dari sebarang potongan (s,t). Akan ditunjukkan bahwa cap(S,T) ≤cap(S`,T`) Teorema 3.2.1 menyatakan bahwa F ≤cap(S`,T`) Dari hipotesis diketahui bahwa F = cap(S,T), maka F = cap(S,T) ≤cap(S`,T`) cap(S,T) ≤cap(S`,T`)

atau

Jadi, cap(S,T) merupakan kapasitas minimum dari jaringan.

Hipotesis pada akibat 3.2.2, yaitu cap(S,T) = F selalu dapat dipenuhi. Pada sebarang jaringan berarah akan selalu dapat ditemukan arus-(s,t) dan potongan (s,t) pada jaringan tersebut sedemikian hingga nilai arus-(s,t) merupakan jumlah kapasitas potongan (s,t). Arus-(s,t) yang memenuhi akibat 3.2.2 akan bernilai maksimum.

66


Konstruksi arus untuk mendapatkan arus maksimum pada jaringan Konstruksi arus maksimum ini dilakukan dengan cara mengubah prosedur dari konstruksi arus yang telah dibahas pada bagian sebelumnya dengan tujuan untuk mencari arus maksimum pada jaringan berarah.

Definisi 3.2.3 Diberikan {f ij} yang merupakan arus-(s,t) pada jaringan. Suatu rantai pada jaringan tersebut disebut rantai flow-augmenting jika dan hanya jika fij < Cij untuk setiap busur maju (i,j) dan fij > 0 untuk setiap busur mundur pada rantai.

Definisi 3.2.4 Nilai arus yang digunakan utuk menambah arus pada busur maju dan mengurangi arus pada busur mundur disebut kapasitas residual,

(ai) dan didefinisikan

sebagai berikut: Cij fij (i , j ) busur maju (ai) =  (i, j ) busur mundur f ij

rantai flow augmenting digunakan untuk melakukan penambahanpenambahan pada arus, yakni penambahan nilai arus pada setiap busur maju dan pengurangan nilai arus pada setiap busur mundur sesuai dengan jumlah penambahan pada busur maju. Jumlah terbesar yang dapat digunakan untuk menambah atau mengurangi nilai arus disebut slack dari rantai. Nilai dari Slack ditentukan sebagai berikut:

67


1) Hitung kapasitas yang belum digunakan yaitu Cij – fij untuk setiap busur maju dan arus f ij pada setiap busur mundur. 2) Slack dari rantai adalah nilai minimum dari nilai-nilai yang sudah ditentukan, yakni slack = min {(ai) }, ai A

Teorema (Kondisi optimal untuk arus maksimum) Pernyataan berikut adalah ekivalen 1.

Nilai arus val(F) merupakan arus maksimum.

2.

Tidak dapat ditemukan flow augmenting path pada jaringan G:(N,A).

3.

Terdapat potongan (s,t) dengan cap(S,T) = val(F).

Bukti i).

1 2 Akan dibuktikan bahwa jika nilai arus val(F) merupakan arus maksimum,

maka tidak dapat ditemukan flow augmenting path pada jaringan G:(N,A). Pernyataan tersebut ekivalen dengan pernyataan Jika dapat ditemukan flow augmenting path pada jaringan G:(N,A), maka nilai arus val(F) bukan merupakan arus maksimum. Misalkan

masih

dapat

ditemukan

flow

augmenting

path

yang

menghubungkan simpul awal ke simpul akhir, berarti masih ada arus yang dapat ditambahkan pada masing-masing busur penyusun flow augmenting path tersebut.

68


Jadi jika masih ada arus yang dapat ditambahkan pada flow augmenting path mka nilai arus val(F) bukan merupakan arus maksimum. Jadi terbukti bahwa jika nilai arus val(F) merupakan arus maksimum, maka tidak dapat ditemukan flow augmenting path pada jaringan G:(N,A).

ii).

■

2 3 Akan dibuktikan bahwa jika tidak dapat ditemukan flow augmenting path

pada jaringan G:(N,A), maka terdapat potongan (s,t) dengan cap(S,T) = val(F). Misalkan tidak dapat ditemukan flow augmenting path pada jaringan G:(N,A). Misalkan S merupakan himpunan simpul-simpul yang dapat dicapai dari simpul awal s pada jaringan dan T = N-S sedemikian sehingga tidak ada busur yang menghubungkan simpul pada himpunan S ke simpul pada himpunan T. Didefinisikan arus pada dua buah himpunan tersebut adalah: i S dan j T  f ij Cij i T dan j S  f ij 0

Karena diketahui nilai arus pada potongan (s,t) adalah : val (F )  fij  fji iS , jT

maka

val( F ) 

C

iS , jT

ij

iS , jT

 0

 Cij iS , jT

= cap (S,T)

69

iS , jT


Jadi terbukti bahwa jika tidak dapat ditemukan flow augmenting path pada jaringan G:(N,A), maka terdapat potongan (s,t) dengan cap(S,T) = val(F). ■ iii).

3 1 Akan

dibuktikan

bahwa

jika

terdapat

potongan

(s,t)

dengan

cap(S,T) = val(F), maka nilai arus val(F) merupakan arus maksimum. Misalkan terdapat val(F), yaitu nilai arus dari simpul awal mencapai simpul akhir. Dari asumsi diketahui bahwa val(F) = cap(S,T). Dari Akibat 3.2.2 diketahui bahwa val(F) merupakan nilai arus maksimum. Jadi terbukti bahwa jika terdapat potongan (s,t) dengan cap(S,T) = val(F), maka nilai arus val(F) merupakan arus maksimum.

■

Teorema 3.2.2 (max flow-min cut theorem) Pada jaringan berarah, nilai maksimum dari arus-(s,t) sama dengan kapasitas minimum dari potongan (s,t).

Bukti Dengan menggunakan prosedur dari aturan konstruksi arus untuk mencari arus maksimum, akan dikonstruksikan F yang merupakan arus-(s,t) yang tidak memuat rantai flow augmenting dari s ke t. Akibat 3.2.2 menyatakan bahwa teorema 3.2.2 ini terbukti jika dapat ditemukan partisi {S,T} yang merupakan potongan (s,t) dengan val(F) = cap(S,T).

70


Misalkan S merupakan sebarang himpunan yang dapat dicapai dari rantai flow augmenting yang dimulai dari s (termasuk simpul awal s) dan misalkan T merupakan himpunan dari setiap simpul-simpul sisanya dalam jaringan. Rantai flow- augmenting dari s ke t, maka t S , tetapi t T , sehingga {S,T} merupakan potongan (s,t). Misalkan i sebarang simpul yang berada pada himpunan S dan misalkan j merupakan sebarang simpul yang berada pada himpunan T. Karena iS maka dapat ditemukan rantai flow augmenting dari s ke t. Karena jS dapat disimpulkan bahwa fij = Cij dan fji = 0, dengan kata lain rantai flow augmenting dari s ke i dapat dilanjutkan oleh rantai flow augmenting dari s ke j. Akibat 3.2.1 menyatakan bahwa:

f f 

F=

ij

ji

iS , jT

C 0

=

ij

iS , jT

=

C

ij

iS , jT

= cap(S,T) Maka ditemukan potongan (s,t) dimana kapasitasnya sama dengan F. ■

Terbukti bahwa nilai F maksimum.

Algoritma max flow-min cut Untuk menentukan nilai arus maksimum sekaligus potongan minimum pada jaringan G dengan underlying digraph D:(N,A), simpul awal s, simpul akhir t,

71


kapasitas busur C dan nilai arus F, dapat dilakukan menggunakan cara sebagai berikut: 1. Susunlah digraf D yang memuat jalur s-t serta memenuhi a. himpunan simpul N(D) sama dengan himpunan simpul pada G:(N,A) dan b.

himpunan busur

A( D)   i, j (i , j ) A dan Cij f ijatau A( D)   i, j  (j,i) A dan f ji 0 Didefinisikan sebarang jalur s-t pada digraf D adalah Q: s = u 0, a1, u1, a2, u2, ........, un-1 , an , un = t 2. Langkah ini akan menunjukkan penambahan arus sepanjang flow augmenting path. Q: s = u0, a1 , u1, a2, u2, ........, un-1, an, u n = t merupakan jalur s-t pada digraf D dengan ai merupakan busur dari D, ai = (ui-1, ui) dan C(ai) > f(ai) atau ai = (ui,ui-1) dan f(ai ) > 0 Untuk i = 1, 2, 3, ......., n maka C (ai) f (ai) jika ai (ui 1,ui )  (ai)  jika ai (ui, ui 1) f (ai) Misalkan = min{ i| 1 ≤i ≤n}. Jika ai = (ui-1,ui) maka f(ai ) = f(ai) + , sebaliknya Jika ai = (ui, ui-1) maka f(ai ) = f(ai) -  Setelah penambahan arus selesai dilakukan, kembali ke Langkah 1. Jika tidak dapat ditemukan jalur s-t pada digraf D, lanjutkan ke Langkah 3.

72


3. Langkah ini akan menghasilkan arus maksimum pada jaringan G:(N,A) dan sekaligus menentukan potongan minimum bagi jaringan. Misal P merupakan himpunan dari simpul-simpul pada D maka {P,P`} merupakan potongan minimum. Contoh 3.2.1 Temukan arus maksimum pada jaringan berarah berikut.

Gambar 3.2.1 Jaringan dengan 8 simpul dan 12 busur

Penyelesaian Masalah arus maksimum pada jaringan tersebut akan diselesaikan dengan menggunakan algoritma max flow-min cut Iterasi 1 Langkah 1 Ambil digraf D1` = {s, a, b, t} yang menghubungkan simpul awal s dengan simpul akhir t. Langkah 2

73


Dari digraf D1` diperoleh Q1: s,(s,a),a,(a,b),b,(b,t),t Dapat dilihat

a1 = (s,a) maka 1 = 8 a2 =(a,b) maka 2 = 6 dan a3 = (b,t) maka 3 = 6. Karena = min (8,6,6) = 6, maka f(a1) = f(a2) = f(a3) = 0 + 6 =6 Pada busur-busur (s,a),(a,b) dan (b,t) ditambahkan arus sebesar 6, seperti pada Gambar 3.2.2. Nilai pada setiap busur dinyatakan dengan Cij , fij dengan Cij : merupakan kapasitas busur yang menghubungkan simpul i dan simpul j. f ij : merupakan arus yang mengalir pada busur yang menghubungkan simpul i dan simpul j.

Gambar 3.2.2 Jaringan setelah iterasi pertama

74


Iterasi 2 Langkah 1 Ambil digraf D2 ` = {s, c, d, t} yang menghubungkan simpul awal s dengan simpul akhir t. Langkah 2 Dari digraf D2` diperoleh Q2: s,(s,c),c,(c,d),d,(d,t),t

1 = 2, 2 = 4, 3 = 3 Karena = min (2,4,3) = 2, maka f(a1) = f(a2) = f(a3) = 0 + 2 =2 Pada busur-busur (s,c),(c,d),(d,t) ditambahkan arus sebesar 2. Seperti pada Gambar 3.2.3

Gambar 3.2.3 Jaringan setelah iterasi kedua

75


Iterasi 3 Langkah 1 Ambil digraf D3` = {s, e, f, t} yang menghubungkan simpul awal s dengan simpul akhir t, maka digraf D3` memuat jalur s-t. Langkah 2 Dari digraf D3` diperoleh Q3: s,(s,e),e,(e,f),f,(f,t),t

1 = 9, 2 = 2, 3 = 8 Karena = min (9,2,8) = 2, maka f(a1) = f(a2) = f(a 3) = 0 + 2 =2 Pada busur-busur (s,e),(e,f),(f,t) ditambahkan arus sebesar 2, seperti pada Gambar 3.2.4

Gambar 3.2.4 Jaringan setelah iterasi ketiga

76


Iterasi 4 Langkah 1 Ambil digraf D4 ` = {s, e, d, t} yang menghubungkan simpul awal s dengan simpul akhir t, maka digraf D4` memuat jalur s-t. Langkah 2 Dari digraf D4` diperoleh Q4: s,(s,e),e,(e,d),d,(d,t),t

1 = 9 – 2 = 7, 2 = 5, 3 = 3 - 2 = 1 Karena = min (7,5,1) = 1, maka f(a1) = 2 + 1 = 3, f(a2) = 1, f(a3) = 2 + 1 = 3 Pada busur-busur (s,e),(e,d),(d,t) ditambahkan arus sebesar 1. Seperti pada Gambar 3.2.5

Gambar 3.2.5 Jaringan setelah iterasi keempat

77


Iterasi 5 Langkah 1 Ambil digraf D5` = {s, e, d, c, f, t} yang menghubungkan simpul awal s dengan simpul akhir t, maka digraf D5` memuat jalur s-t. Langkah 2 Dari digraf D5` diperoleh Q5: s,(s,e),e,(e,d),d,(d,c),c,(c,f),f,(f,t),t

1 = 9 – 3 = 6, 2 = 5 – 1 = 4, 3 = 2, 4 = 2, 5 = 8 - 2 = 6 Karena = min (6,4,2,2,6) = 2, maka f(a1) = 3 + 2 = 5, f(a2) = 1 + 2 = 3, f(a3) = 2 - 2 = 0 f(a4) = 2 dan f(a5) = 2 +2 = 4 Pada busur-busur (s,e),(e,d),(c,f),(f,t) ditambahkan arus sebesar 2 dan pada busur (d,c) dikurangi arus sebesar 2, seperti pada Gambar 3.2.6

Gambar 3.2.6 Jaringan setelah iterasi kelima

78


Iterasi 6 Langkah 1 Ambil digraf D6` = {s,a,b,d,e} namun digraf ini tidak menghubungkan antara simpul awal s dan simpul akhir t. Dikatakan bahwa D6` tidak memuat jalur s-t. Algoritma max flow-min cut dilanjutkan dengan Langkah 3. Langkah 3 Pada tahap ini ditemukan potongan (cut)

pada jaringan. Misalkan

S = D`6 = { s,a,b,d,e} dan T = {N(D)-S} = {c, f, t}.

Busur-busur

(s,c),(b,t),(d,t),(e,f) merupakan busur-busur yang memisahkan atau memotong jaringan menjadi dua buah partisi, yaitu himpunan S dan T. Nilai kapasitas dari busur-busur pada potongan (s,t) tersebut merupakan nilai dari minimum cut yang sama dengan nilai arus maksimum pada jaringan yang sama. Algoritma max flow- min cut selesai dan sudah didapatkan nilai maksimum arus sekaligus potongan minimum pada jaringan. Pada jaringan terdapat partisi yaitu S = { s,a,b,d,e } dimana simpul-simpul tersebut dapat dicapai dari simpul awal s oleh rantai flow augmenting dan T = {c, f, t}.

Dengan demikian kapasitas dari cut adalah Csc + Cbt + Cdt + Cef = 2 + 6 + 3 + 2

79


= 13

dan nilai arus maksimum dari jaringan adalah f bt + fdt + fft = 6 + 3 + 4 = 13 Tampak bahwa F = cap(S,T) = 13

Jika contoh 3.1.1 dan contoh 3.2.1 ini diselesaikan dengan menggunakan program Quantitative Management for windows pada komputer didapatkan arus maksimum yang sama, yaitu : Branch name

Start node

Maximal Network Flow

13

End node

Capacity

Reverse capacity

Flow

Branch 1

1

2

8

0

6

Branch 2

1

4

2

0

2

Branch 3

1

6

9

0

5

Branch 4

2

3

6

0

6

Branch 5

4

5

4

0

-2

Branch 6

4

7

4

0

2

Branch 7

6

5

5

0

-2

Branch 8

6

7

2

0

2

Branch 9

5

3

6

0

0

Branch 10

5

8

3

0

3

80


Branch 11

3

8

6

0

6

Branch 12

7

8

8

0

4

Tabel 3.2.1 Contoh 3.1.1 dan contoh 3.2.1 menggunakan program komputer

Namun jumlah iterasi dan flow augmenting path yang dipilih pada program ini berbeda dengan jumlah iterasi dan flow augmenting path yang dipilih pada pengerjaan sebelumnya, seperti pada tabel berikut :

Iteration

Path

Flow

Cumulative Flow

1

1-> 2-> 3-> 8

6

6

2

1-> 6-> 5-> 8

3

9

3

1-> 4-> 5-> 6-> 7-> 8

2

11

4

1-> 6-> 5-> 4-> 7-> 8

2

13

Tabel 3. 2.2 Banyaknya iterasi dan jalur yang dipilih pada program komputer

C. Mencari potongan minimum menggunakan masalah jalur terpendek

Dalam suatu kejadian khusus, setiap jaringan planar terhubung G:(N,A) bersesuaian dengan jaringan planar kembar G*: (N*, A *) yang menunjuk pada dual dari jaringan G. Ditetapkan dual G* untuk sebarang graf G yang diberikan sebagai berikut: 1) Tempatkan simpul f* didalam setiap daerah z pada jaringan G.

81


2) Setiap busur di G mempunyai busur-busur yang bersesuaian di G*. Setiap busur (i,j) pada G merupakan batas dari dua daerah, yaitu z1 dan z2 atau batas dari satu daerah z1 saja. Jika busur (i,j) tersebut merupakan batas dari dua daerah z1 dan z2 maka G* memuat busur (f1*,f2*). Jika busur (i,j) tersebut merupakan batas dari daerah z1 maka G* memuat loop (f 1*,f1*).

Jaringan awal G disebut sebagai jaringan primal (primal network). Hubungan antara jaringan primal dan jaringan dual antara lain: a. Banyaknya simpul pada jaringan dual sama dengan banyaknya daerah pada jaringan primal. b. Banyaknya daerah pada jaringan dual sama dengan banyaknya simpul pada jaringan primal. c. Kedua buah jaringan, baik jaringan primal maupun jaringan dual mempunyai banyak busur yang sama.

82


Gambar 3.3.1 Dual dari suatu jaringan planar

Dari gambar di atas dapat dilihat bahwa jaringan primal mempunyai lima buah simpul, empat buah daerah dan tujuh busur. Dual dari jaringan tersebut mempunyai empat buah simpul yang merupakan daerah dari jaringan primal, lima buah daerah dan tujuh buah busur. Busur-busur dari jaringan dual ditandai dengan garis putus-putus.

Definisi 3.3.1 Suatu jaringan planar dengan simpul awal s dan simpul akhir t disebut jaringan s - t planar jika simpul awal s dan simpul akhir t keduanya terletak pada daerah tak terbatas.

83


Selanjutnya akan ditunjukkan bagaimana mengubah masalah potongan minimum pada jaringan berarah menjadi jaringan s-t planar dengan menggunakan masalah jalur terpendek. Langkah-langkah untuk mengubah jaringan s-t planar menjadi jaringan dual adalah sebagai berikut: 1)

Pada jaringan s-t planar yang diberikan, pertama-tama gambar busur baru yang menghubungkan simpul s dan t sedemikian hingga busur tersebut terletak di daerah tak terbatas (unbounded region) pada jaringan. Penambahan busur tersebut akan mengakibatkan adanya daerah baru pada jaringan dan disebut

sebagai daerah

tambahan

(additional face).

Penambahan busur dan daerah baru tidak mengubah sifat planar dari jaringan. 2)

Tempatkan simpul awal dari jaringan dual, yaitu s*, pada daerah tambahan dan simpul akhir jaringan dual, yaitu t*, pada daerah tak terbatas.

3) Tempatkan simpul f* di dalam setiap daerah f pada jaringan. 4) Tetapkan bahwa panjang busur dari suatu jaringan dual sama dengan kapasitas dari arus yang bersesuaian pada jaringan primal.

Kapasitas dari potongan pada jaringan primal sama dengan panjang busur yang bersesuaian pada jaringan dual. Karena itu dapat dicari potongan s-t pada jaringan primal dengan nilai kapasitas potongan minimum, yakni dengan menentukan jalur terpendek dari simpul s* ke simpul t * pada jaringan dual.

84


Nilai dari jalur terpendek jaringan dual sama dengan nilai dari potongan minimum s-t. Menurut Teorema 3.2.2, nilai dari potongan minimum sama dengan nilai dari arus maksimum jaringan. Jadi jika diperoleh nilai dari jalur terpendek pada jaringan dual maka diperoleh juga nilai dari arus maksimum jaringan primal. Misalkan d(j *) merupakan jalur terpendek suatu jalur dari simpul s* ke simpul j* pada jaringan dual. Jalur terpendek suatu jalur memenuhi syarat sebagai berikut: d(j*) ≤d(i*) = Ui*j* untuk setiap (i *,j*)A*

(3.3.1)

dengan Ui*j* adalah panjang busur yang menghubungkan simpul i* dan j*. Setiap busur (i,j) pada jaringan primal bersesuaian dengan busur (i *,j*) pada jaringan dual. Misalkan didefinisikan sebuah fungsi x ij untuk setiap (i,j) A, yakni sebagai berikut xij = d(j *) – d(i*)

(3.3.2)

Perhatikan bahwa xij = - xji . Suatu jaringan G merupakan jaringan tak berarah sehingga himpunan busur A memuat busur (i,j) dan busur (j,i). Maka dapat dipandang bahwa arus dengan nilai negatif pada busur (j,i) sebagai arus dengan nilai positif pada busur (i,j). Hal ini mengakibatkan arus x ij akan selalu tak negatif. Berdasarkan definisi 2.1.11, maka xij pada persamaan (3.3.2) memenuhi sifat

i).

xij Cij Dari persamaan (3.3.1) dan ( 3.3.2) diperoleh xij = d(j*) – d(i* ) ≤Ui*j*

85

(3.3.3)


Arus x ij memenuhi kendala dari kapasitas busur, yaitu nilai arus pada busur (i,j) tidak akan melebihi kapasitas busur tersebut yang pada jaringan dual merupakan panjang busur pada jalur yang bersesuaian. ii).

x x ij

jN

ji

0,

i N {s, t }

jN

Misalkan untuk setiap simpul k pada jaringan G kecuali simpul s dan simpul t, didefinisikan potongan Q = ({k}, N - {k}) memuat semua busur yang berhubungan dengan simpul k tersebut. Busur-busur di G* bersesuaian dengan busur-busur di Q membentuk suatu cycle dan disebut w*, maka

( d ( j *) d (i *)) 0

(3.3.4)

( i*, j *)w*

Karena setiap bagian dalam notasi sigma ini akan saling menghapus satu sama lain. Dari persamaan (3.3.2) dan (3.3.4) didapat

x

ij

0

( i , j)Q

Sehingga jumlah arus yang mengalir untuk setiap simpul pada jaringan selain simpul awal dan simpul akhir sama dengan nol untuk setiap simpul k. Akhirnya akan ditunjukkan bahwa arus yang bisa mengalir dalam jaringan dari simpul awal ke simpul akhir adalah arus maksimum.

Teorema 3.3.1 Pada jaringan s-t planar G:(N,A) yang mempunyai jaringan dual G*:(N* ,A*), nilai dari jalur terpendek pada jaringan dual sama dengan nilai arus maksimum pada jaringan primal.

86


Bukti Misalkan P* merupakan jalur terpendek dari simpul s* ke simpul t * pada jaringan G*:(N*,A *), maka d(j *) – d(i*) = Ui*j* untuk setiap (i *,j*) P*

(3.3.5)

Busur-busur yang bersesuaian dengan P* merupakan potongan s-t, Q pada jaringan primal, karena (3.3.2), (3.3.5) dan diketahui bahwa panjang busur pada jaringan dual sama dengan kapasitas busur pada jaringan dual yaitu Ui*j* = Cij Perhatikan bahwa panjang busur pada jaringan primal sama dengan kapasitas busur yang bersesuaian pada jaringan primal. Pada persamaan (3.3.5) karena P* merupakan jalur terpendek yang mempunyai nilai jalur minimum yang dapat menghubungkan simpul awal dan simpul akhir pada jaringan planar, maka nilai kapasitas dari busur pada jaringan primal juga mempunyai nilai minimum. Misalkan didefinisikan potongan Q yang anggotanya merupakan busur-busur dengan kapasitas minimum tersebut, maka menurut teorema max flow-min cut pada jaringan primal tersebut dapat ditemukan arus maksimum yang nilainya sama dengan potongan minimum atau nilai jalur terpendek pada jaringan dual. Contoh 3.3.1 Carilah jalur terpendek dari dual jaringan berikut sekaligus potongan minimum dan arus maksimum dari jaringan primal.

87


Gambar 3.3.2 Jaringan planar dengan delapan simpul dan lima belas busur

Penyelesaian Pertama jaringan diatas akan diubah menjadi jaringan dual dengan cara sebagai berikut: Langkah 1 Gambarkan busur baru yang menghubungkan simpul awal A dan simpul akhir H. Langkah 2 Masukkan simpul awal jaringan dual s* pada daerah tambahan yang baru dibentuk dan simpul akhir jaringan dual t* pada daerah tak terbatas. Langkah 3 Tempatkan simpul-simpul f * jaringan dual. Simpul-simpul tersebut merupakan daerah dari jaringan primal.

Langkah 4 Tetapkan bahwa panjang busur dari suatu jaringan dual sama dengan kapasitas dari arus yang bersesuaian pada jaringan primal.

88


Dengan mengikuti langkah-langkah di atas diperoleh dual dari jaringan sebagai

15

17

17

4

13

8

15

21

20

20

5

21

berikut:

Gambar 3.3.3 Dual dari jaringan planar

Mencari jalur terpendek pada jaringan menggunakan algoritma Dijkstra: Dengan menganggap jaringan tersebut merupakan jaringan planar yang tak berarah, pertama-tama ubahlah jaringan tersebut menjadi bentuk matriks seperti berikut

s*

15

8

15 8

f1 3

3 f2

17 10 4

89


4

f3 7

17

7 f4

13 12

10

f5 6

13

6 f6

20 8

8

f7

14

5

14

f8

21

5

21

t*

12 20

Tabel 3.3.1 Matriks awal sebelum iterasi menggunakan algoritma Djikstra

Dengan menggunakan algoritma Dijkstra diperoleh tabel yang memuat jarak minimum yaitu: 0 *

0

s

11 8

15 8

12 17 21 25

11

8

15

8

f1 3

3 f2 4

17

12

17

21

33

29

38

17 10 4 f3 7

7 f4

10

13 12 f5 6

13

33 29

25

12

38

20

6 f6

20 8

8

f7

14

5

14

f8

21

5

21

t*

Tabel 3.3.2 Matris setelah ditemukan nilai jalur terpendek

Label pada baris dan kolom 11 merupakan jumlah jalur terpendek yang dapat dilalui dari simpul s* ke simpul t* dengan jumlah jarak 38. Dengan memperhatikan proses pencarian jalur terpendek pada algoritma Djikstra tersebut didapatkan jalur terpendek pada jaringan dual seperti Gambar 3.3.4

90


Gambar 3.3.4 Jalur terpendek pada jaringan dual

Jalur terpendek yang dihasilkan pada jaringan dual membentuk potongan pada jaringan primal seperti yang dilihat pada gambar. Kapasitas potongan pada jaringan primal adalah: CBE + CBF + CCF + CCG + CDG = 5 + 8 + 13 + 4 + 8 = 38

Akan dibandingkan nilai jalur terpendek pada jaringan dual dengan nilai arus maksimum pada jaringan primal, dengan menggunakan metode Ford Fulkerson. Pertama-tama bentuk jaringan primal tersebut akan diubah menjadi bentuk matriks sebagai berikut:

A

20

10

B

6

15

0 5

91

8


C 3

3 D

4 8

E 14

21 F

7

12 G

50

17 H

Tabel 3.3.3 Jaringan primal dalam bentuk matriks

Dengan menggunakan algoritma Ford Fulkerson pada jaringan primal diperoleh tabel arus maksimum sebagai berikut:

A

2

1

4

18 9

B 5

1 C

3

11

38

D 5 8

13 4

12

8

E

12

4

2

F

3

7 17

7

G

5

14

H

Tabel 3.3.4 Arus maksimum dengan metode Ford Fulkerson

Diperoleh arus maksimum pada jaringan planar tersebut adalah 38.  Nilai dari jalur terpendek yang dihitung menggunakan algoritma Dijkstra pada jaringan planar sama dengan nilai arus maksimum dan potongan minimum pada jaringan yang sama.

92


Jika contoh 3.3.1 ini diselesaikan dengan menggunakan program Quantitative Management for windows pada komputer didapatkan arus maksimum yang sama, yaitu : End Branch name

Start node

Maximal Network Flow

node

Capacity

Reverse capacity

Flow

38

Branch 1

1

2

20

0

20

Branch 2

1

3

10

0

10

Branch 3

1

4

15

0

8

Branch 4

2

3

9

0

7

Branch 5

2

5

5

0

5

Branch 6

2

6

8

0

8

Branch 7

3

6

13

0

13

Branch 8

3

7

4

0

4

Branch 9

4

7

8

0

8

Branch 10

5

8

21

0

19

Branch 11

6

5

14

0

14

Branch 12

6

8

12

0

11

Branch 13

7

6

7

0

4

Branch 14

7

8

17

0

8

Branch 15

4

3

3

0

0

Tabel 3.3.5 Contoh 3.3.1 menggunakan program komputer

93


Namun jumlah iterasi dan flow augmenting path yang dipilih pada program ini berbeda dengan jumlah iterasi dan flow augmenting path yang dipilih pada pengerjaan sebelumnya, seperti pada tabel berikut

Cumulative Iteration

Path

Flow

Flow

10

10

1

1-> 3-> 6-> 5-> 8

2

1-> 2-> 6-> 8

8

18

3

1-> 4-> 7-> 8

8

26

4

1-> 2-> 5-> 6-> 7-> 8

5

31

5

1-> 2-> 3-> 7-> 6-> 5-> 8

4

35

6

1-> 2-> 3-> 6-> 5-> 8

3

38

Tabel 3.3.6 Banyaknya iterasi dan jalur yang dipilih pada program komputer

Dalam menyelesaikan masalah arus maksimum menggunakan metode Ford-Fulkerson, mula-mula jaringan perlu diubah menjadi bentuk matriks. Pada iterasi selanjutnya dilakukan perhitungan arus maksimum menggunakan bentuk matriks yang lebih ringkas. Selain menggunakan metode Ford-Fulkerson, terdapat alternatif cara menyelesaikan masalah arus maksimum yaitu menggunakan metode max flowmin cut. Dengan metode max flow-min cut setiap iterasi dilakukan dalam bentuk jaringan, dengan memperhatikan arah masing-masing busur pada jaringan dan bertujuan mencari arus maksimum sekaligus potongan minimum pada jaringan

94


tersebut. Penyelesaian optimal pada metode max flow-min cut dapat diperiksa dengan menggunakan Teorema max flow-min cut. Untuk mencari arus maksimum pada suatu jaringan khusus, yaitu jaringan planar dapat digunakan algoritma Djikstra yang bertujuan mencari jalur terpendek. Pertama bentuklah dual dari jaringan awal, kemudian cari jalur terpendek dari jaringan dual. Jalur terpendek itulah yang digunakan untuk menentukan potongan minimum sekaligus arus maksimum pada jaringan awal.

D. Aplikasi masalah arus maksimum Contoh penggunaan jaringan berarah dalam kehidupan sehari-hari meliputi sistem pengambilan dan pembuangan air ledeng dalam memenuhi kebutuhan rumah tangga, distribusi minyak, gas alam, saluran telepon, jaringan listrik dan sistem pengiriman surat. Aplikasi yang akan dibahas pada bagian ini adalah masalah penawaran dan permintaan (supply and demand problem). Jaringan berarah yang dibahas sebelumnya merupakan jaringan berarah yang mempunyai simpul awal dan simpul akhir yang tunggal, tetapi ada beberapa jaringan berarah lain yang mempunyai simpul awal dan simpul akhir yang lebih dari satu. Jaringan berarah tersebut dapat ditangani secara mudah dengan menempatkan dua buah simpul yang baru yaitu simpul s dan simpul t. Kemudian tambahkan busur-busur yang menghubungkan simpul s dengan simpul-simpul awal pada jaringan asli dan tambahkan pula busur-busur yang menghubungkan simpu-simpul akhir dengan simpul t. Maka didapatkan jaringan baru yang mempunyai satu simpul awal s dan satu simpul akhir t. Dengan memberi kapasitas

95


yang cukup besar pada busur-busur yang baru tersebut, maka penambahan simpul s dan t dijamin tidak akan mengubah kemungkinan-kemungkinan aliran arus yang melewati busur-busur pada jaringan asli. Nilai maksimum arus-(s,t) pada jaringan yang baru juga merupakan nilai maksimum arus pada jaringan yang asli, yang didapat bila simpul s dan t dihapus. Contoh dari masalah permintaan dan penawaran (supply and demand problem) Sebuah toko serba ada bernama Alberta mengelola tiga buah toko cabang dan tiga buah gudang penyimpanan barang. Ketiga gudang penyimpanan barang tersebut misalkan disebut A, B dan C terletak di sebelah Selatan propinsi dan ketiga toko cabang disebut C, D dan E terletak di pinggir kota jauh di sebelah Utara. Pada laporan tangal 1 Oktober tercatat bahwa pada masing-masing gudang terdapat sejumlah alat pembersih salju yaitu gudang A sebanyak 500 buah, gudang B sebanyak 500 buah dan di gudang C sebanyak 900 buah. Menurut ramalan cuaca, badai salju pertama pada musim dingin tahun ini akan terjadi sekitar tengah malam pada tanggal 2 Oktober. Setelah disiarkan berita tersebut terjadi permintaan segera dari masyarakat ke toko-toko cabang tersebut yaitu toko D sebanyak 700 barang, toko E sebanyak 600 barang dan toko F sebanyak 600 barang. Untuk memenuhi permintaan tersebut dibutuhkan kiriman alat pembersih salju dari ketiga gudang penyimpanan barang ke toko-toko cabang. Dari gudang penyimpanan barang terdapat beberapa rute untuk mengirimkan barang-barang dagangan tersebut dari gudang menuju ke toko-toko cabang seperti yang ditunjukkan pada gambar. Kapasitas busur merupakan jumlah terbesar dari alat

96


pembersih salju yang dapat dikirimkan dari simpul i ke simpul j dalam satu hari perjalanan.

Gambar 3.4.1 Skema jalan yang dapat dilalui dari gudang ke toko

Simpul-simpul yang berada di antara gudang penyimpanan dan toko-toko cabang merepresentasikan orang-orang perantara yang biasa melakukan pendistribusian barang. Misalnya orang-orang yang biasa menangani pengiriman alat pembersih salju dalam jumlah besar. Diasumsikan muatan-muatan barang dagangan dapat dikirimkan melalui banyak busur dalam sekali pengiriman per hari. Dapatkah alat pembersih salju yang dibutuhkan tersebut mencapai toko sebelum badai salju terjadi? Jika tidak seberapa banyak perusahaan tersebut dapat memenuhi jumlah permintaan konsumen? Langkah pertama untuk menyelesaikan masalah ini adalah dengan memperhatikan bahwa terdapat tiga simpul awal dan tiga simpul akhir. Dengan menggunakan cara seperti yang sudah disinggung di atas, tambahkan simpul baru yaitu simpul s sebagai simpul awal dan simpul t sebagai simpul akhir. Simpul s tersebut dihubungkan dengan simpul-simpul A, B, C dan simpul t dihubungkan dengan

97


simpul-simpul D, E, F. Pada masing-masing busur yang terhubung dengan simpul s, diberikan kapasitas busur yang sama dengan jumlah alat pembersih salju yang tersimpan di gudang penyimpanan dan busur-busur yang terhubung dengan simpul t, diberikan kapasitas busur yang sama dengan jumlah dari permintaan alat pembersih salju pada masing-masing toko cabang. Jaringan yang baru ditunjukkan dengan gambar sebagai berikut.

Gambar 3.4.2 Jaringan dengan simpul awal s dan simpul akhir t

Mencari arus maksimum dengan menggunakan algoritma Ford Fulkerson dan max flow-min cut. Pertama-tama ubahlah jaringan diatas menjadi bentuk matriks sebagai berikut:

98


s

5 A

5

9 6 1

B

5

C

6 D

7 6 6

E F 6

G 6

4

3 H

3

I 3

1

5 J

19

t Tabel 3.4.1 Bentuk matriks dari Gambar 3.3.2

Dengan menggunakan algoritma Ford Fulkerson diperoleh tabel arus maksimum sebagai berikut:

s 5 4 6

1

3

15

A

1 B

2 C D

3 E F

5

1 5 1

3 1

4 6 3

G 3

H

6 1

4

3

6

3

I 4

1 1 J

6

t

Tabel 3.4.2 Matriks setelah metode Ford Fulkerson

Diperoleh arus maksimum pada jaringan tersebut adalah 15. Jika bentuk matriks ini dikembalikan dalam bentuk jaringan berikut

99

berarah lagi akan diperoleh sebagai


Gambar 3.4.3 Jaringan setelah metode Ford Fulkerson

Jaringan seperti yang digambarkan di atas memberikan interpretasi terhadap masalah permintaan dan penawaran. Dapat dibayangkan simpul s sebagai gudang penyimpanan barang raksasa yang dapat menampung 1900 pembersih salju. Nilai pada busur-busur yang keluar dari simpul s menunjukkan jumlah dari alat pembersih salju yang dapat dikirimkan ke gudang penyimpanan lain yaitu A, B, dan C jika dibutuhkan. Dengan cara yang sama dapat ditambahkan sebuah simpul akhir yang dapat menerima kiriman 1900 alat pembersih salju. Nilai arus maksimum pada jaringan tersebut adalah f Dt + fEt + f Ft = 3 + 6 + 6 = 15 Pada jaringan terdapat partisi yaitu S = {s, B, C, I, J} dimana simpul-simpul tersebut dapat dicapai dari simpul awal s oleh rantai flow augmenting dan T = {A, G, H, D, F, t}. Kapasitas dari cut adalah CsA + CBG + CBH + CJH + CJK = 5 + 1 + 5 + 1 + 3 = 15

100


Tampak bahwa F = cap(S,T) = 15

Jika contoh 3.4.1 ini diselesaikan dengan menggunakan program Quantitative Management for windows pada komputer didapatkan arus maksimum yang sama, yaitu : End Branch name Maximal Network Flow

Start node

node

Capacity

Reverse capacity

Flow

15

Branch 1

1

2

5

0

5

Branch 2

1

3

5

0

5

Branch 3

1

4

9

0

5

Branch 4

2

8

6

0

5

Branch 5

3

8

1

0

1

Branch 6

3

9

5

0

5

Branch 7

10

3

3

0

1

Branch 8

10

11

5

0

4

Branch 9

4

10

6

0

5

Branch 10

11

9

1

0

1

Branch 11

8

9

3

0

-1

Branch 12

9

6

6

0

6

Branch 13

9

7

4

0

0

Branch 14

11

7

3

0

3

Branch 15

8

5

6

0

6

101


Branch 16

5

12

7

0

6

Branch 17

6

12

6

0

6

Branch 18

7

12

6

0

3

Tabel 3.4.3 Contoh 3.4.1 menggunakan program komputer

Namun jumlah iterasi dan flow augmenting path yang dipilih pada program ini berbeda dengan jumlah iterasi dan flow augmenting path yang dipilih pada pengerjaan sebelumnya, seperti pada tabel berikut

Iteration

Path

Flow

Cumulative Flow

1

1-> 2-> 8-> 5-> 12

5

5

2

1-> 3-> 9-> 6-> 12

5

10

3

1-> 4-> 10-> 11-> 7-> 12

3

13

4

1-> 4-> 10-> 3-> 8-> 9-> 6-> 12

1

14

5

1-> 4-> 10-> 11-> 9-> 8-> 5-> 12

1

15

Tabel 3.4.4 Banyaknya iterasi dan jalur yang dipilih pada program komputer

Dapat disimpulkan bahwa permintaan akan alat pembersih salju tersebut tidak semua dapat dikirimkan sebelum badai salju datang. Pada kenyataannya jumlah maksimum

yang dapat dikirimkan adalah sejumlah 1500 buah alat

pembersih salju. Pada gambar dapat dilihat bahwa toko D menerima 300 alat pembersih salju, toko E 600 buah dan toko F 600 buah. Penyelesaian yang dihasilkan bukan merupakan penyelesaian yang tunggal.

102


BAB IV PENUTUP

A.

Kesimpulan Masalah arus maksimum merupakan pengembangan dari masalah teori

graf yang muncul pada tahun 1736 dilatar belakangi oleh masalah jembatan Koningberg. Jaringan dapat digunakan untuk memodelkan suatu masalah dalam dunia real. Salah satunya adalah masalah arus maksimum. Ada beberapa cara yang dapat digunakan untuk menyelesaikan masalah arus maksimum dalam jaringan yaitu metode Ford-Fulkerson dan metode max flow- min cut. 1. Penyelesaian masalah arus maksimum menggunakan metode Ford-Fulkerson, pertama-tama dilakukan dengan mengubah bentuk jaringan menjadi bentuk matriks n x n dengan n merupakan banyak simpul pada jaringan. Selanjutnya dilakukan proses pelabelan yang menunjukkan adanya arus pada jaringan dari simpul awal menuju simpul akhir. Dalam penelusuran kembali, setelah proses pelabelan akan dicari nilai minimum dari kapasitas residual dari flow augmenting path pada jaringan. Setelah melakukan perhitungan kembali arus, proses akan kembali lagi pada proses pelabelan dan selanjutnya. Jika sudah tidak dapat ditemukan flow augmenting path dengan kapasitas residual positif, ditemukan arus maksimum. Metode Ford-Fulkerson selesai.

103


2. Penyelesaian masalah arus maksimum menggunakan metode max flow-min cut dilakukan mula-mula dengan mencari jalur yang menghubungkan simpul awal menuju simpul akhir. Kemudian dicari nilai slack dari arus pada masingmasing busur pada jalur. Setelah perhitungan kembali nilai arus proses berlanjut dengan mencari kembali jalur yang menghubungkan simpul awal dan simpul akhir dan selanjutnya, hingga tidak dapat ditemukan lagi jalur pada jaringan. Jika hal itu terjadi cari potongan dari jaringan yang mempartisi jaringan menjadi dua buah himpunan, yaitu himpunan yang memuat simpul awal dan himpunan yang memuat simpul akhir. Setelah ditemukan potongan tersebut, hitung kapasitas busur-busur pada masing-masing potongan. Menurut Teorema max flow-min cut, nilai dari kapasitas tersebut sama dengan nilai dari arus maksimum. Metode max flow-min cut selesai.

Dalam

mencari

penyelesaian

arus

maksimum

selain

metode

Ford-Fulkerson dan metode max flow-min cut dapat digunakan algoritma Djikstra. Namun penggunaan algoritma Djikstra ini hanya berlaku untuk jaringan planar saja. Mula-mula pada suatu jaringan planar, bentuk dual dari jaringan dan ubah jaringan dual menjadi bentuk matriks. Dengan menggunakan algoritma Djikstra dapat ditemukan jalur terpendek pada jaringan dual. Selanjutnya cari potongan minimum sekaligus arus maksimum pada jaringan planar primal menggunakan jalur terpendek pada jaringan dual tersebut. Pada metode Ford-Fulkerson, sebelum dilakukan pelabelan bentuk jaringan harus diubah menjadi bentuk matriks. Dalam iterasi selanjutnya bentuk

104


matriks tersebut membuat proses pengerjaan lebih mudah dan ringkas. Metode ini akan memudahkan untuk pengerjaan saat harus mencari penyelesaian arus maksimum untuk jaringan dengan banyak simpul dan busur. Pada pengerjaan menggunakan metode max flow-min cut, bentuk matriks tidak perlu diubah dalam bentuk matriks. Pada setiap iterasi pengerjaan dilakukan dalam bentuk jaringan sehingga diperlukan ketelitian dalam memperhatikan arah pada masing-masing busur. Setelah iterasi selesai diperoleh potongan minimum dan arus maksimum dan hasil dari metode max flow-min cut tersebut dapat diperiksa menggunakan Teorema max flow-min cut.

C.

Saran Dalam tulisan ini, dibahas masalah optimasi arus hanya seputar masalah

arus maksimum pada jaringan. Masalah optimasi lainnya, yaitu masalah jarak terpendek dan masalah biaya minimum pada jaringan hanya sedikit disinggung. Sedangkan dalam perkembangan masalah optimasi, seseorang cenderung menginginkan optimalisasi bukan hanya jumlah maksimum saja namun sekaligus juga minimalisasi biaya dan efisiensi kerja. Maka penulisan-penulisan masalah optimasi arus yang mencakup ketiga masalah yaitu arus maksimum, jarak terpendek dan masalah biaya minimum pada jaringan akan sangat menarik untuk dikembangkan.

105


DAFTAR PUSTAKA

Ahuja, Ravindra, Thomas L. Magnanti, James B.Orlin. 1993. Network Flows : Theory, Algorithms and Applications. London : Prentice-Hall, Inc.

Bazaraa, MS & Jarvis, JJ. 1990. Linear Programming and Network Flow. London: wiley

Chartrand, Gar & Ollermann, Oop. 1993. Applied and Algorithmic Graph Theory. London : Mc Graw-Hill.inc.

Dantzig, GB.1991. Linear Prorammming and Extensions. Princeton : Princeton university press.

Hillier, Frederick S. 1995. Introduction to Mathematical Programming. Singapore : Mc Graw-Hill.

Liu, CL. 1995. Dasar-dasar Matematika Diskret. Jakarta : PT Gramedia Pustaka Utama.

Neering, Evard & Tucker, Aw.1990. Linear Programs and Related Problem. London : Academic press, inc

Sultan, Alan. 1993. Linear programming an Introduction with Applications. London: Academic press, inc.

106

OPTIMASI ARUS MAKSIMUM PADA JARINGAN

Recommend Documents