Penentuan jarak minimum dalam suatu jaringan dengan Algoritma Prim dan pemrograman bilangan biner

Abstract

Penelitian Operasional yang dimulai sejak revolusi industri merupakan bagian dari aplikasi matematika untuk memecahkan masalah optimasi. Pemrograman Linear merupakan salah satu model Penelitian Operasional yang berkembang dan dapat digunakan untuk menganalisis suatu jaringan seperti jaringan transportasi, listrik, air dan telekomunikasi. Dalam makalah ini akan dibahas Algoritma Prim dan Pemrograman Bilangan Biner, yang berkaitan dengan Pemrograman Linear, untuk mencari suatu jaringan atau pohon rentang minimum pada masalah pendistribusian listrik di Rumania. Pohon Rentang Minimum merupakan variasi dari persoalan pencarian jarak terpendek. Pada pohon rentang minimum akan ditentukan sisi-sisi yang menghubungkan masing-masing simpul yang ada pada jaringan sehingga diperoleh panjang sisi total yang minimum. Baik Algorimta Prim ataupun Pemrograman Bilangan Biner menghasilkan pohon rentang minimum yang sama tetapi terdapat perbedaan dalam waktu pencarian solusi dengan menggunakan Matlab. Algoritma Prim membutuhkan waktu lebih cepat yakni selama 0,002393 detik sedangkan Pemrograman Bilangan Biner selama 0,013275 detik. Hal ini terjadi karena langah-langkah pencarian solusi optimal dari Algoritma Prim relatif lebih sederhana dibandingkan Pemrograman Bilangan Biner.