Metode Karmarkar (Titik interior)

Seingatku, dulu masalah program linear tu udah ada sejak SMP. Ga tau kalo sekarang yach. Yang pasti, di SMU masalah program linear dipelajari tidak hanya untuk jurusan IPA, tapi juga jurusan IPS. Hal ini sih, menurutku, cuz banyak masalah-masalah dalam kehidupan sehari-hari yang merupakan masalah optimasi, such as meminimumkan pengeluaran, memaksimalkan pendapatan, mengoptimalkan kerja mesin, mengatur pola antrian dll. Program linear merupakan bagian kecil dari masalah optimasi..

Jadi, pada prinsipnya pada masalah optimasi, ada tujuan atau sasaran yang akan dioptimalkan (maksimum or minimum) dan ada batasan kendalanya. Akan dicari nilai dari variabel-variabel yang mempengaruhi pengambilan keputusan, yaitu variable yang memenuhi kendala dan memberikan solusi optimum.
Program Linear untuk kasus dua variabel, yang biasa diberikan di SMP or SMU, penyelesaian dari masalah ini dapat mudah dicari dengan metode grafik. Akan tetapi untuk kasus variable yang banyak, metode grafik bisa menjadi cara yang tidak efisien.

Abad 19 (kl ga salah inget ya), Danzig memperkenalkan metode penyelesaian program linear yang disebut dengan Algoritma Simpleks. Algoritma ini bekerja dari titik ekstreme yang satu ke titik ekstreme yang lain. Stopping criterion untuk algoritma ini yaitu sampai tidak ditemukan kemungkinan untuk mengoptimalkan nilai sasaran. Darisini dapat kita cermati bahwa untuk kasus variable yang sedikit (titik ekstremenya juga sedikit), algoritma simpleks bekerja dalam waktu singkat. Akan tetapi untuk kasus variable banyak (titik ekstreme juga banyak), algoritma simpleks membutuhkan waktu yang lama karena harus meneliti tiap titik ekstremenya. Lama waktu algoritma simpleks dinyatakan dalam grafik eksponensial terhadap banyaknya variable.

Untuk mengatasi masalah PL dengan variabel banyak, Karmarkar kemudian memberikan gagasan baru.