Riset Operasi

KELOMPOK

:

Citra Sari Dini Rohaeni Ema Nur Luthfiyani Krisyanti Amalia Ratih Rahmawati

(0607127) (0607131) (0607263) (060641) (060541)

TUGAS RISET OPERASI RANGKUMAN MODEL JARINGAN I.

DEFINISI JARINGAN

Sebuah jaringan terdiri dari sekelompok node yang dihubungkan oleh busur atau cabang. Suatu jenis arus tertentu berkaitan dengan setiap busur. Notasi standar untuk menggambarkan sebuah jaringan G adalah G = (N,A), dimana N adalah himpunan node dan A adalah himpunan busur. Suatu jenis arus tertentu berkaitan dengan setiap jaringan. Pada umumnya, arus dalam sebuah busur dibatasi oleh kapasitasnya, yang dapat terbatas atau tidak terbatas. Sebuah busur dikatakan terarah atau terorientasi jika busur tersebut memungkinkan arus positif dalam satu arah dan arus nol dalam arah yang berlawanan. Karena itu, jaringan yang terarah adalah jaringan dengan semua busur yang terarah. Jalur adalah urutan busur-busur tertentu yang menghubungajan dua node tanpa bergantung pada orientasi busur-busur tersebut secara individual. Jalur akan membentuk sebuah loop atau siklus jika jalur itu menghubungkan sebuah node dengan dirinya sendiri. Sebuah loop yang terarah (atau sebuah sirkuit) adalah sebuah loop di mana semua busur-busurnya memiliki arah atau orientasi yang sama. Jaringan yang berhubungan adalah sebuah jaringan dimana setiap dua node dihubungkan dengan sebuah jalur. Pohon adalah sebuah jaringan yang berhubungan yang dapat hanya melibatkan sebagian dari node dan sebuah pohon perentangan adalah sebuah jaringan yang berhubngan yang mencakup semua node dalam jaringan tersebut tanpa loop.

1

II.

MASALAH POHON PERENTANGAN

Model yang dihasilkan adalah model khas dari masalah pohon perentangan minimal, dimana kita menginginkan pohon perentangan yang menghasilkan jumlah terkecil dari busur-busur penghubung. Akibatnya pohon perentangan minimal menangani penemuan yang paling “efisien” diantar semua node dalam jaringan, yang berdasarkan definisinya, tidak dapat mencakup loop atau siklus apapun. Algoritma pohon perentangan minimal memerlukan awal dari salah satu node manapun dan menghubungkannya dengan node terdekat dalam jaringan tersebut. Dua node yang dihasilkan lalu membentuk himpunan yang dihubungkan, C, dengan node sisanya membentuk node yang tidak dihubungkan, C. Selanjutnya, kita memilih sebuah node dari himpunan yang tidak dihubngkan yang terdekat (memiliki panjang busur terpendek) ke salah satu node dalam himpunan yang dihubungkan. Node yang dipilih tersebut lalu disingkirkan dari himpunan yang tidak dihubungkan dan dimasukkan ke dalam himpunan yang dihubungkan. Proses ini diulangi sampai himpunan yang tidak dihubungkan kosong (atau dengan kata lain, sampai semua node dipindahkan dari C ke himpunan C). Jarak terdekat yang sama dapat dipilih secara sembarang. Tetapi, jarak yang sama tersebut menunjukkan adanya pemecahan alternatif.

III.

MASALAH RUTE TERDEKAT

Masalah rute terdekat berkaitan dengan penentuan busur-busur yang dihubungakan dalam sebuah jaringan transportasi yangs ecara bersama-sama membentuk jarak terdekat di antara sumber dan tujuan. Penerapan tersebut juga diikuti dengan penyajian algoritma pemecahan. Contoh Penerapan rute terdekat Sebuah perusahaan penyewaan mobil sedang mengembangkan sebuah rencana penggantian armadanya dalam 5 tahun mendatang. Sebuah mobil harus dipergunakan setidakanya 1 tahun sebelum penggantian dapat dipertimbangkan. Tabel 1 meringkas biaya penggantian per mobil (dalam ribuan dollar) sebagai fungsi dari waktu dan jumlah tahun operasi. Biaya ini mencakup pembelian, nilai sisa, biaya operasio, dan

2

perawatan. Masalah ini dapat direpresentasikan dengan sebuah jaringan sebagai berikut. Setiap tahun diwakili dengan sebuah node. “Panjang” sebuah busur yang menghubungkan dua node sama dengan biaya penggantian yang bersangkutan seperti yang diberikan dalm tabel 1. Gambar 1 memperlihatkan jaringan ini. Masalahnya jadi menemukan “rute” terdekat dari node 1 ke node 5. ”Rute” terdekat dapat ditentukan dengan menggunakan algoritma yang akan kami sajikan dalam bagian selanjutnya. 1

2

3

4

5

4,0

5,4

9,8

13,7

4,3

6,2

8,1

2

4,8

7,1

3

4,9

4

Tahun 1

ALGORITMA RUTE TERDEKAT A.

ALGORITMA ASIKLIS Algoritma Asiklis didasari oleh penggunaan perhitungan rekursif, yang merupakan dasar dari perhitungan pemrograman dinamis. Langkah-langkah dari algoritma ini diterangkan melaui contoh numerik. Contoh Node 1 adalah node awal (sumber atau asal) dan node 7 adalah titik terminal (tujuan). Jarak dij antara node i dan j diberikan secara lagsung untuk setiap busur. Misalnya d12 = 2. Jaringan ini bersifat asiklis karena mencakup loop. Anggaplah uj = jarak terdekat dari node 1 ke node j

2 [2, 1]

5 5

1

[7, 2]

4

7 3

3

6

2

11

[0, -]

8

10 4

6

[7, 3] 3

7

[13, 5] 9

1 [4, 1]

[5, 3]

Dimana node u1 = 0 berdasarkan definisinya. Nilai-nilai uj, j = 1, 2, …, n, dihitung secara rekursif dengan rumus berikut ini jarak terdekat ui ke satu node i yang tepat mendahuluinya uj = min

plus jarak dij antara node saat ini j ke node sebelumnya i

= min { ui + dij } Rumus rekursif mengharuskan bahwa jarak terdekat uj ke node j dihitung setelah kita menghitung jarak terdekat ui ke setiap node sebelumnya i yang dihubungkan ke j dengan sebuah busur langsung. Dalam pemecahan akhir dari model rute terdekat ini, kita juga harus mengidentifikasi node-node yang ditemui sepanjang rute tersebut. Untuk mncapai tujuan ini, kita mengggunakan prosedur pelabelan yang mengkaitkan label berikut ini dengan node j: label node j = [uj,n] di mana n adalah node j yang tepat mendahuluinya, yang mengarah pada jarak terdekat uj; yaitu uj = min { ui + dij } = un + dnj Berdasarkan definisinya, label di node 1 adalah [0, -], yang menunjukkan bahwa node 1 adalah sumber.

Tabel berikut memberikan urutan perhitungan yang mengarah pada pemecahan akhir.

4

Node j 1 2 3 4 5 6 7

Perhitungan uj u1 = 0 u2 = u1 + d12 = 0 + 2 = 2, dari 1 u3 = u1 + d13 = 0 + 4 = 4, dari 1 u4 = min { u1 + d14, u2 + d24, u3 + d34} = min {0 + 10, 2 + 11, 4 + 3} = 7 dari 3 u5 = min { u2 + d25, u4 + d45 } = min {2 + 5, 7 + 8} = 7 dari 2 u6 = min { u3 + d36, u4 + d46 } = min {4 + 1, 7 + 7} = 5, dari 3 u7 = min { u5 + d57, u6 + d67 } = min {7 + 6, 5 + 9} = 13, dari 5

Label [0, -] [2, 1] [4, 1] [7, 3] [7, 2] [5, 3] [13, 5]

Rute optimum tersebut diperoleh dengan dimulai dari node 7 dan menelusuri ke belakang dengan menggunakan informasi label. Urutan berikut ini memperlihatkan prosedur tersebut: (7) → [13,5] → (5) → [7,2] → (2) → [ 2,1] → (1) Algoritma ini pada kenyataannya memberikan jarak terdekat antara node 1 dan setiap node lainnya dalam jaringan ini. B.

ALGORITMA SIKLIS (Dijakstra) Algoritma siklis memungkinkan sebanyak mungkin kesempatan sebagaimana yang diperlukan untuk mengevaluasi ulang sebuah node. Ketika terlihat bahwa jarak terdekat ke sebuah node telah dicapai, node tersebut dikeluarkan dari pertimbangan lebih lanjut. Proses ini berakhir ketika node tujuan dievalusi. Algoritma siklis menggunakan dua jenis label: sementara dan tetap. Dengan format [d, n], dimana d adalah jarak terdekat yang sejauh ini tersedia untuk node saat ini, dan n adalah node yang tepat mendahuluinya yang memungkinkan realisasi jarak d. Algoritma ini memulai dari node sumber yang memiliki label tetap [0, -]. Selanjutnya kita mempertimbangkan semua node yang dapat dicapai secara langsung dari node sumber tersebut dan lalu menentukan labelnya yang sesuai. Label yang baru dibuat ini dinyatakan sebagai label sementara. Label tetap berikutnya dipilih dari di antara semua label sementara saat ini dengan d terkecil dalam label [d, n] yang bersangkutan (angka yang sama dipilih secara sebarang). Proses ini lalu diulangi untuk node terakhir yang telah dinyatakan dengan label tetap. Dalam kasus demikian, label sementara dari sebuah node 5

hanya dapat diubah jika label baru tersebut menghasilkan jarak d yang lebih dekat. MASALAH

RUTE

TERDEKAT

DIPANDANG

SEBAGAI

MODEL

TRANSSHIPMENT Kita dapat memandang jarinagn rute terdekat sebagai sebuag model transportasidengan satu sumber dan satu tujuan. Penawaran di sumber adalah satu unit dan permintaan di tujuan juga satu unit. Satu unit akan mengalir dari sumber ke tujuan melalui rute yang dapat diterima dalam jaringan tersebut. Tujuannya adalah meminimumkan jarak yang ditempuh oleh unit tersebut sementara mengalir dari sumber ke tujuan. Lihat pengembangan model transshipment pada jaringan Gambar 8-12. Model transshipment hanya menghitung jarak terdekat diantara dua node. Jadi deangan asumsi bahwa kita tertarik untuk menentukan jarak-jarak terdekat diantara dua node 1 dan 7 , (Tabel 8-4) memberikan model transsphipment yang berkaitan dengan masalah ini. Jumlah B biasanya dirujuk sebagai buffer sama dengan 1, karena disetiap saat selama transshipment ini tidak lebih dari satu unit akan memalui setiap node dalam jaringan ini. Catat pula bahwa node 1 tidak berfungsi sebagai tujuan, karena node ini merupakan sumber (utama) untuk jaringan ini. demikian pula, node 7 tidak dapat bertindak sebagai sumber, karena mewakili tujuan akhir dari arus unit tersebut. “ Biaya transportasi” sama dengan jarak yang bersangkutan. Sel yang berwarna abu-abu berarti bawha rute yang bersangkutan tidak tersedia dan harus diberikan biaya M yang sangat tinggi ketika memecahkan model ini. Yang terkahir, jarak dari sebuah node ke node itu sendiri adalah nol. Tabel 8-4 juga memberikan pemecahan optimum, yang diperoleh dari penggunaan teknik transportasi. Tabel tersebut memperlihatkan bahwa x12 = 1, x26 = 1, x33= =1 , x44 = 1 x57 = 1 , x56 = 1 nilai x33=x44= 1

tidak berkonstribusi bagi pemecahan, karena keduannya

menghubungkan node 3 dan 4 dengan node itu sendiri. Sehingga x12=1, x26= 1, x65= 1, x57=1 yang memperlihatkan bahwa rute optimal adalah 1

2

6

5

7

(kondisi

optimalitas seperti ini memperlihatkan pemecahan optimum alternatif antara node 1 dan 7). 6

9

5

7

4 7

8

1

10 2

9 8

23

5

10 1

2

2

6

2

8

5 2

3

2

4

8 3 8

4

9

3 5

1

11

1 Gambar 8-12

7