TLDR
Metode simplex tetap menjadi alat penting dalam pengambilan keputusan logistik dan rantai pasokan. Penelitian terbaru menunjukkan bahwa waktu komputasi algoritma simplex dapat dijamin lebih rendah daripada yang diperkirakan sebelumnya. Penambahan elemen acak dalam algoritma dapat mencegah skenario terburuk dan meningkatkan efisiensi. Pada tahun 1939, George Dantzig menemukan metode penting saat kuliah yang ternyata menjadi dasar metode simplex, sebuah algoritma optimisasi yang digunakan hingga kini untuk mengalokasikan sumber daya secara efisien. Penemuan ini bahkan menjadi inspirasi untuk film Good Will Hunting. Selama Perang Dunia II, metode ini sangat berguna dalam mendukung alokasi sumber daya militer yang kompleks dan besar skalanya.Meski metode simplex efektif, secara teori ada kemungkinan bahwa metode ini bisa memakan waktu yang sangat lama dalam kasus-kasus tertentu yang sangat rumit. Hal ini karena jalur yang ditempuh algoritma dapat sangat panjang, sehingga berpotensi kompleksitas waktu yang eksponensial muncul di kasus terburuk. Namun dalam praktiknya, ini jarang terjadi, dan para peneliti sejak lama penasaran mengapa demikian.Pada 2001, Daniel Spielman dan Shang-Hua Teng membuktikan bahwa dengan sedikit randomisasi, metode simplex berjalan dalam waktu polinomial, jauh lebih cepat daripada yang diperkirakan oleh kasus terburuk eksponensial. Meskipun ini sebuah kemajuan besar, nilai pangkat yang didapat masih sangat tinggi, sehingga peneliti terus mencari cara menurunkannya.Baru-baru ini, Sophie Huiberts dan Eleon Bach berhasil meningkatkan algoritma tersebut dengan menambahkan lebih banyak elemen randomisasi. Hasil penelitian mereka menunjukkan runtime yang jauh lebih rendah secara teoretis dan memberikan penjelasan mengapa kasus eksponensial tidak terjadi dalam penggunaan nyata metode simplex. Penelitian ini dianggap sebagai kemajuan besar dalam bidang optimisasi dan ilmu komputer.Meski riset ini belum berdampak langsung pada aplikasi praktis, penemuan ini memberikan kepastian matematis yang lebih kuat tentang keandalan metode simplex yang digunakan dalam perangkat lunak optimisasi saat ini. Namun, pencapaian runtime yang meningkat hingga waktu linear masih merupakan tantangan besar yang diharapkan dapat dikenal sebagai tujuan akhir riset di masa depan.
