Dasar dalam Program Linear

Pertidaksamaan Linear adalah pertidaksamaan dengan pangkat tertinggi dari variabelnya satu, gabungan dau atau lebih pertidaksamaan linear disebut sistem pertidak samaan linear

Contoh :
$1. \left.\begin{matrix}ax+by\geq c\\ px+qy\geq r\end{matrix}\right\}$
$2. \left.\begin{matrix}ax+by<c\\ px+qy<r\end{matrix}\right\}$
$3. \left.\begin{matrix}ax+by\leq  c\\ px+qy\geq r\end{matrix}\right\}$
$4. \left.\begin{matrix}x\geq 0\\ x\geq 0\\ ax+by\leq  c\end{matrix}\right\}$

Langkah-langkah untuk menentukan daerah himpunan penyelesaian pertidaksamaan linear $ax+by\geq c$ dengan metode grafik.
1. Menggambar garis ax + by = c
2. Melakukan uji titik, yaitu sembarang titik (x,y) yang tidak terlatak pada garis ax + by = c, kemudian mensubstitusikannya ke dalam pertidaksamaan $ax+by\geq c$
a. Jika pertidaksamaan itu bernilai benar, maka himpunan penyelesaiannya adalah daerah yang memuat titik tersebut dengan batas garis ax + by = c
b. Jika pertidaksamaan itu bernilai salah, maka himpunana penyelesaiannya adalah daerah yang tidak memuat titik tersebut dengan garis ax + by = c

Tanpa melakukan uji titik, daerah himpunan penyelesaian suatu pertidaksamaan linear dapat ditentukan dengan aturan sebagai berikut.

Pertidaksamaan	b > 0	b < 0
ax + by ≥ c	Daerah himpunan penyelesaian berada di kanan/ di atas garis ax + by = c	Daerah himpunan penyelesaian berada di kiri/ di bawah garis ax + by = c
ax + by ≤ c	Daerah himpunan penyelesaian berada di kiri/ di bawah garis ax + by = c	Daerah himpunan penyelesaian berada di kanan/ di atas garis ax + by = c

Contoh soal:
1. 2x + y ≤ -4

Jawab:
2x + y = -4
Jika y = 0
2x=-4                   x=-2
(-2,0)

Jika x = 0
y=-4                 
(0,-4)

Grafiknya

2. -1 ≤ x ≤ 3 dan x - y < 2

Jawab:
* -1≤ x ≤ 3
x ≥ -1
x ≤ 3

* x - y < 2
Jika y = 0
x < 2
Jika x = 0
y > 2

Grafiknya

3. 3x + 2y ≤ 4  ;  4x - y ≤ 3  ;  x  ≥ 0  ;  y  ≥  0

* 3x + 2y ≤ 4
Jika y = 0
3x ≤ 4              $x ≤ \frac{4}{3}$
Jika x = 0
2y ≤ 4              $y ≤ 2$

* 4x - y ≤ 3
Jika y = 0
4x ≤ 3              $x ≤ \frac{3}{4}$
Jika x = 0
-y ≤ 3               y ≤ -3

* x  ≥ 0  ;  y  ≥  0

Grafiknya

4. x + y ≤ 4  ;  x - y ≥ 2  ;  x + 2y ≥ -1  ;  x ≤ 3  ;  y ≤ 3 

Jawab:
* x + y ≤ 4
Jika y = 0
x ≤ 4
Jika x = 0
y ≤ 4

* x - y ≥ 2
Jika y = 0
x ≥ 2
Jika x = 0
y ≥ -2

* x + 2y ≥ -1
Jika y = 0
x ≥ -1
Jika x = 0
y ≥ -1/2

*x ≤ 3  ;  *y ≤ 3

Grafiknya

5. Sebuah toko furnitur membuat 2 macam produksi yaitu meja dan kursi yang harus diproses melalui bagian perakitan dan penyempurnaan. Bagian perakitan menyediakan 60 jam dan penyempurnaan 48 jam, setiap pembuatan 1 meja memerlukan 4 jam perakitan dan 2 jam penyempurnaan. Setiap pembuatan 1 kursi memerlukan 2 jam perakitan dan 4 jam penyempurnaan. Keuntungan yang diperoleh adalah 80.000 per meja dan 60.000 per kursi. Tentukan jumlah meja dan kursi yang harus dibuat agar keuntungannya maksimum

Jawab:
Pemodelan 

	Perakitan	Penyempurnaan	Laba
Meja	4 jam	2 jam	80.000
Kursi	2 jam	4 jam	60.000
Persediaan	60 jam	48 jam

4x + 2y ≤ 60 → 2x + y ≤ 30
* (15,0)(0,30)
2x +4y ≤ 48 → x + 2y ≤ 24
* (24,0)(0,12)
x ≥ 0
y ≥ 0
f sasaran 80.000x + 60.000y  → 8x + 6y

2x + y = 30                         2x + y   = 30
x + 2y = 24      | x 2            2x + 4y = 48
                                           ___________ -
                                                  -3y = -18
                                                     y = 6

2x + y = 30  
2x + 6 = 30
2x = 24
x = 12


Grafiknya 

Titik sudut	8x + 6y
(0,0)	0
(0,12)	72
(12,6)	132
(15,0)	120

Karena nilai yang terbesar adalah di titik sudut (12,6) yaitu 132, maka untuk memperoleh keuntungan maksimum haruslah 12 meja dan 6 kursi

Sumber : Buku Catatan Kuliah Program Linear