analisis jaringan - ? web viewanalisis jaringan. jaringan lahir karena berbagai keperluan seperti:...

Download Analisis Jaringan - ? Web viewAnalisis Jaringan. Jaringan lahir karena berbagai keperluan seperti: transportasi,

Post on 26-Apr-2019

212 views

Category:

Documents

0 download

Embed Size (px)

TRANSCRIPT

Analisis Jaringan

PAGE

144

BAB V

Analisis Jaringan

Jaringan lahir karena berbagai keperluan seperti: transportasi, listrik, komunikasi, perencanaan proyek, aliran air, pembuatan jalan, dan lain-lain. Saat ini jaringan sangat penting, sebab dengan jaringan maka masalah yang besar dan rumit dapat disederhanakan. Ada beberapa jaringan yang dapat diselesaikan dengan permasalahan program linear.

Pada kajian di sini akan dibahas empat masalah jaringan, yaitu: permasalahan lintasan terpendek, masalah diagram pohon terpendek, masalah aliran maksimum, dan penyelesaian proyek dengan Program Evaluation and Review Technique (PERT), dan Critical-Path Method (CPM).

Beberapa Istilah yang dipakai dalam Analisis Jaringan

Jaringan didefinisikan sebagai gabungan dua himpunan yaitu himpunan node dan himpunan arc. Himpunan node dilambangkan dengan V dan himpunan arc dilambangkan dengan A.

Arc terdiri dari pasangan terurut dari node dan menggambarkan arah gerakan yang mungkin.

Untuk tujuan ini, misalkan jaringan memuat arc(j, k), maka arah gerakan yang mungkin adalah dari node j ke node k.

Perhatikan jaringan berikut.

Gambar contoh sebuah Jaringan

Rangkaian arc sedemikian hingga untuk setiap arc mempunyai tepat satu node persekutuan bersama dengan arc sebelumnya disebut chain (rantai).

Lintasan adalah rantai yang memenuhi pernyaratan bahwa untuk setiap node akhir suatu arc adalah node awal dari arc sebelumnya.

Pada contoh jaringan di atas, (3, 1) (1, 5) (4, 5) adalah rantai tetapi bukan lintasan, sedangkan (3, 1) (1, 5) (5, 4) adalah lintasan. Lintasan ini menggambarkan perjalanan (gerak) dari node 3 ke node 4.

Selanjutnya kita perhatikan contoh permasalahan berikut.

Gambar 3.1 Jarak antar tempat peristirahatan (dalam kilometer)

Sebuah lokasi sebut saja Taman Sari akan dijadikan sebagai taman wisata yang sejuk, nyaman, dan lingkungan yang terlindungi termasuk satwa di dalamnya. Pada node (bertanda huruf O, A, B, C, D, E, T) dibuat tempat peristirahatan. Jarak antar tempat peristirahatan seperti terlihat pada gambar di atas (dalam kilometer) lihat gambar 3.1. Untuk melindungi satwa dan kesejukan Taman Sari tersebut semua mobil pribadi, termasuk angkutan umum dilarang masuk. Sistem transportasi yang akan dibuat adalah kereta listrik, banyaknya kereta yang lewat setiap jalur dibatasi. Banyaknya kereta yang lewat maksimum setiap harinya terlihat pada Gambar 3.2, Ini diperlukan untuk menjaga ketenangan taman. Pintu masuk adalah node O, dan pintu keluarnya node T. Kembalinya kereta dari T ke O melalui jalur luar taman. Selanjutnya untuk kebutuhan air, akan dibuat jaringan pipa air dari O ke masing-masing tempat peristirahatan.

Gambar 3.2 Maksimum banyaknya kereta yang boleh lewat setiap harinya

Permasalahan yang muncul ada tiga yaitu:

1. Lewat jalur mana dari O menuju ke T sehingga diperoleh jarak terpendek, berapa jaraknya.

2. Buatlah jaringan air yang menghubungkan semua tempat peristirahatan agar panjang pipa yang digunakan minimum.

3. Buatlah jalur kereta, agar banyaknya lintasan maksimum.

Masalah yang pertama disebut sebagai masalah lintasan terpendek, masalah kedua disebut masalah diagram pohon terpendek, dan masalah ke tiga disebut masalah aliran maksimum.

1. Masalah Lintasan Terpendek

Masalah lintasan terpendek adalah masalah yang menyangkut node, panjang jalur, arah lintasan. Dalam lintasan ini perlu diperhatikan khusus yaitu node supply (node awal) dan node demand (node akhir). Dalam hal masalah di atas, node supply adalah node O, dan node demand adalah node T. Untuk menyelesaikan masalah lintasan terpendek ada algoritma yang bisa dipakai yaitu:

Algoritma masalah lintasan terpendek

a. Tujuan pada iterasi ke-n: Tentukan node terdekat dari titik awal (node awal).

b. Input pada iterasi ke-n: node terdekat ke n-1 ke node awal, termasuk di dalamnya lintasan terpendek dan jarak dari node awal. (node-node ini ditambah dengan node awal disebut node terselesaikan, yang lain node belum terselesaikan).

c. Kandidat untuk node terdekat ke-n: Setiap node terselesaikan yang langsung berhubungan dengan satu atau lebih node belum terselesaikan sebagai kandidat-node belum terselesaikan yang mempunyai hubungan terpendek.

d. Perhitungan node terdekat ke-n: Untuk setiap node terselesaikan dan node kandidat, ditambah dengan jarak diantaranya. Kandidat yang mempunyai total jarak terpendek ke-n.

Untuk masalah lintasan terpendek pada Taman Sari di atas adalah sebagai berikut:

Node awal adalah node O dan node akhir adalah node T.

Perhitungan lintasan dapat dilihat pada Tabel 3.3 berikut:

Tabel 3.3 Penerapan Algoritma lintasan terpendek pada Taman sari

n

Node terselesaikan Tersambung langsung dengan Node belum terselesaikan

Sambungan terpendek node belum terselesai-kan

Total jarak

Node terde- kat ke-n

Jarak

Minimum

Sambung-

an terakhir

1

O

A

2

A

2

OA

2,3

O

A

C

B

4

2 + 2 = 4

C

B

4

4

OC

AB

4

A

B

C

D

E

E

2 + 7 = 9

4 + 3 = 7

4 + 4 = 8

E

7

BE

5

A

B

E

D

D

D

2 + 7 = 9

4 + 4 = 8

7 + 1 = 8

D

D

8

BD

ED

6

D

E

T

T

8 + 5 = 13

7 + 7 = 14

T

13

DT

Jarak minimum dari node O ke node T adalah 13 kilometer dengan jalur

O ( A ( B ( E ( D ( T atau

O ( A ( B ( D ( T

Masalah jaringan terpendek di atas dapat kita pandang sebagai masalah transshipment yaitu dengan mengisikan bilangan besar M pada jalur yang tidak ada, oleh karena itu tabel transportasi dari masalah jaringan ini adalah sebagai berikut.

Tabel Jarak antar tempat

A

B

C

D

E

T

O

2

5

4

M

M

M

A

0

2

M

7

M

M

B

M

0

1

4

3

M

C

M

M

0

M

4

M

D

M

M

M

0

1

5

E

M

M

M

1

0

7

Apabila kita kerjakan dengan Solver, yaitu dengan menggantikan M menjadi 1000 dan masing-masing kapasitas 1 serta permintaan 1, maka akan diperoleh hasil berikut.

Tabel Hasil perhitungan dengan Solver

A

B

C

D

E

T

O

1

0

0

0

0

0

1

A

0

1

0

0

0

0

1

B

0

0

0

1

0

0

1

C

0

0

1

0

0

0

1

D

0

0

0

0

0

1

1

E

0

0

0

0

1

0

1

1

1

1

1

1

1

Total

13

Dari tabel hasil di atas, diperoleh bahwa total jarak adalah 13 dengan lintasan O A B D T.

Catatan.

Dengan Solver, lintasan yang diperoleh hanya tunggal (1 macam).

Contoh 2.

Sebuah Toko Bangunan akan menggunakan mobil Pickup untuk melayani pengiriman bahan bangunan kepada pembeli. Harga mobil Pickup baru Rp 60 juta. Mobil tersebut setelah dipakai semakin lama semakin turun harganya, sedangkan biaya perwatannya semakin lama semakin besar. Besarnya biaya perawatan dan harga jual mobil terlihat pada tabel berikut.

Tabel Biaya perawatan dan Harga Jual Kembali Mobil Pickup

Umur

Mobil (Th)

Biaya

Perawatan (Jt)

Harga Jual

(Trade In /Jt)

0

2

1

5

45

2

9

35

3

13

30

4

18

25

5

22

20

6

25

15

7

28

10

Dengan asumsi harga mobil Pickup baru tetap, pada tahun ke-berapa mobil harus diganti agar biaya total yang dikeluarkan minimum?

Penyelesaian

Pada masalah jaringan ini, kita akan melibatkan delapan node V= {1, 2, 3, 4, 5, 6, 7, 8}. Node i menggambarkan awal tahun ke-i.

Untuk setiap i < j, arc(i, j) menggambarkan pembelian mobil baru pada awal tahun ke-i dan tetap memakainya sampai awal tahun ke-j.

Panjang arc (i, j) atau cij adalah total pengeluaran biaya penggunaan mobil dari awal tahun ke-i sampai awal tahun ke-j jika mobil dibeli pada awal tahun ke-i dan mobil akan ditukar mobil baru lagi pada awal tahun ke-j.

Jadi

Cij = biaya perawatan tahun ke-i, i+1, ..., j-1

+ biaya pembelian mobil baru pada awal tahun ke-i

- harga jual mobil pada awal tahun ke-j.

Dengan menerapkan bentuk ini pada masalah di atas, maka diperoleh.

C12 = 2 + 60 45 = 17

C13 = 2 + 5 + 60 35 = 32

C14 = 2 + 5 + 9 + 60 30 = 46

C15 = 2 + 5 + 9 + 13 + 60 25 = 64

C16 = 2 + 5 + 9 + 13 + 18 + 60 20 = 87

C17 = 2 + 5 + 9 + 13 + 18 + 22 + 60 15 = 114

C18 = 2 + 5 + 9 + 13 + 18 + 22 + 25 + 60 10 = 144

C23 = 2 + 60 45 = 17

C24 = 2 + 5 + 60 35 = 32

C25 = 2 + 5 + 9 + 60 30 = 46

C26 = 2 + 5 + 9 + 13 + 60 25 = 64

C27 = 2 + 5 + 9 + 13 + 18 + 60 20 = 87

C28 = 2 + 5 + 9 + 13 + 18 + 22 + 60 15

View more >