masalah arus maksimum
Post on 16-Apr-2015
379 Views
Preview:
DESCRIPTION
TRANSCRIPT
MASALAH ARUS MAKSIMUMMASALAH ARUS MAKSIMUM
OlehAnisa Bella Fathia (1005364)Eka Arifani Putri (1002444)Eka Septia Tantias (1001102)Ismail Jauhari (1006469)Lia Malihah (1000313)Nabilla Khalida S (1004536)Ogi Jayaprana (1006667)
OGI JAYAPRANA (1006667)OGI JAYAPRANA (1006667)
MasalahMasalah aliranaliran maksimummaksimum merupakanmerupakan masalahmasalahjaringanjaringan dimanadimana cabangcabang--cabangcabang jaringanjaringantersebuttersebut memilikimemiliki kapasitaskapasitas arusarus yang yang terbatasterbatas. .
TujuanTujuan daridari masalahmasalah arusarus maksimummaksimum adalahadalahmemaksimumkanmemaksimumkan total total jumlahjumlah arusarus daridari satusatutitiktitik awalawal keke satusatu tujuantujuan
arus (aliran) air, gas, atau minyak melaluisuatu jaringan pipa,
arus formulir melalui suatu sistempemrosesan dalam kantor pemerintah,
arus lalu lintas melalui jaringan jalan raya, arus produk melalui suatu sistem lini
produksi Dll.
1
1
6
0
09
4 0
0
5
4 0
2
0
1
1
3
0
4
0
7
5
A
B
C
D F
E
T
0
0
EKA ARIFANI P (1002444)EKA ARIFANI P (1002444)
JaringanJaringan kerjakerja sisaansisaan: : perbedaanperbedaan dengandengan jaringanjaringan biasabiasahanyahanya padapada setiapsetiap busurbusur berarahberarah ((ii→→jj) yang ) yang tidaktidak memilikimemilikibusurbusur berarahberarah dengandengan araharah kebalikannyakebalikannya ((jj→→ii) , ) , kinikiniditambahkanditambahkan suatusuatu busurbusur berarahberarah kebalikannyakebalikannya dengandengankapsitaskapsitas 0.0.
KapasitasKapasitas sisaansisaan: : kapasitaskapasitas busurbusur yang yang tidaktidaktermanfaatkantermanfaatkan padapada jaringanjaringan kerjakerja aslinyaaslinya..
LintasanLintasan penambahpenambah: : suatusuatu lintasanlintasan berarahberarah daridari simpulsimpulpemasokpemasok menujumenuju simpulsimpul penampungpenampung sdshsdsh setiapsetiap busurbusurdalamdalam lintasanlintasan memilikimemiliki kapasitaskapasitas yang yang positifpositif..
NABILA NABILA KHALIDA (KHALIDA (1004536)1004536)AlgoritmaAlgoritma
1. Identifikasi suatu lintasan penambahdengan mencari beberapa lintasan berarahdari simpul pemasok menuju simpulpenampung dalam jaringan kerja sisaansedemikian rupa sehingga setiap busurdalam lintasan tersebut memiliki nilaikapasitas sisaan positif(Jika tidak terdapatlintasan penambah, jumlah arus bersihtelah menunjukkan pola arus yang maksimum)
2. Identifikasi kapasitas residual c* darilintasan penambah ini dengan mencari nilaikapasitas sisaan minimum dari busur-busuryang terdapat dalam lintasan ini. Tambahkanarus sejumlah c* pada lintasan ini.
3. Kurangi kapasitas setiap busur pada lintasanpenambah ini sejumlah c*. Tambahkankapsitas setiap busur yang berlawanan arahdengan lintasan sejumlah c*
PenerapanPenerapan AlgoritmaAlgoritma padapada masalahmasalahTaman Taman SeervadaSeervada
EKA SEPTIA T (1001102)EKA SEPTIA T (1001102)
A
O B
C
D
E
T5
0
7 0
1
14 0
3
0 90
6
0
4 0
4
00
2 5
0 1
1
Iterasi 1
55
A
O B
C
D
E
T5
0
2 5
1
14 0
3
0 90
1
5
4 0
4
00
2 0
5 1
1
Iterasi 2
88
A
O B
C
D
E
T2
3
2 5
1
14 0
0
3 63
1
5
4 0
4
00
2 0
5 1
1
Iterasi 3
99
A
O B
C
D
E
T1
4
2 5
0
23 1
0
3 54
1
5
4 0
4
00
2 0
5 1
1
Iterasi 4
11 11
A
O B
C
D
E
T1
4
0 7
0
21 3
0
3 36
1
5
4 0
4
00
2 0
5 1
1
Iterasi 5
12
12
A
O B
C
D
E
T1
4
0 7
0
21 3
0
3 27
1
5
3 1
3
10
2 0
5 0
2
Iterasi 6
13
13
A
O B
C
D
E
T1
4
0 7
0
21 3
0
3 27
0
6
2 2
2
20
2 0
5 0
2
Iterasi 7
14
14
A
O B
C
D
E
T1
4
0 7
0
20 4
0
3 18
0
6
1 3
1
30
2 1
4 0
2
Penyelesaian optimal
14
14
A
O B
C
D
E
T
4
7
1
4
3
8
6
3
34
1
LIA MALIHAH (1000313)
Algoritma untuk masalah arus maksimum akansulit diterapkan dalam jaringan kerja yang besaryaitu ketika mencari lintasan penambah.
Dapat disederhanakan dengan prosedursistematik berikut:
1. Dimulai dengan menentukan semua simpul yang dapat dicapai dari simpul pemasok (sumber) sepanjang busur (tunggal) dengan kapasaitas sisaanpositif
2. Untuk setiap simpul yang dicapai, tentukansuatu simpul baru (yang belum pernahdicapai) yang dapat dicapai dari simpul tesebutsepanjang busur dengan kapasitas sisaanpositif.
3. Ulangi langkah ini berturut-turut denganmemulai pada simpul baru (dimanasebelumnya simpul ini telah tercapai)
Hasilnya akan mengidentifikasi suatu pohonyang terdiri atas seluruh simpul yang dapatdicapai dari simpul pemasok (sumber) sepanjang lintasan dengan kapasitas arus sisaanpositif
Prosedur penyebaran (fanning out procedure) iniakan mengidentifikasi suatu lintasan tambahanjika ada.
Iterasi 7
14
14
A
O B
C
D
E
T1
4
0 7
0
20 4
0
3 18
0
6
1 3
1
30
2 1
4 0
2
Untuk mengenali kapan suatu titik optimal tercapai adalah dengan dalil jaringan kerjayang dikenal dengan teorema arus-maksimum potongan-minimum (max-flow min-cut theorem)
PotonganPotongan (Cut)(Cut) Potongan (cut) didefinisikan sebagai
sebarang himpunan yang beranggotakanbusur-busur berarah yang memilikisekurang-kurangnya satu busur dari setiaplintasan berarah dari simpul pemasok kesimpul penampung.
Nilai potongan (cut value) adalah jumlahkapasitas busur-busur (dalam arahtertentu) yang menjadi anggota suatupotongan (cut)
MaxMax--flow Minflow Min--cut Theoremcut Theorem
Pemotong pada Jaringan Kerja Awal
Kapasitas pemotong pada jaringan ini adalah 3+4+1+6 = 14
A
O B
C
D
E
T5
0
7 0
1
14 0
3
0 90
6
0
4 0
4
00
2 5
0 1
1
Pemotong pada Jaringan Kerja Sisaan (Iterasi 7)
14 14
Kapasitas pemotong yang bersesuaian pada Jaringan KerjaSisaan adalah 0
A
O B
C
D
E
T1
4
0 7
0
20 4
0
3 18
0
6
1 3
1
30
2 1
4 0
2
Sehingga kapasitas pemotong padaJaringan Kerja Awal = 14 = jumlaharus maksimum pada Jaringan Kerja.
Pemotong tersebut merupakanpemotong minimum (Minimum Cut) dan arusnya merupakan arusmaksimum (Maximum Flow).
Penyelesaian optimal Penyelesaian optimal maka arus masimumnyya didapatmaka arus masimumnyya didapat
Ismail jauhari 1006469Ismail jauhari 1006469Contoh soalContoh soal
hitung Arus maksimum dari jaringan berikuthitung Arus maksimum dari jaringan berikut
jawabjawab Langkah pertama ambil sembarang lintasan
penambah dari sumber ke tujuan dan lakukan penugasan arus yang mempunyai kapasitas minimum C* pada setiap simpul dilintasan tersebut.
Lalu kapasitas setiap busur dikurangi dengan C*
Lakukan langkah pertama berulang-ulang sehingga tidak ada lintasan penambah lagi dari sumber ke tujuan yang bisa menugaskan arus bernilai positif lebih besar dari nol
Dari gambar jaringan diatas didapatDari gambar jaringan diatas didapat
Lintasan penambah 1-2-5-7 didapat C*= min{6,4,4} Lintasan penambah 1-3-6-7 didapat C*= min {4,3,9}Lintasan 1-4-6-7 penambah didapat min C*= min {1,4,6}Lintasan 1-3-4-6-7 penambah didapat min C* = min{1,3,3,5}
Penyelesaian optimal Penyelesaian optimal maka maka arus maksimumnyya arus maksimumnyya didapatdidapat
AnisaAnisa Bella Bella FathiaFathia (1005364)(1005364)
Hitung arus maksimumnya!
1
3
6
2
4
5
7
9
8
0
8
7
2 4
0
7
0
0
7
0
22
3
0
9
3 3
2
3 5
2
4
03 0 8 0
3
46 1
Iterasi 1Lintasan penambah: 1-5-9C*=3
3 3
1
3
6
2
4
5
7
9
8
0
8
7
2 4
0
7
0
0
7
0
22
3
0
9
3 3
2
3 5
2
4
00 3 5 3
3
46 1
Iterasi 2Lintasan penambah: 1-2-4-7-9C*=4
7 7
1
3
6
2
4
5
7
9
8
4
4
3
6 0
4
3
4
0
7
0
22
3
0
9
3 3
2
3 5
2
4
00 3 5 3
3
46 1
Iterasi 3Lintasan Penambah: 1-2-7-9C*=3
10 10
1
3
6
2
4
5
7
9
8
7
1
3
6 0
4
0
7
0
7
0
22
3
0
9
0 6
2
3 5
2
4
00 3 5 3
3
46 1
Iterasi 4Lintasan Penambah: 1-2-5-9C*=1
11 11
1
3
6
2
4
5
7
9
8
8
0
3
6 0
4
0
7
0
7
0
22
3
0
9
0 6
1
4 5
2
4
00 3 4 4
3
46 1
Iterasi 5Lintasan Penambah: 1-3-8-9C*=6
17 17
1
3
6
2
4
5
7
9
8
8
0
3
6 0
4
0
7
6
1
0
22
3
3
6
0 6
1
4 5
2
4
00 3 4 4
3
40 7
Iterasi 6Lintasan Penambah: 1-3-5-9C*=4
21 21
1
3
6
2
4
5
7
9
8
8
0
3
6 0
4
0
7
6
1
0
22
3
7
2
0 6
1
4 5
2
0
40 3 0 8
3
40 7
Iterasi 7Lintasan Penambah: 1-3-6-8-9C*=1
22 22
1
3
6
2
4
5
7
9
8
8
0
3
6 0
4
0
7
5
0
1
13
2
8
1
0 6
1
4 5
2
0
40 3 0 8
3
40 7
Penyelesaian optimalMaka, arus maksimumnya 22
22 22
1
3
6
2
4
5
7
9
8
8
4 4
7
7
11
8
3
1
4
3 8
6
top related