Belajar Dasar - Dasar Linear Programming |ShareAngga.com|

Belajar Dasar - Dasar Linear Programming

|ShareAngga.com|

Hallo sobat user, Salam programmer buat kita semua :) ...

          Nah kali ini ShareAngga ingin berbagi / sharing ilmu kepada kalian semua yang ingin  belajar tentang pemmograman, judul artikel saya tentang pemmograma kali ini yaitu Dasar - Dasar Linear Programming. Bagi kamu yang udah gak sabar dan ingin tau tentang linear programming , atau apasih linear programming itu? Susah gak belajar linear programming? Langsung aja liat kebawah, mudah-mudahan apa yang saya bagikan dapat menjawab pertanyaan kalian semua.

Pengertian Linear Programming

Linear Programming merupakan suatu 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, dimana masing-masing kegiatan membutuhkan sumber yang sama sedangkan jumlahnya terbatas.

         Dan perlu diketahui juga apa yang dimaksud dengan linear programming menurut para ahli.

*Pengertian Linear Programing berdasarkan pendapat T. Hani Handoko (1999, p379) :

Linear Programing adalah suatu metode analitik paling terkenal yang merupakan suatu bagian  kelompok teknik-teknik yang disebut programisasi matematik.

*Berdasarkan pendapat Sofjan Assauri (1999, p9) :

pengertian linear Programing merupakan suatu teknik perencanaan yang menggunakan model matematika dengan tujuan menemukan kombinasi-kombinasi produk yang terbaik dalam menyusun alokasi sumber daya yang terbatas guna mencapai tujuan yang digunakan secara optimal.

*Berdasarkan pendapat Zainal Mustafa, EQ, dan Ali Parkhan (2000, p43)

Linear Programing  merupakan suatu cara yang lazim digunakan dalam pemecahan masalah pengalokasian sumber-sumber yang terbatas secara optimal.

*Berdasarkan pendapat Zulian Yamit (1996, p14) :

Linear programming adalah  metode  atau  teknik  matematis  yang  digunakan  untuk membantu manajer dalam pengambilan keputusan. Ciri khusus penggunaan metode matematis ini adalah berusaha mendapatkan maksimisasi atau minimisasi.

Tujuan Linear Programing adalah mencari pemecahan persoalan-persoalan yang timbul dalam perusahaan, yaitu mencari keadaan yang optimal dengan memperhitungkan batasan- batasan yang ada.

Model Linear Programing

Salah satu ciri khas model linear programming adalah bahwa linear programming didukung oleh macam-macam asumsi yang menjadi tulang punggung model tersebut. Asumsi tersebut adalah sebagai berikut :

1. Propotionality

Asumsi ini berarti bahwa naik turunnya nilai z dan penggunaan faktor-faktor produksi yang tersedia akan berubah secara sebanding (proposional) dengan perubahan tingkat kegiatan.

2. Additivity

Asumsi ini berarti bahwa nilai tujuan tiap kegiatan tidak saling mempengaruhi, atau dalam linear programming dianggap bahwa kenaikan nilai tujuan yang diakibatkan oleh kenaikan suatu  kegiatan  dapat  ditumbuhkan  tanpa  mempengaruhi  nilai  Z  yang  diperoleh  dari kegiatan lain.

3. Divisibility

Asumsi ini mengatakan bahwa keluaran (output) yang dihasilkan oleh suatu kegiatan dapat berupa bilangan pecahan, demikian pula nilai Z yang dihasilkan.

4. Deterministic (certainty)

Asumsi ini mengatakan bahwa semua parameter yang terdapat dalam model linear programming (aij, bj, cj ) dapat diperkirakan dengan pasti meskipun jarang digunakan tepat.

Dalam model linear programming dikenal 2 macam fungsi :

1.   Fungsi Tujuan (objective Function)

Fungsi tujuan merupakan fungsi yang menggambarkan tujuan atau sasaran didalam permasalahan linear programming yang berkaitan dengan peraturan secara optimal sumber daya – sumber daya untuk memperoleh keuntungan maksimal.

2.   Fungsi Batasan (Constraint Function)

Fungsi merupakan bentuk penyajian secara sistematis batasan-batasan kapasitas yang tersedia akan dialokasikan secara optimal.

Masalah linear programming dapat dinyatakan sebagai proses optimisasi suatu fungsi tujuan dalam bentuk : Memaksimumkan atau meminimumkan

Z = C1 X1   +  C2X2   + ……….. +CnXn

Dengan mengingat batasan-batasan sumber daya dalam bentuk: A11X1   +  A12X2  + …………… + A1nXn < B1

A21X1   +  A22X2   + …………… + A2nXn < B2     

Am1X1   +  Am2X2   + …………… + AmnXn < Bm

Dan X1 > 0, X2 > 0, ……. Xn > 0

Dimana Cj, Aij dan Bi adalah masukan konstan yang sering disebut sebagai parameter model. Keterangan

M         =   macam-macam batasan sumber atau fasilitas yang tersedia

N         =   macam aktivitas yang menggunakan atau fasilitas tersebut i       =   nomor setiap macam sumber atau fasilitas yang tersedia

j           =   nomor setiap macam aktivitas yang menggunakan sumber atau fasilitas yang tersedia

Xj        =   tingkat aktivitas kegiatan atau variable keputusan.

Aij       =    banyaknya sumber daya i yang diperlukan untuk menghasilkan setiap unit output kejadian j

Bi        =   banyaknya sumber atau fasilitas I yang tersedia untuk dialokasikan ke setiap jenis

aktivitas.

Z          =   nilai fungsi tujuan atau nilai yang dimaksimumkan atau diminimumkan. Cj      =   sumbangan per unit kegiatan j

Pada masalah maksimisasi Cj menunjukan keuntungan atau penerimaan per unit, pada kasus minimisasi Cj menunjukan biaya per unit.

Agar linear programming dapat diterapkan, asumsi-asumsi dasar berikut ini harus ditepati :

1.   Fungsi tujuan dan persamaan setiap batasan harus linear. Ini mencakup pengertian bahwa perubahan nilai z dan penggunaan sumber daya terjadi secara proporsional dengan tingkat perubahan kegiatan

2.   Parameter-parameter  harus    diketahui   atau    dapat    diperkirakan  dengan   pasti  (deterministic).

3.   Variabel-variabel keputusan harus dapat dibagi ini berarti bahwa suatu penyelesaian “feasible” dapat berupa bilangan pecahan.

Dasar-dasar umum Linear Programing meliputi bentuk model dan prosedur penyelesaian yang dibagi atas dua pemecahan masalah, yaitu:

Alur Kerja Linear Programming

Berikut  disajikan  diagram  alir  pengerjaan  Linear  programming.

 

         

Metode Grafik (Grafical Method)

Metode grafik adalah metode yang digunakan untuk memecahkan masalah linear programming yang menyangkut dua variabel keputusan.

Didalam penerapan metode grafik, ada langkah-langkah yang harus ditempuh adalah sebagai berikut:

•     Menyusun permasalahan yang ada

•     Menetukan fungsi tujuan yang akan dicapai

•     Mengidentifikasi kendala-kendala, yang berlaku dalam bentuk ketidaksamaan menjadi bentuk persamaan

•     Menggambarkan masing-masing garis pembatas dalam satu system koordinat.

•     Menentukan daerah (area) yang memenuhi batasan-batasan tersebut. Daerah ini disebut dengan “daerah Feasible”.

Metode Simpleks

Salah satu teknik penentuan solusi optimal yang digunakan dalam linear programming adalah metode simpleks. Penentuan solusi optimal menggunakan metode simpleks didasarkan pada teknik eleminasi Gauss Jordan. Penentuan solusi optimal dilakukan dengan memeriksa titik ekstrim satu per satu dengan cara perhitungan iteratif. Sehingga penentuan solusi optimal dengan simpleks dilakukan tahap demi tahap yang disebut dengan iterasi. Iterasi ke-i hanya tergantung dari iterasi sebelumnya (i-1) .

Ada beberapa istilah yang sangat sering digunakan dalam metode simpleks, diantaranya :

1. Iterasi adalah tahapan perhitungan dimana nilai dalam perhitungan itu tergantung dari nilai tabel sebelumnya.

2. Variabel non basis adalah variabel yang nilainya diatur menjadi nol pada sembarang iterasi. Dalam terminologi umum, jumlah variabel non basis selalu sama dengan derajat bebas dalam sistem persamaan.

3. Variabel basis merupakan variabel yang nilainya bukan nol pada sembarang iterasi. Pada solusi awal, variabel basis merupakan variabel slack (jika fungsi kendala merupakan pertidaksamaan ≤) atau variabel buatan (jika fungsi kendala menggunakan pertidaksamaan ≥ atau =). Secara umum, jumlah variabel basis selalu sama dengan jumlah fungsi pembatas (tanpa fungsi non negatif).

4. Solusi atau nilai kanan merupakan nilai sumber daya pembatas yang masih tersedia. Pada solusi awal, nilai kanan atau solusi sama dengan jumlah sumber daya pembatas awal yang ada, karena aktivitas belum dilaksanakan.

5. Variabel slack adalah variabel yang ditambahkan ke model matematik kendala untuk mengkonversikan pertidaksamaan (≤) menjadi persamaan (=). Penambahan variabel ini terjadi pada tahap inisialisasi. Pada solusi awal, variabel slack akan berfungsi sebagai variabel basis.

6. Variabel surplus adalah variabel yang dikurangkan dari model matematik kendala untuk mengkonversikan pertidaksamaan ≥ menjadi persamaan (=). Penambahan ini terjadi pada tahap inisialisasi. Pada solusi awal, variabel surplus tidak dapat berfungsi sebagai variabel basis.

7. Variabel buatan adalah variabel yang ditambahkan ke model matematik kendala dengan bentuk (≥) atau (=) untuk difungsikan sebagai variabel basis awal. Penambahan variabel ini terjadi pada tahap inisialisasi. Variabel ini harus bernilai 0 pada solusi optimal, karena kenyataannya variabel ini tidak ada. Variabel hanya ada di atas kertas.

8. Kolom pivot (kolom kerja) adalah kolom yang memuat variabel masuk. Koefisien pada kolom ini akn menjadi pembagi nilai kanan untuk menentukan baris pivot (baris kerja).

9. Baris pivot (baris kerja) adalah salah satu baris dari antara variabel basis yang memuat variabel keluar.

10. Elemen pivot (elemen kerja) adalah elemen yang terletak pada perpotongan kolom dan baris pivot. Elemen pivot akan menjadi dasar perhitungan untuk tabel simpleks berikutnya.

11. Variabel masuk adalah variabel yang terpilih untuk menjadi variabel basis pada iterasi berikutnya. Variabel masuk dipilih satu dari antara variabel non basis pada setiap iterasi. Variabel ini pada iterasi berikutnya akan bernilai positif.

12. Variabel keluar adalah variabel yang keluar dari variabel basis pada iterasi berikutnya dan digantikan oleh variabel masuk. Variabel keluar dipilih satu dari antara variabel basis pada setiap iiterasi. Variabel ini pada iterasi berikutnya akan bernilai nol.