Seminar Tugas Akhir

Rini Maedianengsih
g54080044

Analisis Kompleksitas Masalah Optimasi Linear menggunakan Metode Interior Primal-Dual dengan Langkah Full-Newton

Pengoptimuman merupakan salah satu cabang matematika terapan yang mempelajari masalah meminimumkan atau memaksimumkan. Dalam kehidupan sehari-hari banyak permasalahan yang memerlukan optimasi. Optimasi digunakan secara luas hampir di setiap aspek kehidupan, termasuk ilmu pengetahuan, teknik, ekonomi, manajemen dan industri. Banyak penelitian yang telah menghasilkan teknologi baru, dan metode baru dalam optimasi. Pada tahun 1972, Klee dan Minty memberikan suatu masalah optimasi linear. Dengan metode simpleks masalah tersebut memerlukan 2^n-1 iterasi dengan 2n pertidaksamaan. Klee-Minty juga menunjukkan bahwa metode simpleks memerlukan waktu eksponensial untuk menyelesaikan masalah optimasi linear. Dalam karya ilmiah ini akan digunakan metode interior primal-dual dengan langkah full-Newton dalam memecahkan masalah Klee-Minty tersebut. Selanjutnya akan dilakukan analisis kompleksitas algoritme dari masalah Klee-Minty dan menyelesaikan beberapa masalah optimasi linear untuk melihat kesesuaiannya dengan kompleksitas algoritme.