Pencarian Solusi Pemrograman Non Linier Menggunakan Algoritma Branch-and-Bound

AVictor Hariadi

Abstract

Pemrograman nonlinier adalah satu bagian penting dari permasalahan optimasi, baik dari sudut pandang
matematis maupun aplikasi. Banyak permasalahan dunia nyata yang dapat direpresentasikan ke dalam bentuk
permasalahan pemrograman non linier. Dalam pemrograman nonlinier diperlukan metode untuk mencari nilai
optimal global agar tidak terjebak pada pencapaian nilai optimal local. Pada penelitian ini dicoba
untukmengaplikasikan algoritma branch-and-bound melalui proses relaxation pada permasalahan untuk
mendapatkan solusi optimal global. Agar pertumbuhan jumlah sub permasalahan dapat dikendalikan maka
kami memanfaatkan reformulasi kondisi (Karush-Kuhn Tucker) KKT. Uji coba dilakukan dengan menggunakan
permasalahan pemrograman kuadratik. Dari percobaan yang dilakukan menunjukkan bahwa pembatasan sub
permasalahan melalui reformulasi KKT sangat membantu pencapaian solusi optimal dengan algortima branchand-
bound.

Kata kunci: permaslahan optimasi, pemrograman non linier, algoritma branch-and-bound, reformulasi kondisi
KKT.

Full Text:

PDF