Seminar Tugas Akhir

Brammanto Pratama Baskara
g54080056

Penyelesaian Masalah Optimasi Linear Menggunakan Metode Titik-Interior Primal-Dual dengan Langkah Newton-Penuh

Optimasi linear khusus mempelajari hal-hal yang berkaitan dengan meminimumkan atau memaksimumkan fungsi-fungsi linear, dengan kendala yang juga linear (berupa persamaan atau pertidaksamaan). Optimasi linear muncul menjadi suatu model matematika pada situasi perang dunia II, ketika Dantzig (1947) mengajukan penggunaan metode simpleks untuk menyelesaikan masalah pemrograman linear. Metode simpleks bergerak dari verteks ke verteks untuk memperoleh solusi optimal. Penemuan Dantzig telah menginspirasi banyak penelitian dalam matematika, khususnya bidang optimasi. Keefisienan metode simpleks untuk menyelesaikan banyak problem optimasi linear, memunculkan pertanyaan saat itu: apakah ada masalah optimasi linear yang memerlukan iterasi yang eksponensial bila diselesaikan dengan metode simpleks. Pertanyaan ini dijawab oleh Klee dan Minty pada tahun 1972, dengan memberikan suatu contoh masalah optimasi linear yang memiliki 2n pertidaksamaan dan memerlukan 2^n-1 iterasi (Silalahi 2011). Hal ini memacu penelitian-penelitian untuk menemukan algoritme optimasi linear yang memerlukan iterasi yang polinomial (Silalahi 2011). Metode elipsoid yang diusulkan oleh Khachiyan pada tahun 1979 dapat menyelesaikan masalah optimasi linear dengan kompleksitas polinomial. Meskipun metode elipsoid memiliki kompleksitas polinomial, namun dalam penerapan secara komputasi metode ini tidak efisien. Metode proyektif yang dipaparkan oleh Karmarkar pada tahun 1984 dapat menyelesaikan masalah optimasi linear dengan kompleksitas yang lebih efisien daripada metode elipsoid. Metode proyektif Karmarkar memulai revolusi dalam bidang optimasi karena memunculkan sesuatu yang disebut interior-point methods (metode–metode titik-interior). Berbeda dengan metode simpleks yang bergerak dari verteks ke verteks, metode–metode titik-interior bergerak di interior dari domain untuk menemukan nilai optimal (Silalahi 2011). Ada beberapa variasi dari metode titik-interior, di antaranya metode path-following, dengan penentuan solusi optimal menggunakan central path. Pada buku yang ditulis oleh Roos C, Terlaky T, dan Vial J-Ph tahun 2006, dipaparkan algoritme primal-dual Newton-penuh dengan central path untuk menentukan solusi optimal dari masalah optimasi linear.