BAB II. PEMROGRAMAN LINEAR KARAKTERISTIK PEMROGRAMAN LINEAR Sifat linearitas suatu kasus dapat ditentukan 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
merupakan
asumsi
aktivitas
dipertimbangkan secara bebas dari aktivitas lainnya.
individual
yang
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. Sifat additivitas dipenuhi jika fungsi tujuan merupakan penambahan langsung kontribusi masing-masing variabel keputusan; untuk fungsi pembatas (kendala), sifat additivitas dipenuhi jika nilai kanan merupakan total penggunaan 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 dipenuhi.
Pemrograman Linear
1
Sifat divisibilitas berarti unit aktivitas dapat dibagi ke dalam sembarang level fraksional, sehingga nilai variabel keputusan noninteger 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 •
Penetapan tujuan yang tepat merupakan aspek yang sangat penting dalam formulasi masalah.
•
Sudah menjadi karakteristiknya, riset operasional berhubungan dengan keseluruhan kekayaan organisasi bukan hanya dengan komponen tertentu.
•
Studi riset operasional mencari penyelesaian (solusi) yang mengoptimalkan keseluruhan organisasi bukan hanya penyelesaian suboptimal terbaik bagi hanya satu atau beberapa komponen.
•
Salah satu pendekatan yang mungkin untuk mengatasi permasalahan suboptimal bagi organisasi pencari keuntungan adalah menggunakan maksimisasi keuntungan jangka panjang sebagai satu-satunya tujuan.
•
Jangka
panjang
mengindikasikan
bahwa
tujuan
ini
menyediakan
fleksibilitas dalam mempertimbangkan aktivitas yang tidak menerjemahkan ke keuntungan secara langsung tetapi perlu dilakukan kadang-kadang supaya berarti.
PEMBENTUKAN MODEL MATEMATIK
Pemrograman Linear
2
•
Pendekatan konvensional riset operasional untuk pemodelan adalah membangun model matematik yang menggambarkan inti permasalahan.
•
Model matematika permasalahan optimasi terdiri dari dua bagian: •
Memodelkan
tujuan
optimasi.
Model
menggunakan bentuk persamaan.
matematik
tujuan
selalu
Bentuk persamaan digunakan
karena kita ingin mendapatkan solusi optimum pada satu titik. •
Model
matematik
yang
merepresentasikan
sumber
daya
yang
(=)
atau
membatasi. o Fungsi
pembatas
bisa
berbentuk
persamaan
pertidaksamaan (≤ atau ≥). o Fungsi pembatas disebut juga sebagai konstrain. o Konstanta (baik sebagai koefisien maupun nilai kanan) dalam fungsi pembatas maupun pada tujuan dikatakan sebagai parameter model. o Model matematika mempunyai beberapa keuntungan dibandingkan pendeskripsain permasalahan secara verbal. matematik mempunyai kelemahan.
Di sisi lain, model
Tidak semua karakteristik
sistem dapat dengan mudah dimodelkan menggunakan fungsi matematik. Meskipun dapat dimodelkan dengan fungsi matematik, kadang-kadang
penyelesaiannya
susah
diperoleh
karena
kompleksitas fungsi dan teknik yang dibutuhkan. •
Alternatif keputusan merupakan variabel keputusan model matematika.
•
Kompleksitas model matematik pada pemrograman linear ini ditentukan oleh jumlah variabel keputusan.
•
Semakin banyak kegiatan atau aktifitas atau alternatif keputusan, semakin kompleks perhitungan yang akan dihadapi pada tahap penyelesaian model. Bentuk umum pemrograman linear adalah sebagai berikut:
Pemrograman Linear
3
Fungsi Tujuan Maksimumkan atau minimumkan z = c1x1+ c2x2 + …+ cnxn Sumber daya yang membatasi (Kendala) : a11x1 + a12x2 +…+ a1nxn = / ≤ / ≥ b1 a21x1 + a22x2 +…+ a2nxn = / ≤ / ≥ b2 : am1x1 + am2x2 +…+ amnxn = / ≤ / ≥ bm x1, x2, ..., xn ≥ 0 o x1, x2, ..., xn (xi): variabel keputusan. o c1, c2, ..., cn merupakan kontribusi masing-masing variabel keputusan terhadap tujuan, kita sebut juga dengan koefisien fungsi tujuan pada model matematiknya. o a11, ..., a1n, ..., amn merupakan penggunaan per unit variabel keputusan akan sumber daya yang membatasi, atau kita sebut juga sebagai koefisien fungsi kendala pada model matematiknya. o 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. Meskipun fungsi tujuan misalnya hanya mempunyai kemungkinan bentuk maksimisasi atau minimisasi, keputusan untuk memilih salah satunya bukan pekerjaan mudah. pada kasus yang lain.
Tujuan pada suatu kasus bisa menjadi batasan
Kita harus hati-hati menentukan tujuan, koefisien
tujuan, batasan dan koefisien pada fungsi pembatas.
Contoh: 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.
Pemrograman Linear
4
Perakitan dilakukan oleh 4 orang karyawan dengan waktu kerja 8 jam per hari. Pelanggan pada umumnya membeli paling banyak 4 kursi untuk satu 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 rupiah. Formulasikanlah kasus tersebut ke dalam model matematiknya! Solusi: ¾ Hal pertama yang harus dilakukan adalah mengidentifikasi tujuan, alternatif keputusan dan sumber daya yang membatasi.
Berdasarkan
informasi yang diberikan pada soal, tujuan yang ingin dicapai adalah memaksimumkan pendapatan. Alternatif 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). ¾ Langkah berikutnya adalah memeriksa sifat proporsionalitas, additivitas, divisibilitas dan kepastian.
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 proporsional terhadap jumlah produk yang terjual. Penggunaan sumber daya yang membatasi, dalam hal ini waktu kerja karyawan dan pangsa pasar
juga
proporsional
diproduksi.
terhadap
jumlah
meja
dan
kursi
yang
Dengan demikian dapat dinyatakan sifat proporsional
dipenuhi. Total pendapatan pengrajin merupakan jumlah pendapatan dari keseluruhan meja dan kursi yang terjual. daya
(waktu
kerja
karyawan
dan
pangsa
Penggunaan sumber pasar)
merupakan
penjumlahan waktu yang digunakan untuk memproduksi meja dan kursi.
Maka dapat dinyatakan juga sifat additivitas dipenuhi.
divisibilitas dan sifat kepastian juga dipenuhi.
Pemrograman Linear
5
Sifat
¾ Ada dua variabel keputusan dan dua sumber daya yang membatasi. Fungsi
tujuan
merupakan
maksimisasi,
karena
pendapatan akan semakin disukai oleh pengrajin.
semakin
besar
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 defenisikan : x1 = jumlah meja yang akan diproduksi x2 = jumlah kursi yang akan diproduksi Model umum Pemrograman Linear (PL) kasus di atas oleh karenanya adalah: Fungsi Tujuan: Maksimumkan z = 1.2 x1 + 0.5 x2 Kendala:
2x1 + 0.5x2 ≤ 32 x1/ x2 ≥ ¼ atau 4x1 ≥ x2 atau 4x1 - x2 ≥ 0 x1, x2 ≥ 0
Pemrograman Linear
6
