Seminar Tugas Akhir

Endah Ayu Ningsih
G54101044

Algoritma Titik-Dalam untuk Menyelesaikan Program Linear

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 apda posisi dekat denagn 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 digerakan 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 diproleh dikembalikan lagi keruang 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.