Algoritma Titik-Dalam untuk Menyelesaikan Program Linear

Abstract

Algoritma Titik-Dalam merupakan suatu metode untuk menyelesaikan Program Linear (PL). Berbeda dengan metode Simpleks yang mencari solusi melalui batas politop, algoritma Titik-Dalam mencari solusi melalui daerah interior politop. Konsep dasar dari algoritma ini adalah: Jika suatu PL mempunyai suatu solusi pada posisi dekat dengan pusat politop, maka fungsi obyektif dapat dikurangi (diminimumkan) dengan menggerakan solusi saat ini dengan arah steepest descent vektor fungsi obyektifnya. Ruang solusi (daerah fisibel) dari suatu PL dapat ditransformasikan sedemikian rupa sehingga menempatkan solusi saat ini dekat dengan pusat politop tanpa secara esensial mengubah persoalan. Untuk memulai algoritma diperlukan vektor solusi awal yang memenuhi kendala interior. Kemudian daerah fisibel dari PL ditransformasikan sedemikian sehingga vektor solusi berada dekat dengan pusat politop (scaling). Kemudian solusi tersebut digerakkan dengan arah steepest descent vektor fungsi obyektifnya, yaitu negasi dari vektor fungsi obyektif. Untuk mendapatkan solusi yang fisibel, negasi dari vektor tersebut diproyeksikan ke Ruang Nol (Nullspace) dari matriks kendala. Solusi baru yang diperoleh dikembalikan lagi ke ruang originalnya (rescaling). Proses tersebut diulang sampai kondisi optimal dicapai. Proses scaling dan rescaling disini hanya untuk mengilustrasikan tujuan. Dalam prakteknya proses tersebut dibangun dalam suatu algoritma keseluruhan. Analisis metode Karmarkar menjelaskan bahwa algoritma Titik-Dalam memiliki kompleksitas yang bersifat polinomial. Sedangkan algoritma Simpleks memiliki kompleksitas yang bersifat eksponensial.