TUGAS SPK

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

****+++++****