Program linear

Program linear atau pemrograman linear adalah metode untuk memperoleh hasil optimal dari suatu model matematika yang disusun dari hubungan linear. Program linear adalah kasus khusus dalam pemrograman matematika (juga dikenal dengan optimisasi matematika).

Secara lebih formal, program linear adalah sebuah teknik optimisasi untuk fungsi objektif linear, dengan kendala (beberapa) persamaan linear dan pertidaksamaan linear. Daerah feasibel dari kendala berupa sebuah politop konveks, yakni sebuah himpunan yang didefinisikan dari perpotongan banyak (namun terhingga) half spaces. Sedangkan fungsi objektif berupa fungsi (linear) bernilai real yang terdefinisi pada politop tersebut. Sebuah algoritme program linear akan mencari sebuah titik pada politop, yang menyebabkan fungsi objektif akan menghasilkan nilai terkecil (atau terbesar); jika titik tersebut ada.

Program linear adalah masalah yang dapat dinyatakan dalam bentuk kanonik (baku) sebagai

${\displaystyle {\begin{aligned}&{\text{Cari sebuah vektor}}&&\mathbf {x} \\&{\text{yang memaksimumkan}}&&\mathbf {c} ^{T}\mathbf {x} \\&{\text{dengan kendala}}&&A\mathbf {x} \leq \mathbf {b} \\&{\text{dan}}&&\mathbf {x} \geq \mathbf {0} .\end{aligned}}}$

Disini, komponen-komponen dari ${\displaystyle \mathbf {x} }$ adalah variabel yang ingin ditentukan nilainya. Vektor ${\displaystyle \mathbf {c} }$ adalah vektor koefisien fungsi objektif, sedangkan ${\displaystyle \mathbf {b} }$ adalah vektor nilai kunci. Fungsi objektif adalah fungsi yang nilainya ingin dimaksimumkan atau diminimumkan, dalam kasus ini berupa fungsi ${\displaystyle \mathbf {x} \mapsto \mathbf {c} ^{T}\mathbf {x} }$. Matriks ${\displaystyle \mathbf {A} }$ berisi koefisien-koefisien dari persamaan (dan pertidaksamaan) kendala-kendala. Pertidaksamaan ${\displaystyle \mathbf {A} \mathbf {x} \leq \mathbf {b} }$ dan ${\displaystyle \mathbf {x} \geq \mathbf {0} }$ menyatakan daerah pencarian titik untuk mengoptimisasi fungsi objektif. Dalam konteks ini, dua vektor dapat dibandingkan jika keduanya memiliki dimensi yang sama. Vektor ${\displaystyle \mathbf {x} }$ dikatakan lebih kecil atau sama dengan vektor ${\displaystyle \mathbf {y} }$, jika semua nilai komponen vektor ${\displaystyle \mathbf {x} }$ lebih kecil atau sama dengan nilai komponen ${\displaystyle \mathbf {y} }$ yang bersesuaian.

Program linear dapat diterapkan dalam berbagai bidang studi. metode ini digunakan secara luas di bidang matematika dan secara khusus di bidang bisnis, ekonomi, dan teknologi. Banyak bidang industri juga menerapkan program linear, seperti transportasi, pengelolaan energi, telekomunikasi, dan manufaktur. Program ini terbukti berguna dalam memecahkan masalah perencanaan, penjadwalan, dan desain.