Praktikum RO 1 [PDF]

Citation preview

LAPORAN PRAKTIKUM RISET OPERASI “ Shortest Path and Maximum Flow“ Asisten Praktikum: 1 2



Nur Asfi Royhan Wahyu Cahyaningrum



Oleh : Nama NIM



: HERWINA EVA YULITASARI : 125090500111027



LABORATORIUM STATISTIKA JURUSAN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS BRAWIJAYA 2013 BAB I



PENDAHULUAN 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 II TINJAUAN 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 tujuan b) 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 III



METODELOGI 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 IV



PEMBAHASAN 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 Biaya Usia di Biaya perawatan pembelian awal untuk tahun tahun berikutnya 0 28000 1 32000 2 69000 3 120000 4 144000 Tahun 1 2 3 4 5



95000 141000 172000 199000 230000



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 : 2



4



14 9 1



11



3



12



4



10 5



32 Jawaban a.



Menggunakan QM 1. 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 : 1→5 1→2→4→5 1→3→4→5 Dengan maximum network flow = 42



b.



Manual 1. 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) 9 (1,2) 1



(2,4) 14



(2,3) 11



(4,5) 10



(3,4) 1



(4,5) 1



BAB V PENUTUP 5.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-2004254970994035-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