Algoritma karmarkar untuk menyelesaikan masalah pemrograman linear

Abstract

Salah satu masalah yang sering dijumpai dalam dunia nyata adalah menentukan alokasi optimal terbaik) dari sumberdaya yang terbatas. ( Jika masalah tersebut mempunyai sifat linearitas, maka ia dapat dimodelkan ke dalam bentuk Pemrograman Linear (PL). Untuk memecahkan permasalahan PL telah dikembangkan tiga algoritma, yaitu: algoritma Simpleks Dantzig, 1951], algoritma Ellipsoid [Khachiyan, 1979] dan algoritma Karmarkar [Karmarkar, 1984]. Algoritma Simpleks mempunyai kompleksitas yang lebih tinggi daripada algoritma Ellipsoid, dan algoritma Ellipsoid mempunyai kompleksitas yang lebih tinggi daripada algoritma Karmarkar. Algoritma Karmarkar yang diperkenalkan oleh Narendra Karmarkar pada tahun 1984 mempunyai prinsip kerja sebagai berikut: 1. Solusi fisibel yang terletak di pusat daerah fisibel digerakkan untuk mendapatkan solusi fisibel baru. yang lebih baik. 2. Daerah fisibel ditransformasikan sehingga solusi fisibel baru terletak di pusat daerah fisibel. Proses 1 dan 2 diulang-ulang sampai diperoleh solusi optimal. Algoritma Karmarkar dapat diterapkan secara langsung pada permasalahan PL dengan sifat sebagai Derikut: 1. Permasalahan PL memiliki bentuk khusus Karmarkar sebagai berikut: min ely y dengan kendala Ay = 0 ely I. y20 2. Fungsi obyektif permasalahan PL tersebut mempunyai nilai minimum nol.