Program Linier

Program linear adalah suatu metode untuk mencari nilai maksimum atau nilai minimum dari bentuk linear pada daerah yang dibatasi grafik -grafik fungsi linear.

Himpunan penyelesaian dari sistem pertidaksamaan linear dua peubah merupakan suatu himpunan titik-titik (pasangan berurut (x,y)) dalam bidang cartesius yang memenuhi semua pertidaksamaan linear dalam sistem tersebut. 

Sehingga daerah himpunan penyelesaiannya merupakan irisan himpunan-himpunan penyelesaian dari pertidaksamaan dalam sistem pertidaksamaan linear dua peubah itu. Untuk  lebih mudah dalam memahami daerah penyelesaian dari sistem pertidak-samaan linear dua peubah, perhatikan contoh berikut.

Contoh:

Tentukan daerah  penyelesaian dari sistem pertidaksamaan linear berikut!
3x + 5y ≤  15
x ≥  0
y ≥  0

Penyelesaian:

Gambar garis 3x + 5y =15, x = 0, dan y =0
Untuk 3x + 5y ≤  15
Pilih titik (0,0), kemudian substitusikan ke pertidaksamaan sehingga diperoleh:
3 × 0 + 5× 0 ≤ 15
0 ≤  15 (benar), artinya dipenuhi
Sehingga daerah penyelesaiannya adalah daerah yang memuat titik (0,0)
Untuk x ≥ 0, pilih titik (1,1) kemudian disubstitusikan ke pertidaksamaan sehingga diperoleh:
1 ≥ 0 (benar), artinya dipenuhi.
Sehingga daerah penyelesaiannya adalah daerah yang memuat titik (1,1)
Untuk y ≥ 0, pilih titik (1,1) kemudian substitusikan ke pertidaksamaan sehingga diperoleh:
1 ≥  0 (benar), artinya dipenuhi.
Sehingga himpunan penyelesaiannya adalah daerah yang memuat titik (1,1).
Selanjutnya arsir daerah yang memenuhi persamaan, seperti gambar dibawah ini.

Daerah  penyelesaian sistem pertidaksamaan merupakan irisan dari ketiga himpunan penyelesaian pertidaksamaan di atas, yaitu seperti terlihat pada gambar berikut ini (daerah yang diarsir).

Pertidaksamaan Linear juga dapat digunakan untuk memecahkan masalah dalam kehidupan sehari-hari. Hal ini dapat dilakukan dengan memodelkan masalah menjadi model matematika. Jadi, Model matematika merupakan suatu cara sederhana untuk menerjemahkan suatu masalah ke dalam bahasa matematika dengan menggunakan persamaan, pertidaksamaan, atau fungsi.

Perhatikan contoh berikut :

Pak Adi merupakan seorang pedagang roti. Beliau menjual roti menggunakan gerobak yang dapat memuat 600 bungkus roti. Roti yang dijualnya yaitu roti manis dan roti tawar dengan harga masing-masing  Rp 5.500,00 untuk roti manis dan Rp 4.500,00 untuk roti tawar per bungkusnya. Dari penjualan roti tersebut, beliau memperoleh keuntungan Rp 500,00 dari sebungkus roti manis dan Rp 600,00 dari sebungkus roti tawar. Apabila modal yang dimiliki oleh Pak Budi adalah Rp 600.000, buatlah model matematika agar beliau dapat memperoleh keuntungan sebesar-besarnya!

Penyelesaian :

Permasalahan Pak Adi diatas  dapat dimodelkan dalam bentuk matematika dengan menggunakan sistem pertidaksamaan linear dua variabel. Dengan memisalkan banyaknya roti manis sebgai x dan roti tawar sebagai y sehingga diperoleh tabel sebagai berikut.

Berdasarkan tabel diatas jika kita tuliskan dalam bentuk pertidaksamaan linear menjadi

x + y ≤ 600,
5.500x + 4.500y ≤ 600.000,
Untuk x, y anggota bilangan cacah, x ≥ 0, y ≥ 0

Dua pertidaksamaan terakhir (baris ketiga) menunjukkan syarat dari nilai x dan y. Dikarena x dan y merupakan pernyataan yang menyatakan banyaknya roti, maka tidak mungkin nilai x dan y bernilai negatif.

Perhatikan kolom keempat dari tabel di atas yang menyatakan fungsi yang akan ditentukan nilai maksimumnya (nilai optimum). Fungsi tersebut dapat dituliskan dalam persamaan matematika sebagai berikut.

f(x,y) = 500x + 600y

untuk menyelesaikan sistem pertidaksamaan diatas kita dapat mengikuti langkah berikut :
1. Ubah masalah tersebut ke dalam model matematika yaitu dengan membuat tabel, fungsi pembatas dan fungsi tujuan. Tabel di sini untuk mempermudah membaca data. Fungsi pembatas/kendala yaitu beberapa pertidaksamaan linier yang berhubungan dengan permasalahan tersebut. Fungsi tujuan/objektif yaitu suatu fungsi yang berhubungan dengan tujuan yang akan dicapai. Biasanya fungsi tujuan dinyatakan dengan f(x,y) = ax + by atau z = ax + by
2. Lukislah daerah penyelesaian dari fungsi pembatasnya
3. Tentukan koordinat-koordinat titik ujung daerah penyelesaian. Jika belum ada gunakan bantuan eliminasi dari perpotongan 2 garis
4. Ujilah masing-masing titik ujung daerah penyelesaian
5. Tentukan nilai terbesar/terkecilnya sesuai dengan tujuan yang akan dicapai
dimana langkah no 1 telah kita dapatkan karena disini rumus matematika menunjukan bagaimana cara membuat model matematika. Selanjutnya ikuti langkah berikutnya agar kita memperoleh daerah penyelesaiannya.

contoh 2 : 

Luas daerah parkir 1.760 m². Luas rata-rata untuk mobil kecil 4 m² dan mobil besar 20 m². 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....

penyelesaian :
 Membuat model matematika dari soal cerita di atas
Misal:
mobil kecil sebagai x, mobil besar sebagai y.
Luas parkir 1760 m²:
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