Program Linear

Program linear merupakan salah satu bagian dari matematika terapan yang dapat digunakan dalam memecahkan berbagai macam persoalan yang timbul dalam kehidupan sehari-hari. Sebelum Anda belajar lebih jauh mengenai program linear, terlebih dahulu Anda akan diperkenalkan pada model matematika berikut.

1. Model Matematika

Permasalahan yang Anda hadapi dalam kehidupan sehari-hari adalah masalah nyata, bukan masalah yang langsung berbentuk angka ataupun hitungan-hitungan matematika. Masalah nyata yang akan Anda selesaikan ataupun dicari solusinya, dapat Anda temukan dalam berbagai bidang. Misalnya, dalam menjalani proses produksi pada suatu perusahaan, pastilah tersedia bahan baku, tenaga kerja, mesin, dan sarana produksi lainnya. Seorang pengusaha harus memperhitungkan semua faktor yang ada supaya perusahaannya dapat meminimumkan biaya produksi dan memaksimumkan keuntungan yang diperoleh. Program linear dapat digunakan untuk menyelesaikan masalahmasalah tersebut. Akan tetapi, masalah-masalah tersebut terlebih dahulu harus diterjemahkan ke dalam bahasa matematika sampai ke tingkat yang paling sederhana. Proses menterjemahkan masalah nyata ke dalam bahasa matematika dinamakan pemodelan matematika. Bagan proses pemodelan matematika dapat digambarkan sebagai berikut :

Supaya memahami proses pemodelan matematika tersebut, pelajarilah uraian berikut.

Misalkan seorang agen sepeda ingin membeli paling banyak 25 buah sepeda untuk persediaan. Ia ingin membeli sepeda model biasa dengan harga Rp1.200.000,00/buah dan sepeda model sport dengan harga Rp1.600.000,00/buah. Ia mempunyai modal Rp33.600.000,00. Ia berharap memperoleh untung Rp200.000,00 untuk setiap sepeda biasa dan Rp240.000,00 untuk setiap sepeda sport. Jika Anda diminta untuk memodelkan masalah ini, dengan harapan agen sepeda tersebut mendapatkan keuntungan maksimum, dapatkah Anda membantunya? Untuk memodelkan permasalahan tersebut, langkah pertama dimulai dengan melakukan pemisalan. Pada permasalahan tersebut, ada 2 model sepeda yang ingin dibeli oleh agen, yaitu sepeda biasa dan sepeda sport. Misalkan banyaknya sepeda biasa yang dibeli adalah x buah dan banyaknya

sepeda sport yang dibeli adalah y buah. Oleh karena keuntungan yang diharapkan dari sepeda biasa dan sport berturut-turut adalah Rp200.000,00 dan Rp240.000,00 maka keuntungan yang mungkin diperoleh agen tersebut ditentukan oleh z = f(x, y) = 200.000x + 240.000y Fungsi z = f(x, y) tersebut dinamakan sebagai fungsi objektif (fungsi tujuan). Dari permasalahan yang ada, diinginkan untuk memaksimumkan keuntungan yang didasarkan pada kondisi-kondisi yang ada (kendala).

Setiap kendala yang ada, bentuknya berupa pertidaksamaan. Fungsi kendala dari permasalahan agen sepeda tersebut ditentukan sebagai berikut:

• Banyaknya sepeda yang akan dibeli oleh agen tersebut x + y ≤ 25

• Besarnya modal yang dimiliki agen sepeda 1.200.000x + 1.600.000y ≤ 33.600.000 15x + 20y ≤ 42 

• Banyaknya sepeda yang dibeli tentu tidak mungkin negatif sehingga nilai x ≥ 0 dan y ≥ 0.

Dengan demikian, terbentuklah model matematika berikut.

z = f(x, y) = 200.00x + 240.000y

Tujuannya memaksimumkan fungsi tujuan yang didasarkan pada kondisi

x + y ≤ 25

15x + 20y ≤ 42

x ≥ 0

y ≥ 0

Model matematika dari setiap permasalahan program linear secara umum terdiri atas 2 komponen, yaitu:

1. Fungsi tujuan z = f(x, y) = ax + by dan

2. Fungsi kendala (berupa pertidaksamaan linear)