Tuesday, May 26, 2009

Linear Programming

Model optimasi telah digunakan selama berabad-abad. Pada masa sekarang ini, optimasi menjadi sangat esensial untuk tujuan bisnis yang semakin kompleks dan rumit. Para insinyur pun menjadi semakin ambisius dalam mengembangkan hal ini. Dalam banyak hal, keputusan dapat saja dibuat tanpa mempertimbangkan tujuan dari model tersebut. Sebagai contoh, dalam kerjasama multinasional, sebagian kecil perkembangan proses operasi dapat mencapai peningkatan keuntungan berjuta-juta dolar. Tetapi, untuk mencapainya dibutuhkan analisis dan kerjasama setiap divisi.
Untuk model yang kompleks, dengan berbagai kerumitan yang ada, keputusan bisnis akan sangat berpengaruh. Dalam beberapa dasawarsa ini, telah dikembangkan hardware dan software komputer, yang berhasil melakukan optimasi secara praktis dalam bisnis dan ilmu pengetahuan. Sekarang ini, pemecahan masalah dengan ribuan atau bahkan jutaan variabel menjadi mungkin untuk diselesaikan.
Secara sederhana, dapat diambil contoh bagian produksi suatu perusahaan yang dihadapkan pada masalah penentuan tingkat produksi masingmasing jenis produk dengan memperhatikan batasan faktor-faktor produksi: mesin, tenaga kerja, bahan mentah, dan sebagainya untuk memperoleh tingkat keuntungan maksimal atau biaya yang minimal.
Program linier merupakan salah satu aplikasi solusi permasalahan Lebih lanjut formulasi model tersebut mengijinkan perpindahan masalah umum menjadi sebuah kerangka kerja matematika. Persoalan pengalokasian ini akan muncul manakala seseorang harus memilih tingkat aktivitas-aktivitas tertentu yang bersaing dalam hal penggunaan sumber daya langka yang dibutuhkan untuk melaksanakan aktivitas-aktivitas tersebut. Beberapa contoh dari uraian tersebut adalah persoalan pengalokasian fasilitas produksi, persoalan pengalokasian sumber daya nasional untuk kebutuhan domestik, penjadwalan produksi, solusi permainan (game), dan pemilihan pola pengiriman (shipping). Satu hal yang menjadi ciri situasi diatas ialah adanya keharusan untuk mengalokasikan sumber.
Dalam laporan ini berisikan tentang solusi matematis masalah pembuangan limbah. Pada kasus ini limbah yang dihasilkan pabrik merupakan masalah utama yang harus dihadapi oleh sebuah pabrik dalam menyikapi lingkungan sekitarnya. Karena pemerintah menetapkan ambang batas limbah yang aman bagi lingkungan dan sementara itu sebuah pabrik tidak mungkin hanya menghasilkan limbah yang aman (di atas ambang batas pemerintah). Sehingga limbah pabrik yang belum memenuhi standar harus diolah kembali. Pengolahan tersebut tentunya identik dengan biaya yang tinggi.
Permasalahan pabrik tersebut telah jelas bahwa bagaimana sebuah pabrik dapat menghasilkan limbah yang memenuhi standar pemerintah agar pabrik tidak perlu mengeluarkan biaya tambahan untuk mengurusi masalah limbah.
Linear Programming merupakan model umum yang dapat digunakan dalam pemecahan masalah pengalokasian sumber-sumber yang terbatas secara optimal. Masalah tersebut timbul apabila seseorang diharuskan untuk memilih atau menentukan tingkat setiap kegiatan yang akan dilakukannya, di mana masing-masing kegiatan membutuhkan sumber yang sama sedangkan jumlahnya terbatas. Secara sederhana, dapat diambil contoh bagian produksi suatu perusahaan yang dihadapkan pada masalah penentuan tingkat produksi masingmasing jenis produk dengan memperhatikan batasan faktor-faktor produksi: mesin, tenaga kerja, bahan mentah, dan sebagainya untuk memperoleh tingkat keuntungan maksimal atau biaya yang minimal.

Pada masa modern sekarang, Linear Programming masih menjadi pilihan dalam upaya untuk memperoleh tingkat keuntungan maksimal atau biaya yang minimal.
Dalam memecahkan masalah di atas, Linear Programming menggunakan model matematis. Sebutan “linear” berarti bahwa semua fungsi matematis yang disajikan dalam model ini haruslah fungsi-fungsi linier. Dalam Linear Programming dikenal dua macam fungsi, yaitu fungsi tujuan (objective function) dan fungsi-fungsi batasan (constraint function). Fungsi tujuan adalah fungsi yang menggambarkan tujuan/sasaran di dalam permasalahan Linear Programming yang berkaitan dengan pengaturan secara optimal sumber daya-sumber daya, untuk memperoleh keuntungan maksimal atau biaya minimal. Pada umumnya nilai yang akan dioptimalkan dinyatakan sebagai Z. Fungsi batasan merupakan bentuk penyajian secara matematis batasan-batasan kapasitas yang tersedia yang akan dialokasikan secara optimal ke berbagai kegiatan.
Menurut Supranto(1983,p76-82), suatu persoalan disebut persoalan Linear Programming apabila memenuhi:
1. Tujuan (obyektif) yang akan dicapai harus dapat dinyatakan dalam fungsi linier. Fungsi ini disebut fungsi tujuan (fungsi obyektif).
2. Harus ada alternatif pemecahan yang membuat nilai fungsi tujuan optimum (laba yang maksimum, biaya yang minimum).
3. Sumber-sumber tersedia dalam jumlah yang terbatas (bahan mentah, modal, dan sebagainya). Kendala-kendala ini harus dinyatakan di dalam pertidaksamaan linier (linear inequalities).
Pada dasarnya, persoalan Linear Programming dapat dirumuskan sebagai berikut.
Cari x1,x2, …, xj, …, xn. sedemikian rupa sehingga
Z = c1×1 + c2×2 + … + cjxj + … + cnxn = Optimum (Maksimum atau Minimum)
dengan kendala:






Keterangan:
Ada n macam barang yang akan diproduksi masing-masing sebesar x1, x2, … , xj, … xn.
xj = banyaknya produksi barang yang ke j, j = 1,2,…,n
cj = harga per satuan barang ke j, disebut “price”
Ada m macam bahan mentah masing-masing tersedia h1, h2, …, hj, …, hm.
hi = banyaknya bahan mentah ke i, i = 1,2, …,m
aij = banyaknya bahan mentah ke i yang dipergunakan untuk memproduksi 1 satuan barang ke j
xj unit memerlukan aij unit bahan mentah i.

Asumsi-asumsi Linear Programming
Asumsi-asumsi Linear Programming dapat dirinci sebagai berikut.
o Proportionality
Asumsi ini berarti bahwa naik turunnya nilai Z dan penggunaan sumber atau fasilitas yang tersedia akan berubah secara sebanding (proporsional) dengan perubahan tingkat kegiatan.
Z = C1X1 + C2X2 + C3X3 + …..CnXn
Setiap penambahan 1 unit X1 akan menaikkan Z dengan C1. Setiap penambahan 1 unit X2 akan menaikkan Z dengan C2, dan seterusnya.
a11X1 + a12X2 + a13X3 + ….. + anXn ≤ b1
Setiap penambahan 1 unit X1 akan menaikkan penggunaan sumber/fasilitas 1 dengan a11. Setiap penambahan 1 unit X2 akan menaikkan penggunaan sumber/fasilitas 1 dengan a12, dan seterusnya. Asumsinya adalah, setiap ada kenaikan kapasitas riil tidak perlu ada biaya persiapan (set up cost).
o Additivity
Asumsi ini berarti bahwa nilai tujuan tiap kegiatan tidak saling mempengaruhi, atau dalam Linear Programming dianggap bahwa kenaikan dari nilai tujuan (Z) yang diakibatkan oleh kenaikan suatu kegiatan dapat ditambahkan tanpa mempengaruhi bagian nilai Z yang diperoleh dari kegiatan lain.
Z = 3X1 + 5X2 di mana X1 = 10; X2 = 2;
Sehingga Z = 30 + 10 = 40
Jika X1 bertambah 1 unit, maka sesuai dengan asumsi, maka nilai Z menjadi 40 + 3 = 43. Jadi, nilai 3 karena kenaikan X1 dapat langsung ditambahkan pada nilai Z mula-mula tanpa mengurangi bagian Z yang diperoleh dari kegiatan 2 (X2). Dengan kata lain, tidak ada korelasi antara X1 dan X2.
o Divisibility
Asumsi ini menyatakan bahwa keluaran yang dihasilkan oleh setiap kegiatan dapat berupa bilangan pecahan. Demikian pula dengan nilai Z yang dihasilkan.
o Deterministic (certainty)
Asumsi ini menyatakan bahwa semua parameter yang terdapat dalam model Linear Programming (aij, bi, cj) dapat diperkirakan dengan pasti, meskipun jarang dengan tepat.

2.2 Model-Model dalam Penelitian Operational
Model – model dalam Penelitian Operasional yang biasa digunakan adalah :
1. Model – model ikonis / fisik
Yaitu penggambaran fisik dari suatu sistem , baik dalam bentuk yang ideal maupun dalam skala yang berbeda.
2. Model – model analog / diagramatis
Model ini dapat menggambarkan situasi – situasi yang dinamis dan lebih banyak digunakan daripada model ikonis karena sifatnya yang dapat dijadikan analogi bagi karakteristik sesuatu yang sedang dipelajari.
3. Model – model simbolis / matematis
Yaitu penggambaran dunia nyata melalui simbol – simbol matematis.
4. Model – model simulasi
Yaitu model – model yang meniru tingkah laku sistem dengan mempelajari interaksi komponen – komponennya. Karena tidak memerlukan fungsi – fungsi matematis secara eksplisit untuk merelasikan variabel – variabel sistem, maka model – model ini dapat digunakan untuk memecahkan sistem kompleks yang tidak dapat diselesaikan secara matematis. Tetapi ini tidak dapat memberikan solusi yang benar-benar optimum, yang dapat diberikan jawaban suboptimum, yaitu optimum dari alternati – alternatif yang dites.
5. Model – model heuristik
Kadang formulasi matematis bersifat sangat kompleks untuk dapat memberikan suatu solusi yang pasti,kadang dapat diperoleh tetapi memerlukan proses pehitungan yang sangat panjang dan tidak praktis, maka digunakan model ini, yaitu suatu metode pencarian didasarkan atas intuisi atau aturan empiris untuk memperoleh solusi yang lebih baik daripada solusi yang dicapai sebelumnya.

ASUMSI MODEL LP

Model LP mengandung asumsi-asumsi implisit tertentu yang harus dipenuhi agar definisinya sebagai suatu masalah LP menjadi absah. Asumsi itu menuntut bahwa hubungan fungsional dalam masalah itu adalah linier dan additif, dapat dibagi dan deterministik. Linearity dan Additivity Bahwa fungsi tujuan dan semua kendala harus linier. Dengan kata lain, jika suatu kendala melibatkan dua variabel keputusan, dalam diagram dimensi dua ia akan berupa garis lurus. Begitu juga, suatu kendala yang melibatkan tiga variabel akan menghasilkan suatu bidang datar dan kendala yang melibatkan n variabel akan menghasilkan hyperplane (bentuk geometris yang rata) dalam ruang berdimensi n.
Kata linier secara tidak langsung mengatakan bahwa hubungannya proporsional yang berarti bahwa tingkat perubahan atau kemiringan hubungan fungsional itu adalah konstan dan karena itu perubahan nilai variabel akan mengakibatkan perubahan relatif nilai fungsi tujuan dalam jumlah yang sama. LP juga mensyaratkan bahwa umlah variabel kriteria dan jumlah penggunaan sumber daya harus bersifat additif. Contohnya, keuntungan total Z yang merupakan variabel kriteria, sama dengan jumlah keuntungan yang diperoleh dari masing-masing kegiatan, cj x. Juga, seluruh sumber daya yang digunakan untuk seluruh kegiatan, harus sama dengan jumlah sumber daya yang digunakan untuk masing-masing kegiatan.

2. 3 Metodologi Penelitian Operasional
Metodelogi Penelitian Operasional , ada lima langkah, yaitu :
Langkah 1 : Memformulasikan persoalan
Definisikan persoalan lengkap denagn spesifikasi tujuan organisasi dan bagian – bagian organisasi atau sistem yang bersangkutan.
Langkah 2 : Mengobservasikan sistem
Kumpulkan data untuk mengestimasikan besaran parameter yang berpengaruh terhadap persoalan yang dihadapi. Estimasi ini digunakan untuk membangun dan mengevaluasi model matematis dari persoalan.
Langkah 3 : Memformulasikan model matematis dari persoalan yang dihadapi
Dalam memformulasikan persoalan ini biasanya digunakan model analitik, yaitu model matematis yang menghasilkan persamaan. Jika pada suatu situasi yang sangat rumit tidak diperoleh model analitik maka perlu dikembangkan suatu model simulasi.
Langkah 4 : Mengevaluasi model dan menggunakannya untuk prediksi
Pada langkah ini tentukan apakah model matematis yang dibangun pada langkah 3 telah menggambarkan keadaan nyata secara akurat . Bila belum buatlah model yang baru.
Langkah 5 : Mengimplementasikan hasil studi
Kita harus menerjemahkan hasil studi atau hasil perhitungan ke dalam bahasa sehari – hari yang mudah dimengerti.
(Tjutju Tarliah Dimyati-Ahmad Dimyati, Operations Research, Hal 2-5)

Programa linier dari kata Linear Programming, adalah suatu cara untuk menyelesaikan persoalan pengalokasian sumber – sumber yang terbatas di antara beberapa aktivitas yang bersaing, dengan cara yang terbaik yang mungkin dapat dilakukan. Programa linier ini menggunakan model matematis untuk menjelaskan persoalan yang dihadapi. Sifat “ linier “ memberi arti bahwa seluruh fungsi matematis dalam model ini merupakan fungsi yang linier, sedangkan “ programa “ merupakan sinonim untuk perencanaan aktivitas – aktivitas untuk memperoleh suatu hasil yang optimum, yaitu hasil yang mencapai tujuan terbaik diantara seluruh alternatif yang fisibel.
Dalam membangun model dari formulasi akan digunakan karkteristik – karakteristik yang biasa digunakan dalam persoalan programa linier, yaitu :
a. Variabel keputusan
Adalah variabel yang menguraikan secara lengkap keputusan – keputusan yang akan dibuat.
b. Fungsi tujuan
Merupakan fungsi dari variabel keputusan yang akan dimaksimumkan ( untuk pendapatan atau keuntungan ) atau meminimumkan ( untuk ongkos ).
c. Pembatas
Merupakan kendala yang dihadapi sehingga kita tidak bisa menentukan harga – harga variabel keputusan secara sembarang. Koefisien dari variabel keputusan pada pembatas disebut koefisien teknologis, sedangkan bilangan pada sisi kanan setiap pembatas disebut ruas kanan pembatas.
d. Pembatas tanda
Adalah pembatas yang menjelaskan apakah varibel keputusannya diasumsikan hanya berharga nonnegatif atau variabel keputusan tersebut boleh berharga positif , boleh juga negatif ( tidak terbatas dalam tanda ).
(Tjutju Tarliah Dimyati-Ahmad Dimyati, Operations Research, Hal 17-20)
Programa dinamis adalah suatu teknik matematis yang biasanya digunakan untuk membuat suatu keputusan dari serangkaian keputusan yang saling berkaitan. Tujuan utamanya adalah untuk mempermudah penyelesaian persoalan optimasi yang mempunyai karakteristik tertentu.
Ide dasarnya adalah membagi persoalan menjadi beberapa bagian yang lebih kecil sehingga memudahkan penyelesaiannya. Berbeda dengan programa linier , pada persoalan programa dinamis tidak ada formulasi matematis yang standard.

2.4 Model Programa Linier
Salah satu keputusan managerial yang sangat penting adalah penyaluran sumber–sumber yang sangat langka, dimana sumber–sumber ini dapat dipergunakan untuk menghasilkan komoditi tertentu. Metode analisis yang paling bagus untuk menyelesaikan peralokasi sumber ialah metode programa linier.
Programa linear yang diterjemahkan dari Linear Programming (LP) adalah suatu cara untuk menyelesaikan persoalan pengalokasian sumber-sumber yang terbatas di antara beberapa aktivitas yang bersaing, dengan cara yang terbaik yang mungkin dilakukan. Persoalan pengalokasian ini akan muncul manakala seseorang harus memilih tingkat aktivitas-aktivitas tertentu yang bersaing dalam hal penggunaan sumber daya langka yang dibutuhkan untuk melaksanakan aktivitas-aktivitas tersebut. Programa linear ini menggunakan model matematis untuk menjelaskan persoalan yang dihadapinya. Sifat “linier” disini memberi arti bahwa seluruh fungsi matematis dalam model ini merupakan fungsi yang linier, sedangkan kata “programa” merupakan sinonim untuk perencanaan aktivitas-aktivitas untuk memperoleh suatu hasil yang optimum, yaitu suatu hasil ynag mencapai tujuan terbaik di antara seluruh alternatif yang fisibel.
Pada dasarnya metode-metode yang dikembangkan untuk memecahkan model programa linear ditujukan untuk mencari solusi dari beberpa alternatif solusi yang dibentuk oleh persamaan-persamaan pembatas sehingga diperoleh nilai fungsi tujuan yang optimum. Ada dua cara yang bisa digunakan untuk menyelesaikan persoalan-persoalan programa linier yaitu:
1. Solusi Grafis
Cara grafis dapat kita pergunakan apabila persoalan programa linier yang akan diselesaikan itu hanya mempunyai 2 variabel.
2. Metode Simpleks
Metode Simpleks merupakan teknik perhitungan yang dikembangkan untuk memecahkan persoalan programa linear yang mempunyai jumlah variabel keputusan dan pembatas yang besar.
(Tjutju T.D, Operations Research ,2003, hal 38-39)

2.5 Solusi Pada Model Programa Linier
Ada 3 macam solusi pada model programa linier :
1. Feasible
Solusi feasible terjadi bila terdapat titik solusi yang masuk ke daerah feasible. Daerah feasible dari programa linier adalah set dari seluruh titik yang memenuhi seluruh pembatas, termasuk pembatas tanda. Untuk persoalan maksimasi, solusi optimal dari persoalan programa linier adalah suatu titik pada daerah feasible dengan nilai fungsi
tujuan terbesar. Pada persoalan minimasi, solusi optimal adalah suatu titik pada daerah feasible dengan nilai fungsi tujuan terkecil.
2. Infeasible
Solusi infeasible terjadi bila tidak terdapat ruang solusi atau tidak ada daerah yang memenuhi seluruh pembatas. Dalam hal ini daerah feasiblenya kosong sehingga dengan sendirinya tidak ada solusi optimum.
3. Unbounded
Kasus ini terjadi apabila ruang solusi tidak terbatas sehingga nilai fungsi tujuan dapat meningkat/menurun secara tidak terbatas. Pada umumnya, kasus ini terjadi karena kesalahan dalam memformulasikan persoalan.
(Tjutju T.D, Operations Research ,2003, hal 41-45)
2.6 Shadow Prices
Untuk mendefinisikan kegunaan konsep shadow price ini, misalkan kita mempunyai persoalan maksimasi dengan pembatas di mana adalah ruas kanan dari pembatas ke- .
Shadow price pembatas ke- dari suatu persoalan maksimasi adalah besaran yang menyatakan peningkatan nilai optimal sebagai akibat dinaikkannya harga sebesar 1 unit, yaitu dari menjadi .
Shadow price pembatas ke- dari suatu persoalan maksimasi adalah nilai optimal dari variabel dual ke- . Karena shadow price adalah variabel dual, maka :
Shadow price untuk pembatas bertanda akan nonnegatif.
Shadow price untuk pembatas bertanda akan nonpositif.
Shadow price untuk pembatas bertanda akan tidak terbatas dalam tanda.
Definisi shadow price di atas juga berlaku untuk persoalan minimasi, dengan ketentuan bahwa :
Shadow price untuk pembatas bertanda akan nonnegatif.
Shadow price untuk pembatas bertanda akan nonpositif.
Shadow price untuk pembatas bertanda akan tidak terbatas dalam tanda.

2.7 Software QS (Quantitative System)
Solusi komputer merupakan bentuk solusi yang memberi kemudahan bagi pengambil keputusan LP. Solusi ini menawarkan beberapa jenis pilihan persoalan yang dapat diselesaikan, sehingan pengguna harus tahu jenis persolan yang dihadapinya. Hal pokok yang perlu diperhatikan dalam solusi komputer adalah software tidak mampu mendeteksi adanya kesalahan yang dibuat oleh pengguna dalam membuat model LP, sehingga apapun bentuk model LP akan diselesaikan oleh software. Software yang dapat digunakan antara lain QS (Quantitative System), LP solve, Lingo, dan lain-lain.
(Diktat Operttonal Research, Lab OPSI,2004)
Dalam praktikum kali ini untuk mempermudah perhitungan programa linier kami menggunakan software QS (Quantitative System). Dalam software QS ini kita menggunakan aplikasi (modul) untuk bernama LP-ILP.

No comments:

Post a Comment