Seminar Tugas Akhir

Irwan Nursolih
g54080062

Metode Interior Primal-Dual dengan Langkah Full-Newton (Studi Kasus Masalah Klee-Minty dengan Kendala Redundant Tipe yk>=0

Optimasi dalam matematika mengacu pada pemillihan elemen terbaik dari beberapa himpunan alternatif yang tersedia. Dalam kasus yang paling sederhana berarti memecahkan masalah-masalah dimana orang berusaha meminimumkan atau memaksimumkan fungsi yaitu dengan cara yang sistematis memilih nilai-nilai variabel integer atau real dari himpunan yang diperbolehkan (Nematollahi 2008). Optimasi Linear (OL) muncul menjadi model matematika setelah perang dunia ke-2, yaitu ketika Dantzig memaparkan metode simpleks untuk menyelesaikan masalah optimasi linear. Daerah fisibel dari masalah OL adalah suatu polihedron. Untuk memperoleh solusi optimal, metode simpleks bergerak dari verteks ke verteks. Metode ini dirancang sedemikian rupa sehingga dalam pergerakan dari satu verteks ke verteks selanjutnya, nilai fungsi tujuan berubah secara monoton menuju nilai optimal. Kesuksesan metode simpleks telah menimbulkan beberapa pertanyaan. Salah satu pertanyaan pada saat itu adalah: apakah ada masalah optimasi linear yang memerlukan iterasi eksponensial bila diselesaikan dengan metode simpleks. Pertanyaan tersebut dijawab pada tahun 1972 oleh Klee dan Minty dengan memberikan contoh masalah OL dengan pertidaksamaan, dimana metode simpleks memerlukan iterasi untuk menye-lesaikan permasalahan Klee-Minty. Dalam karya ilmiah ini akan diamati kendala redundant Klee-Minty tipe (kendala redundant tipe lima pada Table 1), yaitu semua kendala redundantnya menyentuh daerah fisibel, yang akan di analisa menggunakan metode interior (MI) dengan pendekatan central trajectory (path-following).