Matematik pengaturcaraan linear

Pengaturcaraan linier, teknik pemodelan matematik di mana fungsi linier dimaksimumkan atau diminimumkan apabila dikenakan pelbagai kekangan. Teknik ini telah berguna untuk membimbing keputusan kuantitatif dalam perancangan perniagaan, kejuruteraan industri, dan - pada tahap yang lebih rendah - dalam sains sosial dan fizikal.

pengoptimuman: Pengaturcaraan linear

Walaupun digunakan secara meluas sekarang untuk menyelesaikan masalah keputusan sehari-hari, pengaturcaraan linear tidak diketahui sebelum tahun 1947. Tidak ada karya yang penting

Penyelesaian masalah pengaturcaraan linear mengurangkan mencari nilai optimum (terbesar atau terkecil, bergantung pada masalah) ekspresi linear (disebut fungsi objektif)

tertakluk kepada sekumpulan kekangan yang dinyatakan sebagai ketaksamaan:

The a, b, dan c adalah pemalar yang ditentukan oleh kapasiti, keperluan, kos, keuntungan, dan keperluan lain dan sekatan masalah. Andaian asas dalam penerapan kaedah ini adalah bahawa pelbagai hubungan antara permintaan dan ketersediaan adalah linear; iaitu, tidak satu pun dari x _i dinaikkan ke kekuatan selain dari 1. Untuk mendapatkan penyelesaian untuk masalah ini, adalah perlu untuk mencari penyelesaian sistem ketaksamaan linear (iaitu, set nilai n dari pemboleh ubah x _i yang secara serentak memenuhi semua ketaksamaan). Fungsi objektif kemudiannya dinilai dengan menggantikan nilai x _i dalam persamaan yang menentukan f.

Aplikasi kaedah pengaturcaraan linier pertama kali dilakukan secara serius pada akhir tahun 1930-an oleh ahli matematik Soviet Leonid Kantorovich dan ahli ekonomi Amerika Wassily Leontief dalam bidang jadual pembuatan dan ekonomi, masing-masing, tetapi karya mereka diabaikan selama beberapa dekad. Selama Perang Dunia II, pengaturcaraan linier digunakan secara meluas untuk menangani pengangkutan, penjadualan, dan peruntukan sumber daya yang dikenakan sekatan tertentu seperti biaya dan ketersediaan. Aplikasi-aplikasi ini banyak membuktikan keberagaman kaedah ini, yang mendapat dorongan lebih jauh pada tahun 1947 dengan pengenalan kaedah simplex ahli matematik Amerika George Dantzig, yang sangat memudahkan penyelesaian masalah pengaturcaraan linear.

Namun, kerana masalah yang semakin kompleks yang melibatkan lebih banyak pemboleh ubah dicuba, jumlah operasi yang diperlukan berkembang secara eksponensial dan melebihi kapasiti komputasi bahkan komputer yang paling berkuasa. Kemudian, pada tahun 1979, ahli matematik Rusia Leonid Khachiyan menemui algoritma masa polinomial - di mana bilangan langkah pengiraan bertambah sebagai kekuatan bilangan pemboleh ubah dan bukannya secara eksponensial - sehingga memungkinkan penyelesaian masalah yang tidak dapat diakses sehingga kini. Walau bagaimanapun, algoritma Khachiyan (disebut kaedah elipsoid) lebih perlahan daripada kaedah simplex ketika diterapkan secara praktikal. Pada tahun 1984 ahli matematik India Narendra Karmarkar menemui algoritma masa polinomial lain, kaedah titik dalaman, yang terbukti kompetitif dengan kaedah simplex.