Pengertian Program Linear

Program Linear adalah suatu metode penentuan nilai optimum dari suatu permasalahan linear. Nilai maksimal atau minimum diperoleh dari nilai dalam suatu himpunan penyelesaian permasalahan linear. Di dalam permasalahan linear terdapat fungsi linear yang biasa kita sebut sebagai fungsi objektif. Syarat, aturan, kendala, atau batasan dalam permasalahan linear merupakan sistem pertidaksamaan linear.

Model Matematika Program Linear

Permasalahan yang ada di dalam program linear masih menggunakan kalimat-kalimat yang menggunakan bahasa secara umum, namun kemudian diubahnya menjadi kalimat matematika. Yaitu kalimat yang menggunakan peubah dan notasi matematika.

Sebagai contohnya seperti ini : “Suatu toko tas membuat dua model tas memakai dua bahan yang berbeda. Untuk model pertama terdiri dari 200 gr bahan pertama dan 150 gr bahan kedua. Sedangkan untuk model tas yang kedua terdiri dari 180 gr bahan pertama dan 170 gr bahan kedua. Persediaan di gudang untuk bahan pertama adalah 72 kg dan persediaan di gudang untuk bahan kedua adalah 64 gr. Dan harga tas model pertama ialah Rp. 500.000 dan harga tas model kedua harganya Rp. 400.000.”

Dari contoh tersebut apabila disederhanakan dalam bentuk tabel adalah sebagai berikut :

Jenis TasBahan 1Bahan 2Harga TasJumlah Tas
Model 1200 gr150 grRp. 500.000x
Model 2180 gr170 grRp. 400.000y
Ketersediaan72000 gr64000 gr

Peubah dari jumlah model 1 adalah  dan peubah untuk model 2 adalah , serta hasil penjualan optimal adalah  dengan beberapa syarat. Pertama, Apabila jumlah maksimal bahan 1 yaitu 72.000 gr, maka Kedua, Apabila jumlah maksimal bahan 2 yaitu 64.000 gr, maka Ketiga, Masing-masing model harus terbuat.

Model matematika untuk memperoleh jumlah maksimum adalah Maksimum  dengan syarat :  dan  dimana .

Nilai-nilai dari variabel  disebut sebagai himpunan penyelesaian pada masalah program linear, jika nilai  memenuhi.

Konsep program linear didasari oleh konsep persamaan dan pertidaksamaan bilangan real, oleh karena itu sifat-sifat yang ada pada persamaan dan pertidaksamaan bilangan real dipakai sebagai acuan untuk menyelesaikan suatu masalah program linear.

Model matematika merupakan cara untuk menyelesaikan masalah kontekstual. Dua atau lebih pertidaksamaan linear dua variabel menjadi kendala program linear jika variabel-variabelnya saling terhubung dan variabel yang sama punya nilai sama sebagai penyelesaian. Jadi sistem pertidaksamaan ini disebut sebagai kendala.

Pertidaksamaan Linear Dua Variabel

Pertidaksamaan linear adalah suatu pertidaksamaan dengan kombinasi operasi antar variabel yang ditandai dengan adanya simbol atau tanda  Dan untuk kumpulan dari beberapa pertidaksamaan linear disebut sebagai sistem pertidaksamaan linear, yang mana pertidaksamaan linear ini diajarkan di tingkat SMA yang pada umumnya akan melibatkan dua variabel.

Pertidaksamaan linear dua variabel adalah pertidaksamaan yang berbentuk  atau  atau  atau .

Di mana  adalah koefisien  adalah konstanta , dan  adalah variabel .

Pada umumnya pertidaksamaan linear dua variabel mempunyai himpunan penyelesaian tak hingga banyaknya.

Contoh Permasalahan : “Susi memiliki uang Rp. 250.000 dan digunakan untuk berbelanja di toko peralatan sekolah. Susi memperkirakan apa saja yang akan dibeli dengan uang yang ia punyai tersebut. Di setiap barang dalam toko tersebut telah disertakan harga barang. Jika susi membeli 2 seragam sekolah dan 3 kaos kaki maka dia akan mendapatkan uang kembalian. Modelkan harga belanjaan Susi tersebut!”

Penyelesaian : kita misalkan harga seragam =  dan kaos kaki =  . Susi membeli 2 seragam sekolah dan 3 kaos kaki dan memperoleh uang kembalian, maka dapat dimodelkan menjadi . Untuk menentukan himpunan penyelesaian tersebut kita pilih  yang memenuhi.

Tabel semua kemungkinan nilai  yang memenuhi 

 (Rp) (Rp) (Rp)Uang Kembalian (Rp)
20.0005.00055.000195.000
30.0006.00078.000172.000
40.00010.000110.000140.000
50.00020.000160.00090.000
….….….….

Tabel tersebut masih bisa dilanjut sampai tak hingga banyaknya nilai  yang memenuhi . Dengan demikian kita dapat mengilustrasikan sebagai berikut.

Keterangan :

Daerah yang tidak diarsir adalah daerah yang memenuhi pertidaksamaan tersebut. Garis putus-putus berarti, tanda pertidaksamaan  bukan . Dan untuk pertidaksamaan yang menggunakan . Grafik garisnya berupa garis lurus tidak putus.         
Dari grafik tersebut, kita dapat menemukan tak hingga banyaknya pasangan  yang memenuhi pertidaksamaan tersebut.

Cara Menyelesaikan Masalah Program Linear

Cara menyelesaikan masalah dari program linear kita dapat menyebutnya sebagai proses mencari nilai maksimum dan minimum dari suatu pertidaksamaaan. Wujudnya tergantung dengan soal yang diberikan.

Untuk bentuk umum dari suatu fungsi objektif pada model matematika adalah . Metode yang kita dapat gunakan untuk menentukan nilai maksimum dan minimum ini adalah metode uji titik pojok.

Metode Uji Titik Pojok

Cara menggunakan metode ini yaitu dengan menghitung nilai fungsi tujuan dari titik pojok yang diperoleh. Titik pojok yang dimaksud adalah titik-titik pada koordinat yang membatasi daerah yang sesuai dari sebuah sistem pertidaksamaan linear. Beberapa tahapan yang dilakukan untuk menentukan nilai maksimum dan minimum dengan menggunakan metode uji titik pojok.

Pertama, carilah garis-garis dari sistem pertidaksamaan yang menjadi fungsi kendala dari permasalahan. Kedua, cari beberapa titik pojok yang merupakan koordinat pembatas daerah yang memenuhi fungsi kendala. Ketiga, hitunglah nilai maksimum atau minimum dari titik-titik pojok yang diperoleh. Keempat, mendapatkan nilai maksimum atau minimum sesuai dengan permasalahan.

Contoh Soal : “Suatu adonan roti basah dibuat dengan menggunakan bahan 2 kg tepung dan 1 kg gula. Sementara 1 adonan roti kering dibuat dengan memakai 2 kg tepung dan 3 kg gula. Ani mempunyai persediaan tepung sebanyak 6 kg dan gula sebanyak 5 kg. Jika pada adonan 1 kue basah bisa memberikan keuntungan Rp. 75.000 dan satu adonan kue kering bisa memberikan untung Rp. 60.000. maka berapa banyak kombinasi adonan roti yang bisa dibuat untuk mendapatkan keuntungan maksimal?”

Penyelesaian :

Misal 

Model matematika : 

Gambar daerah yang memenuhi sistem pertidaksamaan.

Jika, 1 adonan roti basah keuntung Rp. 75.000 dan 1 adonan kue kering Rp. 60.000. maka fungsi tujuannya yaitu memaksimalkan .

Titik koordinat O, A dan juga C kita dapatkan dengan melihat gambar yaitu O(0,0), A(0,5),dan C(3,0) dan untuk koordinat dari titik B kita bisa menemukan dengan menggunakan metode eliminasi.

Dari eliminasi persamaan tersebut telah kita dapatkan bahwa koordinat B (1,4). Untuk itu sekarang kita mencari nilai maksimum.

Titik O(0,0) maka keuntungan 

Titik A(0,5) maka keuntungan 

Titik B(1,4) maka keuntungan 

Titik C(3,0) maka keuntungan 

Sehingga nilai keuntungan maksimum yang bisa didapatkan yaitu Rp. 315.000 dengan membuat 1 adonan roti basah dan 4 adonan roti kering.