Kasus-kasus Buruk Penggunaan Metode Titik Interior pada Optimisa si Linear

Abstract

Metode titik interior adalah suatu metode dengan waktu polinomial dalam menyelesaikan masalah optimisasi linear. Metode titik interior sering menggunakan central path sebagai panduan menuju solusi optimalnya. Pada paper ini diberikan suatu teorema yang menyatakan bahwasanya kendala redundan dapat mengubah pusat analitik central path yang sekaligus mengubah centrah path. Dengan bantuan teorema ini ditampilkan suatu kasus dimana metode titik interior berunjuk kerja buruk dengan adanya kendala redundan. Kemudian disajikan suatu masalah optimasi linear yang memiliki central path dengan pola zifzag. Pola zigzag pada central path juga mengakibatkan metode titik interior bekerja lebih lama dalam menuju solusi optimal. ..... ...