Aplikasi Linear Programming


George B. Dantzig adalah penerima National Medal of Science dari Presiden Amerika Serikat, karena telah menemukan ilmu Linear Programming dan Algoritma simplex. Kedua ilmu tersebut merupakan ilmu yang telah memungkinkan umat manusia untuk pertama kalinya, untuk membuat struktur dan memecahkan masalah alokasi sumber daya yang sangat kompleks. Kedua ilmu tersebut merupakan ilmu yang sangat penting  untuk memecahkan berbagai macam pada bidang logistik, penjadwalan, dan optimalisasi jaringan (Dantzig dan Thapa, 2003).

 

Konsep Linear Programming dikembangkan oleh Dantzig ketika masa perang dunia ke-2,  untuk merencanakan kegiatan militer di US Air Force.  Komandan militer perlu dibantu untuk membuat keputusan yang terbaik pada situasi yang kompleks dan melibatkan banyak pihak, misalnya pengadaan perlengkapan perlu mempertimbangkan kemampuan ekonomi negara, dan kapabilitas produksi yang dimiliki oleh masyarakat sipil. Setelah masa perang selesai, Linear Programming digunakan untuk mengalokasikan sumber daya manusia (tentara dan sipil) yang berjumlah sangat besar (gigantic scale) untuk kepentingan selain perang (Dantzig, 1963).

 

Pada tahun 1947, ilmu pemrograman sedang berkembang di Amerika, selaras dengan kebangkitan industri elektronik, yang memiliki karakteristik saling terkait dengan industri penunjangnya. Pada tahun 1947, Dantzig menemukan algoritma Simplex untuk memecahkan masalah kompleks. Menurut Bixby (2012), algoritma simplex membutuhkan kemampuan matematis yang tinggi dan memakan waktu yang lama, sebagai contoh diperlukan 120 hari kerja untuk mencari solusi masalah The Classical Stigler Diet Problem(memiliki 21 contraint dan 77 variabel). Oleh karena itu, komputer digunakan untuk membantu menyelesaikan masalah dengan Algoritma Simplex.

 

Pada tahun 1960, William Orchard Hays menuliskan Algoritma Simplex (Revised Simplex Algorithm) ke dalam suatu bahasa pemrograman di komputer IBM 7094 36bit. Program komputer ini berhasil digunakan oleh berbagai macam masalah, diantara (1) masalah relokasi pabrik milik Phillip Petroleum, (2) masalah pemilihan pesawat acheterdufrance.com udara dan kapal sebagai sarana transportasi bagi tentara Inggris, (3) masalah investasi pabrik pengilangan minyak milik British Petroleum, dan (4) memilih tambang batu bara oleh Dewan Batubara Nasional Inggris (Bixby, 2012).

 

Dewasa ini, bidang pemrograman linear dan ekstensinya (pemrograman matematika) telah berkembang secara pesat, serta menjadi alat yang paling banyak digunakan untuk perencanaan dan penjadwalan di dunia industri hingga hari ini.

 

 

 

 

Ref

George B. Dantzig Mukund N. Thapa. 2003. Linear Programming: 2: Theory and Extensions. Springer-Verlag New York

 

Robert E. Bixby. A Brief History of Linear and Mixed-Integer Programming Computation. Documenta Mathematica. Extra Volume ISMP (2012) 107–121

 

George B. Dantzig. 1963. Linear Programming and Extensions.  Princeton University Press. New Jersey


Leave a Reply