Jabarkan Sejarah dari Metode simpleks

Pada masa Perang Dunia II George Dantzig bekerja di AU Amerika Serikat untuk mengurus metode penjadwalan. Selama tahun 1946, rekan kerjanya menantang dia untuk menstandarkan (mechanize) proses penjadwalan, untuk mengalihkan perhatiannya dari mengambil pekerjaan-pekerjaan lain. Terinspirasi dari karya Wassily Leontief, Dantzig memformulasi masalah sebagai sistem pertidaksamaan linear. Namun pada saat itu ia tidak mengikutkan objektif sebagai bagian dalam formulasi. Tanpa sebuah objektif, ada banyak solusi yang mungkin; sehingga untuk mencari solusi yang "optimal", aturan-aturan militer perlu digunakan untuk menjelaskan objektif yang diinginkan. Pencerahan yang didapatkan Dantzig adalah banyak dari aturan-aturan militer tersebut dapat disusun menjadi sebuah fungsi objektif linear yang perlu dimaksimumkan. Perkembangan metode simpleks adalah sebuah inovasi dan terjadi hanya dalam kurun waktu sekitar satu tahun.

Setelah Dantzig mengikutsertakan fungsi objektif dalam formulasinya pada sekitar tahun 1947, permasalahan menjadi lebih mudah secara matematis. Dantzig menyadari satu dari pertanyaan belum terpecahkan yang tidak sengaja dia selesaikan, karena ia pikir itu adalah pekerjaan rumah dari profesornya Jerzy Neyman, dapat digunakan untuk menemukan algoritma bagi program linear. Pertanyaan itu melibatkan proses mencari eksistensi pengali Langrange untuk program linear secara umum. Program linear ini dapat terdiri dari banyak variabel, masing-masing terbatas (bounded) diantara nol dan satu, dan memenuhi kendala linear yang dinyatakan dalam bentuk integral Lebesgue. Dantzig kemudian mempublikasikan "pekerjaan rumah"-nya sebagai tesis untuk mendapatkan gelar doktor. Geometri yang digunakan dalam tesis ini memberikan Dantzig wawasan bahwa metode simpleks dapat sangat efisien.