Program linear atau biasa disebut juga sebagai optimasi linear merupakan suatu program yang bisa dipakai untuk memecahkan masalah mengenai optimasi. Di dalam masalah optimasi linear, batasan-batasan atau kendala-kendalanya bisa kita terjemahkan ke dalam bentuk sistem pertidaksamaan linear. Nilai-nilai peubah yang memenuhi suatu system pertidaksamaan linear berada pada suatu himpunan penyelesaian yang mempunyai beragam kemungkinan penyelesaian. Dari beragami kemungkinan penyelesaian tersebut terdapat sebuah penyelesaian yang memberikan hasil paling baik (penyelesaian optimum). Jadi dapat disimpulkan bahwa tujuan dari masalah optimasi linear adalah untuk mengoptimumkan (memaksimalkan atau meminimumkan) sebuah fungsi f. Fungsi f ini disebut dengan fungsi sasaran, fungsi tujuan, atau fungsi objektif.

Masalah optimasi linear seperti yang telah dijelaskan di atas banyak dijumpai dalam bidang produksi barang, distribusi barang, dalam bidang ekonomi, dan bidang-bidang lainnya yang termasuk ke dalam kajian riset operasional.

Pengertian Model MatematikaSudah dijelaskan di atas bahwa dalam memecahkan masalah program linear kita harus bisa menerjemahkan terlebih dahulu mengenai kendala-kendala yang terdapat di dalam masalah program linear ke dalam bentuk perumusan matematika. Proses tersebut adalah yang dinamakan dengan model matematika. Model matematika dapat didefinisikan sebagai suatu rumusan matematika yang diperoleh dari hasil penafsiran seseorang ketika menerjemahkan suatu masalah program linear ke dalam Bahasa matematika. Suatu model matematika dikatakan baik apabila di dalam model tersebut hanya memuat bagian-bagian yang diperlukan saja.

Untuk memahaminya dengan lebih mudah, perhatikan beberapa contoh pembuatan model matematika di bawah ini:

Contoh Soal Model Matematika dan Pembahasannya

Contoh 1 :Mas Bejo membeli 6 buku tulis dan 8 pensil di suatu toko buku. Untuk itu Mas Bejo harus membayar Rp.6.900. Sedangkan Bang Jarwo hanya membeli 1 buah buku tulis dan 1 buah pensil dengan harga Rp.1.050. apabila harga dari sebuah buku rupiah dan sebuah pensil dinyatakan dengan x dan y, buatlah model matematika dari permasalahan tersebut!

Jawab:Berdasarkan jumlah uang yang dibayar oleh Mas Bejo, didapat hubungan:6x + 8y = 6.900Berdasarkan jumlah uang yang dibayar oleh Bang Jarwo, didapat hubungan:x+ y = 1.050Maka model matematikanya adalah: 6x + 8y = 6.900 dan   x +   y = 1.050 dengan x dan y ε C

Contoh 2:Seorang siswa memilih jurusan IPA, jika memenuhi syarat-syarat sebagai berikut:

a.) Jumlah nilai Matematika dan Fisika tidak boleh kurang dari 12b.) Nilai masing-masing pada pelajaran tersebut tidak boleh kurang dari 5

Buatlah model matematika yang bisa digunakan sebagai patokan agar seorang siswa bisa memilih jurusan IPA!

Jawab:Kita misalkan nilai matematika = x dan nilai fisika = y , maka dari syarat a.) diperoleh hubungan:x + y ≥ 12Dan dari syarat b.) diperoleh hubungan:x ≥ 5 dan y ≥ 5maka, model matematika yang dapat digunakan untuk patokan agar seorang siswa bisa memilih jurusan IPA adalah:x ≥ 5 dan y ≥ 5, dan  x + y ≥ 12 ε C

Contoh 3:Sebuah lahan parker hanya dapat menampung 200 mobil sedan. Apabila tempat tersebut digunakan untuk memarkir Bis, maka 1 Bis akan menempati luas yang sama dengan 5 buah mobil sedan. Apabila di lahan tersebut diparkir x Bis dan y Sedan, tentukanlah model matematikanya!

Jawab:Misalkan untuk memarkir sebuah mobil sedan diperlukan luas rata-rata L m2, maka luas lahan parker yang tersedia adalah 200L m2 (L > 0).

Untuk memarkir sebuah Bis diperlukan lahan seluas 5L m2 , Sehingga untuk memarkir x Bis dan y Sedan diperoleh hubungan:

(5L)x + (L)y ≤ 2005x + y ≤ 200

Karena banyajnya mobil Bis dan Sedan tidak mungkin negatif, sehingga:x ≥ 0 dan y ≥ 0sehingga model matematika untuk persoalan di atas adalah:x ≥ 0 , y ≥ 0 dan 5x + y ≤ 200, dengan x dan y

Latihan soal:1. Sebuah pabrik memproduksi dua jenis barang K dan L dengan menggunakan dua buah mesin yaitu G1 dan

G2. Untuk memproduksi barang K, mesin G1 harus beroperasi selama 3 menit dan mesin G2 selama 6 menit. Sedangkan untuk memproduksi barang L, mesin G1 harus beroperasi selama 9 menit dan mesin G2 beroperasi selama 6 menit. Mesin G1 dan G2 hanya bisa beroperasi tidak lebih dari 9 jam dalam sehari. Keuntungan bersih yang didapat untuk tiap barang K adalah Rp.350 dan untuk tiap barang L adalah Rp.700. Cobalah untuk membuat model matematika dari masalah program linear tersebut, apabila diharapkan keuntungan bersih yang sebesar-besarnya.

2. Sebuah pabrik farmasi menyediakan dua jenis campuran L dan M. bahan-bahan dasar yang terkandung dalam setiap Kilogram campuran L dan M dapat dilihat pada tabel berikut ini:

Bahan 1 Bahan 2Campuran L 0,4 Kg 0,6 KgCampuran M 0,8 Kg 0,2 Kg

3.Dari campuran L dan M tersebut akan dibuat campuran N. Campuran N tersebut sekurang-kurangnya mengandung bahan 1 sebanyak 4 Kg dan bahan 2 sebanyak 3Kg. Harga setiap Kilogram campuran L adalah Rp. 30.000 dan setiap campuran M adalah Rp. 15.000. Tentukanlah model matematika dari persamaan di atas jika biaya total untuk membuat campuran N diharapkan bisa semurah-murahnya.