MENENTUKAN LINTASAN TERPENDEK SUATU GRAF BERBOBOT DENGAN PENDEKATAN PEMROGRAMAN DINAMIS
Oleh 1
Novia Suhraeni , Asrul Sani2, Mukhsar3
ABSTRACT One of graph application on whole life is to establish the shortest track between two nodes, problem of shortest track is an optimation problem which minimum value of some tracks will be find. A lot of methods can be used to solve optimation problem, dinamic program is one of them. Dinamic program is a method that scattering the solution becomes a horde steps or phasesso the solution of the problem can be viewed from a connecting structure. This research purpose to determine the shortest track of a quality graph with dinamic program approachment. There are two approachment can be used in dinamic program: increase dinamic program and decrease dinamic program. Output of these research are the optimum route of case 1 with the shortest track 19 km is A – C – E – H – I, and optimum route in case 2 with the shortest track 25 km is A – C – F – H – K. Keywords : shortest track, quality graph, dinamic program. PENDAHULUAN Graf merupakan model matematika yang sangat kompleks dan rumit, tetapi bisa juga menjadi solusi terhadap beberapa kasus tertentu. Banyak sekali aplikasi menggunakan graf sebagai alat untuk mempresentasikan suatu persoalan sehingga dapat diselesaikan dengan baik. Secara umum graf merupakan suatu diagram yang memuat informasi yang dapat diaplikasikan dalam kehidupan sehari-hari. Salah satu aplikasi graf dalam kehidupan seharihari adalah menentukan lintasan terpendek antara dua buah simpul (node). Misalnya terdapat banyak lintasan yang menghubungkan kota asal ke kota tujuan, maka yang dicari adalah lintasan dengan bobot paling minimum dari kota asal menuju kota tujuan. Bobot dapat berupa jarak, waktu tempuh, atau ongkos transportasi dari satu node ke node yang lain yang membentuk lintasan tertentu. Dengan kata lain dapat diartikan lintasan terpendek adalah bobot minimal suatu lintasan. Permasalahan lintasan terpendek merupakan permasalahan optimasi dimana akan dicari nilai minimum dari beberapa lintasan. Banyak metode yang dapat digunakan untuk menyelesaikan permasalahan optimasi, salah satunya adalah pemrograman dinamis. Pemrograman dinamis merupakan metode pemecahan masalah dengan cara menguraikan solusi menjadi sekumpulan langkah atau tahapan sedemikian sehingga solusi dari persoalan dapat dipandang dari serangkaian keputusan yang saling berkaitan. Tujuan utama model ini ialah untuk mempermudah penyelesaian persoalan optimasi yang mempunyai
karakteristik tertentu. Ide dasar program dinamis ialah membagi persoalan menjadi beberapa yang lebih kecil sehingga memudahkan penyelesaiannya [1]. Pada penelitian ini akan dibahas bagaimana menentukan lintasan terpendek suatu graf berbobot dengan pendekatan pemrograman dinamis. TINJAUAN PUSTAKA Graf Graf G didefinisikan sebagai pasangan dua himpunan (V,E), ditulis dengan notasi G = (V,E). V adalah himpunan tidak kosong dari simpul-simpul (vertices atau node) dan E adalah himpunan sisi (edges atau arcs) yang menghubungkan sepasang simpul [2]. Terminologi Graf Ada beberapa terminologi graf yang perlu diketahui, antara lain: 1. Bertetangga (Adjacent) 2. Bersisian (Incidency) 3. Simpul Terpencil (Isolated Vertex) 4. Derajat (Degree) 5. Lintasan (Path) 6. Sirkuit atau Siklus 7. Terhubung. Jenis Graf Berdasarkan orientasi arah pada sisi dan bobotnya, maka secara umum graf dibedakan atas empat jenis: 1. Graf Tidak Berarah Dan Berbobot (Undirected Graph).
2. Graf Berarah Dan Berbobot (Directed Graph). 3. Graf Tidak Berarah Dan Tidak Berbobot. 4. Graf berarah dan tidak berbobot. Beberapa Graf Khusus Terdapat beberapa jenis graf sederhana khusus. Berikut ini didefinisikan beberapa graf khusus yang sering ditemui: 1. Graf Lengkap (Complete Graph) 2. Graf Lingkaran 3. Graf Teratur 4. Graf Bipartit Pemrograman Dinamis Pemrograman dinamis adalah prosedur matematis yang terutama dirancang untuk memperbaiki efisiensi perhitungan masalah pemrograman matematis tertentu dengan menguraikannya menjadi bagian-bagian masalah yang lebih kecil dan karena itu lebih sederhana dalam perhitungan. Pemrograman dinamis pada umumnya menjawab masalah dalam tahap-tahap, dengan setiap tahap meliputi tepat satu variabel optimisasi.perhitungan di tahap yang berbeda-beda dihubungkan melalui perhitungan rekursif dengan cara yang menghasilkan pemecahan optimal yang mungkin bagi seluruh masalah. Istilah-istilah yang biasa digunakan dalam program dinamis adalah: 1. Tahap (stage) adalah bagian persoalan yang mengandung decision variabel. 2. Kondisi (state), state menunjukkan kaitan satu stage dengan stage lainnya sedemikian rupa sehingga setiap stage dapat dioptimisasikan secara terpisah sehingga hasil optimasi layak untuk seluruh persoalan. 3. Keputusan (decision), yang harus diambil dari tiap tahap untuk sampai kepada solusi keseluruhan
menggunakan hasil optimal dari tahap k tanpa harus kembali ke tahap awal.
Gambar 2. Ongkos
pada tahap k+1
Konsep Sub-Optimasi Konsep sub-optimasi sangat mempengaruhi hasil dari masalah ini. Maka dengan demikian diharapkan sebelum melaksanakan proses optimasi satu persoalan perlu mengetahui konsep sub-optimasi berikut secara mendalam. 1. Tahap pertama tidak mempengaruhi tahap-tahap yang lain. Jadi tahap ke-1 dapat dioptimumkan tersendiri yang merupakan sub-optimasi yang pertama. 2. Penyelesaian tahap pertama digabungkan dengan tahap yang kedua merupakan masalah sub-optimum yang ke-2. 3. Penyelesaian tahap kedua digabungkan dengan tahap ketiga merupakan masalah sub-optimasi yang ke-3. Demikian seterusnya sampai dengan tahap ke-n [3]. Pendekatan Penyelesaian Secara Rekursif Dreyfuse (1997) menyatakan bahwa adanya pendekatan yang digunakan dalam pemrograman dinamis yaitu: pemrograman dinamis maju (Forward Induction) dan pemrograman dinamis mundur (Backward Induction) [4]. METODE PENELITIAN Waktu dan Tempat Penelitian Penelitian ini akan berlangsung selama tiga bulan yaitu bulan Januari sampai April 2016 bertempat di Laboratorium Komputasi Jurusan Matematika FMIPA Universitas Halu Oleo.
Gambar 1. Tahap
program dinamis
Prinsip Optimalisasi Dikatakan prinsip optimalitas, jika solusi total optimal maka bagian solusi sampai tahap ke-k juga optimal. Prinsip optimalitas berarti bahwa jika kita bekerja dari tahap k ke tahap k+1, kita dapat
Materi Penelitian Dalam penelitian ini dibahas mengenai menentukan lintasan terpendek suatu graf berbobot dengan pendekatan pemrograman dinamis. Prosedur Penelitian Metode yang diterapkan dalam penyelesaian ini adalah metode kepustakaan dan studi kasus dengan mengikut langkah-langkah sebagai berikut: 1. Penelusuran pustaka yang relevan dan sistematis dengan masalah.
2. Menggambar graf berarah dan berbobot. 3. Menerapkan metode pemrograman dinamik untuk menyelesaikan masalah lintasan graf berbobot. 4. Membuat simulasi numerik dari solusi yang diperoleh dengan menggunakan software matlab. 5. Menginterpretasikan dan menganalisa hasil simulasi yang diperoleh HASIL DAN PEMBAHASAN Studi Simulasi A. Kasus I Seorang kurir jasa pengiriman barang akan mengantarkan barang dari kota A menuju I, ditangannya terbentang sehelai peta yang menggambarkan arah perjalanan beserta arahnya. Jalan-jalan yang manakah harus dilalui agar jarak tempuh yang dilaluinya minimum.
Gambar 3. Peta dari kota A menuju ke kota I Pada Gambar 3 dapat dilihat graf yang memiliki bobot dimana simpul-simpul dilambangkan dengan kode A, B, C, D, F, G, H, I, dan bobot yang terlihat pada graf adalah jarak dalam satuan kilimoter (km). Agar analisanya sesuai dengan teori, maka pada kasus I akan diimplementasikan ke dalam pemrograman dinamis dengan cara rekursif mundur. Karena dianalisa secara rekursif mundur maka dimulai dari tahap akhir atau tahap 4 untuk kasus ini, sehingga perhitungan untuk lintasan dimulai dari kota I dan berakhir pada kota A. Maka tahap-tahap penyelesaian untuk kasus I dapat dilihat pada Gambar 4 berikut:
Dari Gambar 4.4 tiap tahapan akan ditentukan: 1. Peubah keputusan : 𝑥𝑘 (𝑘 = 1,2,3,4) adalah simpul-simpul yang dikunjungi pada tahap 𝑘. 2. Jalur yang dipilih: A 𝑥1 𝑥2 𝑥3 𝑥4 = J. 3. Tujuan: mendapatkan 𝑓1∗ (𝐴) dan jalur-jalur yang bersesuain. Dimulai dari tahap 4. Tahap 4: Pada tahap ini terdapat dua rute submasalah yaitu dimulai dari tahap G ke I dan dimulai dari H ke I, hanya satu pilihan untuk menuju ke I. Jika didefinisikan bahwa keputusan pada tahap 4 adalah 𝑥4 = I. Hasil analisa tahap 4 dapat dilihat pada Tabel 1 sebagai berikut: Tabel 1. Solusi optimum untuk tahap 4 𝑺 𝒇∗𝟒 (𝒔) 𝒙∗𝟒 5 I G 4 I H Pada Tabel 4.8 diperoleh bahwa nilai 𝑓4∗ (𝑠) paling minimum adalah rute yang melalui H dengan 𝑓4∗ 𝑠 = 4. Dengan demikian pada tahap 4 ini rute yang diambil adalah H. Proses dilanjutkan pada tahap 3 berikutnya. Tahap 3: Pada tahap ini terdapat tiga rute submasalah yaitu dimulai dari D, E, F, untuk mencapai I harus melewati G atau H. Hasil analisa untuk tahap 3 dapat dilihat pada Tabel 2 sebagai berikut: Tabel 2. Solusi optimum untuk tahap 3
Pada Tabel 2 diperoleh bahwa nilai 𝑓3∗ (𝑠) paling minimum adalah rute yang melalui H dengan 𝑓3∗ 𝑠 = 10. Dengan demikian pada tahap 3 ini rute yang diambil adalah H. Proses dilanjutkan pada tahap 2 berikutnya. Tahap 2: Pada tahap ini terdapat dua rute submasalah yaitu dimulai dari B, C, untuk mencapai I harus melewati D, E, F. Hasil analisa untuk tahap 2 dapat dilihat pada Tabel 3 sebagai berikut: Gambar 4. Rute perjalanan kasus I
Tabel 3. Solusi optimum untuk tahap 2
melanjutkan kembali perjalanannya menuju terminal K. Jalan – jalan manakah yang akan dilaluinya agar jarak yang ditempuh minimum
Pada Tabel 3 diperoleh nilai 𝑓2∗ (𝑠) paling minimum adalah rute yang melalui E, dengan 𝑓2∗ 𝑠 = 14. Dengan demikian pada tahap 2 ini rute yang diambil adalah E. Proses dilanjutkan pada tahap 1 berikutnya. Tahap 1: Pada tahap ini terdapat satu rute submasalah yaitu dimulai dari A, untuk mencapai J harus melewati B, C. Hasil analisa untuk tahap 1 dapat dilihat pada Tabel 4 sebagai berikut: Tabel 4. Solusi optimum untuk tahap 1
Gambar 6. Terminal A menuju terminal K Agar analisanya sesuai teori, maka kasus II akan diimplementasikan ke dalam pemrograman dinamis dengan cara rekursif maju. Karena di analisa secara rekursif maju, maka akan dimulai pada tahap awal atau tahap 1. Sehingga perhitungannya dimulai dari terminal A, namun bus akan berhenti di terminal F sebelum menuju terminal K. Maka tahap-tahap penyelesaian untuk kasus II dapat dilihat pada Gambar 7 berikut:
Pada Tabel 4 diperoleh nilai 𝑓1∗ (𝑠) paling minimum adalah rute yang melalui C, dengan 𝑓1∗ 𝑠 = 19. Sehingga rute optimal untuk Kasus I diberikan dalam Gambar 5 .
Gambar 5. Rute optimal kasus I Pada Gambar 5 graf yang bergaris tebal merupakan rute yang harus dilalui seorang kurir jasa pengiriman barang dari kota A ke C, E, H, dan menuju ke kota I dengan total jarak 19 km. B. Kasus II Sebuah bus berangkat dari terminal A menuju terminal K. Dengan syarat bahwa sebelum menuju terminal K bus akan berhenti di terminal F dan akan
Gambar 7. Rute perjalanan kasus II Dari Gambar 4.7 tiap tahapan akan ditentukan: 1. Peubah keputusan : 𝑥𝑘 (𝑘 = 1,2,3,4) adalah simpul-simpul yang dikunjungi pada tahap 𝑘. 2. Jalur yang dipilih: A 𝑥1 𝑥2 𝑥3 𝑥4 = K. 3. Tujuan: mendapatkan 𝑓4∗ (𝐾) dan jalur-jalur yang bersesuain. Dimulai dari tahap 1. Tahap 1: Pada tahap ini terdapat satu rute submasalah yaitu dimulai dari A, untuk mencapai K harus melewati B, C, D. Hasil analisa untuk tahap 1 dapat dilihat pada Tabel 5 sebagai berikut:
Tabel 5 Solusi optimum untuk tahap 1
Tabel 7. Solusi optimum untuk tahap 3
Pada Tabel 5 diperoleh nilai 𝑓1∗ (𝑠) paling minimum adalah rute yang melalui C, dengan 𝑓1∗ 𝑠 = 7. Dengan demikian pada tahap 1 ini rute yang diambil adalah C. Proses dilanjutkan untuk tahap 2 berikutnya. Tahap 2: Pada tahap ini terdapat tiga rute submasalah yaitu dimulai dari B, C, D, untuk mencapai K harus melewati E, F, G. Hasil analisa tahap 2 dapat dilihat pada Tabel 6. Tabel 6. Solusi optimum untuk tahap 2
Pada Tabel 7 diperoleh nilai 𝑓3∗ (𝑠) paling minimum adalah rute yang melalui H, dengan 𝑓3∗ 𝑠 = 19. Dengan demikian pada tahap 3 ini rute yang diambil adalah H. Proses dilanjutkan untuk tahap 4 berikutnya. Tahap 4: Pada tahap ini terdapat tiga rute submasalah yaitu dimulai H, I, J, untuk mencapai K. Hasil analisa tahap 4 dapat dilihat pada Tabel 8. Tabel 8. Solusi optimum untuk tahap 4
Pada Tabel 6 diperoleh nilai 𝑓2∗ (𝑠) paling minimum adalah rute yang melalui F, dengan 𝑓2∗ 𝑠 = 12. Dengan demikian pada tahap 2 ini rute yang diambil adalah F. Karena diasumsikan bahwa bus akan berhenti di terminal F maka rute yang harus dilalui bus dari terminal A menuju F adalah A C F Dengan jarak = 7 km + 5 km = 12 km. Proses dilanjutkan untuk tahap 3 berikutnya, dimana tahap 3 akan dimulai dari terminal F menuju K. Tahap 3: Pada tahap ini terdapat tiga rute submasalah yaitu dimulai E, F, G, untuk mencapai K harus melewati H, I, J. Hasil analisa tahap 4 dapaat dilihat pada Tabel 7.
Dari solusi optimal yang telah di dapatkan pada tahap 3 dan 4 rute yang dilalui dari terminal F menuju terminal K adalah F H K Sehingga rute optimal untuk Kasus II diberikan dalam Gambar 8.
untuk tempat persinggahan pada contoh kasus II. Diharapkan pada penelitian selanjutnya dapat menggunakan lebih dari 1 terminal dan mengambil permasalahan pada kasus-kasus yang lebih kompleks.
Gambar 8 Rute optimal kasus II Pada Gambar 8 graf yang bergaris tebal merupakan rute yang harus dilalui sebuah bus dari terminal A ke C, F, H, dan menuju terminal K yang merupakan perjalanan akhirnya. Sehingga total jarak dari terminal A menuju terminal K adalah 25 km. PENUTUP Kesimpulan Dari hasil penelitian menentukan lintasan terpendek suatu graf berbobot dengan pendekatan pemrograman dinamis maka dapat disimpulkan bahwa persoalan lintasan terpendek suatu graf berbobot dengan pendekatan pemrograman dinamis dapat ditentukan dengan simulasi contoh kasus dengan menggunakan persamaan rekursif mundur dan persamaan rekursif maju. Pada contoh kasus I persoalan lintasan terpendek suatu graf berbobot diselesaikan dengan persamaan rekursif mundur dimana tahap penyelesaiannya dimulai dari tahap akhir atau tahap 4 sampai dengan tahap awal atau tahap 1 sehingga rute optimal yang dihasilkan pada contoh kasus I adalah dari kota A ke C, E, H menuju I dengan total jarak yang diperoleh adalah 19 km. Pada contoh kasus II persoalan lintasan terpendek diselesaikan dengan menggunakan persamaan rekursif maju dimana tahap penyelesaiannya dimulai dari tahap awal atau tahap 1 sampai dengan tahap akhir atau tahap 4, namun pada contoh kasus II bus tidak langsung menuju ke terminal akhir atau terminal K namun akan berhenti di terminal F sehingga tahap penyelesaiannya terdiri dari 2. Pertama diselesaikan dari tahap 1 ke tahap 2 untuk mendapatkan rute optimal dari terminal A menuju F dan kedua diselesaikan dari tahap 3 ke tahap 4 untuk mendapatkan rute optimal dari terminal F menuju K. Sehingga rute optimal yang diperoleh keseluruhan dari terminal A menuju terminal K adalah dari terminal A ke C, F, H, menuju ke terminal K dengan total jarak yang diperoleh adalah 25 km. Saran Adapun saran yang dikemukakan adalah pada penelitian ini peneliti hanya menggunakan 1 terminal
DAFTAR PUSTAKA [1] Hadiwinoto. 2010. Aplikasi Program Dinamis Pada Penyusunan Flight Planning. Bandung: Makalah Strategi Algoritmik Tahun 2007. [2] Munir, R. 2009. Matematika Diskrit Edisi Ketiga. Bandung: Penerbit Informatika [3] Simanjuntak, H.N. 2009. Aplikasi Model Program Linear Dengan Program Dinamik Untuk Menentukan Jumlah Produksi Optimum Pada Turangie Oil Mill. Skripsi. Medan: Departemen Matematika Fakulatas Matematika dan Ilmu Pengetahuan Alam Universitas Sumatera Utara. [4] Deyfus. 1997. The Art an Theory of Dynamic Programming. New Jersey San Fransisco London: Academic Press.
