Teori Optimasi 1

Analisa Jaringan

Teori Optimasi

Teori Optimasi 2

DEFINISI JARINGANJaringan terdiri dari sekelompok node/vertek yang dihubungkan oleh busur/ cabang.

Contoh : dalam jaringan transportasi, kota mewakili node dan jalan raya mewakili busur, dengan lalu lintas mewakili arus busur

Network G=(N,A)

dimana N : himpunan node

A : himpunan busur

Teori Optimasi 3

N = {1, 2, 3, 4, 5}

A = {(1,2), (1,3), (2,3), (2,4), (2,5), (3,4), (3,5), (4,5)}

Suatu jenis arus tertentu berkaitan dengan setiap jaringan (misalnya, arus produksi minyak dalam jaringan pipa dan arus lalu lintas dalam jaringan transportasi). Arus dalam sebuah busur dibatasi oleh kapasitasnya. Sebuah busur dikatakan terarah jika busur tersebut memungkinkan arus positif dalam satu arah dan arah nol dalam arah yang berlawanan

Teori Optimasi 4

Jalur urutan busur-busur tertentu yang menghubungkan dua node tanpa bergantung pada orientasi busur-busur tersebut secara individual.Contoh : busur (1,3), (3,2) dan (2,4) mewakili sebuah jalur dari node 1 ke node 4.

Loop jika jalur itu menghubungkan sebuah node dengan dirinya sendiri.Contoh : busur (2,3), (3,4) dan (4,2) membentuk sebuah loop

Teori Optimasi 5

Penentuan jadwal kegiatan (mulai & akhir) suatu proyek konstruksi.

Instalasi jaringan pipa. Biaya minimal minimal spanning tree

Penentuan jarak minimal dari 2 kota dalam suatu jaringan jalan. algoritma jarak terpendek

Penentuan kapasitas maksimum dalam suatu sistem distribusi. max flow algorithm

Penentuan biaya minimal. minimum cost capasitased network algorithm

Beberapa contoh permasalahan yang dapat dimodelkan dengan analisa jaringan :

Teori Optimasi 6

Algoritma ES & EF (early start & early finish) Algoritma LS & LF (lates start & lates finish)

Penentuan jadwal kegiatan (mulai & akhir) suatu proyek konstruksi :

Teori Optimasi 7

Catatan :1. Sebelum semua kegiatan dimulai, semua kegiatan

yang mendahului harus sudah diselesaikan.2. Anak panah hanya menunjukan urutan aktifitas3. Dua events hanya dihubungkan dengan satu

aktifitas4. Jaringan hanya dimulai dari satu kejadian awal

dan diakhiri satu kejadian akhirDari Masalah (3) dan (4) diatas diselesaikan dengan : Aktivitas semu (dummy activity) : suatu kejadian

tanpa bobot (tidak memerlukan waktu/biaya/fasilitas)

Teori Optimasi 8

6 event, 7 activity

Teori Optimasi 9

Kegiatan ES EF

a1a2a3a4a5a6a7

00424

119

2495

111918

Algoritma ES & EF (early start & early finish)6 event, 7 activity

ai : aktivitas ke-ici : bobot aktivitas ke-iES: early startEF: early finish

Jalur kritis A ke Fa2, a5, a6 dengan lama waktu 19 minggu

ES EF

(ai, ci)

Teori Optimasi 10

Algoritma LS & LF (lates start & lates finish)6 event, 7 activity

ai : aktivitas ke-ici : bobot aktivitas ke-iLS: lates startLS: lates finish

LS LF

(ai, ci)Kegiatan ES EF LS LF

a1a2a3a4a5a6a7

00424

119

2495

111918

50574

1110

74

1010111919

Teori Optimasi 11

Perbedaan waktu antara LF dan EF disebut slack (float)

Pada aktivitas ke-7 (a7)

EF7 = 18LF7 = 19

S7 = 1

Sehingga Pelaksanaan a7 dapat ditunda 1 minggu

Untuk kegiatan tanpa slack atau s = 0, tidak dapat ditunda pelaksanaannya.

Teori Optimasi 12

Soal :Tentukan ES, EF, LS, LF dan S, serta jalur kritisnya jaringan berikut :

Teori Optimasi 13

Teori Optimasi 14

Teori Optimasi 15

Teori Optimasi 16

Penyajian Masalah Network dengan Persamaan Linier

Jalur kritis jalur terpanjang

Misal Xij variabel yang menentukan dilalui (dipilih) atau tidaknya aktivitas aij oleh jalur kritis

Nilai Xij 1 : jika aktivitas aij terpilih sebagai anggota dari jalur kritis

0 : jika aktivitas aij tdk terpilih

Teori Optimasi 17

Contoh :

Dari gambar

Jalur kritis = rk {a13, a34, a46}Karena a12 rk rk = 0

a13 rk rk = 1

LP :Tentukan nilai x12, x13, x25, x34, x46, x56Maksimumkan : Z = c12x12 + c13x13 + c25x25 + c34x34 + c46x46 + c56x56Dengan batasan :1 = x12 + x13 pada titik awalX46 + x56 = 1 pada titik akhirX13 = x35 + x34 dalam rangkaianX56 = x25 + x35 dalam rangkaianx12, x13, x25, x34, x46, x56 {0,1}