Program linear

Program linear adalah cara untuk memperoleh hasil optimal dari suatu model matematika yang disusun dari hubungan linear. Program linear adalah kasus khusus dalam pemrograman matematika.

Secara formal, suatu program linear digambarkan sebagai

usaha untuk memaksimalkan $\mathbf {c} ^{T}\mathbf {x}$ dengan kendala $\mathbf {Ax} \leq \mathbf {b}$ dan $\mathbf {x} \geq 0$

dengan $\mathbf {c}$ adalah vektor koefisien fungsi tujuan/objektif, $\mathbf {A}$ adalah matriks koefisien persamaan kendala, $\mathbf {b}$ adalah vektor nilai kunci, dan $\mathbf {x}$ adalah vektor peubah/variabel.

Program linear dapat diterapkan dalam berbagai bidang. Ia digunakan secara luas di bidang matematika dan secara khusus di bidang bisnis, ekonomi, dan teknologi. Industri pun menerapkan program linear, seperti transportasi, pengelolaan energi, telekomunikasi, dan manufaktur. Program ini terbukti mampu memecahkan masalah perencanaan, penjadwalan, dan desain.

Bentuk baku

Bentuk baku program linear adalah bentuk yang mudah dipahami untuk menjelaskan permasalahan program linear. Bentuk ini terdiri dari tiga bagian:

• Suatu fungsi tujuan/objektif

$f(x_{1},x_{2},\dots ,x_{n})=c_{1}x_{1}+c_{2}x_{2}+\dots +c_{n}x_{n}$

• Batasan/kendala permasalahan

${\begin{aligned}a_{11}x_{1}+a_{12}x_{2}+\dots +a_{1n}x_{n}&\leq b_{1}\\a_{21}x_{1}+a_{22}x_{2}+\dots +a_{1n}x_{n}&\leq b_{2}\\\vdots \quad &\\a_{m1}x_{1}+a_{m2}x_{2}+\dots +a_{mn}x_{n}&\leq b_{m}\end{aligned}}$

• Variabel nonnegatif

${\begin{aligned}x_{1}&\geq 0\\x_{2}&\geq 0\\&\vdots \\x_{n}&\geq 0\end{aligned}}$

Bentuk ini juga bisa ditulis dalam bentuk matriks seperti berikut.

${\text{maks}}\{\mathbf {c} ^{T}\mathbf {x} \;|\;\mathbf {Ax} \leq \mathbf {b} \land \mathbf {x} \geq 0\}$

Bentuk imbuhan (bentuk lempai/slack)

Program linear juga dapat digambarkan dalam bentuk imbuhan (augmented form) agar dapat diselesaikan dengan metode simpleks. Bentuk ini menggunakan variabel lempai (slack) yang nonnegatif untuk menggantikan pertidaksamaan dalam batasan/kendala. Permasalahan ini dapat ditulis ulang dalam bentuk matriks sebagai berikut.

Maksimalkan $z$ pada

${\begin{bmatrix}1&-\mathbf {c} ^{T}&0\\0&\mathbf {A} &\mathbf {I} \end{bmatrix}}{\begin{bmatrix}z\\\mathbf {x} \\\mathbf {s} \end{bmatrix}}={\begin{bmatrix}0\\\mathbf {b} \end{bmatrix}}$

dengan $\mathbf {s}$ adalah vektor variabel lempai ($\mathbf {s} \geq 0$) dan $\mathbf {x}$ adalah vektor penentu.

Penyelesaian

Tahapan umum untuk menyelesaikan program linear adalah

1. menentukan variabel keputusan;
2. membuat fungsi objektif;
3. merumuskan kendala/batasan;
4. menentukan daerah penyelesaian;
5. menentukan titik optimal;
6. mengartikan titik yang diperoleh.

Terdapat banyak cara untuk menyelesaikan program linear, antara lain metode grafik dan metode simpleks. Metode grafik hanya bisa menyelesaikan program linear dengan hingga dua (grafik dua dimensi) atau tiga variabel (grafik tiga dimensi). Metode simpleks tidak memiliki batasan jumlah variabel, tetapi lebih rumit daripada metode grafik.

Daftar pustaka

• Manullang, Sudianto; S., Andri Kristianto; Hutapea, Tri Andri; Sinaga, Lasker Pangarapan; Sinaga, Bornok; S., Mangaratua Marianus; Sinambela, Pardomuan N. J. M. (2017). Matematika untuk SMA/MA/SMK/MAK Kelas XI. Jakarta: Kementerian Pendidikan dan Kebudayaan.
• Arifien, Febianto. "Pemrograman Linier". Teknik Riset Operasional.

Pranala luar

• (Inggris) Guidance On Formulating LP Problems
• (Inggris) Mathematical Programming Glossary
• (Inggris) The Linear Programming FAQ
• (Inggris) Benchmarks For Optimisation Software