Jabarkan Sejarah dari Program linear

Masalah menyelesaikan sebuah sistem pertidaksamaan linear dapat dilacak ke Fourier, yang pada tahun 1827 menerbitkan sebuah metode untuk menemukan solusinya. Metode ini selanjutnya diberi nama eliminasi Fourier-Motzkin.

Pada tahun 1939, seorang matematikawan dan ekonom Uni Soviet, Leonid Kantorovich, membuat formulasi program linear dari masalah yang serupa dengan formulasi masalah program saat ini. Ia juga mengusulkan sebuah metode untuk menyelesaikannya. Formulasi ini ia kembangkan pada masa Perang Dunia II, untuk merencanakan pengeluaran dan pendapatan agar mengurangi rugi bagi tentara dan meningkatkan kerugian bagi musuh. Karya Kantorovich awalnya dihiraukan oleh USSR. Pada saat yang sama dengan Kantorovich, ekonom Amerika-Belanda T. C. Koopmans memformulasikan masa ekonomi klasik dalam bentuk program linear. Kantorovich dan Koopmans nantinya mendapatkan penghargaan Nobel bidang ekonomi tahun 1975. Pada tahun 1941, Frank Lauren Hitchcock juga memformulasikan masalah transportasi dalam bentuk program linear, dan memberikan solusi yang sangat mirip dengan metode simpleks. Hitchcock meninggal pada tahun 1957 dan penghargaan Nobel tidak diberikan secara anumerta.

Sepanjang tahun 1946–1947, George B. Dantzig secara independen mengembangkan formulasi program linear yang umum agar dapat digunakan dalam masalah perencanaan di Angkata Udara Amerika Serikat. Di tahun 1947, juga menemukan metode simpleks yang untuk pertama kalinya menyelesaikan banyak masalah program linear secara efisien. Ketika Dantzig melakukan pertemuan dengan John von Neumann untuk mendiskusikan metode simpleksnya, Neumann langsung memberikan konjektur tentang teori tentang dualitas; dari realisasinya bahwa ini ekuivalen dengan masalah yang ia kerjakan di bidang teori permainan. Dantzig memberikan bukti formal pada sebuah laporan yang tidak dipublikasikan, "A Theorem on Linear Inequalities" pada 5 Januari 1948. Karya Dantzig dipublikasikan ke publik pada tahun 1951. Dalam masa setelah perang, banyak industri yang menerapkan metodenya dalam masalah perencanaan harian mereka.

Contoh masalah yang diberikan Dantzig adalah menemukan penugasan 70 orang ke 70 pekerjaan. Daya komputasi untuk mengecek semua permutasi kemungkinan penugasan sangat besar, melebihi banyaknya partikel yang ada di alam semesta yang teramati. Namun, butuh waktu yang singkat untuk menemukan solusi ketika masalah disusun sebagai program linear dan menerapkan algoritme simpleks. Teori yang mendasari program linear secara drastis mengurangi banyaknya kemungkinan solusi yang perlu dicek.

Masalah program linear dibuktikan dapat diselesaikan dalam waktu polinomial oleh Leonid Khachiyan pada tahun 1979. Namun baru pada tahun 1984 terobosan besar di bidang teori dan praktek terjadi, ketika Narendra Karmarkar memperkenalkan metode interior-point untuk menyelesaikan masalah program linear.