Program linear
Contoh kasus sederhana

Terdapat banyak cara untuk menyelesaikan program linear, antara lain metode grafik dan metode simpleks. Karena batasan visualisasi, metode grafik hanya dapat digunakan untuk menyelesaikan program linear dengan dua atau tiga variabel. Metode simpleks dapat digunakan tanpa memiliki batasan jumlah variabel[butuh rujukan]
, tetapi lebih rumit daripada metode grafik. Dalam bagian ini, akan dibahas cara penyelesaian masalah program linear dua variabel dengan menggunakan metode grafik. Berikut sebuah masalah memaksimumkan keuntungan:
Seorang pemilik tanah mengubah lahan seluas 150 m2 yang dia miliki menjadi tempat parkir. Melihat keadaan ekonomi di daerahnya, ia menetapkan harga parkir untuk mobil sebesar Rp. 3000 dan harga parkir untuk motor sebesar Rp. 2000. Dari pengukuran didapatkan bahwa satu motor memerlukan 1 m2 petak tanah, sedangkan satu mobil memerlukan 3 m2. Malangnya, desain dari tempat parkir hanya memungkinkan untuk menampung maksimum 100 kendaraan. Setelah beberapa bulan, pemilik tanah memerlukan data keuntungan maksimum yang mungkin ia diperoleh, sebagai salah satu pertimbangannya untuk memperbaiki desain tempat parkir tersebut.
Secara umum, terdapat beberapa tahapan dalam menyelesaikan sebuah program linear, yakni: menentukan variabel-variabel keputusan dari masalah, dan dilanjutkan dengan membuat fungsi objektif. Setelah itu setiap kendala/batasan perlu diformulasikan dalam bentuk persamaan atau pertidaksamaan. Tahap berikutnya adalah menentukan/mengecek daerah penyelesaian, karena sedikit banyak hal ini akan berpengaruh pada algoritma pencarian solusi yang perlu digunakan. Masalah program linear dianggap terselesaikan, ketika titik optimal sudah ditemukan (dan sudah dapat diartikan/dimaknai). Untuk permasalahan di atas, kita dapat menyusun program linear berikut:
Mencari maksimum dari  f(x,y)=3.000x+2.000y (keuntungan parkir dalam rupiah)
dengan kendala:
x+y\leq 100 (batas jumlah kendaraan)
3x+y\leq 150 (batas luas kendaraan dalam m2)
x\geq 0 (jumlah tidak boleh negatif)
y\geq 0 (jumlah tidak boleh negatif)
dengan  x dan  y masing-masing menyatakan banyak mobil dan motor yang terparkir.
Pada metode grafik, kita membentuk persamaan garis dari setiap kendala program linear. Hal ini dilakukan dengan mengubah setiap pertidaksamaan menjadi bentuk persamaan. Sebagai contoh, persamaan garis dari kendala  3x+y\leq 150 adalah  3x+y=150. Selanjutnya, kita mencatat setiap titik yang terbentuk dari semua perpotongan dua persamaan garis yang mungkin. Tabel berikut berisi titik perpotongan dari persamaan garis pada kolom dengan persamaan garis pada baris.
|   | (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.
Titik-titik perpotongan yang memenuhi semua kendala (berwarna hijau pada tabel) adalah solusi feasibel (yang mungkin) dari permasalahan program linear. Langkah berikutnya yang perlu dilakukan adalah menghitung fungsi objektif  f(x,y)=3.000x+2.000y pada keempat titik tersebut.
| Titik | Nilai (Rp) |
| --- | --- |
(0, 0): 0
(50, 0): 150.000
(0, 100): 200.000
(25, 75): 225.000
Dari tabel di atas, terlihat bahwa keuntungan maksimum yang dapat diperoleh adalah Rp 225.000. Hal ini tercapai ketika tempat parkir terisi dengan 25 mobil dan 75 motor.