Matematika pemrograman linier

Pemrograman linier, teknik pemodelan matematika di mana fungsi linier dimaksimalkan atau diminimalkan ketika mengalami berbagai kendala. Teknik ini bermanfaat untuk memandu keputusan kuantitatif dalam perencanaan bisnis, teknik industri, dan — pada tingkat lebih rendah — dalam ilmu sosial dan fisik.

optimisasi: pemrograman linier

Meskipun banyak digunakan sekarang untuk memecahkan masalah keputusan sehari-hari, pemrograman linier secara komparatif tidak diketahui sebelum 1947. Tidak ada pekerjaan yang signifikan

Solusi dari masalah pemrograman linier mengurangi untuk menemukan nilai optimal (terbesar atau terkecil, tergantung pada masalah) dari ekspresi linear (disebut fungsi objektif)

tunduk pada serangkaian kendala yang dinyatakan sebagai ketidaksetaraan:

A, b, dan c adalah konstanta yang ditentukan oleh kapasitas, kebutuhan, biaya, keuntungan, dan persyaratan serta batasan lain dari masalah tersebut. Asumsi dasar dalam penerapan metode ini adalah bahwa berbagai hubungan antara permintaan dan ketersediaan bersifat linier; yaitu, tidak satupun dari x _i dinaikkan ke kekuatan selain 1. Untuk mendapatkan solusi untuk masalah ini, perlu untuk menemukan solusi dari sistem ketidaksetaraan linear (yaitu, himpunan n nilai dari variabel x _i yang secara bersamaan memenuhi semua ketidaksetaraan). Fungsi tujuan kemudian dievaluasi dengan menggantikan nilai-nilai x _i dalam persamaan yang mendefinisikan f.

Aplikasi metode pemrograman linier pertama kali dicoba secara serius pada akhir 1930-an oleh matematikawan Soviet Leonid Kantorovich dan oleh ekonom Amerika Wassily Leontief di bidang jadwal manufaktur dan ekonomi, masing-masing, tetapi pekerjaan mereka diabaikan selama beberapa dekade. Selama Perang Dunia II, pemrograman linier digunakan secara luas untuk menangani transportasi, penjadwalan, dan alokasi sumber daya yang tunduk pada batasan tertentu seperti biaya dan ketersediaan. Aplikasi ini berbuat banyak untuk menetapkan penerimaan metode ini, yang memperoleh dorongan lebih lanjut pada tahun 1947 dengan diperkenalkannya metode simpleks matematikawan Amerika George Dantzig, yang sangat menyederhanakan solusi masalah pemrograman linier.

Namun, karena masalah yang semakin kompleks yang melibatkan lebih banyak variabel dicoba, jumlah operasi yang diperlukan diperluas secara eksponensial dan melebihi kapasitas komputasi bahkan komputer yang paling kuat. Kemudian, pada tahun 1979, matematikawan Rusia Leonid Khachiyan menemukan algoritma waktu polinomial — di mana jumlah langkah komputasi tumbuh sebagai kekuatan jumlah variabel daripada secara eksponensial — sehingga memungkinkan solusi dari masalah yang sampai sekarang tidak dapat diakses. Namun, algoritma Khachiyan (disebut metode ellipsoid) lebih lambat daripada metode simpleks ketika diterapkan secara praktis. Pada 1984, ahli matematika India Narendra Karmarkar menemukan algoritma waktu polinomial lain, metode titik interior, yang terbukti kompetitif dengan metode simpleks.