ANALISIS METODE KARMARKAR PADA PENYELESAIAN PROBLEM PROGRAM LINIER

Penelitian ini difokuskan untuk mendalami metode Karmarkar melalui
penyelesaian problem program linier. Metode Karmarkar merupakan metode yang
digunakan untuk memecahkan permasalahan yang kompleks dan skala besar, dimana
permasalahan tersebut memiliki kendala fungsional dan variabel keputusan yang
jumlahnya sangat besar. Melalui transformasi proyektif metode Karmarkar dimulai dari
himpunan fisibel dan memindahkan sampai menjadi suatu titik optimum dimana titik-
titik awal ditransformasikan ke dalam pusat dari daerah fisibel melalui pengubahan
bentuk masalah primal menjadi masalah dual. Untuk itu masalah program linier dalam
bentuk umum harus diubah ke bentuk kanonik Karmarkar. Bentuk kanonik tersebut
harus memenuhi dua asumsi, yaitu titik awal memenuhi pembatas homogen dan optimal
fungsi tujuan adalah nol. Secara umum metode Karmarkar dapat digunakan untuk
menyelesaikan sembarang problem program linier melalui transformasi ke suatu bentuk
minimisasi. Subtansinya solusi optimal merupakan harga pendekatan yang diperoleh
melalui suatu prosedur mulai dari titik interior dalam daerah fisibel dan bergerak
sepanjang arah yang dinyatakan oleh gradien yang diproyeksikan oleh fungsi tujuan
pada daerah fisibel sedemikian sehingga dicapai nilai optimal.