Senin, 28 September 2009

LINIER PROGRAMING

Linier programming adalah suatu teknik optimasi untuk memecahkan persoalan dimana fungsi obyektif maupun fungsi kendala dinyatakan sebagai fungsi linier dari variabel desain. Metode yang sangat populer untuk menyelasaikan persoalan linier programming adalah “Metode Simpleks-”.
Karakteristik dari persoalan linier programing adalah:
1. Tipe Optimasi adalah minimisasi fungsi obyektif
2. Semua fungsi kendala mempunyai jenis “Equality”
3. Semua variabel desain adalah non negatif.

1 Model Linier Programing
Dalam Linier Programing dikenal dua macam fungsi yaitu fungsi obyektif dan fungsi kendala. Fungsi obyektif yang sering juga disebut dengan fungsi tujuan adalah fungsi yang menggambarkan tujuan atau sasaran didalam permasalahan LP yang berkaitan dengan pengaturan secara optimal untuk memperoleh keuntungan secara maksimal atau biaya secara minimal. Fungsi kendala merupakan batasan-batasan kapasitas yang tersedia atau kemampuan yang ada yang akan dialokasikan secara optimal ke dalam berbagai kegiatan.
Persoalan LP dapat dinyatakan dalam bentuk standar seperti pada tabel berikut:

Tabel 3.1 Data untuk model linear programming

Dengan mengunakan Tabel diatas dapat disusun suatu model matematis yang digunakan untuk menyatakan permasalahan LP yaitu:

Fungsi tujuan:
Maksimumkan Z=C1X1 + C2X2 + C3X3 + …. + CnXn
Dengan Fungsi kendala
1). a11X1 + a12X2 +a13X3 + … + a1nXn ≤ b1
2). a21X1 + a22X2 +a23X3 + … + a2nXn ≤ b2
.
.
.
m). am1X1 + am2X2 +am3X3 + … + amnXn≤ bm
dan X1,X2, …, Xn ≤ 0

2 Pemecahan Persoalan Linier Programing dengan Metode Grafik
Persoalan linier programing dengan dua variabel dapat dipecahkan dengan menggunakan metode geometri atau metode grafik. Langkah-langkah penyelesaian dalam metode grafik adalah:
1. Menentukan fungsi tujuan dan memformulasikannya dalam bentuk persamaan matematis
2. Mengidentifikasi batasan-batasan yang berlaku dan memformulasikanya dalam bentuk matematis
3. Menggambarkan masing-masing garis fungsi batasan dalam satu sistem sumbu x-y
4. Mencari titik yang paling menguntungkan (optimal) dihubungkan dengan fungsi tujuan.
Contoh.
Sebuah perusahaan sepatu membuat 2 jenis sepatu. Jenis pertama dengan merek I1, dengan sol dari karet dan jenis yang kedua dengan merek I2, dengan sol dari kulit. Untuk membuat sepatu-sepatu itu perusahaan memiliki 3 macam mesin. Mesin 1 khusus membuat sol dari karet, mesin 2 khusus memuat sol dari kulit, dan mesin 3 membuat bagian atas sepatu dan melakukan assembling bagian atas dengan sol. Setiap lusin sepatu merek I1 mula-mula dikerjakan dimesin 1 selama 2 jam, kemudian tanpa melalui mesin 2 terus dikerjakan di mesin 3 selama 6 jam. Sedang untuk sepatu merek I2 tidak diproses di mesin 1, tetapi pertama kali dikerjakan pada mesin 2 selama 3 jam kemudiandi mesin 3 selama 5 jam. Jam kerja maksimum setiap hari untuk mesin 1 adalah 8 jam, mesin 2 = 15 jam, dan mesin 3 = 30 jam. Sumbangan terhadap laba untuk setiap lusin sepatu merek I1 = Rp. 30.000,- dan untuk sepatu merek I2 sebesar Rp. 50.000,-. Berapa lusin sebaiknya diproduksi untuk masing-masing merek agar diperoleh laba yang maksimum.
Solusi:
Data tersebut diatas dapat disusun kedalam tabel diatas sebagai berikut:
Tabel 3.2 Data dari perusahaaan sepatu ideal


Untuk menentukan formulasi masalah pertama kali dilakukan adalah menentukan desain variabel yaitu:
X1 = Jumlah sepatu merek I1 yang akan dibuat tiap hari
X2 = Jumlah sepatu merek I2 yang akan dibuat tiap hari
Z = Jumlah laba seluruh sepatu merek I1 dan merek I2 yang akan diperoleh.
Kemudian ditentukan fungsi obyektif yaitu dengan melihat tujuan dari permasalahan. Dari soal tujuannya adalah mencari laba maksimum dimana diperoleh dari sepatu merek I1 = Rp. 30.000,- dan Merek I2 = Rp. 50.000,- sehingga dapat ditulis dalam bentuk matematis.
Maksimumkan Z = 3X1 + 5X2 ( dalam puluhan ribu rupiah)
Selanjutnya ditentukan fungsi kendalanya. Kendala muncul dengan adanya batasan kapasitas mesin 1, mesin 2 dan mesin 3 yaitu 8 jam, 15 jam dan 30 jam, sehingga dapat ditulis
1. 2 X1 ≤ 8
2. 3X2 ≤ 15
3. 6X1 + 5X2 ≤ 30

Setelah fungsi obyektif dan fungsi kendala sudah didapatkan langkah selanjutnya adalah melakukan penggambaran dalam bentuk grafik untuk masing-masing fungsi kendala.

Gambar 3.1. Grafik fungsi-fungsi batasan perusahaan sepatu “IDEAL”

Dari grafik dapat diketahui perpotongan antara dua persamaan garis dan dapat diketahui daerah feasible. Selanjutnya mencari perpotongan titik yang akan memaksimumkan fungsi obyektif. Ada dua cara untuk mencari titik yang memaksimumkan fungsi obyektif yaitu dengan menggambarkan fungsi tujuan dan dengan membandingkannya untuk masing-masing titik yang terletak di daerah feasible.
Untuk cara yang pertama, dibuat garis dengan menggunakan persamaan fungsi obyektif dengan memisalkan pada suatu harga (Z=10=3X1+5X2), kemudian garis ini digeser-geser sehingga didapatkan suatu titik didaerah feasible yang terletak paling akhir (untuk arah pergeseran ke kanan-atas)

Gambar 3.2. Grafik fungsi tujuan dan batasan-batasan perusahaan sepatu “IDEAL”

Dari hasil perrgeseran garis didapatkan suatu titik yang terakhir yaitu titik (5/6,5). Dari hasil tersebut dapat diketahuai besarnya X1 = 5/6 dan X2 = 5 dengan besarnya Z=27,5.
Cara kedua dengan membandingkan besarrnya Z untuk masing-masing titik, untuk mendapatkan nilai Z yang terbesar.
Tabel 3.3. Nilai Z pada alternative nilai X untuk memilih titik yang optimal
Z = 3X1 + 5X2

Di antara kelima alternatif tersebut yang paling besar adalah Z = 27,5 dengan X1=5/6 dan X2=5.
Dengan demikian untuk mendapatkan laba maksimum haruslah diproduksi untuk merek I1 sebesar 5/6 dosin dan merek I2 sebesar 5 dosin tiap hari, dengan laba sebesar Rp. 275.000,-.
4.3 Metode Simpleks
Apabila suatu masalah dalam LP hanya mengandung 2 variabel saja, maka akan dapat diselesaikan dengan metode grafik. Tetapi bila melibatkan lebih dari dua variabel akan sulit diselesaikan dengan metode grafik, sehingga perlu suatu metode baru untuk menyelesaikan permasalahan tersebut. Metode baru ini disebut dengan “Metode Simpleks” yang lazim digunakan untuk menyelesaikan permasalahan dalam LP dengan 3 variabel atau lebih.
Pada bagian ini akan dijelaskan mengenai langkah-langkah dalam menyelesaikan permasalahan dengan menggunakan metode simpleks dengan meggunakan tabel.

file complete dapat didownload disini dan untuk mendapatkan software simulasi metode simplex dapat didownload disini, Semoga bermanfaat.

2 komentar:

Unknown mengatakan...

Permisi ka,mau tanya, itu cara mencari yang di tabel gmna yah? Mksh mhon di jwab

Unknown mengatakan...

Permisi ka,mau tanya, itu cara mencari yang di tabel gmna yah? Mksh mhon di jwab

Posting Komentar

Twitter Delicious Facebook Digg Stumbleupon Favorites More