Apa itu Program Linear?
Pemrograman Linier disingkat PL merupakan metode matematik dalam mengalokasikan sumber daya yang terbatas untuk mencapai suatu tujuan seperti memaksimumkan keuntungan dan meminimumkan biaya. PL banyak diterapkan dalam masalah ekonomi, industri, militer, sosial dan lain-lain
A. Himpunan penyelesaian Sistem Pertidaksamaan Linear Dua Variable
Pertidaksamaan linear adalah pertidaksamaan yang peubah bebasnya berbentuk linear (pangkat satu). Kalian tentu masih ingat bentuk-bentuk di bawah ini.
1. 2x ≥ 4; pertidaksamaan linear satu peubah
2. 3x + y < 0; pertidaksamaan linear dua peubah
3. x – 2y ≤ 3; pertidaksamaan linear dua peubah
4. x + y – 2z > 0; pertidaksamaan linear tiga peubah
B. Nilai Optimum Fungsi Objektif dari Sistem Pertidaksamaan Linear
1. Nilai Optimum Fungsi Objektif dengan uji Titik Pojok (Titik Ekstrem)
Uji titik pojok (titik ekstrim) merupakan cara yang sering digunakar dalam menentukan nilai optimum fungsi objektif dari sistem pertidaksamaan linear, yaitu dengan mensubstitusikan koordinat titik- titik pojok daerah penyelesaian ke dalam fungsi objektif. Langkah-langkah menentukan nilai optimum fungsi objektif dengan uji titik pojok adalah sebagai berikut.
a. Tentukan daerah penyelesaian dari sistem pertidaksamaan yang dike
b. Tentukan semua titik-titik pojok pada daerah penyelesaian tersebut.
c. Substitusi setiap titik pojok yang diperoleh ke dalam fungsi tahui. objektif yang diketahui.
d. Berdasarkan hasil pada langkah c, tetapkan nilai maksimum atau minimumnya.
Contoh soal Program Linear :
1. 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 parkir 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 pergi dan datang, maka hasil maksimum tempat parkir itu adalah….
A. Rp 176.000,00
B. Rp 200.000,00
C. Rp 260.000,00
D. Rp 300.000,00
E. Rp 340.000,00
Pembahasan
Membuat model matematika dari soal cerita di atas
Misal:
mobil kecil sebagai x, mobil besar sebagai y.
Luas parkir 1760 m2:
4x + 20 y ≤ 1760 disederhanakan menjadi
x + 5y ≤ 440…….(Garis I)
Daya tampung lahan parkir 200 kendaraan:
x + y ≤ 200 …………..(Garis II)
Fungsi objektifnya adalah hasil parkiran:
f(x, y) = 1000 x + 2000 y
Membuat Sketsa Garis 1 dan garis 2
Ubah tanda lebih besar atau lebih kecil menjadi tanda sama dengan terlebih dahulu,
Garis 1
x + 5y = 440
Titik potong sumbu x, y = 0
x + 5(0) = 440
x = 440
Dapat titik (440, 0)
Titik potong sumbu y, x =0
0 + 5y = 440
y = 440/5 = 88
Dapat titik (0, 88)
Garis 2
x + y = 200
Titik potong sumbu x, y = 0
x + 0 = 200
x = 200
Dapat titik (200, 0)
Titik potong sumbu y, x =0
0 + y = 200
y = 200
Dapat titik (0, 200)
Menentukan titik potong garis 1 dan garis 2
Untuk menentukan titik potong bisa dengan substitusi ataupun eliminasi.
x + 5y = 440
x + y = 200
____________ _
4y = 240
y = 60
x + y =200
x + 60 = 200
x = 140
Titik potong kedua garis aalah (140, 60)
Berikut lukisan kedua garis dan titik potongnya, serta daerah yang diarsir adalah himpunan penyelesaian kedua pertidaksamaan di atas.
Uji titik untuk mendapatkan fungsi obektif maksimum:
Masukkan koordinat titik-titik uji / warna merah ke f(x, y) = 1000 x + 2000 y
Titik (0,0) → f(x, y) = 1000 (0) + 200 (0) = 0
Titik (200,0) → f(x, y) = 1000 (200) + 2000 (0) = 200 000
Titik (0, 88) → f(x, y) = 1000 (0) + 2000 (88) = 176 000
Titik (140,60) → f(x, y) = 1000 (140) + 2000 (60) = 260 000
Dari uji titik terlihat hasil parkiran maksimum adalah Rp 260 000
2. Daerah yang diarsir pada gambar ialah himpunan penyelesaian suatu sistem pertidaksamaan linear.
Nilai maksimum dari f (x, y) = 7x + 6y adalah….
A . 88
B. 94
C. 102
D. 106
E. 196
Pembahasan
Cari persamaan kedua garis untuk dapat menentukan titik potongnya:
Cara pertama dalam membuat persamaan garis
y − y1 = m (x − x1)
dengan
m = Δy/Δx
Persamaan garis yang melalui titik (12, 0) dan (0, 20) adalah m = 20/−12 = − 5/3
y − 20 = − 5/3 (x − 0)
y − 20 = − 5/3 x
y + 5/3 x = 20
3y + 5x = 60
Persamaan garis yang melalui titik (18, 0) dan (0, 15) :
m = 15/−18 = − 5/6
y − 15 = − 5/6 (x − 0)
y + 5/6 x = 15
6y + 5x = 90
Cara kedua dalam membuat persamaan garis
bx + ay = ab
Untuk garis yang memotong sumbu x di 12 dan y di 20 adalah:
20x + 12 y = 240 sederhanakan lagi
5x + 3y = 60
Untuk garis yang memotong sumbu x di 18 dan y di 15 adalah:
15x + 18y = 270 sederhanakan lagi
5x + 6y = 90
Titik potong kedua garis:
6y + 5x = 90
3y + 5x = 60
_________ –
3y = 30
y = 10
3(10) + 5x = 60
5x = 30
x = 6
Titik potong kedua garis adalah (6, 10)
Uji titik: f (x, y) = 7x + 6y
Titik (0, 0) → f (x, y) = 7(0) + 6(0) = 0
Titik (12,0) → f (x, y) = 7(12) + 6(0) = 84
Titik (0, 15) → f (x, y) = 7(0) + 6(15) = 90
Titik (6, 10) → f (x, y) = 7(6) + 6(10) = 102
Nilai maksimum tercapai saat x = 6 dan y = 10 yaitu 102
3. Suatu perusahaan meubel memerlukan 18 unsur A dan 24 unsur B per hari. Untuk membuat barang jenis I dibutuhkan 1 unsur A dan 2 unsur B, sedangkan untuk membuat barang jenis II dibutuhkan 3 unsur A dan 2 unsur B. Jika barang jenis I dijual seharga Rp 250.000,00 per unit dan barang jenis II dijual seharga Rp 400.000,00 per unit, maka agar penjualannya mencapai maksimum, berapa banyak masing-masing barang harus dibuat?
A. 6 jenis I
B. 12 jenis II
C. 6 jenis I dan 6 jenis II
D. 3 jenis I dan 9 jenis II
E. 9 jenis I dan 3 jenis II
Pembahasan
Barang I akan dibuat sebanyak x unit
Barang II akan dibuat sebanyak y unit
Ilustrasi berikut untuk memudahkan pembuatan model matematikanya:
x + 3y ≤ 18
2x + 2y ≤ 24
Fungsi objektifnya:
f(x, y) = 250000 x + 400000 y
Titik potong
x + 3y = 18 |x2|
2x + 2y = 24 |x 1|
2x + 6y = 36
2x + 2y = 24
____________ _
4y = 12
y = 3
2x + 6(3) = 36
2x = 18
x = 9
Titik potong kedua garis (9, 3)
Berikut grafik selengkapnya:
Uji Titik ke f(x, y) = 250000 x + 400000 y
Titik (0,0) f(x, y) = 250000 (0) + 400000 (0) = 0
Titik (12, 0) f(x, y) = 250000 (12) + 400000 (0) = 3000 000
Titik (9, 3) f(x, y) = 250000 (9) + 400000 (3) = 3450 000
Titik (0, 6) f(x, y) = 250000 (0) + 400000 (6) = 2400 000
Dari uji titik terlihat hasil maksimum jika x = 9 dan y = 3 atau dibuat 9 barang jenis I dan 3 barang jenis II.
4. Seorang pedagang sepeda ingin membeli 25 sepeda untuk persediaan. Ia ingin membeli sepeda gunung dengan harga Rp1.500.000,00 per buah dan sepeda balap dengan harga Rp2.000.000,00 per buah. Ia merencanakan tidak akan mengeluarkan uang lebih dari Rp42.000.000,00. Jika keuntungan sebuah sepeda gunung Rp500.000,00 dan sebuah sepeda balap Rp600.000,00, maka keuntungan maksimum yang diterima pedagang adalah…
A. Rp13.400.000,00
B. Rp12.600.000,00
C. Rp12.500.000,00
D. Rp10.400.000,00
E. Rp8.400.000,00
Pembahasan
Banyak sepeda maksimal 25
Uang yang tersedia 42 juta
Titik potong (i) dan (ii)
Keuntungan
Jawaban: A
5. Seorang pedagang gorengan menjual pisang goreng dan bakwan. Harga pembelian untuk satu pisang goreng Rp1.000,00 dan satu bakwan Rp400,00. Modalnya hanya Rp250.000,00 dan muatan gerobak tidak melebihi 400 biji. Jika pisang goreng dijual Rp1.300,00/biji dan bakwan Rp600,00/biji, keuntungan maksimum yang diperoleh pedagang adalah…
A. Rp102.000,00
B. Rp96.000,00
C. Rp95.000,00
D. Rp92.000,00
E. Rp86.000,00
Pembahasan
Gorengan jadi x, bakwan jadi y
Modelnya:
1000x + 400y ≤ 250000, sederhanakan, bagi 100 dapat persamaan (i)
(i) 10x + 4y ≤ 2500
(ii) x + y ≤ 400
f(x,y) = 300x + 200y
Titik potong garis (i) dan (ii) dengan sumbu x dan y masing-masing:
Grafik selengkapnya:
Uji titik A, B, C
6. Nilai minimum dari f(x,y) = 4x + 5y yang memenuhi pertidaksamaan 2x + y ≥ 7, x + y ≥ 5, x ≥ 0, dan y ≥ 0 adalah…
A. 14
B. 20
C. 23
D. 25
E. 35
Pembahasan
Langsung cari titik potongnya dulu:
2x + y = 7
x + y = 5
———— −
x = 2
y = 3
Dapat titik A (2, 3)
Berikut grafik selengkapnya:
Uji titik
f(x, y) = 4x + 5y
A(2, 3) = 4(2) + 5(3) = 23
B(5, 0) = 4(5) + 5(0) = 20
C(0, 7) = 4(0) + 5(7) = 35
Terlihat nilai minimumnya adalah 20.
7.Seorang pedagang kue akan membuat dua jenis kue. Setiap kue A menggunakan modal Rp2.000,00 dan dijual mempunyai keuntungan Rp1.000,00 per buah, sedang untuk kue B menggunakan modal Rp3.000,00 dan dijual memperoleh keuntungan Rp1.500,00 per buah. Modal yang tersedia adalah Rp1.200.000,00 dan paling banyak hanya dapat membuat 500 kue setiap hari. Jika kue tersebut terjual habis, keuntungan maksimum yang diperoleh pedagang kue tersebut adalah ….
A. Rp500.000,00
B. Rp600.000,00
C. Rp650.000,00
D. Rp700.000,00
E. Rp750.000,00
Pembahasan
Tabel bantuan untuk soal di atas:
Kue A (x) Kue B (y) 500
Modal 2.000
2 3.000
3 1.200.000
1.200
Keuntungan 1.000 1.500 ?
Model matematika yang dapat diperoleh dari tabel bantuan tersebut adalah:
x + y = 500 … (1)
2x + 3y = 1.200 … (2)
z = 1.000x + 1.500y
Mari kita eliminasi persamaan (2) dan (1). Persamaan (1) kita kalikan dengan 2 agar mempunyai koefisien x yang sama dengan persamaan (2).
2x + 3y = 1.200
2x + 2y = 1.000
——————— −
y = 200
Selanjutnya kita substitusikan y = 200 ke persamaan (1).
x + y = 500
x + 200 = 500
x = 500 − 200
= 300
Dengan demikian nilai z adalah:
z = 1.000x + 1.500y
= 1.000 × 300 + 1.500 × 200
= 300.000 + 300.000
= 600.000
Jadi, keuntungan maksimum yang diperoleh pedagang kue tersebut adalah Rp600.000,00 (B).
8.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 parkir mobil kecil Rp1.000,00/jam dan mobil besar Rp2.000,00/jam. Jika dalam satu jam terisi penuh dan tidak ada kendaraan yang pergi dan datang, penghasilan maksimum tempat parkir adalah ….
A. Rp176.000,00
B. Rp200.000,00
C. Rp260.000,00
D. Rp300.000,00
E. Rp340.000,00
Pembahasan
Tabel bantuan untuk soal di atas:
Mobil Kecil (x) Mobil Besar (y) 200
Luas Parkir 4
1 20
5 1.760
440
Biaya Parkir 1.000 2.000 ?
Model matematika berdasarkan tabel bantuan tersebut adalah:
x + y = 200 … (1)
x + 5y = 440 … (2)
z = 1.000x + 2.000y
Eliminasi persamaan (2) dan (1) diperoleh:
x + 5y = 440
x + y = 200
—————— −
4y = 240
y = 60
Kemudian kita substitusikan y = 60 ke persamaan (1).
x + y = 200
x + 60 = 200
x = 140
Dengan demikian nilai z adalah:
z = 1.000x + 2.000y
= 1.000 × 140 + 2.000 × 60
= 140.000 + 120.000
= 260.000
Jadi, penghasilan maksimum tempat parkir tersebut adalah Rp260.000,00 (C)
9.Luas daerah parkir 360 m^{2}. Luas rata-rata sebuah mobil 6 \; m^{2} dan luas rata-rata bus 24 \; m^{2}. Daerah parkir tersebut dapat memuat paling banyak 30 kendaraan roda empat (mobil dan bus). Jika tarif parkir mobil Rp2000,00 dan tarif parkir bus Rp5000,00 maka pendapatan terbesar yang dapat diperoleh adalah …. (Soal Ujian Nasional)
A. Rp40.000,00
B. Rp50.000,00
C. Rp60.000,00
D. Rp75.000,00
E. Rp90.000,00
Pembahasan:
Misalkan:
x = banyak mobil
y = banyak bus
Perhatikan tabel di bawah!
Pemodelan Matematika pada Program Linear
Diperoleh dua persamaan:
\[ x + y \leq 30 \]
\[ 6x + 24y \leq 360 \rightarrow x + 4y \leq 60 \]
Menentukan daerah yang memenuhi pertidaksamaan:
Contoh Soal Ujian Nasional Program Linear
Akan ditentukan nilai maksimum dengan metode titik sudut.
Titik koordinat O, A, dan C dapat diperoleh dengan melihat gambar, yaitu O(0,0), A(0, 15), dan C(30,0). Untuk koordinat B dapat diperoleh dengan menggunakan eliminasi dan substitusi.
Metode eliminasi
Substitusi nilai y = 10 pada persamaan x + y = 30 untuk mendapatkan nilai x.
\[ x + y = 30 \]
\[ x + 10 = 30 \]
\[ x = 30 – 10 = 20 \]
Koordinat titik B adalah (20, 10)
Perhitungan keuntungan maksimal yang dapat diperoleh:
Fungsi Objektif Pembahasan Soal Ujian Nasional Program Linear SMA
Jawaban: E
10. Biaya produksi satu buah payung jenis A adalah Rp20.000,00 per buah, sedangkan biaya satu buah produksi payung jenis B adalah Rp30.000,00. Seorang pengusaha akan membuat payung A dengan jumlah tidak kurang dari 40 buah. Sedangkan banyaknya payung jenis B yang akan diproduksi minimal adalah dari 50 buah. Jumlah maksimal produksi kedua payung tersebut adalah 100 buah. Biaya minimum yang dikeluarkan untuk melakukan produksi kedua payung sesuai ketentuan tersebut adalah ….
A. Rp2.000.000,00
B. Rp2.300.000,00
C. Rp2.200.000,00
D. Rp2.100.000,00
E. Rp2.000.000,00
Pembahasan:
Pemisalan:
x = banyak payung A
y = banyak payung B
Model matematika dari permasalahan tersebut adalah:
Fungsi tujuan: meminimumkan
\[ f(x,y) = 20.000x + 30.000y \]
Fungsi kendala:
\[ x \geq 40 \]
\[ y \geq 50 \]
\[ x + y \leq 100 \]
Daerah penyelesaian yang memenuhi permasalahan:
Daerah Penyelesaian Metode Garis Selidik
Nilai minimim akan diperoleh melalui titik koordinat yang dilalui garis selidik yang pertama kali, yaitu titik A(40, 50). Sehingga, biaya produksi minimum adalah
\[ f(40,50) = 20.000(40) + 30.000(50) \]
\[ f(40,50) = 800.000 + 1.500.000 \]
\[ f(40,50) = 2.300.000 \]
Jawaban: B
Ghifari.vld 