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

menentukan variabel keputusan;
membuat fungsi objektif;
merumuskan kendala/batasan;
menentukan daerah penyelesaian;
menentukan titik optimal;
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.

Contoh kasus sederhana

Program linear yang memiliki dua variabel dapat digambarkan dalam grafik untuk mempermudah penyelesaian (walau tidak perlu). Berikut contoh soal dan penyelesaiannya.

Harga parkir mobil adalah Rp3 ribu dan harga parkir motor adalah Rp2 ribu. Suatu lahan parkir seluas 150 m² dapat menampung 100 kendaraan. Satu motor menghabiskan 1 m² dan satu mobil menghabiskan 3 m². Bila lahan parkir tersebut disewakan, berapa keuntungan maksimum yang bisa didapat?

Dari soal di atas, dapat disusun program linear berikut:

memaksimalkan $f(x,y)=3.000x+2.000y$ (keuntungan parkir dalam rupiah)
dengan kendala:
1. $x+y\leq 100$ (batas jumlah kendaraan)
2. $3x+y\leq 150$ (batas luas kendaraan dalam m²)
3. $x\geq 0$ (jumlah tidak boleh negatif)
4. $y\geq 0$ (jumlah tidak boleh negatif)

dengan $x$ adalah mobil dan $y$ adalah motor.

Dari empat persamaan itu, dapat diambil empat titik perpotongan yang memenuhi empat persamaan di atas.

	(1)	(2)	(3)	(4)
(1)	-
(2)	$(25, 75)$	-
(3)	$(0, 100)$	$(0, 150)$	-
(4)	$(100, 0)$	$(50, 0)$	$(0, 0)$	-
Sel yang berwarna hijau memenuhi empat persamaan di atas.

Hitung fungsi objektif $f(x,y)=3.000x+2.000y$ untuk empat titik tersebut.

Titik	Nilai (Rp)
$(0, 0)$	0
$(50, 0)$	150.000
$(0, 100)$	200.000
$(25, 75)$	225.000

Dari tabel di atas, dapat dilihat bahwa keuntungan maksimum yang bisa didapat adalah Rp225 ribu dengan 25 mobil dan 75 motor.

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