Program Linear

Program linear merupakan salah satu bidang matematika terapan yang banyak digunakan untuk memecahkan permasalahan dalam kehidupan sehari-hari misalnya membantu pimpinan perusahaan dalam mengambil keputusan managerial. Permasalahan yang berhubungan dengan program linear selalu berhubungan dengan optimasi fungsi objektif berdasarkan berbagai kondisi yang membatasinya, dalam hal ini optimasi yang berupa memaksimumkan atau meminimumkan fungsi objektif.

Salah satu contoh soal dengan menggunakan program linear adalah :

Seorang pedagang soft drink mempunyai ruangan yang hanya cukup untuk menyimpan 40 box soft drink. Soft drink merek A dibeli dengan harga Rp, 60.000,00/box dan soft drink merek B dibeli dengan harga Rp. 80.000,00 /box. Jika pedagang tersebut mempunyai modal Rp. 3.000.000,00 tentukan sistem pertidaksamaan dari masalah tersebut.

Permasalahan diatas dapat disusun seperti tabel dibawah ini :

	Merek A	Merek B	Maksimum
Banyaknya Soft Drink	x	y	40
Biaya Pembelian	60.000	80.000	3.000.000

Misalkan banyaknya soft drink A dan soft drink B berturut-turut adalah x dan y . Oleh karena ruangan hanya dapat menampung 40 box dan modal Rp. 3.000.000,00 maka memenuhi hubungan berikut :

x + y ≤ 40
60.000 + 80.000 ≤ 3.000.000
x ≥ 0
y ≥ 0

Jadi model matematika untuk permasalahan tersebut adalah x + y ≤ 40, 60.000 + 80.000 ≤ 3.000.000, x ≥ 0 dan y ≥ 0

Karakteristik Pemrograman Linear

Sifat linearitas suatu kasus dapat ditentukan dengan menggunakan beberapa cara. Secara statistik, kita dapat memeriksa kelinearan menggunakan grafik (diagram pencar) ataupun menggunakan uji hipotesa. Secara teknis, linearitas ditunjukkan oleh adanya sifat proporsionalitas, additivitas, divisibilitas dan kepastian fungsi tujuan dan pembatas. 

Sifat proporsional dipenuhi jika kontribusi setiap variabel pada fungsi tujuan atau penggunaan sumber daya yang membatasi proporsional terhadap level nilai variabel. Jika harga per unit produk misalnya adalah sama berapapun jumlah yang dibeli, maka sifat proporsional dipenuhi. Atau dengan kata lain, jika pembelian dalam jumlah besar mendapatkan diskon, maka sifat proporsional tidak dipenuhi. Jika penggunaan sumber daya per unitnya tergantung dari jumlah yang diproduksi, maka sifat proporsionalitas tidak dipenuhi. 

Sifat additivitas mengasumsikan bahwa tidak ada bentuk perkalian silang diantara berbagai aktivitas, sehingga tidak akan ditemukan bentuk perkalian silang pada model. Sifat additivitas berlaku baik bagi fungsi tujuan maupun pembatas (kendala). Sifat additivitas dipenuhi jika fungsi tujuan merupakan penambahan langsung kontribusi masing-masing variabel keputusan. Untuk fungsi kendala, sifat additivitas dipenuhi jika nilai kanan merupakan total penggunaaan masing-masing variabel keputusan. Jika dua variabel keputusan misalnya merepresentasikan dua produk substitusi, dimana peningkatan volume penjualan salah satu produk akan mengurangi volume penjualan produk lainnya dalam pasar yang sama, maka sifat additivitas tidak terpenuhi. 

Sifat divisibilitas berarti unit aktivitas dapat dibagi ke dalam sembarang level fraksional, sehingga nilai variabel keputusan non integer dimungkinkan. 

Sifat kepastian menunjukkan bahwa semua parameter model berupa konstanta. Artinya koefisien fungsi tujuan maupun fungsi pembatas merupakan suatu nilai pasti, bukan merupakan nilai dengan peluang tertentu. (Siringoringo, 2005)

Salah satu tokoh dalam program linear ini adalah George B. Dantzig yang telah mengembangkan metode simplex sebagai suatu cara untuk menyelesaikan permasalahan pada program linear yang mempunyai pertidaksamaan dan variable yang besar. (Finite Matematics and its application, 1994)