masalah arus maksimum

41
MASALAH ARUS MAKSIMUM MASALAH ARUS MAKSIMUM Oleh Anisa Bella Fathia (1005364) Eka Arifani Putri (1002444) Eka SeptiaTantias (1001102) Ismail Jauhari (1006469) Lia Malihah (1000313) Nabilla Khalida S (1004536) Ogi Jayaprana (1006667)

Upload: ogijayaprana

Post on 16-Apr-2015

377 views

Category:

Documents


3 download

DESCRIPTION

Riset Opersi

TRANSCRIPT

Page 1: Masalah Arus Maksimum

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)

Page 2: Masalah Arus Maksimum

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

Page 3: Masalah Arus Maksimum

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.

Page 4: Masalah Arus Maksimum

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

Page 5: Masalah Arus Maksimum

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..

Page 6: Masalah Arus Maksimum

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)

Page 7: Masalah Arus 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*

Page 8: Masalah Arus Maksimum

PenerapanPenerapan AlgoritmaAlgoritma padapada masalahmasalahTaman Taman SeervadaSeervada

EKA SEPTIA T (1001102)EKA SEPTIA T (1001102)

Page 9: Masalah Arus Maksimum

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

Page 10: Masalah Arus Maksimum

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

Page 11: Masalah Arus Maksimum

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

Page 12: Masalah Arus Maksimum

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

Page 13: Masalah Arus Maksimum

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

Page 14: Masalah Arus Maksimum

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

Page 15: Masalah Arus Maksimum

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

Page 16: Masalah Arus Maksimum

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

Page 17: Masalah Arus Maksimum

Penyelesaian optimal

14

14

A

O B

C

D

E

T

4

7

1

4

3

8

6

3

34

1

Page 18: Masalah Arus Maksimum

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

Page 19: Masalah Arus Maksimum

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.

Page 20: Masalah Arus Maksimum

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

Page 21: Masalah Arus Maksimum

Untuk mengenali kapan suatu titik optimal tercapai adalah dengan dalil jaringan kerjayang dikenal dengan teorema arus-maksimum potongan-minimum (max-flow min-cut theorem)

Page 22: Masalah Arus Maksimum

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)

Page 23: Masalah Arus Maksimum

MaxMax--flow Minflow Min--cut Theoremcut Theorem

Page 24: Masalah Arus Maksimum
Page 25: Masalah Arus Maksimum

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

Page 26: Masalah Arus Maksimum

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

Page 27: Masalah Arus Maksimum

Sehingga kapasitas pemotong padaJaringan Kerja Awal = 14 = jumlaharus maksimum pada Jaringan Kerja.

Pemotong tersebut merupakanpemotong minimum (Minimum Cut) dan arusnya merupakan arusmaksimum (Maximum Flow).

Page 28: Masalah Arus Maksimum

Penyelesaian optimal Penyelesaian optimal maka arus masimumnyya didapatmaka arus masimumnyya didapat

Page 29: Masalah Arus Maksimum

Ismail jauhari 1006469Ismail jauhari 1006469Contoh soalContoh soal

hitung Arus maksimum dari jaringan berikuthitung Arus maksimum dari jaringan berikut

Page 30: Masalah Arus Maksimum

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

Page 31: Masalah Arus Maksimum

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}

Page 32: Masalah Arus Maksimum

Penyelesaian optimal Penyelesaian optimal maka maka arus maksimumnyya arus maksimumnyya didapatdidapat

Page 33: Masalah Arus Maksimum

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

Page 34: Masalah Arus Maksimum

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

Page 35: Masalah Arus Maksimum

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

Page 36: Masalah Arus Maksimum

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

Page 37: Masalah Arus Maksimum

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

Page 38: Masalah Arus Maksimum

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

Page 39: Masalah Arus Maksimum

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

Page 40: Masalah Arus Maksimum

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

Page 41: Masalah Arus Maksimum

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