BAB 1
PENDAHULUAN
1.1 Latar Belakang
Masalah dalam menentukan rantaian terpendek diantara pasangan node (titik) tertentu dalam suatu graph telah banyak menarik perhatian. Persoalan dirumuskan sebagai kasus khusus dari persoalan aliran biaya minimal, dan algoritma efisien yang tersedia untuk menghitung lintasan terpendek dan biaya minimum. Shortest path yang diperoleh akan meminimumkan fungsi linear yang khusus (fungsi) dari path seperti biaya, jarak atau waktu. Perumusan persoalan ini akan menjadi salah satu kegunaan dari lintasan dengan jarak (waktu) diminimumkan terhadap biaya yang dianggarkan.
Beberapa masalah dalam menentukan rantaian terpendek diantara pasangan node tertentu dalam suatu graph atau jaringan kerja, antara lain : masalah transportasi, jaringan komunikasi, serta masalah pengiriman barang tidak bisa lepas dari permasalahan jarak (waktu) dan tentunya juga masalah biaya. Permasalahan dituntut untuk meminimisasi jarak (waktu) ke tujuan yaitu dengan memilih lintasan tersingkat dengan biaya yang telah dianggarkan sehingga dapat dicapai hasil yang optimal. Sebagai contoh dapat kita lihat pada masalah transportasi, kita dihadapkan pada pilihan lintasan perjalanan dari Kota S (sumber) ke Kota T (tujuan), untuk sampai ke Kota T ada beberapa lintasan berbeda yang dapat dilalui dan juga biaya perjalanan yang berbeda, permasalahan yang terjadi adalah lintasan terpendek mana yang harus dipilih yang sesuai dengan biaya yang dianggarkan untuk perjalanan tersebut agar hasil yang optimal diperoleh.
Universitas Sumatera Utara
Algoritma Dijkstra merupakan dasar pemikiran untuk menentukan suatu lintasan terpendek dalam suatu graph berarah dari suatu titik awal (sumber) ke suatu titik akhir (tujuan), bilamana pada setiap node dan arc menotasikan suatu ukuran atau bobot yang tidak negatif. Algoritma ini juga untuk menentukan lintasan terpendek untuk setiap pasangan lintasan yang diinginkan. Pada umumnya algoritma Dijkstra digunakan hanya untuk menentukan lintasan terpendek pada suatu graph. Tetapi bilamana shortest path tersebut harus memenuhi kendala-kendala linear yang ditentukan, algoritma tersebut tidak dapat digunakan.
Masalah khusus dari persoalan graph ini adalah mendapatkan suatu lintasan dengan jarak minimum yang memenuhi terhadap (subject to) kendala anggaran (budgetary). Kemungkinan masalah lainnya adalah path juga merupakan minimasi biaya yang harus memenuhi kendala waktu. Andaikan diberikan sebuah graph G dengan node (titik) N = 1,2,…,i dan arc (garis) F = 1,2,…,j serta a(x,y) dan b(x,y) adalah jarak (waktu) dan biaya. yang dihubungkan dengan tiap garis (i,j) dalam graph G. Masalahnya adalah menentukan lintasan terpendek dari titik 1 (sumber) ke titik n (tujuan) dalam graph G yang memenuhi terhadap kendala biaya yang dianggarkan. Jarak (waktu) dan biaya dari lintasan adalah jumlah nilai-nilai yang terdapat pada tiap garis dalam lintasan.
Universitas Sumatera Utara
(f5)
2
(10,12)
(3,2)
(f1) (f3) 1
(f4)
(8,1)
4
(4,1)
(f2)
(8,5) (9,4)
3
(f6)
Gambar 1.1 Contoh ilustrasi masalah shortest path yang berkendala.
Gambar diatas menerangkan sebuah graph G dimana (a,b) = 10, 12 dinyatakan sebagai jarak (waktu) dan biaya yang dihubungkan tiap garis F(i,j), dan node 1, 2, 3, 4 adalah node-node N yang ditentukan pada graph. Dan pada gambar juga diperlihatkan yang bergaris tebal adalah merupakan lintasan terpendek yang harus dilewati dari sumber (node 1) ke tujuan (node 4). Pada persoalan ini diandaikan biaya sebagai kendala, dan ditentukan pula biaya berbanding terbalik dengan jarak atau keduanya bernilai sama.
Menentukan jarak terpendek yang memenuhi kendala biaya yang dianggarkan pada suatu graph adalah merupakan salah satu tipe masalah Integer Knapsack, yaitu dimana kita diminta untuk memilih bobot minimum yang akan dimasukkan kedalam knapsack (karung) yang mempunyai bobot maksimum tertentu. Persoalan ini disebut Integer Knapsack karena tiap objek hanya memiliki dua status yaitu terpilih atau tidak. Untuk permasalahan knapsack pada suatu graph, bobot minimum yang dipilih adalah merupakan lintasan terpendek yang harus dilewati dari titik sumber ke titik tujuan. Sedangkan biaya adalah sebagai kendala
yang harus dipenuhi dalam
menentukan lintasan terpendek.
Universitas Sumatera Utara
Masalah knapsack ini dapat dirumuskan dengan memberi nilai 1 sampai n dan memperkenalkan suatu vektor variabel biner
xj (j = 1,…,n) dengan arti sebagai
berikut :
1 xj = 0
Jika objek j dipilih Lainnya
Jika pj merupakan ukuran kelayakan yang diberikan oleh objek j, wj adalah besarannya dan K adalah bobot maksimum dari knapsack, masalahnya akan terpilih, diantara semua semua vektor biner x (0–1) yang akan memenuhi kendala n
∑w x j =1
j
j
≤K
Dimana salah satu fungsi objektif di maksimumkan n
∑p x j =1
j
j
0–1 Programming adalah salah satu metode yang dipergunakan untuk menyelesaikan masalah Knapsack, dimana keadaan tertentu terjadi dan masingmasing keadaan mempunyai sebuah nilai yang dihubungkan dengan besarannya. Secara nyata bahwa solusi optimal dari masalah Knapsack akan menunjukkan kemungkinan yang terbaik. Oleh sebab itu penulis berkeinginan untuk membahas bagaimana metode 0-1 Programming dalam menyelesaikan masalah lintasan terpendek
yang
memenuhi
kendala-kendala
yang
telah
ditentukan,
serta
menerapkannya dengan menggunakan program LINDO .
Universitas Sumatera Utara
1.2 Perumusan Masalah Masalah yang dibahas adalah bagaimana menentukan lintasan terpendek yang merupakan masalah knapsack dari titik sumber ke titik tujuan pada suatu graph yang memenuhi kendala biaya yang dianggarkan (budgetary) dengan menggunakan 0-1 Programming.
1.3 Tujuan Penelitian
Problem shortest path diantara dua node tertentu dalam sembarang graph umumnya dapat diselesaikan dengan menggunakan Dijkstra Algorithm. Tetapi bilamana shortest path tersebut harus memenuhi kendala-kendala linear yang ditentukan, algoritma tersebut pada umumnya tidak dapat digunakan. Penelitian bertujuan untuk memperlihatkan dan menerangkan suatu konsep algoritma untuk penyelesaian dalam menentukan shortest path yang memenuhi kendala-kendala yang ditentukan, dengan menerapkan 0-1 programming.
1.4 Kontribusi Penelitian
Dengan adanya penelitian menggunakan 0-1 Programming pada masalah shortest path yang berkendala, diharapkan dapat bermanfaat sebagai salah satu metode dalam mengambil keputusan yang optimal pada suatu network. Dalam bidang ilmu pengetahuan sebagai dasar pengembangan dari Algoritma Dijkstra, juga dapat digunakan pada permasalahan comunication network, transportasi oleh Departemen Perhubungan, pengembangan ekspor oleh Departemen Perdagangan.
Universitas Sumatera Utara
1.5 Tinjauan Pustaka
Teori graf merupakan pokok bahasan yang sudah tua usianya namun memiliki banyak terapan sampai saat ini. Graf digunakan untuk mempresentasikan objek-objek diskrit [10] dan hubungan antara objek-objek tersebut. Reprentasikan visual dari graf adalah dengan menyatakan objek dinyatakan sebagai noktah, bulatan, atau titik, sedangkan hubungan antara objek dinyatakan dengan garis. Salah satu contoh yaitu sebuah peta jaringan jalan raya yang menghubungkan sejumlah provinsi, dimana sesungguhnya peta tersebut adalah sebuah graf, di dalam hal ini kota dinyatakan sebagai bulatan sedangkan jalan dinyatakan sebagai garis. Dengan pencarian jalur terpendek maka kita dapat mengetahui perjalanan yang singkat dari satu kota ke kota yang lainnya.
Integer Programming 0-1 adalah suatu linier programming dengan tambahan persyaratan bahwa semua atau beberapa variabel bernilai bulat nonnegatif, tetapi tidak perlu bahwa parameter model juga bernilai bulat.Ada banyak kasus dalam masalah integer programming yang membatasi variabel model bernilai nol atau satu. Dalam kasus demikian, persoalan lintasan hanya memiliki dua pilihan yaitu masuk atau keluar dari jaringan. Jika variabel ini bernilai satu, persoalan masuk, dan jika variabel bernilai nol, persoalan keluar [4].
Algoritma 0 – 1 Programming merupakan salah satu tipe masalah Knapsack dimana keadaan tertentu terjadi, masing-masing keadaan mempunyai sebuah nilai yang dihubungkan dengan besarannya.
Secara nyata bahwa solusi optimal dari
masalah knapsack akan menunjukkan kemungkinan yang terbaik. Pada masalah ini
Universitas Sumatera Utara
akan terdorong untuk menyelesaikan suatu persoalan dalam menentukan lintasan terpendek pada suatu distribusi aliran. Pendekatan yang sederhana dapat dimasukkan ke dalam program komputer untuk memeriksa semua harga 0-1 yang mungkin, dipilih yang terbaik yang memenuhi kendala [3] .
1.6 Metode Penelitian
Secara umum penelitian yang dilakukan dengan beberapa tahapan, yaitu : 1. Menguraikan teori dasar graph dan terminologi-terminologi graph yang menunjang terhadap pembahasan. 2. Menguraikan tentang konsep lintasan terpendek serta 0-1 Programming pada permasalahan Knapsack pada sembarang graph. 3. Menjelaskan penggunaan dan pengembangan 0-1 Programming untuk menentukan path yang memungkinkan dari sumber ke tujuan. 4. Menyelesaikan permasalahan shortest-path yang memenuhi kendala-kendala tertentu dalam suatu graph dengan menggunakan 0-1 Programming.
5. Mengimplementasikannya kedalam Program LINDO.
Universitas Sumatera Utara
