Seminar Tugas Akhir

Nurhayati
g54080057

Analisi Perubahan Analytic center Masalah Optimasi Linear dengan Metode Interior Primal-Dual Langkah Full-Newton

Optimasi adalah salah satu cabang ilmu matematika terapan yang mempelajari masalah untuk meminimumkan atau memaksimumkan fungsi real dari variabel real dengan kendala-kendala pada setiap variabel. Optimasi digunakan hampir di setiap aspek kehidupan, termasuk dalam ilmu pengetahuan, ekonomi, teknik, manajemen dan industri. Salah satu bagian dari optimasi adalah optimasi linear, yang mempelajari masalah untuk meminimumkan atau memaksimumkan fungsi linear dengan kendala yang dinyatakan dalam persamaan linear dan/atau pertaksamaan linear. Sebuah terobosan yang benar-benar efektif terjadi pada tahun 1984 ketika Karmarkar mengusulkan metode polynomial–time yang berbeda, yang dikenal dengan metode proyektif Karmarkar untuk masalah OL. Metode ini memiliki kompleksitas yang lebih baik dari metode elipsoid dan juga efisien dalam penerapannya. Metode proyektif Karmarkan memacu revolusi dalam bidang optimasi, dengan munculnya penelitian-penelitian pengoptimuman dengan menggunakan metode interior (MI). Tidak seperti metode simpleks yang bergerak dari verteks ke verteks dalam mencari solusi optimalnya, metode interior bergerak di dalam interior dari domain secara monoton menuju solusi optimal (Silalahi 2011).Deza dkk, memberikan suatu contoh kasus terburuk (pada saat itu) untuk kasus penyelesaian optimasi linear dengan metode interior. Kasus mereka adalah dengan menambahkan kendala-kendala redundant pada masalah Klee-Minty (KM). Secara teoritis diperlihatkan bahwa central path dan analytic center dapat berubah dengan penambahan kendala redundant (Deza et al. 2006). Dalam karya tulis ini, akan dibahas tentang perubahan analytic center pada masalah Klee-Minty (KM) dengan penambahan kendala redundant yang akan dianalisis menggunakan metode interior (MI) dengan pendekatan central trajectory (path-following).