Penyelesaian program linear dengan menggunakan algoritma titik interior dan metode simpleks

Oleh :
Suparno - M0101047 - Fak. MIPA

ABSTRAK Program linear adalah suatu model yang melibatkan fungsi-fungsi linear dan dapat digunakan dalam pemecahan masalah pengalokasian sumber-sumber terbatas secara optimal. Pokok pikiran menggunakan program linear adalah merumuskan masalah dari informasi yang tersedia, kemudian menerjemahkannya dalam bentuk model matematika. Metode simpleks merupakan algoritma yang efisien untuk menyelesaikan permasalahan program linear. Algoritma titik interior merupakan alat baru yang dapat digunakan untuk menyelesaikan masalah-masalah yang sangat besar. Tujuan dari penulisan ini adalah menyelesaikan permasalahan program linear yang memuat n jumlah variabel dan m jumlah kendala dengan menggunakan kedua metode tersebut. Selanjutnya, ditunjukkan keefisienan algoritma titik interior dibandingkan metode simpleks, ditinjau dari banyaknya iterasi untuk menyelesaikan suatu permasalahan. Berdasarkan hasil penelitian, algoritma titik interior lebih efisien jika digunakan setidaknya 93 variabel dan tidak kurang dari 10 kendala untuk kasus maksimisasi dengan semua kendala bertanda kurang dari atau sama dengan (≤).