Pengembangan Algoritma Dinkelbach untuk menyelesaikan masalah pemrograman penjumlahan pecahan linear

Abstract

Pemrograman pecahan linear berkaitan dengan memaksimalkan dua fungsi objektif dengan tujuan untuk menghitung rasio efisiensi. Misalnya perbandingan antara jumlah barang yang diproduksi dengan biaya produksi atau perbandingan antara keuntungan yang diperoleh dengan biaya produksi. Metode yang digunakan untuk menyelesaikan masalah pemrograman pecahan linear adalah algoritma Dinkelbach. Algoritma Dinkelbach mengubah suatu masalah pemrograman pecahan linear ke bentuk pemrograman linear dengan cara mendefinisikan suatu fungsi baru pada fungsi objektifnya yang akan menghasilkan fungsi objektif yang linear namun tetap dengan kendala yang serupa. Kemudian solusi optimal dari masalah pemrograman linear tersebut dapat diperoleh menggunakan metode simpleks. Selanjutnya, masalah pemrograman pecahan linear tersebut dikembangkan menjadi penjumlahan pecahan linear yang diselesaikan dengan cara mentransformasi menjadi pecahan nonlinear lalu diselesaikan dengan algoritma Dinkelbach serta digunakan kondisi optimalitas Kuhn-Tucker untuk menyelesaikan masalah pemrograman nonlinear. Selain itu, diajukan suatu metode baru yang merupakan pengembangan dari algoritma Dinkelbach untuk menyelesaikan masalah pemrograman penjumlahan pecahan linear. Untuk memverifikasi dan mempermudah penyelesaian, dibuat pula suatu kode program untuk pemrograman pecahan nonlinear dan penjumlahan pecahan linear. Pada skripsi ini, dilakukan pengembangan dari algoritma Dinkelbach untuk menyelesaikan masalah pemrograman penjumlahan pecahan linear. Algoritma dari pengembangan ini diverifikasi dengan menggunakan beberapa contoh perhitungan numerik. Namun, pengembangan ini masih belum didukung oleh teori yang dapat membuktikan kebenarannya.