Versi asli dari artikel ini muncul di Quanta Magazine.
Pada 1939, saat terlambat masuk ke kelas statistiknya di UC Berkeley, George Dantzig—seorang mahasiswa pascasarjana tahun pertama—menyalin dua soal dari papan tulis, mengira itu adalah tugas pekerjaan rumah. Ia merasa tugas itu “lebih sulit dari biasanya,” seperti yang kemudian diceritakannya, dan meminta maaf kepada profesornya karena membutuhkan waktu ekstra beberapa hari untuk menyelesaikannya. Beberapa minggu kemudian, profesornya memberitahunya bahwa ia telah memecahkan dua masalah terbuka (open problems) yang terkenal dalam statistika. Karya Dantzig ini kemudian menjadi dasar disertasinya dan, beberapa dekade kemudian, inspirasi untuk film *Good Will Hunting*.
Dantzig meraih gelar doktornya pada 1946, tepat setelah Perang Dunia II, dan segera menjadi penasihat matematika untuk Angkatan Udara AS yang baru dibentuk. Seperti semua perang modern, hasil dari PD II bergantung pada alokasi sumber daya yang terbatas secara bijaksana. Namun, berbeda dengan perang-perang sebelumnya, konflik ini berskala global dan dimenangkan sebagian besar berkat kekuatan industri yang luar biasa. AS bisa memproduksi lebih banyak tank, kapal induk, dan pesawat pengebom daripada musuh-musuhnya. Menyadari hal ini, militer sangat tertarik pada masalah optimisasi—yaitu, bagaimana mengalokasikan sumber daya terbatas secara strategis dalam situasi yang bisa melibatkan ratusan atau ribuan variabel.
Angkatan Udara menugaskan Dantzig untuk menemukan cara baru dalam memecahkan masalah optimisasi seperti ini. Sebagai respons, ia menciptakan metode simpleks, sebuah algoritma yang memanfaatkan beberapa teknik matematika yang ia kembangkan saat memecahkan masalah papan tulisnya hampir satu dekade sebelumnya.
Hampir 80 tahun kemudian, metode simpleks masih menjadi salah satu alat yang paling banyak digunakan ketika keputusan logistik atau rantai pasok harus diambil di bawah kendala yang kompleks. Metode ini efisien dan terbukti berhasil. “Metode ini selalu berjalan cepat, dan tidak pernah ada yang melihatnya berjalan lambat,” kata Sophie Huiberts dari Pusat Penelitian Ilmiah Nasional Prancis (CNRS).
Di sisi lain, ada sifat aneh yang telah lama membayangi metode Dantzig ini. Pada 1972, para matematikawan membuktikan bahwa waktu yang dibutuhkan untuk menyelesaikan suatu tugas dapat meningkat secara eksponensial seiring dengan jumlah kendala. Jadi, tidak peduli seberapa cepat metode ini dalam praktiknya, analisis teoritis secara konsisten menawarkan skenario terburuk yang menyiratkan bahwa ia bisa memakan waktu jauh lebih lama. Untuk metode simpleks, “alat tradisional kita untuk mempelajari algoritma tidak bekerja,” kata Huiberts.
Eleon Bach adalah salah satu penulis dari hasil penelitian baru ini.
Photograph: Courtesy of Eleon Bach
Namun, dalam sebuah makalah baru yang akan dipresentasikan pada bulan Desember di konferensi Foundations of Computer Science, Huiberts dan Eleon Bach, seorang mahasiswa doktoral di Universitas Teknik Munich, tampaknya telah mengatasi masalah ini. Mereka telah membuat algoritma lebih cepat, dan juga memberikan alasan teoritis mengapa waktu proses (runtime) eksponensial yang telah lama ditakuti tidak terwujud dalam praktik. Karya ini, yang dibangun berdasarkan hasil monumental dari tahun 2001 oleh Daniel Spielman dan Shang-Hua Teng, dinilai “brilian [dan] indah” menurut Teng.
“Ini adalah pekerjaan teknis yang sangat mengesankan, yang dengan mahir menggabungkan banyak ide yang dikembangkan dalam garis penelitian sebelumnya, [sambil menambahkan] beberapa ide teknis baru yang benar-benar bagus,” kata László Végh, seorang matematikawan di Universitas Bonn yang tidak terlibat dalam upaya ini.
Geometri yang Optimal
Metode simpleks dirancang untuk menangani kelas masalah seperti ini: Misalkan sebuah perusahaan furnitur membuat lemari pakaian, tempat tidur, dan kursi. Kebetulan, setiap lemari pakaian menghasilkan laba tiga kali lipat dari setiap kursi, sementara setiap tempat tidur menghasilkan laba dua kali lipat. Jika kita ingin menulis ini sebagai ekspresi, menggunakan a, b, dan c untuk mewakili jumlah furnitur yang diproduksi, kita akan mengatakan bahwa total laba sebanding dengan 3a + 2b + c.
Untuk memaksimalkan laba, berapa banyak dari setiap barang yang harus dibuat perusahaan? Jawabannya bergantung pada kendala yang dihadapinya. Katakanlah perusahaan dapat menghasilkan, paling banyak, 50 barang per bulan, jadi a + b + c kurang dari atau sama dengan 50. Lemari pakaian lebih sulit dibuat—tidak lebih dari 20 yang dapat diproduksi—jadi a kurang dari atau sama dengan 20. Kursi membutuhkan kayu khusus, dan pasokannya terbatas, jadi c harus kurang dari 24.
Metode simpleks mengubah situasi seperti ini—meski sering kali melibatkan lebih banyak variabel—menjadi masalah geometri. Bayangkan menggambarkan kendala kita untuk a, b, dan c dalam tiga dimensi. Jika a kurang dari atau sama dengan 20, kita dapat membayangkan sebuah bidang pada grafik tiga dimensi yang tegak lurus terhadap sumbu a, memotongnya di a = 20. Kita akan menetapkan bahwa solusi kita harus berada di suatu tempat pada atau di bawah bidang itu. Demikian pula, kita dapat membuat batasan yang terkait dengan kendala lainnya. Secara gabungan, batasan-batasan ini dapat membagi ruang menjadi bentuk tiga dimensi kompleks yang disebut polihedron.
Dalam upaya untuk terus meningkatkan kualitas layanan kami, maka perlu diadakan pemeliharaan rutin pada server. Hal ini akan menyebabkan beberapa layanan menjadi offline untuk sementara waktu mulai tanggal 15 Oktober.
Kami memohon maaf atas ketidaknyamanan yang mungkin timbul. Untuk informasi lebih lanjut, silahkan kunjungi halaman status resmi kami.