Program Linier

Program linear adalah suatu metode penentuan nilai optimum dari suatu persoalan linear. Nilai optimum (maksimal atau minimum) diperoleh dari nilai dalam suatu himpunan penyelesaiaan persoalan linear. Di dalam persoalan linear terdapat fungsi linear yang bisa disebut sebagai fungsi objektif. Persyaratan, batasan, dan kendala dalam persoalan linear merupakan sistem pertidaksamaan linear.

CONTOH SOAL

1.    Nilai maksimum f(x, y) = 5x + 4y yang memenuhi pertidaksamaan x + y ≤ 8, x + 2y ≤ 12, x ≥ 0, dan y ≥ 0 adalah ...
a.    24
b.    32
c.    36
d.    40
e.    60
PEMBAHASAN:
-    x + y ≤ 8
ketika x = 0, maka y = 8 .... (0, 8)
ketika y = 0, maka x = 8 .... (8, 0)
-    x + 2y ≤ 12
ketika x = 0, maka y = 6 .... (0, 6)
ketika y = 0, maka x = 12 .... (12, 0)
Sehingga, grafik dari pertidak samaan di atas adalah:

Kita cari dulu titik B, yaitu titik potong dua buah garis, yaitu:

subtitusikan y = 4 dalam x + y = 8
x + 4 = 8
x = 4 .... (4, 4)
Jadi, nilai fungsi obyektifnya adalah:
f(x, y) = 5x + 4y
-    titik A (0, 6)
      5x + 4y = 5.0 + 4.6 = 24
-    titik B (4, 4)
      5x + 4y = 5.4 + 4.4 = 20 + 16 = 36
-    titik C (8, 0)
      5x + 4y = 5.8 + 4.0 = 40
Jadi, nilai maksimumnya adalah 40.
JAWABAN: D

2.    Daerah yang merupakan himpunan penyelesaian dari pertidaksamaan 2x + 3y ≤ 12, 4x + y ≥ 10, x ≥ 0, y ≥ 0 adalah ...

a.    I
b.    II
c.    III
d.    IV
e.    I dan III
PEMBAHASAN:
-    Daerah hasil 2x + 3y ≤ 12 adalah area II dan III
-    Daerah hasil  4x + y ≥ 10 adalah area III dan IV
Maka, yang mencakup keduanya adalah area nomor III
JAWABAN: C

3.    Daerah mana yang diarsir di bawah ini adalah daerah penyelesaian suatu sistem pertidaksamaan. Nilai maksimum fungsi objektif (3x + 5y) pada daerah penyelesaian tersebut ...

a.    30
b.    26
c.    24
d.    21
e.    18
PEMBAHASAN:
Perhatikan gambar:

-    Persamaan garis p = 6x + 4y = 24 atau 3x + 2y = 12
-    Persamaan garis q = 4x + 6y = 24 atau 2x + 3y = 12
Titik potong garis p dan q adalah:

subtitusikan y = 12/5 dalam 2x + 3y = 12:
2x + 3.12/5 = 12
2x = 12 – 36/5
2x = 60/5 – 36/5
2x = 24/5
x = 24/10 = 12/5 .... titik B (12/5, 12/5)
Nilai dari fungsi obyektif  3x + 5y adalah:
-    Titik A (0, 6)
      3x + 5y = 3.0 + 5. 6 = 30
-    Titik B (12/5, 12/5)
      3x + 5y = 3.12/5 + 5.12/5 = 36/5 + 60/5 = 96/5 = 19,2
-    Titik C (6, 0)
      3x + 5y = 3.6 + 5.0 = 18
Jadi, nilai minimumnya adalah 18
JAWABAN: E

4.    Nilai minimum fungsi obyektif  f(x, y) = 3x + 2y dari daerah yang diarsir pada gambar adalah  ...

a.    4
b.    6
c.    7
d.    8
e.    9
PEMBAHASAN:
Perhatikan gambar berikut:

Ingat ya, rumus persamaan garis yang melalui titik (0, a) dan (b, 0) adalah: ax + by = a.b, maka:
-    Persamaan garis p = 4x + 2y = 4.2 = 4x + 2y = 8 = 2x + y = 4
-    Persamaan garis q = 3x + 3y = 3.3 = 3x + 3y = 9 = x + y = 3
Selanjutnya, kita cari titik potong garis p dan q, yaitu di titik B:

subtitusikan x = 1 dalam x + y =3
1 + y = 3
y = 2 .... B(1, 2)
kita cari nilai dari fungsi obyektif  f(x, y) = 3x + 2y:
-    Titik A (0, 4)
     3x + 2y = 3.0 + 2.4 = 8
-    Titik B (1, 2)
      3x + 2y = 3.1 + 2.2 = 7
-    Titik C (3, 0)
      3x + 2y = 3.3 + 2.0 = 9
Jadi, nilai minimumnya adalah 7
JAWABAN: C

5.    Nilai minimum f(x, y) = 3 + 4x – 5y untuk x dan y yang memenuhi –x + y ≤ 1, x + 2y ≥ 5 dan 2x + y ≤ 10 adalah ...
a.    -19
b.    -6
c.    -5
d.    -3
e.    23
PEMBAHASAN;
-    –x + y = 1
Jika x = 0, maka y = 1 ... (0, 1)
Jika y = 0, maka x = -1 ... (-1, 0)
-     x + 2y = 5
jika x = 0, maka y = 5/2 ... (0, 5/2)
jika y =0, maka x = 5 ... (5, 0)
-    2x + y = 10
Jika x = 0, maka y = 10 ... (0, 10)
Jika y = 0, maka x = 5 ... (5, 0)
Mari kita gambar daerah hasilnya:

-    Titik A adalah titik potong antara –x + y = 1 dan 2x + y = 10, maka titik potongnya:

     2.3 + y = 10
     6 + y = 10
     y = 4 ... titik A (3,  4)
Maka, nilai obyektif  fungsi f(x, y) = 3 + 4x – 5y adalah: 3 + 4.3 – 5.4 = 3 + 12 – 20 = -5
-    Titik B adalah titik potong antara  –x + y = 1 dan x + 2y = 5, maka titik potongnya:

      x + 2.2 = 5
      x + 4 = 5
      x =1 ... titik B (1, 2)
Maka, nilai obyektif  fungsi f(x, y) = 3 + 4x – 5y adalah: 3 + 4.1 – 5.2 = 3 + 4 – 10 = -3
-    Titik C (5, 0)
Maka, nilai obyektif  fungsi f(x, y) = 3 + 4x – 5y adalah: 3 + 4.5 – 5.0 = 3 + 20 – 0 = 23
Jadi, nilai minimum fungsi adalah -5
JAWABAN: C