Pemrogaman Linier

A.    PEMROGRAMAN LINIER

Pemrograman Linier disingkat PL merupakan metode  matematik dalam mengalokasikan sumber daya yang terbatas untuk mencapai suatu tujuan seperti memaksimumkan keuntungan dan meminimumkan biaya. PL banyak diterapkan dalam masalah ekonomi, industri, militer, social dan lain-lain. PL berkaitan dengan penjelasan suatu kasus dalam dunia nyata sebagai suatu model matematik yang terdiri dari sebuah fungsi tujuan linier dengan beberapa kendala linier.

Formulasi Permasalahan

Urutan pertama dalam penyelesaian adalah mempelajari sistem relevan dan mengembangkan pernyataan permasalahan yang dipertimbangakan dengan jelas. Penggambaran sistem dalam pernyataan ini termasuk pernyataan tujuan, sumber daya yang membatasi, variabel keputusan yang mungkin (kegiatan atau aktivitas), batasan waktu pengambilan keputusan, hubungan antara bagian yang dipelajari dan bagian lain  dalam perusahaan, dan lain-lain.

Penetapan tujuan yang tepat merupakan aspek yang sangat penting dalam formulasi masalah. Untuk membentuk tujuan optimalisasi, diperlukan identifikasi anggota manajemen yang benar-benar akan melakukan pengambilan keputusan dan mendiskusikan pemikiran mereka tentang tujuan yang ingin dicapai.

Pembentukan model matematik

Tahap berikutnya yang harus dilakukan setelah memahami permasalahan optimasi adalah membuat model yang sesuai untuk analisis. Pendekatan konvensional riset operasional untuk pemodelan adalah membangun model matematik yang menggambarkan inti permasalahan. Kasus dari bentuk cerita diterjemahkan ke model matematik. Model matematik merupakan representasi kuantitatif tujuan dan sumber daya yang membatasi sebagai fungsi variabel keputusan. Model  matematika permasalahan optimal terdiri dari dua bagian. Bagian pertama memodelkan tujuan optimasi. Model matematik tujuan selalu menggunakan bentuk persamaan. Bentuk persamaan digunakan karena kita ingin mendapatkan solusi optimum pada satu titik.

Bagian kedua merupakan model matematik yang merepresentasikan sumber daya yang membatasi. Fungsi pembatas bisa berbentuk persamaan (=) atau pertidaksamaan (≤ atau ≥). Fungsi pembatas disebut juga sebagai konstrain. Konstanta (baik sebagai koefisien maupun nilai kanan) dalam fungsi pembatas maupun pada tujuan dikatakan sebagai parameter model. Model matematika mempunyai beberapa keuntungan dibandingakan pendeskripsian permasalahan secara verbal. Salah satu keuntungan yang paling jelas adala model matematik menggambarkan permasalahan secara lebih ringkas. Hal ini cenderung membuat struktur keseluruhan permasalahan lebih mudah dipahami, dan membantu mengungkapkan relasi sebab akibat penting. Model matematik juga memfasilitasi yang berhubungan dengan permasalahan dan keseluruhannya dan mempertimbangkan semua keterhubungannya secara simultan.

Bentuk umum pemrograman linier adalah sebagai berikut :

Fungsi tujuan :

Maksimumkan atau minimumkan z = c₁x₁ + c₂x₂ + ... + c_nx_n

Sumber daya yang membatasi :

a₁₁x₁ + a₁₂x₂ + ... + a_1nx_n = /≤ / ≥ b₁

a₂₁x₁ + a₂₂x₂ + … + a_2nx_n = /≤ / ≥ b₂

…

a_m1x₁ + a_m2x₂ + … + a_mnx_n = /≤ / ≥ b_m

x₁, x₂, …, x_n ≥ 0

Simbol x₁, x₂, ..., x_n  (x_i) menunjukkan variabel keputusan. Jumlah variabel keputusan (x_i) oleh karenanya tergantung dari jumlah kegiatan atau aktivitas yang dilakukan untuk mencapai tujuan.  Simbol c₁,c₂,...,c_n merupakan kontribusi masing-masing variabel keputusan terhadap tujuan, disebut juga koefisien fungsi tujuan pada model matematiknya.Simbol a₁₁, ...,a_1n,...,a_mn merupakan penggunaan per unit variabel keputusan akan sumber daya yang membatasi, atau disebut juga sebagai koefisien fungsi kendala pada model matematiknya. Simbol b₁,b₂,...,b_m menunjukkan jumlah masing-masing sumber daya yang ada. Jumlah fungsi kendala akan tergantung dari banyaknya sumber daya yang terbatas.

Kasus pemrograman linier sangat beragam. Dalam setiap kasus, hal yang penting adalah memahami setiap kasus  dan memahami konsep permodelannya. Meskipun fungsi tujuan misalnya hanya mempunyai kemungkinan bentuk maksimisasi atau minimisasi, keputusan untuk memilih salah satunya bukan pekerjaan mudah. Harus hati-hati dalam menentukan tujuan, koefisien fungsi tujuan, batasan dan koefisien pada fungsi pembatas.

Contoh Kasus yang diselesaikan

1. Seorang pengrajin menghasilkan satu tipe meja dan satu tipe kursi. Proses yang dikerjakan hanya merakit meja dan kursi. Dibutuhkan waktu 2 jam untuk merakit 1 unit meja dan 30 menit untuk merakit 1 unit kursi. Perakitan dilakukan oleh 4 orang karyawan dengan waktu kerja @8 jam perhari. Pelanggan pada umumnya membeli paling banyak 4 kursi untuk 1 meja. Oleh karena itu pengrajin harus memproduksi kursi paling banyak empat kali jumlah meja. Harga jual per unit meja adalah Rp 1,2 juta dan per unit kursi adalah Rp 500 ribu.

Bagaimanakah formulasi dari kasus tersebut untuk mengetahui berapa unit masing-masing meja dan kursi yang harus dibuat agar diperoleh keuntungan yang maksimum?

Solusi :

Hal pertama yang harus dilakukan adalah mengidentifikasi tujuan, variabel keputusan dan sumber daya yang membatasi. Berdasarkan informasi yang diberikan pada soal, tujuan yang ingin dicapai adalah memaksimumkan pendapatan. Variabel keputusan adalah jumlah meja dan kursi yang akan diproduksi. Sumber daya yang membatasi  adalah waktu kerja karyawan dan perbandingan jumlah kursi dan meja yang harus diproduksi (pangsa pasar ).

Informasi di atas tidak menunjukkan adanya pemberian diskon, sehingga harga jual per meja maupun kursi akan sama meskipun jumlah yang dibeli semakin banyak. Hal ini mengisyaratkan bahwa total  pendapatan yang diperoleh pengrajin proposional terhadap jumlah produk yang terjual. Penggunaan sumber daya yang membatasi , dalam hal ini waktu kerja karyawan dan pangsa pasar juga proporsional terhadap jumlah meja dan kursi yang diproduksi. Total pendapatan pengrajin merupakan jumlah pendapatan dari keseluruhan meja dan kursi yang terjual. Penggunaan sumber daya ( waktu kerja karyawan dan pangsa pasar) merupakan penjumlahan waktu yang digunakan untuk memproduksi meja dan kursi.

Ada dua variabel keputusan dan dua sumber daya yang membatasi. Fungsi tujuan merupakan maksimisasi, karena semakin besar pendapatan akan semakin disukai oleh pengrajin. Fungsi kendala pertama (batasan waktu) menggunakan pertidaksamaan ≤, karena waktu yang tersedia dapat digunakan sepenuhnya atau tidak, tapi tidak mungkin melebihi waktu yang ada. Fungsi kendala yang kedua bisa menggunakan ≤ atau ≥ tergantung dari pendefinisian variabelnya.

Kita definisikan :

x₁ = jumlah meja yang akan diproduksi

x₂ = jumlah kursi yang akan diproduksi

Model umum Pemrograman Linier kasus di atas adalah :

Fungsi tujuan :

Maksimumkan z = 1.2 x₁ + 0.5 x₂

Kendala :

2x₁ + 0.5 x₂ ≤ 32

x₁/x₂ ≥ ¼ atau 4x₁≥ x₂ atau 4x₁ – x₂ ≥ 0

x₁ , x₂ ≥ 0

2. Seorang peternak memiliki 200 kambing yang mengkonsumsi 90 kg pakan khusus setiap harinya. Pakan tersebut disiapkan menggunakan campuran jagung dan bungkil kedelai dengan komposisi sebagai berikut :

Bahan	Kg per kg bahan
	Kalsium	Protein	Serat	Biaya (Rp/kg)
Jagung	0.001	0.09	0.02	2000
Bungkil kedelai	0.002	0.60	0.06	5500

Kebutuhan pakan kambing setiap harinya adalah paling banyak 1% kalsium, paling sedikit 30% protein dan paling banyak 5% serat.

Formulasikan permasalahan di atas kedalam model matematiknya !

Solusi :

Hal pertama yang harus dilakukan adalah mengidentifikasi tujuan , variabel keputusan dan sumber daya yang membatasi. Berdasarkan informasi yang diberikan pada soal, tujuan yang ingin dicapai adalah meminimumkan biaya pembelian bahan pakan. Variabel keputusan adalah jumlah jagung dan bungkil kedelai yang akan digunakan. Sumber daya yang membatasi adalah kandungan kalsium, protein dan serat pada  jagung dan bungkil kedelai, serta kebutuhan jumlah pakan per hari.

Informasi di atas tidak menunjukkan adanya pemberian diskon, sehingga harga pembelian jagung dan bungkil kedelai per kg tidak berbeda meskipun pembelian dalam jumlah besar. Hal ini mengisyaratkan bahwa total biaya yang harus dikeluarkan peternak proporsional  terhadap jumlah jagung dan  bungkil kedelai yang dibeli. Penggunaan sumber daya yang membatasi, dalam hal ini komposisi jagung dan bungkil kedelai akan serat, protein dan kalsium proporsional terhadap jumlah jagung dan bungkil. Total pengeluaran pembelian bahan pakan  merupakan penjumlahan  pengeluaran untuk jagung dan bungkil kedelai. Jumlah  masing-masing serat, protein dan kalsium yang ada di pakan  khusus merupakan penjumlah serat, protein dan kalsium yang ada pada jagung dan bungkil kedelai. Jumlah pakan khusus yang dihasilkan merupakan penjumlahan jagung dan bungkil kedelai yang digunakan. 

Ada dua variabel keputusan dan empat sumber daya yang membatasi. Fungsi tujuan merupakan minimisasi, karena semakin kecil biaya akan semakin disukai oleh peternak. Fungsi kendala pertama (batasan jumlah pakan yang dibutuhkan per hari) menggunakan persamaan (=), fungsi kendala kedua (kebutuhan kalsium) dan kendala keempat (kebutuhan serat) menggunakan pertidaksamaan ≤, dan fungsi kendala ketiga (kebutuhan akan protein) menggunakan pertidaksamaan ≥.

Kita definisikan :

x₁ = jumlah jagung yang akan digunakan

x₂ = jumlah bungkil kedelai yang akan digunakan

Model umum Pemrograman linier kasus di atas oleh karenanya adalah :

Fungsi tujuan : minimumkan z = 2000 x₁ + 5500 x₂

Kendala :

x₁ + x₂ = 90

0.001 x₁ + 0.002 x₂ ≤ 0.9

0.09 x₁ + 0.6 x₂ ≥ 27

0.02 x₁ + 0.06 x₂ ≤ 4.5

x₁, x₂ ≥ 0

Rangkuman

Tahapan dalam penyelesaian optimasi dari Linear programming ini adalah sebagai berikut :

1. Menentukan decision of variables
2. Membuat objective function
3. Memformulasikan constraints
4. Menggambarkan dalam bentuk grafik
5. Menentukan daerah kemungkinan/ "feasible"
6. Menentukan solusi optimum.

Referensi

1.       Nanang, H., (1999). Integral Program Linier Matriks Vektor Transformasi Barisan Dan Deret

2.       Siringoringo, H., (2005) Seri Teknik Riset Operasional. Pemrograman Linear. Penerbit Graha Ilmu. Yogyakarta.