modul 6 sm-metode simpleks

Modul 6 Scientific Management 1

MODUL 6 PROGRAMA LINIER-METODE SIMPLEKS Pengantar Metode simpleks akan sangat efektif digunakan untuk persoalan programa linier dengan lebih dari 2 variabel keputusan. Untuk persoalan PL dengan 2 variabel keputusan, dapat juga diselesaikan dengan metode ini. Sebagai catatan, sangat diperlukan pemahaman dan penguasaan yang utuh terhadap metode OBE (Operasi Baris Elementer) untuk menyelesaikan suatu persoalan programa linier. Langkah Metode Simpleks Berikut tahap-tahap penyelesaian programa linier dalam metode simpleks : 1. Ubah formulasi programa linier ke bentuk standar, baik fungsi tujuan maupun fungsi pembatasnya 2. Untuk fungsi pembatas dengan tanda () tambahkan variable slack. 3. Untuk fungsi pembatas dengan tanda () , kurangidulu dengan variable

surplus, kemudian tambahkan variable artificial. 4. Untuk fungsi pembatas dengan tanda (=), tambahkan variable artificial. 5. Untuk fungsi tujuan, tambahkan tujuan variable slack (dengan koefisien 0), variable surplus (dengan koefisien )), dan variable artificial (dengan koefisien M). Siapkan tabulasi untuk proses iterasi simpleks dengan memasukkan fungsi pembatas yang standar, demikian pula fungsi tujuannya. Tabulasi ini terdiri atas kolombasis, kolom variable keputusan, kolom ruas kanan, dan baris Zj Cj (untuk persoalan maksimasi atau minimasi). Prosedur tabulasi simpleks adalah sebagai berikut : 1. Lakukan serangkaian OBE sehingga diperoleh jawaban optimal

2 Modul 6 Scientific Management

2. Tentukan variable masuk (dari elemen Zj Cj terkecil) 3. Tentukan variable keluar (dari rasio antara ruas kanan dengan koefisien variable masuk, pilih yang terkecil) 4. Tentukan pivot (elemen penentu iterasi simpleksdan diubah nilainya menjadi 1), dari perpotongan antara variable masuk dan variable keluar. 5. Lakukan OBE berdasarkan pivot ini untuk baris lainnya, termasuk Zj Cj. 6. Proses iterasi dihentikan (karena artinya solusi sudah optimal) bila semua nilai pada Zj Cj 0 . Perhatikan contah soal pada modul sebelumnya, dengan formulasi sebagai berikut : Max Z = 250 X1 + 200 X2 S/t 20 X1 + 4 5 X2 10750 30 X1 + 25 X2 9750 Bentuk standar dari persoalan tersebut adalah sebagai berikut : Max Z = 250 X1 + 200 X2 S/t 20 X1 + 45 X2 + X3 = 10750 30 X1 + 25 X2 + = 9750 dimana : X3 = variable slack atau tambahan untuk fungsi pembatas 1 X4 = variable slack atau tambahan untuk fungsi pembatas 2 Proses tabulasi simpleks : Basis X1 X2 X3 X4 Ruas Kanan Rasio X3 20 45 1 1 10750 537.5 X4 30 25 0 0 9750 325 Zj Cj -250 -200 0 0 0 Nilai Zj Cj diperoleh dengan cara 0 250 = - 250 untuk kolom X1 dan 0-200 = - 200 untuk kolom X2


Elemen baris dan kolom (I;j) ditujukan untuk elemen baris i dan kolom variable keputusan j , misalnya untuk elemen (1;1) bebrarti elemen baris 1 (variable basis pertama) dan elemen kolom 1 (variable keputusan pertama), demikian seterusnya. Iterasi 1 : Variabel masuk adalah X1 (dari nilai Zj Cj terkecil atau negative terbesar). Variabel yang keluar adalah X3 (dari rasio ruas kanan RK terhadap koefisien kolom X 1 yang terkecil). Pivot ada pada elemen (2;1), maka semua elemen pada baris 2 dibagi dengan 30, sehingga elemen (2;1) = 30/30 = 1, elemen (2;2) = 25/30 =0.83 , elemen (2;3)=0/30 = 0, elemen (2;4)= 1/30 = 0.03 , dan elemen (2;5) = 10750/30 = 325. Hasil Iterasi 1 : Basis X1 X2 X3 X4 Ruas Kanan X3 0 28.33 1 -0.67 4250 X1 1 0.83 0 0.03 325 Zj Cj 0 8.33 0 8.33 81250 Hasil perhitungan untuk baris 1 dengan pembulatan hingga 2 desimal : Elemen (1;1) = (-20) x (1) + (20) = 0 Elemen (1;2) = (-20) x (0.83) + (45) = 28.33 Elemen (1;3) = (-20) x (0) + (1) = 1 Elemen (1;4) = (-20) x (0.03) + (0) = -0.67 Elemen (1;5) = (-20) x (325) + (10750) = 4250 Hasil perhitungan untuk baris 3 dengan pembulatan hingga 2 desimal : Elemen (3;1) = (250) x (1) + (-250) = 0 Elemen (3;2) = (250) x (0.83) x (-200) = 8.33 Elemen (3;3) = (250) x (0) + (0) = 0 Elemen (3;4) = (250) x (0.03) +(0) = 8.33 Elemen (3;5) = (250) x (325) +(0) = 81250


Jika semua komponen pada baris Zj Cj 0, berarti solusi sudah optimal. Jawaban : X1 = 325, X 2 = 0, X3 = 4250, X4 = 0 dan Z = 81.250 (hasilnya sama seperti solusi dengan metode grafik, yaitu hanya membuat meja saja 325 unit). Z = 250 (325)+ 200(0) =81.250 (atau Rp 81.250.000,-) Persoalan dengan 3 variabel keputusan dan 3 fungsi pembatas : Max Z = 200 X1 + 220 X2 + 180 X3 S/t 4 X1 + 6 X2 + 9 X3 9200 8 X1 + 3 X2 + 5 X3 7800 5 X1 + 7 X2 + 4 X3 8300 Misalkan X1 = jumlah meja, X2 = jumlah lemari , dan X3 = jumlah kursi yang dapat dijual dengan harga berturut-turut sebesar 200, 220 dan 180 juta rupiah. Kasus seperti ini (lebih dari 2 variabel keputusan) memang perlu diselesaikan dengan metode simpleks. Bentuk standar : Max Z = 200 X1 + 220 X2 + 180 X3 S/t 4 X1 + 6 X2 + 9 X3 + X4 = 9200 8 X1 + 3 X2 + 5 X3 + X5 = 7800 5 X1 + 7 X2 + 4 X3 + X6 = 8300 X4 , X5 dan X6 masing-masing adalah variable slack (tambahan) untuk fungsi pembatas 1, 2 dan 3.


Tabulasi simpleks dan proses iterasinya adalah sebagai berikut : Basis X1 X2 X3 X4 X5 X6 Ruas

Kanan

Rasio

X4 4 6 9 1 0 0 9200 1533 X5 8 3 5 0 1 0 7800 2600 X6 5 7 4 0 0 1 9300 1186

Zj Cj -200 -220 -180 0 0 0 Basis adalah X4, X5, dan X6 Variabel yang masuk adalah X2 (karena nilai Zj Cj terkecil atau negatif terbesar) Variabel yang keluar adalah X6 (karena nilai rasio ruas kanan dan koefisiennya yang terkecil). Elemen (3;2) adalah pivot, maka semua nilai pada baris 3 dibagi dengan 7. Lakukan OBE pada baris 1,2 dan 4 dengan merujuk kepada baris 3. Hasil iterasi 1 :

Basis X1 X2 X3 X4 X5 X6 Ruas

Kanan

Rasio

X4 -0.286 0 5.571 1 0 -0.857 2086 374 X5 5.857 0 3.286 0 1 -0.426 4243 1291 X2 0.714 1 0.571 0 0 0.143 1186 2075

Zj Cj -42.857 0 -54.286 0 0 31.429 260857 Dari hasil iterasi 1, diketahui hal-hal berikut : Basis adalah X4 , X5 dan X2 Baris Zj Cj masih ada yang bernilai negatif, berarti masih harus dilanjutkan ke iterasi selanjutnya Variabel masuk berikutnya adalah X3 Variabel yang keluar dari basis berikutnya adalah X4


Hasil iterasi 2 : Basis X1 X2 X3 X4 X5 X6 Ruas

Kanan

Rasio

X3 -0.051 0 0.179 1 0 -0.154 374 - X5 6.026 0 -0.590 0 1 0.077 3013 500 X2 0.744 1 -0.103 0 0 0.231 972 1307

Zj Cj -45.641 0 9.743 0 0 23.077 281179 Basis adalah X3 , X5 dan X2 Nilai pada baris Zj Cj masih negatif, berarti harus lanjut ke iterasi berikutnya Variabel masuk berikutnya adalah X1 Variabel yang keluar berikutnya adalah X5 Hasil iterasi 3 :

Basis X1 X2 X3 X4 X5 X6 Ruas

Kanan

X3 0 0 1 0.174 0.009 -0.153 400 X1 1 0 0 -0.098 0.166 0.013 500 X2 0 1 0 -0.123 -0.123 0.221 600

Zj Cj 0 0 0 7.574 7.574 23.660 304000 Karena semua Zj Cj 0 maka solusi sudah optimal Diperoleh : Jumlah meja X1 = 500 unit Jumlah lemari X2 = 600 unit Jumlah kursi X3 = 400 unit Total pendapatan Z = 304.000 (atau Rp 304.000.000)


Perhatikan soal berikut : Sebuah pabrik mobil menghasilkan 3 jenis sedan. Harga jual ketiga jenis sedan tersebut adalah 300, 500 dan 400 juta rupiah per unit. Sebut saja merk Jazz, Accord dan City. Kebutuhan proses produksinya untuk ketiga merk sedan tersebut dapat ditabelkan sebagai berikut : KEPERLUAN JAZZ ACCORD CITY Bahan Baku 10 20 15 Tenaga Kerja 20 15 30 Lainnya 10 30 40 Kapasitas yang tersedia untuk bahan baku = 15000 (satuan), tenaga kerja = 20000 (satuan) dan lainnya = 26500 (satuan). Bagaimana formulasi dan solusinya ? Jawab ; Jazz = X1 , Accord = X2 , City = X3 Fungsi tujuan : Max Z = 300 X1 + 500 X2 + 400 X3 Fungsi pembatas : 10 X1 + 20 X2 + 15 X3 15.000 20 X1 + 15 X2 + 30 X3 20.000 10 X1 + 30 X2 + 40 X3 26.500 Formula standar ; Max Z = 300 X1 + 500 X2 + 400 X3 S/t 10 X1 + 20 X2 + 15 X3 + X4 = 15.000 20 X1 + 15 X2 + 30 X3 + X5 = 20.000 10 X1 + 30 X2 + 40 X3 + X6 = 26.500


Solusi untuk iterasinya : Basis X1 X2 X3 X4 X5 X6 Ruas

Kanan

Rasio

X4 10 20 15 1 0 0 15000 750 X5 20 15 30 0 1 0 20000 1333.3 X6 10 30 40 0 0 1 26500 883.3

Zj Cj -300 -500 -400 0 0 0 Iterasi 1 Basis X1 X2 X3 X4 X5 X6 Ruas

Kanan

Rasio

X2 0.5 1 0.75 0.05 0 0 750 1500 X5 12.5 0 18.75 -0.75 1 0 8750 700 X6 -5 0 17.5 -1.5 0 1 4000 700

Zj Cj -50 0 -25 0 0 0 375000 - Iterasi 2 Basis X1 X2 X3 X4 X5 X6 Ruas

Kanan

Rasio

X2 0 1 0 0.08 -0.04 0 400 X1 1 0 1.5 -0.06 0.08 0 700 X6 0 0 25 -1.8 0.4 1 7500

Zj Cj 0 0 50 22 4 0 410000 - Awal iterasi : Variabel masuk adalah X2 dan yang keluar X4 Rasio Ruas Kanan/koefisien terkecil ada pada baris 1 Pivot ada pada elemen (1;2) Lakukan serangkaian OBE pada baris 2,3 dan 4 dengan mengacu pada baris 1


Hasil iterasi 1 : Variabel yang akan masuk adalah X1 dan yang keluar X5 Rasio Ruas Kanan/Koefisien terkecil ada pada baris 2 Pivot ada pada elemen (2;1) Lakukan serangkaian OBE pada baris 1,3 dan 4 dengan mengacu pada baris 2 Komponen Zj Cj masih ada yang negative, artinya harus ada iterasi 2 Hasil iterasi 2 : Semua elemen Zj Cj sudah nol atau positif, artinya solusi sudah optimal, diperoleh : X1 = 400 (mobil Jazz 400 unit) X2 = 700 (mobil Accord 700 unit) X3 = 0 (tidak perlu membuat mobil City) Z = 410.000 (total keuntungan) Referensi : Materi diambil dari buku : Noer, Bustanul Arifin. 2010. Belajar Mudah Riset Operasional. Yogyakarta : ANDI.

modul 6 sm-metode simpleks

Documents