Versi aslinya dari cerita ini muncul di Majalah Kuanta.
Pada tahun 1939, setelah datang terlambat ke mata kuliah statistika di UC Berkeley, George Dantzig—seorang mahasiswa pascasarjana tahun pertama—menyalin dua soal dari papan tulis, mengira itu adalah pekerjaan rumah. Dia mendapati pekerjaan rumahnya “lebih sulit untuk dikerjakan daripada biasanya,” dia kemudian menceritakannya, dan meminta maaf kepada profesor karena mengambil beberapa hari ekstra untuk menyelesaikannya. Beberapa minggu kemudian, profesornya memberi tahu dia bahwa dia telah memecahkan dua permasalahan terbuka yang terkenal dalam statistik. Karya Dantzig menjadi dasar disertasi doktoralnya dan, beberapa dekade kemudian, menjadi inspirasi untuk film tersebut Perburuan Niat Baik.
Dantzig menerima gelar doktornya pada tahun 1946, tepat setelah Perang Dunia II, dan ia segera menjadi penasihat matematika di Angkatan Udara AS yang baru dibentuk. Seperti semua perang modern, hasil Perang Dunia II bergantung pada alokasi sumber daya yang terbatas secara bijaksana. Namun tidak seperti perang-perang sebelumnya, konflik ini benar-benar berskala global, dan sebagian besar dimenangkan melalui kekuatan industri. AS bisa saja memproduksi lebih banyak tank, kapal induk, dan pembom dibandingkan musuh-musuhnya. Mengetahui hal ini, pihak militer sangat tertarik pada masalah optimalisasi—yaitu, bagaimana mengalokasikan sumber daya yang terbatas secara strategis dalam situasi yang dapat melibatkan ratusan atau ribuan variabel.
Angkatan Udara menugaskan Dantzig untuk mencari cara baru untuk memecahkan masalah optimasi seperti ini. Sebagai tanggapan, ia menemukan 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 pasokan perlu diambil dalam kondisi yang kompleks. Ini efisien dan berhasil. “Ia selalu berjalan cepat, dan tak seorang pun pernah melihatnya tidak cepat,” katanya Sophie Huiberts dari Pusat Penelitian Ilmiah Nasional Perancis (CNRS).
Pada saat yang sama, ada sifat aneh yang telah lama membayangi metode Dantzig. Pada tahun 1972, ahli matematika membuktikan bahwa waktu yang dibutuhkan untuk menyelesaikan suatu tugas dapat meningkat secara eksponensial seiring dengan banyaknya kendala. Jadi, tidak peduli seberapa cepat metode ini dipraktikkan, analisis teoritis secara konsisten menawarkan skenario terburuk yang menyiratkan bahwa hal ini bisa memakan waktu lebih lama secara eksponensial. Untuk metode simpleks, “alat tradisional kami untuk mempelajari algoritma tidak berfungsi,” kata Huiberts.
Namun dalam cara yang baru kertas yang akan dipresentasikan pada bulan Desember di konferensi Foundations of Computer Science, Huiberts dan Eleon Bachseorang mahasiswa doktoral di Technical University of Munich, tampaknya telah mengatasi masalah ini. Mereka telah membuat algoritme menjadi lebih cepat, dan juga memberikan alasan teoretis mengapa runtime eksponensial yang telah lama dikhawatirkan tidak terwujud dalam praktik. Pekerjaan yang dibangun di atas a hasil penting dari tahun 2001 oleh Daniel Spielman Dan Shang-Hua Tengadalah “cemerlang (dan) indah,” menurut Teng.
“Ini merupakan pekerjaan teknis yang sangat mengesankan, yang secara ahli menggabungkan banyak ide yang dikembangkan dalam penelitian sebelumnya, (sambil menambahkan) beberapa ide teknis baru yang benar-benar bagus,” kata Laszló Véghseorang ahli matematika di Universitas Bonn yang tidak terlibat dalam upaya ini.
Geometri Optimal
Metode simpleks dirancang untuk mengatasi sekelompok masalah seperti ini: Misalkan sebuah perusahaan furnitur membuat lemari, tempat tidur, dan kursi. Secara kebetulan, setiap lemari tiga kali lebih menguntungkan dibandingkan setiap kursi, sementara setiap tempat tidur dua kali lebih menguntungkan. Jika kita ingin menulis ini sebagai ekspresi, gunakan A, BDan C untuk mewakili jumlah furnitur yang diproduksi, kita katakan bahwa total keuntungan sebanding dengan 3A + 2B + C.
Untuk memaksimalkan keuntungan, berapa banyak setiap barang yang harus diproduksi perusahaan? Jawabannya tergantung pada kendala yang dihadapi. Katakanlah sebuah perusahaan dapat memproduksi paling banyak 50 item per bulan, jadi A + B + C kurang dari atau sama dengan 50. Lemari lebih sulit dibuat—tidak lebih dari 20 yang bisa diproduksi—jadi A kurang dari atau sama dengan 20. Kursi membutuhkan kayu khusus, dan persediaannya terbatas C harus kurang dari 24.
Metode simpleks mengubah situasi seperti ini—walaupun seringkali melibatkan lebih banyak variabel—menjadi masalah geometri. Bayangkan membuat grafik batasan kita 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 A sumbu, memotongnya di A = 20. Kita akan menetapkan bahwa solusi kita harus terletak pada atau di bawah bidang tersebut. Demikian pula, kita dapat membuat batasan yang terkait dengan batasan lainnya. Jika digabungkan, batas-batas ini dapat membagi ruang menjadi bentuk tiga dimensi kompleks yang disebut polihedron.
