1 network opt. method1

Network OptimizationMethods

1

Methods

Sebuah metodepenyelesaian masalahyang menggunakan

2

yang menggunakanpendekatan Network

(Graph)

ModelPenyelesaian MasalahPenyelesaian Masalah

(Basic Modelling)

3

Masalah

ModelModelPenyelesaianPenyelesaian ???

4

Solusi

ModelModelPenyelesaianPenyelesaian ???

Masalah

ModelModelPenyelesaianPenyelesaian

Model Model MatematisMatematis

5

Solusi


Model Model MatematisMatematis

MasalahMasalah


6

KarakteristikKarakteristik PenyelesaianPenyelesaian(Model (Model MatematisMatematis))

Tingkat Tingkat PertumbuhanPertumbuhan KuatKuat ArusArusMixing ProblemMixing Problem

Model PDModel PDModel PDModel PDModel PDModel PD

PendekatanPendekatanKarakteristikKarakteristik MasalahMasalah

7

Mixing ProblemMixing Problem OptimisasiOptimisasi SumberdayaSumberdaya PenjadwalanPenjadwalan OptimisasiOptimisasi JaringanJaringan

Model PDModel PDModel LPModel LP

Model GraphModel GraphModel GraphModel Graph

dll

ModellingModelling Advertising AwarenessAdvertising Awareness

SebuahSebuah produkproduk barubaru, , diperkenalkandiperkenalkan melaluimelalui iklaniklanterhadapterhadap 1 1 jutajuta konsumenkonsumen potensialpotensial. . PadaPada akhirakhirtahuntahun pertamapertama, , ternyataternyata separuhseparuh populasipopulasi mengenalmengenal

Contoh :

tahuntahun pertamapertama, , ternyataternyata separuhseparuh populasipopulasi mengenalmengenalprodukproduk barubaru tsbtsb. . JikaJika populasipopulasi ygyg mengenalmengenal ttgttgkeberadaankeberadaan produkproduk barubaru tersebuttersebut diasumsikandiasumsikanproporsionalproporsional thdthd populasipopulasi konsumenkonsumen ygyg belumbelummengenalmengenal produkproduk barubaru tsbtsb, , berapakahberapakah jumlahjumlahkonsumenkonsumen ygyg akanakan mengetahuimengetahui keberadaankeberadaan produkprodukbarubaru tsbtsb padapada akhirakhir tahuntahun keke duadua. .

Populasi (juta)=y

1

0,50

0,75?

9

t (thn)1

0,25

0,50

2

MisalkanMisalkan ::y : y : menyatakanmenyatakan jumlahjumlah orangorang ygyg

mengetahuimengetahui produkproduk barubaru tsbtsbdalamdalam waktuwaktu t.t.

BerartiBerarti : : (1(1--y) : y) : menunjukkanmenunjukkan jumlahjumlah orangorang

ygyg belumbelum mengetahuimengetahui adanyaadanya(1(1--y) : y) : menunjukkanmenunjukkan jumlahjumlah orangorang

ygyg belumbelum mengetahuimengetahui adanyaadanyaprodukproduk barubaru tsbtsb..

MakaMaka : : dydy//dtdt menunjukkanmenunjukkan tingkattingkatperubahanperubahan populasipopulasi ygyg mengetahuimengetahuikeberadaankeberadaan produkproduk barubaru tsbtsb..

Tingkat Tingkat perubahanperubahan populasipopulasiyang yang mengetahuimengetahui produkprodukbarubaru tsbtsb

dydy//dtdt

11

dydy//dtdt = k(1= k(1--y)y)

PersamaanPersamaan diferensialdiferensial

SolusiSolusi :: y = 1y = 1--CeCe --ktkt

y = 1y = 1--CeCe --ktkt

y=0 y=0 ketikaketika t=0t=0 C = 1C = 1

y=0,5 y=0,5 ketikaketika t=1 & C=1t=1 & C=1

12

y=0,5 y=0,5 ketikaketika t=1 & C=1t=1 & C=1

0,5 = 10,5 = 1--ee --kk k = k = lnln 2 2 0,6930,693

y = 1y = 1--ee --0,693t0,693t

y = 1y = 1--ee --0,693t0,693t

FungsiFungsi ygyg menunjukkanmenunjukkan hubunganhubunganpopulasipopulasi (y) yang (y) yang mengenalmengenal produkprodukterhadapterhadap waktuwaktu (t).(t).

13

terhadapterhadap waktuwaktu (t).(t).

JumlahJumlah konsumenkonsumen potensialpotensial yang yang mengenalmengenal produkproduk padapada akhirakhirtahuntahun keke--2 :2 :

y = 1y = 1--e ; t=2e ; t=2--0,693t0,693t

y = 1y = 1--ee --0,693t0,693t

y = 1y = 1--ee --0,693(2)0,693(2) 0,750,75

AtauAtau 750.000750.000

14

AtauAtau 750.000750.000

PadaPada akhirakhir tahuntahun keke--2 2 akanakan adaada750.000 750.000 orangorang ygyg mengenalmengenalprodukproduk barubaru tsbtsb..

Network OptimizationMethodsMethods

16

Sebuah metodepenyelesaian masalahyang menggunakanyang menggunakan

pendekatan Network(Graph)

17

Masalah Model Penyelesaian Solusi

Konsep :

18

Penyelesaian Solusi

Model Network(Graph)

Mengapa harusdi optimalkan?

Jaringan apa ?

19

Bagaimana Caranya ?

Mengapa harusdi optimalkan?

KonsepKonsep DasarDasar ygyg perluperlu dipahamidipahami

Apa yang dimaksud denganNetwork ?

Apa komponen-komponen dari

20

Apa komponen-komponen darisebuah Network ?

Bagaimana hubungan Networkdengandengan GraphGraph ?

Network (Network (JaringanJaringan):):

koleksi dari verteks (titik/simpul)dan edge (garis/ruas), dimanadan edge (garis/ruas), dimanasetiap verteks anggotanya harusterhubung dgn suatu edge.

21

Edge adalah sebuah garis yangmenghubungkan 2 vertex(disebut juga ruas/garis/branch).

22

(disebut juga ruas/garis/branch).

1

23

Contoh Network (Jaringan) :

1

45

23

: Vertex/Node

: Branch (ruas/garis/edge)

2

PadaPada kasuskasus tertentutertentu digunakandigunakan tandatandapanahpanah padapada ruasnyaruasnya.

1

23

45

24

Hubungan Network dengan Graph

Sebuah Network pasti Graph

25

Sebuah Graph belum tentu Network

12 3

45

SebuahSebuah Network Network ygyg jugajuga GraphGraph

26

12 3

45

SebuahSebuah Graph Graph tetapitetapi bukanbukan NetworkNetwork

UntukUntuk dapatdapat menggunakanmenggunakanmodel Network/Graphmodel Network/Graph

27

PerluPerlu penguasaanpenguasaanterminologiterminologi Network/GraphNetwork/Graph

Terminologi Graph

28

Terminologi Graph

DefinisiDefinisi GraphGraph

SebuahSebuah Graph G Graph G dengandengan n n verteksverteksdandan m m ruasruas dinotasikandinotasikan dengandengan ::

29

dandan m m ruasruas dinotasikandinotasikan dengandengan ::G(V,E)G(V,E)

dimanadimana :: V={v1, v2, v3, …., vn}

E = {e1, e2, e3, …., em}

ei = (vi, vj) ruas yg menghubungkansimpul vi dgn simpul vj

Simpul = titik = verteks = node

30

Ruas = branch = arc = edge =busur = garis

Jenis-jenis Graph Null GraphNull Graph Graph Graph TerhubungTerhubung

Graph Graph TakterhubungTakterhubung Graph Graph TakterhubungTakterhubung

Graph Graph BerarahBerarah

Graph Graph TdkTdk berarahberarah

Graph Graph BerlabelBerlabel

dstdst

Contoh (1) :Graph G dengan 5 simpul dan 5 ruas

v

v2v3

e1 e3

e

32

Simpul disebut simpul terpencilv5

v1

v4

v5

e4

e2

e5

v2v3

e1 e3e

Contoh (2) :

Graph G dengan 5 simpul dan 8 ruas

33

v1

v3

v4

v5

e4

e2 e7

e6 e8

Ruas (branch) disebut self -loop e8

e5

Pertanyaan :

v1

1. Mungkinkah sebuah graph hanyamemiliki :

- satu simpul tanpa ruas ???

34

2. Mungkinkah sebuah graph hanya memilikiruas saja tanpa simpul ???

e1

-- memilikimemiliki beberapabeberapa simpulsimpul tetapitetapitanpatanpa ruasruas ??????

Path/Path/JalurJalur

BeberapaBeberapa IstilahIstilah PentingPenting dalamdalam GraphGraph

Cycle /Cycle /SiklusSiklus

Hamiltonian Cycle Hamiltonian Cycle

35

Tree Tree Spanning Tree Spanning Tree

Hamiltonian Cycle Hamiltonian Cycle

Path/Path/JalurJalur

Dari suatu nodeke node lain

36

Dinyatakan dengan sederetan :Simpul – ruas - simpul

v1

v2v3

v4 v5

e1e2

e3

e4e5

e6

e7

37

Path/jalur : - v1, e1, v2, e2, v3, e6, v5

- v1, e1, v2, e4, v4, e7, v5

- v1, e3, v4, e5, v3, e6, v5

e7

- dsb…

v1

v2v3e1

e2

e4e5

e6

38

v4 v5e3

e5e6

e7

v1

v2v3e1

e2

e4e5

e6

39

v4 v5e3

e5e6

e7

v1

v2v3e1

e2

e4e5

e6

40

v4 v5e3

e5e6

e7

Cycle (Cycle (siklussiklus))

SebuahSebuah jalurjalur (path) yang(path) yangdimulaidimulai daridari suatusuatu nodenode dandan

41

dimulaidimulai daridari suatusuatu nodenode dandankembalikembali keke nodenode ybsybs..

Cycle/Cycle/siklussiklus

v1

v2v3

v4 v5

e1 e2

e3

e4e5 e6

e7

42

v1

v2v3

v4 v5

e1 e2

e3e6

e7

v5e7


v1

v2v3

v4 v5

e1 e2

e3

e4e5 e6

e7

43

v1

v2v3

v4

e1 e2

e3 e5

v4 v5e7

v1

v2v3

v4 v5

e1 e2

e3

e4e5 e6

e7


44

e7

v1

v2

v4

e1

e3

e4

dlldll

Hamiltonian CycleHamiltonian Cycle

SebuahSebuah CycleCycle yangyang mengandungmengandungsemuasemua nodenode dandan memilikimemilikisemuasemua nodenode dandan memilikimemilikijumlahjumlah panjangpanjang ruasruas minimalminimal

TreeTree

GraphGraph terhubungterhubung yangyangtidaktidak mengandungmengandung cyclecycle

46

tidaktidak mengandungmengandung cyclecycle

Tree :Tree :

v1

v2v3

v4 v5

e1 e2

e3

e4e5 e6

47

v1

v2v3

v4 v5

e1 e2

e4

e7

v4 v5e3

e7

v1

v2v3

v4 v5

e1 e2

e3

e4e5 e6

e7

v1

v2v3e1 e2Tree

TreeTree yangyang mengandungmengandungsemuasemua nodenode daridari graphnyagraphnya

Spanning TreeSpanning Tree

49

semuasemua nodenode daridari graphnyagraphnya

50

v1

v2v3

v4 v5

e2

e3

e4

e7

Untuk keperluan programming

Graph

Matriks

51

MatriksMatriks ygmenyatakanHubungan antarnodenya

v1 v2 v3 v4

v1 0 1 0 1

52

v2 1 0 1 1v3 0 1 0 0v4 1 1 0 0v5 0 0 1 1

tdk ada ruas (v5,v1) ada ruas (v5,v4)

MasalahMasalahModel Model GraphGraph

Path (Path (JalurJalur))Tree Tree

NeworkNework FlowFlow

Network Optimization MethodNetwork Optimization Method

Spanning TreeSpanning Tree

53

MasalahMasalahModel Model GraphGraph

(Network)(Network)PewarnaanPewarnaan

CycleCycleNeworkNework FlowFlow

BipartisiBipartisi

dlldll

Barat Timur

ContohContoh ::

54

Selatan

TTBB

Barat

Selatan

Timur

55

TTBB

SS

8.00 9.00 10.00 11.00 12.00 13.00 14.00 15.00 16.00

D1

D2

D3

D4

56

D5

D1D1D2D2

D3D3

D4D4

D5D5

Mengajar di Kelas

G1 BI 1A 1B 1CG2 Mat - 1B -

Ada 4 kelas yang harus diberikan pelajaranBahasa Inggris, Matematika, dan IPA oleh4 orang guru.

57

G2 Mat - 1B -G3 IPA 1A 1B 1C

G4 Mat 1A - 1C

Gambarkan Network yang mewakilitabel diatas.

GuruGuru

Mata Mata PelajaranPelajaran

KelasKelas ygyg diasuhdiasuhBentrokBentrok

58

GuruGuru

Mata Mata PelajaranPelajaran

KelasKelas ygyg diasuhdiasuh

Mengajar di Kelas

G1 BI 1A 1B 1CG2 Mat - 1B -G3 IPA 1A 1B 1C

G4 Mat 1A - 1C

59

G4 Mat 1A - 1C

Node 1 : G1/BI/1ANode 1 : G1/BI/1ANode 2 : G1/BI/1BNode 2 : G1/BI/1BNode 3 : G1/BI/1CNode 3 : G1/BI/1C

Node 5 : G3/IPA/1ANode 5 : G3/IPA/1ANode 6 : G3/IPA/1BNode 6 : G3/IPA/1B

Node 4 : G2/Mat/1BNode 4 : G2/Mat/1B

Node 7 : G3/IPA/1CNode 7 : G3/IPA/1CNode 8 : G4/Mat/1ANode 8 : G4/Mat/1ANode 9 : G4/Mat/1CNode 9 : G4/Mat/1C

Node 1 : G1/BI/1ANode 1 : G1/BI/1ANode 2 : G1/BI/1BNode 2 : G1/BI/1BNode 3 : G1/BI/1CNode 3 : G1/BI/1CNode 4 : G2/Mat/1BNode 4 : G2/Mat/1B

Node 5 : G3/IPA/1ANode 5 : G3/IPA/1A

332211

44

66

60

Node 5 : G3/IPA/1ANode 5 : G3/IPA/1ANode 6 : G3/IPA/1BNode 6 : G3/IPA/1BNode 7 : G3/IPA/1CNode 7 : G3/IPA/1C

Node 8 : G4/Mat/1ANode 8 : G4/Mat/1ANode 9 : G4/Mat/1CNode 9 : G4/Mat/1C

55 77

66

9988



332211

44

61



55 7766

9988

332211

44

332211

44

55 7766

9988

62

55 7766

9988



332211

44

63



55 7766

9988

RUANG-1 RUANG-2 RUANG-3

Sesi-1

Sesi-2

332211

55

44

7766

11

33

22

55

66

99

64

Sesi-2

Sesi-3

55 7766

9988

33

44

55

77

99

88

RUANG-1 RUANG-2 RUANG-3

Sesi-1 G1G1--BIBI--1A1A G1/BI/1BG1/BI/1B G3/IPA/1BG3/IPA/1B

65

Sesi-2 G1G1--BIBI--1C1C G3/IPA/1AG3/IPA/1A G4/Mat/1CG4/Mat/1C

Sesi-3 G2G2--MatMat--1B1B G3/IPA/1CG3/IPA/1C G4/Mat/1AG4/Mat/1A

Pada beberapa Masalah

membentuk Network dari suatupersoalan, mempunyai kesulitan

66

persoalan, mempunyai kesulitantersendiri.

4 4 JenisJenis persoalanpersoalansehubungansehubungan dgndgn Network Network

(1). Shortest-Path Problem

(2). Minimal Spanning Tree Problem

67

(2). Minimal Spanning Tree Problem

(3). Maximal Flow Problem

(4). Travelling Salesman Problem

Shortest-Path Problem

PersyaratanPersyaratan ::

(1). Graph (Network) (1). Graph (Network) berlabelberlabel

68

(1). Graph (Network) (1). Graph (Network) berlabelberlabel

(2). (2). AdaAda SumberSumber dandan TujuanTujuan

69Kota_1 Jarak antar kota Kota_2

SetiapSetiap ruasruas dikaitkandikaitkan dengandengan kuantitaskuantitastertentutertentu, , sepertiseperti ::

JarakJarak

70

JarakJarak

WaktuWaktu

UangUang//BiayaBiaya //KeuntunganKeuntungan

mengidentifikasimengidentifikasi jalurjalur terpendekterpendek yang yang menghubungkanmenghubungkan node node awalawal keke node node akhirakhir

Objective :Objective :

71

PanjangPanjang JalurJalur terpendekterpendek dapatdapat berartiberartijarakjarak terpendekterpendek, , cost cost termurahtermurah, , waktuwaktutercepattercepat, , dsbdsb…….…….

SelanjutnyaSelanjutnya ::

Algoritma yang digunakan :

- Greedy- Algoritma Dijkstra- Algoritma Kruskal

72

- Algoritma Kruskal- Algoritma Prims

dsb…

Notasi :

: Jarak dari node i ke node jdij

min(a,b) : Nilai yg minimum antara a dan b

73

min(a,b) : Nilai yg minimum antara a dan b

min(a,b) = a ; jika a b

b ; jika a b

Contoh :

Suatu distributor yg berkedudukan dikotaH harus menghitung rute terpendek yang akan dilalui armadanya menuju kota S dan harus melalui beberapa kota antara H dan harus melalui beberapa kota antara H dan S. Peta jalan yang menghubungkankota S dan kota-kota lainnya hingga kekota S digambarkan dalam bentukjaringan sebagai berikut :

74

Peta Jalan yang dapat dilalui :

AsalH

C

D

P5

3

5

2 73

75

tujuan

H

JB

D

S43

2

16

8

7

Ketentuan dalam Algoritma :

1. 1. PadaPada kondisikondisi awalawal seluruhseluruh node node dalamdalamkategorikategori “unsolved” .“unsolved” .

2. Node 2. Node ii disebutdisebut “solved”, “solved”, jikajika jarakjarak

76

2. Node 2. Node ii disebutdisebut “solved”, “solved”, jikajika jarakjarakminimum minimum daridari node 1 node 1 keke node node ii telahtelahditemukanditemukan. .

3. 3. AlgoritmaAlgoritma berhentiberhenti jikajika semuasemua node node masukmasuk kategorikategori “solved”. “solved”.

Langkah 1 :

1

2

3

4

6

55

43

52

16

8

73

Beri Label node 1 dengan 0 node 1 solved

77

Beri Label node 1 dengan 0 node 1 solved

1

2

3

4

6

55

43

52

16

8

730

Langkah 2 :

1

2

3

4

6

55

43

52

16

8

730

78

Periksa unsolved node yg terdekat ke node 1Kandidatnya : node 2 dan 3

min(d12, d13) = d13 = 4 beri label node 3dgn 4

node 3 solved node

41

2

4

55

3

52

6730

79

4

3

4

643

16

84

1

2

3

4

6

55

43

52

16

8

730

4Langkah 3 :

Cari unsolved node yg terdekat ke solved node 1

80

Bandingkan dan pilih yg terdekat :(1,2)=5; (1,3,4)=5, dan (1,3,6) = 12 pilih (1,2) atau (1,3,4) misal dipilih (1,2)

Cari unsolved node yg terdekat ke solved node 1dan 3 (terhubung langsung).Kandidat : node 2, 4 dan 6

Solved node : 1, 2, 3

1

2

3

4

6

55

43

52

16

8

730

4

5

Unsolved node : 4, 5, 6

81

Cari node terdekat dari 2 dan 3 yg terhubunglangsung dengan node 2 dan 3 dan mempunyaipath terpendek dari node 1 melalui node 2 & 3

Unsolved node : 4, 5, 6

LangkahLangkah 4 :4 :

Kandidat : node 4, 5, 6

12

3

4

6

55

43

52

16

8

730

4

5

Unsolved node i Shortest distance from node 1 to i

82

Unsolved node i Shortest distance from node 1 to i4 min(d24 + label node 2, d34+label

node 3) = min(2+5, 1+4)=5 dr node 35 d25 + label node 2 = 10 dr node 26 d36 + label node 3 = 12 dr node 3

Node 4 solved node, beri label 5 pada node 4

12

4

55

43

52

16

7305

5

83

3 643

16

84

Langkah 5 :

12

3

4

6

55

43

52

16

8

730

4

55

unsolved node, 5 dan 6

84

Unsolved node i Shortest distance from node 1 to i5 min(d25 + label node 2, d45+label

node 4)= min(5+5, 3+5) = 8 dr node 46 min(d36 + label node 3, d46+label

node 4) = min(8+4, 6+5) = 11 dr node 4


12

4

55

3

52

6730

55

8

85

1

3

4

643

16

8

7

4

Langkah 6 :

unsolved node : node 6

12

3

4

6

55

43

52

16

8

730

4

55

8

86

unsolved node : node 6 4Unsolved node i Shortest distance from node 1 to i

6 min(d56 + label node 5, d46+labelnode 4, d36 + label node 3)= min(8+7, 6+5, 8+4) = 11 dr node 4


12

4

55

3

52

6730

55

8

87

1

3

464

32

16

8

7

4 11

12

3

46

55

43

52

16

8

730

4

55

8

11

88

Shortest Path : 1-3-4-6 = 11

1

3

4664 1

60

4

5

11

1 network opt. method1

Documents