Pemograman Linier
Pemrograman Linier (PL) merupakan metode matematik dalam mengalokasikan sumber daya yang terbatas untuk mencapai suatu tujuan seperti memaksimumkan keuntungan dan meminimumkan. PL berkaitan dengan penjelasan suatu kasus dalam dunia nyata sebagai suatu model matematik yang terdiri dari sebuah fungsi tujuan linier dengan beberapa kendala linier.
Karakteristik Pemrograman Linier
Karakteristik dari Pemrograman Linier terdiri atas beberapa sifat diantaranya :
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 = dapat terpenuhi 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 terpenuhi. Atau dengan kata lain, jika pembelian dalam jumlah besar mendapatkan
diskon, maka sifat proporsional tidak terpenuhi. Jika penggunaan sumber daya per unitnya tergantung dari jumlah yang diproduksi, maka sifat proporsionalitas tidak terpenuhi.
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.
Keempat Asumsi (sifat) = ini dalam dunia nyata tidak selalu dapat dipenuhi. Untuk meyakinkan dipenuhinya keempat asumsi ini, dalam pemrograman linier diperlukan analisis sensitivitas terhadap solusi optimal yang diperoleh.
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,
alternatif 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.
Fungsi tujuan yang akan dioptimalkan hanya satu. Bukan berarti bahwa permasalahan optimasi
hanya dihadapkan pada satu tujuan. Tujuan dari suatu usaha bisa lebih dari satu. Tetapi pada
bagian ini kita hanya akan tertarik dengan permasalahan optimal dengan satu tujuan.
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. Terakhir,
model matematik membentuk jembatan ke penggunaan teknik matematik dan komputer
kemampuan tinggi untuk menganalisis permasalahan.
Di sisi lain, model matematik mempunyai kelemahan. Tidak semua karakteristik sistem
dapat dengan mudah dimodelkan menggunakan fungsi matematik. Meskipun dapat dimodelkan
dengan fungsi matematik, kadang-kadang penyelesaiannya sulit diperoleh karena kompleksitas
fungsi dan teknik yang dibutuhkan.
Bentuk umum pemrograman linier adalah sebagai berikut :
Fungsi tujuan :
Maksimumkan atau minimumkan z = c1×1 + c2×2 + … + cnxn
Sumber daya yang membatasi :
a11×1 + a12×2 + … + a1nxn = /? / ? b1
a21×1 + a22×2 + … + a2nxn = /? / ? b2
…a
m1×1 + am2×2 + … + amnxn = /? / ? bm
x1, x2, …, xn ? 0
Simbol x1, x2, …, xn (xi) menunjukkan variabel keputusan. Jumlah variabel keputusan
(xi) oleh karenanya tergantung dari jumlah kegiatan atau aktivitas yang dilakukan untuk
mencapai tujuan. Simbol c1,c2,…,cn merupakan kontribusi masing-masing variabel keputusan
terhadap tujuan, disebut juga koefisien fungsi tujuan pada model matematiknya.Simbol a11,
…,a1n,…,amn merupakan penggunaan per unit variabel keputusan akan sumber daya yang
membatasi, atau disebut juga sebagai koefisien fungsi kendala pada model matematiknya.
Simbol b1,b2,…,bm menunjukkan jumlah masing-masing sumber daya yang ada. Jumlah fungsi
kendala akan tergantung dari banyaknya sumber daya yang terbatas.
Pertidaksamaan terakhir (x1, x2, …, xn ? 0) menunjukkan batasan non negatif.
Membuat model matematik dari suatu permasalahan bukan hanya menuntut kemampuan
matematik tapi juga menuntut seni permodelan. Menggunakan seni akan membuat permodelan
lebih mudah dan menarik.
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. Tujuan pada suatu kasus bisa menjadi batasan
pada kasus yang lain. Harus hati-hati dalam menentukan tujuan, koefisien fungsi tujuan, batasan
dan koefisien pada fungsi pembatas.
Contoh Kasus yang dapat diselesaikan dengan mengunakan Pemrograman Linier.
Suatu pabrik perakitan radio menghasilkan dua tipe radio, yaitu HiFi-1 dan HiFi-2 pada fasilitas
perakitan yang sama. Lini perakitan terdiri dari 3 stasiun kerja. Waktu perakitan masing-masing
tipe pada masing-masing stasiun kerja adalah sebagai berikut :
Stasiun kerja Waktu perakitan per unit (menit)
HiFi-1 HiFi-2
1 6 4
2 5 5
3 4 6
Waktu kerja masing-masing stasiun kerja adalah 8 jam per hari. Masing-masing stasiun
kerja membutuhkan perawatan harian selama 10%, 14% dan 12% dari total waktu
kerja (8 jam) secara berturut-turut untuk stasiun kerja 1,2 dan 3.
Formulasikan permasalahan ini kedalam model matematiknya !
Solusi Permasalahan Kasus :
Alternatif keputusan adalah : radio tipe HiFi-1 (x1) dan radio tipe HiFi-2 (x2).
Tujuannya adalah memaksimumkan jumlah radio HiFi-1 dan HiFi-2 yang diproduksi.
Sumber daya pembatas adalah : jam kerja masing-masing stasiun kerja dikurangi dengan
waktu yang dibutuhkan untuk perawatan.
Waktu produktif masing-masing stasiun kerja oleh karenanya adalah :
Stasiun 1 : 480 menit – 48 menit = 432 menit
Stasiun 2 : 480 menit – 67.2 menit = 412.8 menit
Stasiun 3 : 480 menit – 57.6 menit = 422.4 menit.
Model umum pemrograman linier :
Maksimumkan z = x1 + x2
Kendala :
6×1 + 4×2 ? 432
5×1 + 5×2 ? 412.8
4×1 + 6×2 ? 422.4
x1, x2 ? 0
****+++++****
