LAPORAN PRAKTIKUM RISET OPERASI Shortest Path and Maximum Flow

Asisten Praktikum:

0. Nur Asfi Royhan0. Wahyu Cahyaningrum

Oleh :

Nama: HERWINA EVA YULITASARINIM: 125090500111027

LABORATORIUM STATISTIKAJURUSAN MATEMATIKAFAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAMUNIVERSITAS BRAWIJAYA2013

BAB IPENDAHULUAN

1.1 Latar Belakang

Masalah transportasi dan penugasan merupakan kelompok khusus dari masalah pemrograman linier yang disebut masalah arus jaringan (Network Problem). Topik ini mempunyai penerapan yang luas diberbagai bidang dan juga mempunyai struktur matematika yang memungkinkan dibuatnya prosedur solusi khusus dan efisien. Perbedaan yang nyata antara problem transportasi dengan model-model pemrograman linier yang telah dibahas adalah adanya titik asal dan titik tujuan. Titik asal menawarkan sejumlah unit tertentu yang disebut sebagai penawaran dan titik tujuan membutuhkan sejumlah unit tertentu yang disebut permintaan. Bila total semua penawaran dari setiap titik asal sama dengan total permintaan semua titik tujuan, maka hal ini disebut problem transportasi seimbang.Model network adalah salah satu metode yang digunakan untuk menyelesaikan masalah dalam pencarian rute terpendek. Untuk menyelesaikan masalah rute terpendek tersebut, kita dapat merepresentasikan masalah yang ada menjadi struktur graph, dimana titik menyatakan node dan sisi menyatakan jalur yang menghubungkan dua buah node. Setiap sisi yang ada diberi bobot yang menyatakan jarak antara kedua node tersebut. Network model terdiri dari Shortest Path, Maximum Flow, dan Minimum Spaning Tree. Untuk lebih jelasnya pemahaman menganai bagian dari model network, maka diberikan penjelasan dari studi kasus yang dijelaskan pada bab berikutnya.

1.2 Tujuan

1. Mengetahui model-model jaringan apa saja yang dapat dilakukan untuk membantu pemecahan suatu kasus yang berkaitan dengan riset operasi.2. Memecahkan serta menganalisis suatu permasalahan secara analitis dan sistematis.3. Memenuhi tugas praktikum pertama Riset Operasi.

BAB IITINJAUAN PUSTAKA

Sebuah jaringan terdiri dari sekelompok node yang dihubungkan oleh busur atau cabang. Suatu jenis arus tertentu, berkaitan dengan setiap busur. Arus dalam sebuah busur dibatasi oleh kapasitasnya, yang dapat terbatas, tidak dapat terbatas, maupun tidak terbatas. Jalur adalah urutan busur-busur tertentu yang menghubungkan 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.(Anonim,2011)

Jaringan (network) adalah suatu susunan garis edar (path) yang menghubungkan berbagai titik. Ada beberapa masalah tentang jaringan (network) yaitu :1. Masalah Rute Terpendek (Shortest Path) Berguna untuk menentukan jarak tersingkat antara titik awal Langkah-langkah :a) Dengan beberapa titik tujuanb) Dengan set permamanen

2. Masalah Arus Maksimum (Maximum Flow) Bertujuan untuk memaksimisasi total arus dari titik awal ke satu tujuan melalui cabang-cabang yng terbatas kapasitasnya. Langkah-langkah :a) Pilih secara sembarang garis edar dalam jaringan tersebut, dari titik awal ke titik tujuan.b) Sesuaikan kapasitas pada setiap simpul dengan mengurangkan arus maksimal untuk garis edar yang dipilih dalam langkah 1.c) Tentukan arus maksimal sepanjang garis edar ke arus berlawanan arah pada setiap simpul.d) Ulangi langkah 1,2, dan 3 sampai tidak ada lagi garis edar dengan kapasitas arus yang tersedia.(Glen,1995)Pada masalah jaringan dengan Shortest Path, beberapa metode algoritma yang telah dikembangkan untuk menyelesaikan persoalan jalur terpendek diantaranya algoritma Djikstra, algoritma Floyd-Warshall, dan algoritma Bellman-Ford . Algoritma ini dapat diselesaikan dengan cepat jika kota-kota yang akan dikunjunginya sedikit. Seiring dengan itu muncul permasalahan bagaimana menentukan jalur terpendek jika terdapat banyak jalur alternatif ke kota tujuan dengan mempertimbangkan efisiensi dan waktu sehingga diperlukan ketepatan dalam menentukan jalur terpendek antar suatu kota. Semakin banyak alternatif jalur ke kota tujuan, semakin rumit cara untuk menghitung jalur terpendek. Untuk itu diperlukan metode/ cara yang handal untuk dapat menentukan jalur terpendek dari kota asal ke kota tujuan sehingga diperoleh solusi yang terbaik.(Mutakhiroh Iing, 2007)

Sedangkan pada masalah jaringan dengan Maximum Flow, biasanya seringkali dihadapkan dengan situasi dimana ingin dilakukan pengangkutan maksimum dari titik awal ke titik akhir. Untuk masalah ini banyak dibahas dengan menggunakan metode Ford-Fulkerson.(Winston,2003)

Jaringan yang berhubungan adalah sebuah jaringan di mana setiap dua node dihubungkan dengan sebuah jalur. Masalah Rute terdekat berkaitan dengan penenutan busur busur yang di hubungan daa sebuah jaringan transportasi yang secara bersama sama membentuk jarak terdekat di antara sumber dan tujuan. Algoritma rute terdekat terbagi ke-dalam dua bagian yaitu jaringan asiklis dan siklis. Sebuah jaringan di katakan bersifat asiklis jika tidak memiliki loop. Jika memiliki loop maka jaringan tersebut bersifat siklis.(Taha, 1996)

BAB IIIMETODELOGI

1. Buka program QM. Akan muncul tampilan awal seperti gambar di bawah ini. Klik OK.

2. Pada menu Module pilih sub menu networks.

3. Klik menu file, pilih new. Apabila ingin menghitung biaya dengan jarak terpendek pilih shortest route dan apabila ingin menghitung arus maksimal pilih maximal flow.

A. Jarak Terpendek

1. Setelah memilih shortest route pada menu file, akan muncul kotak dialog shortest route seperti di bawah ini.

Pada kolom title isilah judul data yang akan diinput.Pada kolom Flow Names pilih branch 1, branch 2, branch 3... Isikan jumlah cabang pada kotak Number of Branches.Pada Network type pilih directed.

2. Klik OK. Akan muncul data tabel seperti di bawah ini.

Isilah data tabel tersebut. Start node menunjukkan titik awal suatu cabang dan End node menunjukkan akhir dari cabang tersebut. Pada kolom distance isilah biaya yang dikeluarkan.

3. Setelah semua data diinput, klik ikon solve pada toolbar. Akan muncul kotak Network Result seperti di bawah ini.

B. Arus Maksimal

1. Setelah memilih Maximal Flow pada menu file, kotak dialog Maximal Flow akan muncul.

Pada kolom title isilah judul data yang akan diinput.Pada kolom Flow Names pilih branch 1, branch 2, branch 3... Isikan jumlah cabang pada kotak Number of Branches.

2. Klik OK. Akan muncul data tabel seperti di bawah ini.

Isilah data tabel tersebut. Start node menunjukkan titik awal suatu cabang dan End node menunjukkan akhir dari cabang tersebut. Pada kolom distance isilah kapasitas muatan.

3. Setelah semua data diinput, klik ikon solve pada toolbar. Akan muncul kotak Network Result seperti di bawah ini.

BAB IVPEMBAHASAN

Soal

1. Sebuah mesin dibeli pada tahun 2005. Tahun pembelian mesin dianggap sebagai tahun pertama. Biaya perawatan mesin yang berusia i tahun dan biaya pembelian mesin di awal setiap tahun diberikan pada tabel di bawah ini. Tidak ada biaya pengganti untuk mesin yang akan diganti. Minimalkan biaya total (biaya perawatan dan pembelian) kepemilikan mesin selama 5 tahun. Tentukan tahun dimana mesin baru harus dibeli

Usia di awal tahunBiaya perawatan untuk tahun berikutnya

028000

132000

269000

3120000

4144000

Tahun

Biaya pembelian

195000

2141000

3172000

4199000

5230000

2. Istec Corporation ingin menganalisis masalah maximum flow of cars (arus kendaraan maksimum ; dalam ratusan) yang melewati jalan penghubung antara mess karyawan dengan kantor baru. Jalan penghubung tersebut digambarkan sebagai berikut :42

14 911 4 103

1251

32Jawaban

a. Menggunakan QM1. Dengan menggunakan program QM diperoleh hasil output sebagai berikut

Interpretasi :Untuk meminimumkan biaya total mesin, mesin dibeli pada tahun pertama dan dirawat selama 2 tahun. Setelah mencapai 2 tahun, tepatnya pada tahun 2007, mesin dijual. Pada tahun yang sama sebuah mesin serupa dibeli dan dirawat selama 3 tahun.

2. Dengan menggunakan program QM diperoleh hasil output berikut ini

Interpretasi :Untuk memaksimalkan jumlah pengiriman barang dari kota 1 ke kota 7 dapat melalui 3 jalur, yaitu :

1512451345

Dengan maximum network flow = 42

b. Manual1. Shortest path problem Jangka 1 :C12 = C23 = C34 = C45 = C56= 95 + 28= 123 Jangka 2 :C13 = C24 = C35 = C46= 141 + 32 + 28= 201

Jangka 3 :C14 = C25 = C36= 172 + 69 + 32 + 28= 301 Jangka 4 :C15 = C26= 199 + 120 + 69 + 32 + 28= 448 Jangka 5 :C16= 230 + 144 + 120 + 69 + 32 + 28= 623

2. Dengan penghitungan manual diperoleh :

(1,5)

32

(1,2)(2,4)(4,5)

91410

(1,2)(2,3)(3,4)(4,5)

11111

BAB VPENUTUP5.1 Kesimpulan

Network analysis terdiri dari rute terdekat dan arus maksimum, dimana untuk masalah rute terdekat berkaitan dengan penentuan busur busur yang membentuk jalan terpendek dari node sumber ke node tujuan, sedangkan arus maksimum bertujuan untuk mengirim jumlah maksimum barang tetentu dari satu node sumber ke satu node tujuan melalui sebuah jaringan busur dengan kapasitas terbatas.Untuk permasalahan shotest path, dapat disimpulkan bahwa untuk meminimumkan biaya total mesin, mesin dibeli pada tahun pertama dan dirawat selama 2 tahun. Setelah mencapai 2 tahun, tepatnya pada tahun 2007, mesin dijual. Pada tahun yang sama sebuah mesin serupa dibeli dan dirawat selama 3 tahun.Untuk permasalahan max flow, dapat disimpulkan bahwa arus kendaraan maksimum yang memalui jalan penghubung antara mess karyawan dengan kantor baru memiliki muatan maksimum yang dapat dimuat sebanyak 4200 unit kendaraan dengan berbagai jalur yang di tempuh.

5.2 Saran

Dalam melakukan analisis suatu permasalahan baik itu pada kasus Shortest Path maupun Maksimum Flow, dibutuhkan ketelitian agar tidak terjadi kesalahan selama proses analisis. Sehingga hasil yang diperoleh benar-benar akurat.

DAFTAR PUSTAKA

Anonim. 2011.http://digilib.petra.ac.id/.../jiunkpe-ns-s1-200425497099-4035-jadwal-chapter2.pdf. Diakses pada tanggal 20 Maret 2013.Glen, M.C. 1995. http://project.mvps.org/networkanalysis.htm. Diakses pada tanggal 19 Maret 2013.

Taha, H.A. 1996. Riset Operasi JilidII. Binarupa Aksara. Jakarta.Mutakhiroh, Iing, et al. (2007). Pemanfaatan metode heuristik dalam pencarian jalur terpendek dengan algoritma semut dan algoritma genetika. Seminar Nasional Aplikasi Teknologi Informasi, Juni 2007. Retrieved 24 July 2010 from .Wayne Winston, Operations Research Applications and Algorithms 4th. Edition, 2003. Publisher: Duxbury Press.

LAMPIRAN