BAB II
PROGRAM LINEAR
A RINGKASAN MATERI
1. Pengertian
Program linear adalah suatu permasalahan dalam matematika dengan tujuan untuk mengoptimalkan fungsi
obyektif yang berbentuk linear dengan kendala/batasan berupa pertidaksamaan linear.
2. Persamaan Garis Lurus
persamaan garis bergradien m dan melalui titik (x1, y1) adalah :
y – y1= m(x – x1)
persamaan garis yang melalui titik-titik (x1, y1) dan (x2, y2) adalah :
y 2 y1
y – y1 = (x – x1)
x 2 x1
persamaan garis yang melalui titik (b, 0) dan (0, a) adalah :
ax + by = ab
3. Sistem Persamaan Linear dua Peubah
Penyelesaian dari persamaan linear dua peubah dapat dilakukan dengan beberapa cara, diantaranya :
Kombinasi elimenasi dan substitusi
Determinan matriks
4. Pertidaksamaan Linear
Daerah penyelesaian pertidaksamaan linear dua peubah ax + by c atau ax + by c dapat dicari dengan cara :
Gambar garis ax + by = c, sehingga koordinat Cartesius terbagi menjadi dua bagian.
Uji dengan sebuah titik diluar garis untuk memastikan daerah penyelesaian.
Bila titik tersebut memenuhi pertidaksamaan yang diminta, maka disitulah daerah penyelesaian dan bila
tidak, maka sebaliknya.
5. Program Linear
Langkah-langkah menyelesaikan permasalahan dalam program linear
Terjemahkan permasalahan ke dalam bahasa matematika (model matematika)
a. Misalnya peubah dalam x dan y
b. Tentukan fungsi obyektif dan kendala- kendalanya
Menggambar daerah kendala pada bidang Cartesius
Tentukan titik-titik sudut/pojok dari himpunan penyelesain dari kendala
Substitusikan titik–titik pojok tersebut ke fungsi obyektif untuk mendapatkan nilai optimum yang
diinginkan (maksimum atau minimum)
B SOAL DAN PEMBAHASAN
1. Tunjukanlah daerah himpunan penyelesaian dari pertidaksamaan x 0, y 0, x + 2y 4 dan x + 2y 6.
Penyelesaian:
Buat garis x + 2y = 4 y
untuk x = 0 maka 0 + 2y = 4 y = 2, sehingga diperoleh titik (0, 2)
untuk y = 0 maka x + 0 = 4 x = 4, sehingga diperoleh titik (4, 0) 6
Buat garis 2x + y = 6 2
untuk x = 0 maka 0 + y = 6 x = 6, sehingga diperoleh titik (0, 6)
untuk y = 0 maka 2x + 0 = 6 x = 3, sehingga diperoleh titik (3, 0) x
Gambarkan garis yang diperoleh dalam bidang Cartesius 3 4
Untuk garis x + 2y = 4 pilih titik P(0, 0) sebagai titik uji maka x + 2y = 4
2x + y = 6
diperoleh 0 +2(0) = 0 4 (benar), maka titik P terletak pada
daerah himpunan penyelesaian dari x + 2y 4
1
Program Linear Sukses Ujian Nasional Matematika
Untuk garis 2x + y = 6 pilih titik P(0,0) sebagai titik uji dan diperoleh 2(0)+ 0 = 0 6 (benar), maka titik P
terletak pada daerah himpunan penyelesaian dari 2x + y 6
Jadi, daerah himpunan penyelesaiannya merupakan daerah yang diarsir.
2. Ebtanas 1997
Y
Daerah yang diarsir pada gambar berikut merupakan
himpunan penyelesaian sistem pertidaksamaan … 12
a. x 0, 6x + y 12, 5x + 4y 20
b. x 0, 6x + y 12, 5x + 4y 20
c. x 0, 6x + y 12, 4x + 5y 20
d. x 0, x + 6y 12, 4x + 5y 20
e. x 0, x + 6y 12, 5x + 4y 20 5
Jawaban: a
Penyelesaian: O
X
2 4
Pertidaksamaan yang sesuai dengan daerah yang diarsir adalah
batas garis x = 0, karena daerah penyelesaian sebelah kanan maka pertidaksamaannya x 0
batas garis melalui titik (0, 12) dan (2, 0) adalah 12x + 2y = 24 atau 6x + y = 12, karena daerah
penyelesaian sebelah kiri maka pertidaksamaannya 6x + y 12
batas garis melalui titik (0, 5) dan (4, 0) adalah 5x + 4y = 20, karena daerah penyelesaian sebelah kanan
maka pertidaksamaannya 5x + 4y 20
Jadi, sistem pertidaksamaan dari daerah arsiran adalah x 0, 6x + y 12 dan 5x + 4y 20.
3. UAN 2002
Tentukan nilai minimum fungsi objektif x + 3y yang memenuhi pertidaksamaan 3x + 2y 12, x + 2y 8,
x + y 8, x 0 adalah ....
a. 8 b. 9 c. 11 d. 18 e. 24
Jawaban: a
Penyelesaian:
Gambarkan daerah himpunan penyelesaian pada koordinat Cartesius. Y
Himpunan penyelesaian sistem pertidaksamaan
8
3x + 2y 12, x + 2y 8, x + y 8, x 0
ditunjukkan oleh daerah yang diarsir. 6
x +2y = 8 x+y=8
Tentukan titik-titik pojoknya.
3x + 2y = 12 4
x + 2y = 8
= 4
(2, 3)
2x
X
x=2 O 4 8
x = 2 x + 2y = 8
3x +12y =12
2 + 2y = 8
y =3
Koordinat titik potongnya (2, 3)
Jadi, Koordinat titik pojoknya adalah (0, 8), (0, 6), (2, 3), dan (8, 0)
Tentukan nilai fungsi objektifnya.
(x, y) z = x + 3y
(0, 8) 0 + 24 = 24
(0, 6) 0 + 18 = 18
(2, 3) 2 + 9 = 11
(8, 0) 8 + 3(0) = 8
Jadi, nilai minimumnya adalah 8
4. Tempat parkir seluas 600 m2 hanya mampu menampung 58 bus dan mobil. Tiap mobil membutuhkan 6 m2 dan
bus 24 m2. Biaya parkir tiap mobil Rp. 500,- dan bus Rp. 750,-. Pendapatan maksimum dari tempat parkir
tersebut adalah ….
a. Rp. 32.000,00 b. Rp. 32.500,00 c. Rp. 33.500,00 d. Rp. 34.500,00 e. Rp. 35.500,00
Jawaban: b
Penyelesaian:
Misalnya parkir tersebut terdapat x mobil dan y bus, maka diperoleh model :
Fungsi objektif : maksimum z = 500 x + 750 y
Dengan kendala (batasan) : x + y 58 ; 6x + 24y 600 ; x 0 ; y 0
2
Program Linear Sukses Ujian Nasional Matematika
Gambarkan daerah himpunan penyelesaian pada koordinat Cartesius.
y
58
25
x
58 100 6x + 24y = 600
x + y = 58
Tentukan titik-titik pojoknya.
x + y = 58 6 6x + 6y = 348
6x + 24y = 600 1 6x + 24y = 600 –
–18y = –252 y = 14
y = 14 x + 14 = 58 x = 44 (44, 14)
Koordinat titik pojoknya adalah titik-titik (0, 0), (58, 0), (0, 25), dan (44, 14)
Tentukan nilai fungsi objektifnya.
(x, y) z = 500 x + 750 y
(0, 0) 500 (0) + 750 (0) = 0
(58, 0) 500 (58) + 750 (0) = 2.900
(44, 14) 500 (44) + 750 (4) = 32.500
(0, 25) 500 (0) + 750 (25) = 18.750
Jadi, pendapatan maksimum dari parkir tersebut adalah Rp. 32.500,00 dicapai saat 44 mobil dan 14 bus parkir.
C LATIHAN SOAL
1. Daerah yang memenuhi sistem pertidaksamaan
5x + 3y ≤ 15, y ≤ 1, x ≥ 2, dan y 0, berbentuk ….
a. trapesium d. jajar genjang
b. segitiga e. titik
c. belah ketupat
2. Ebtanas 1998 y
Daerah yang diarsir B(3, 6)
pada gambar
merupakan grafik C(0, 4)
himpunan penyelesaian
sistem pertidaksamaan …. x
0 A(7, 0)
a. 3x + 2y 21, –2x + 3y 12, x 0, y 0
b. 2x + 3y 21, –2x – 3y 12, x 0, y 0
c. –3x + 2y 21, –2x + 3y 12, x 0, y 0
d. –3x – 2y 21, 2x + 3y 12, x 0, y 0
e. 3x – 2y 21, 2x – 3y 12, x 0, y 0
Y
3. Ebtanas 2000
Himpunan penyelesaian
sistem pertidaksamaan 10
5x + y ≥ 10, 2x + y ≤ 8,
y ≥ 2 ditunjukkan
I
oleh daerah …. 8
a. I
III
b. II
c. III
d. IV IV II
2
e. V V
X
0 2 4
3
Program Linear Sukses Ujian Nasional Matematika
4. UN 2008
Daerah yang diarsir pada gambar merupakan
himpunan penyelesaian suatu sistem
pertidaksamaan linear. Nilai maksimum dari f(x, y)
= 7x + 6y adalah …. Y
a. 88 20
b. 94 8
c. 102 15
d. 106
e. 196 X
5. UAN 2003 12 18
Nilai maksimum dari bentuk objektif k = 3x + 4y
yang memenuhi sistem pertidaksamaan x 0, y 0,
2x + y ≤ 11, x + 2y ≤ 10, dengan x, y R adalah ....
a. 36 d. 27
b. 32 e. 24
c. 30
6. UAN 2002
Nilai maksimum fungsi obyektif 4x + 2y pada
himpunan penyelesaian sistem pertidaksamaan
x + y 4, x + y ≤ 9, –2x + 3y ≤ 12, 3x – 2y ≤ 12
adalah ….
a. 16 d. 36
b. 24 e. 48
c. 30
7. Dalam himpunan penyelesaian pertidaksamaan
x 1, y 2, x + y ≤ 6, 2x + 3y ≤ 15, nilai minimum
dari 3x + 4y sama dengan ....
a. 9 d. 12
b. 10 e. 13
c. 11
8. Ebtanas 1999
Pedagang teh mempunyai lemari yang hanya cukup
ditempati untuk 40 boks teh. Teh A dibeli dengan
harga Rp6.000,00 setiap boks dan teh B dibeli
dengan harga 8.000,00 setiap boks. Jika pedagang
tersebut mempunyai modal Rp300.000,00 untuk
membeli x boks teh A dan y boks teh B,maka sistem
pertidaksamaan dari masalah tersebut adalah ….
a. 3x + 4y 150, x + y 40, x 0, y 0
b. 3x + 4y 150, x + y 40, x 0, y 0
c. 3x + 4y 150, x + y 40, x 0, y 0
d. 6x + 8y 300, x + y 40, x 0, y 0
e. 8x + 6y 300, x + y 40, x 0, y 0
9. Suatu perusahaan cat menyediakan campuran A dan
B untuk dibuat satu jenis cat. Campuran A
mengandung 400 gr bahan I dan 600 gram bahan II.
Campuran B mengandung 800 gr bahan I dan 200 gr
bahan II. Cat tersebut berkualitas baik bila
mengandung minimal 4 kg bahan I dan 2 kg bahan
II. Jika harga tiap kg campuran A Rp. 20.000,- dan
B Rp. 10.000,- maka berapa banyaknya campuran A
dan B agar biaya yang dikeluarkan minimum ….
a. 4 kg campuran A dan 2 kg B
b. 4 kg campuran A dan 12 kg B
c. 2 kg campuran A dan 4 kg B
d. 2 kg campuran A dan 2 kg B
e. 2 kg campuran A dan 1 kg B
4
Program Linear Sukses Ujian Nasional Matematika
10. UN 2006
Seorang tukang roti mempunyai bahan A, B, dan C
masing-masing sebanyak 160 kg, 110 kg, dan 150
kg. Roti I memerlukan 2 kg bahan A, 1 kg bahan B,
dan 1 kg bahan C. Roti II memerlukan 1 kg bahan
A, 2 kg bahan B, dan 3 kg bahan C. Sebuah roti I
dijual dengan harga Rp 30.000,00 dan sebuah roti II
dijual dengan harga Rp 50.000,00. Pendapatan
maksimum yang dapat diperoleh tukang roti
tersebut adalah ….
a. Rp 8.000.000,00 d. Rp 3.100.000,00
b. Rp 4.500.000,00 e. Rp 2.900.000,00
c. Rp 3.900.000,00
11. UN 2007
Luas daerah parkir 1.760 m2. Luas rata-rata untuk
mobil kecil 4 m2 dan mobil besar 20 m2. Daya
tampung maksimum hanya 200 kendaraan, biaya
parker mobil kecil Rp 1.000,00/jam dan mobil besar
Rp 2.000,00/jam. Jika dalam satu jam terisi penuh
dan tidak ada kendaraan yang pergi dan datang,
maka hasil maksimum tempat parkir itu adalah ….
a. Rp 176.000,00 d. Rp 300.000,00
b. Rp 200.000,00 e. Rp 340.000,00
c. Rp 260.000,00
12. UN 2008
Seorang pembuat kue mempunyai 4 kg gula dan 9
kg tepung. Untuk membuat sebuah kue jenis A
dibutuhkan 20 gram gula dan 60 gram tepung,
sedangkan untuk membuat sebuah kue jenis B
dibutuhkan 20 gram gula dan 40 gram tepung. Jika
kue A dijual dengan harga Rp4.000,00/buah dan
kue B dijual dengan harga Rp3.000,00/buah, maka
pendapatan maksimum yang dapat diperoleh
pembuat kue tersebut adalah ….
a. Rp600.000,00 d. Rp750.000,00
b. Rp650.000,00 e. Rp800.000,00
c. Rp700.000,00
13. UN 2002
Untuk menambah penghasilan seorang ibu setiap
harinya memproduksi dua jenis kue untuk dijual.
Setiap kue jenis I modalnya Rp200,00 dengan
keuntungan 40%, sedangkan setiap kue jenis II
modalnya Rp300,00 dengan keuntungan 30%. Jika
modal yang tersedia setiap harinya adalah
Rp100.000,00 dan paling banyak hanya dapat
memproduksi 400 kue, maka keuntungan terbesar
yang dapat dicapai ibu tersebut dari modalnya
adalah ….
a. 30% d. 36%
b. 32% e. 40 %
c. 34%
5
Program Linear Sukses Ujian Nasional Matematika