linier programming mpk

Download Linier programming   mpk

Post on 14-Apr-2017

234 views

Category:

Engineering

4 download

Embed Size (px)

TRANSCRIPT

BAB 1PENDAHULUAN

Salah satu metode kuantitatif dalam pembuatan keputusan yaitu Linier Programming (Programasi linier). Konsep program linier ditemukan dan diperkenalkan pertama kali oleh George Dantzig yang berupa metode mencari solusi masalah program linier dengan banyak variabel keputusan. Dantzig bekerja di bidang penelitian teknis matematis untuk memecahkan masalah logistik militer angkatan udara Amerika Serikat selama perang dunia II. Penelitiannya didukung oleh J. Von Neumann, L. Hurwich dan T. C. Koopmans yang bekerja dalam bidang yang sama. Adapun teknik yang asli adalah program saling ketergantungan kegiatan-kegiatan dalam suatu struktur linier dan kemudian disederhanakan menjadi program linier.Penerapan program linier pertama kalinya adalah dalam bidang perencanaan militer, khususnya dalam perang Perang Dunia II oleh angkatan bersenjata Amerika Serikat dan Inggris. Sejak itulah seiring dengan berkembangnya waktu, dalam bidang teknologi dan pembangunan, teknik-teknik analisis program linier dengan cepat sekali menjalar dan diterapkan dalam berbagai bidang dan disiplin ilmu dalam rangka memecahkan berbagai permasalahan yang dihadapi.Model program linier mengandung asumsi-asumsi implisit tertentu yang harus dipenuhi agar definisinya sebagai suatu masalah program linier menjadi absah, dan salah satu asumsi dasar dalam permasalahan program linier adalah asumsi kepastian (deterministik/certainty), dimana setiap parameter yaitu data-data dalam pemodelan program linier yang terdiri dari koefisien-koefisien fungsi tujuan, konstanta-konstanta sebelah kanan dan koefisien-koefisien teknologi diketahui secara pasti.Untuk membuat suatu keputusan, seorang manager memerlukan alat bantu. Oleh karena itu, dalam tulisan ini akan diselesaikan suatu permasalahan Linier Programming (LP) dengan judul Metode Pembuatan Keputusan Dengan Programasi Linier (Linier Programming)

BAB 2DASAR TEORI

2.1 Sejarah Singkat Programasi LinierMenurut George B. Dantzig yang sering disebut Bapak Linier Programming, didalam bukunya: Linier Programming and Extension, menyebutkan bahwa ide daripada linier programming ini berasal dari ahli matematik Rusia bernama L.V. Kantorivich yang pada tahun 1939 menerbitkan sebuah karangan dengan judul: Mathematical Methods in The Organization and Planning of Production (telah diterjemahkan ke dalam bahasa Inggris dan diterbitkan di dalam majalah: Management Science Vol 6, 1960, halaman 366-422).Didalam karangan tersebut telah dirumuskan persoalan linier programming untuk pertama kalinya. Akan tetapi ide ini rupanya di Rusia tidak bisa berkembang. Ternyata dunia barat yang memanfaatkan ide ini selanjutnya. Kemudian pada tahun 1947 seorang ahli matematik dari Amerika Serikat, yang namanya telah disebutkan diatas yaitu: George B. Dantzig menemukan suatu cara untuk memecahkan persoalan linier programming tersebut dengan suatu metode yang disebut simplex method. Setelah saat itu yaitu sejak tahun lima puluhan linier programming tersebut berkembang dengan pesat sekali mula-mula di bidang kemiliteran (untuk penyusunan strategi perang) maupun didalam bidang business (persoalan untuk mencapai maksimum profit, minimum loss, dan lain sebagainya).Sekarang penggunaan linier programming bukan saja terbatas pada bidang kemiliteran, bidang ekonomi perusahaan yang sifatnya mikro, sebagai alat management, akan tetapi sudah meluas terutama sekali didalam perencanaan pembangunan ekonomi nasional yang makro sifatnya, misalnya didalam penentuan allocation of investments ke dalam sektor-sektor perekonomian, rotation corp policy peningkatan penerimaan devisa, dan lain sebagainya.

2.2 Karakterisasi Persoalan Programasi LinierProgramasi Linier merupakan bagian dari Matematika yang khusus diterapkan untuk menyelesaikan persoalan yang berkaitan dengan penentuan:a. Jumlah vaiabel-variabel input yang dipakai dalam suatu masalah.b. Kombinasi variabel input yang harus disediakan atau kombinasi output yang harus dihasilkan.c. Jumlah output yang harus dihasilkan untuk mencapai tujuan (objective) tertentu yakni untuk mencapai optimalisasi dari suatu masalah, misalnya untuk mencapai profit maksimum atau biaya minimum.Sesuai dengan sifat dari program ini, maka hubungan antara variabel input/output serta fungsi objective yang harus dicapai harus merupakan hubungan linier baik yang berbentuk persamaan linier atau pertidaksamaan linier sedangkan kuantitas input/output merupakan kuantitas yang non negatif ( 0)Dalam membangun model dari persoalan linier programming digunakan karakteristik-karakteristik sebagai berikut:a. Variabel keputusanVariabel keputusan adalah variabel yang menguraikan secara lengkap keputusan-keputusan yang akan dibuat, yang dimaksud disini adalah X1, X2, X3, X4, , Xnb. Fungsi tujuanFungsi tujuan merupakan fungsi dari variabel keputusan yang akan dimaksimumkan (untuk pendapatan atau keuntungan) atau diminimumkan (untuk ongkos).c. Pembatas-pembatasMerupakan kendala-kendala yang dihadapi sehingga kita tidak bisa menentukan harga variabel keputusan secara sembarang. Jadi maksudnya disini nilai dari variabel keputusan tersebut dibatasi oleh pembatas (constraint).d. Pembatas tandaPembatas tanda adalah pembatas yang menjelaskan apakah variabel keputusannya diasumsikan hanya berharga non-negatif atau variabel keputusan tersebut boleh berharga positif, boleh juga negatif (tidak terbatas dalam tanda).

2.3 Model Programasi LinierModel programasi linier merupakan suatu cara untuk menyelesaikan persoalan pengalokasian sumber-sumber yang terbatas diantara beberapa aktivitas yang bersaing, dengan cara yang terbaik yang mungkin dilakukan. Persoalan pengalokasian ini 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 situasi dari uraian di atas antara lain ialah 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 di atas ialah adanya keharusan untuk mengalokasikan sumber terhadap aktivitas.Bentuk umum dari model programasi linier dapat disusun sebagai berikut:1. Fungsi tujuan: untuk mencapai maksimasi Z = c1 x1 + c2 x2 + + cn xn 2. Himpunan constraint:a11 x1 + a12 x2 + + a1n xn b1a21 x1 + a22 x2 + + a2n xn b2...am1 x1 + am2 x2 + + amn xn bm3. x1, x2, ., xn 0 dimana:c1 x1 + c2 x2 + + cn xn: fungsi tujuan atau fungsi kriteria yang akan dimaksimasi, dinyatakan dengan Z c1, c2, , cn: koefisien ongkos (yang diketahui) x1, x2, ., xn: variabel keputusan atau level aktivitas yang harus dicari aij, i = 1, 2, , m: pembatas ke i j = 1, 2, , n: koefisien teknologi bi: koefisien ruas kanan x1, x2, ., xn 0: pembatas non-negatif

Formulasi diatas dinamakan sebagai bentuk standar dari persoalan programasi linier, dan setiap situasi yang formulasi matematisnya memenuhi model ini adalah persoalan programasi linier.Istilah yang lebih umum dari model programasi linier ini adalah sebagai berikut:a. Fungsi yang memaksimumkan, yaitu c1 x1 + c2 x2 + + cn xn, disebut sebagai fungsi tujuan.b. Pembatas-pembatas adalah constraint.c. Sebanyak m buah konstrain pertama sering disebut sebagai konstrain fungsional atau pembatas teknologis.d. Pembatas xj 0 disebut sebagai konstrain non negatif.e. Variabel adalah variabel keputusan.f. Konstanta-konstanta aij, bi dan cj adalah parameter-parameter model.Selain model programasi linier dengan bentuk seperti yang telah diformulasikan diatas, ada pula model programasi linier dengan bentuk yang agak lain, seperti:a. Fungsi tujuan bukan memaksimumkan, melainkan meminimumkan.Contoh: Meminimumkan: Z = c1 x1 + c2 x2 + + cn xnb. Beberapa konstrain fungsionalnya mempunyai ketidaksamaan dalam bentuk lebih besar atau sama dengan.Contoh: ai1 x1 + ai2 x2 + + ain xn bi, untuk beberapa harga ic. Beberapa konstrain fungsionalnya mempunyai bentuk persamaan.Contoh: ai1 x1 + ai2 x2 + + ain xn = bi, untuk beberapa harga id. Menghilangkan konstrain non-negatif untuk beberapa variabel keputusan.Contoh: xj tidak terbatas dalam tanda, untuk beberapa harga j

2.4 Asumsi dalam Model Programasi LinierDalam menggunakan model programasi linier, diperlukan beberapa asumsi sebagai berikut:a. Asumsi kesebandingan (proportionality)Kontribusi setiap variabel keputusan terhadap fungsi tujuan dan ruas kiri dari setiap pembatas adalah sebanding dengan nilai variabel keputusan itu. Jadi variabel Xj berkontribusi pada ongkos Cj Xj dan pada pembatas aij Xj. Jika Xj ditingkatkan dua kali, maka Cj Xj dan aij Xj akan meningkat dua kali.b. Asumsi penambahan (additivity)Ongkos total adalah penjumlahan dari ongkos individual, dan kontribusi total pada batas yang ke- i merupakan penjumlahan dari kontribusi individual dari individu aktivitas. Jadi berapapun nilai X2, pembuatan sejumlah X1 suatu variabel keputusan akan selalu berkontribusi sebesar C1 terhadap fungsi tujuan, dan berapapun harga X1 tidak akan mempengaruhi pembuatan sejumlah X2c. Asumsi pembagian (divisibility)Variabel keputusan dapat dibagi menjadi beberapa level fraksi (pecahan) sehingga nilai variabel keputusan dibolehkan bukan integer. Jadi semua variabel dapat memiliki harga berapapun asalkan real non-negatif.

d. Asumsi kepastian (certainty)Setiap parameter, seperti koefisien fungsi tujuan, ruas kanan, koefisien teknologis, diasumsikan dapat diketahui secara pasti.

2.5 Bentuk-bentuk Model Programasi LinierUntuk menyelesaikan masalah programasi linier, maka model pemecahan persoalan perlu dinyatakan dalam bentuk tertentu. Bentuk-bentuk model matematis programasi linier dapat dinyatakan dalam dua bentuk, yaitu bentuk kanonik dan bentuk standar (baku).a. Bentuk KanonikKarakteristik dari bentuk kanonik adalah sebagai berikut:1. Semua variabel keputusan adalah tidak negati