KEL 8 Metode Dual Simpleks [PDF]

Citation preview

MAKALAH PROGRAM LINIER METODE DUAL SIMPLEKS



OLEH : KELOMPOK 8



CHINDY E. NABABAN



4183530002



NURHALIZAH



4183230001



JURUSAN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS NEGERI MEDAN 2020



KATA PENGANTAR Puji syukur kami panjatkan kehadirat Tuhan yang maha esa atas berkatnya kami dapat menyelesaikan tugas makalah yang berjudul Dualitas ini tepat pada waktunya. Kami mengucapkan terima kasih kepada ibu Dr.Faiz Ahyaningsi,S.Si.,M.Si selaku dosen mata kuliah Program Linear yang telah memberikan tugas ini sehingga dapat menambah pengetahuan dan wawasan sesuai dengan bidang studi yang kami tekuni. Kami menyadari, makalah ini masih jauh dari kata sempurna, oleh karena itu kritik dan saran yang membangun akan kami nantikan demi kesempurnaan makalah ini.



Medan, April 2020



Kelompok 8



2



DAFTAR ISI KATA PENGANTAR..........................................................................................................................1 DAFTAR ISI.........................................................................................................................................3 BAB I PENDAHULUAN 1.1 Latar Belakang...........................................................................................................................4 1.2 Rumusan Masalah......................................................................................................................4 1.3 Tujuan.........................................................................................................................................4 BAB II PEMBAHASAN 2.1. Metode Dual Simpleks...............................................................................................................5 2.2. Contoh Soal Metode Dual Simpleks........................................................................................5 BAB III PENUTUP 3.1 Kesimpulan...............................................................................................................................10 3.2 Saran........................................................................................................................................10



3



BAB I PENDAHULUAN 1.1 Latar Belakang Prosedur perhitungan yang dibicarakan sejauh ini bergerak dari solusi dasar layak yang belum optimum ke solusi layak yang lain. Apakah proses tersebut akhirnya akan mencapai suatu solusi layak optimum, adalah tergantung pada kemampuan untuk mendapatkan suatu solusi dasar awal yang layak. Dalam kaitan ini, artificial variabel kadang-kadang digunakan untuk menemukan solusi awal layak. Jika formulasi LP mengandung sejumlah besar artificial variable, maka membutuhkan banyak perhitungan untuk memperoleh solusi awal layak. Karena itu, akan dijelaskan suatu prosedur perhitungan yang memberikan suatu solusi layak optimum, meskipun solusi awalnya tidak layak. Prosedur itu dinamakan dual simplex algorithm yang pertama kali disusun oleh Lemke. Algoritma ini tidak banyak digunakan di antara program-program komputer yang ada. Namun ia memainkan peranan penting dalam post optimality analysis.



1.2 Rumusan Masalah 1. Apa itu metode dual simpleks? 2. Bagaimana cara perhitungan menggunakan metode dual simpleks?



1.3 Tujuan 1. Mengetahui apa itu metode dual simpleks 2. Mengetahui cara perhitungan menggunakan metode dual simpleks



4



BAB II PEMBAHASAN



Apabila pada suatu iterasi kita mendapat persoalan programa linier yang sudah optimum (berdasarkan kondisi optimalitas), tetapi belum fisibel (ada pembatas nonnegatif yang tidak terpenuhi), maka persoalan tersebut harus diselesaikan dengan menggunakan metode dual simpleks. Syarat digunakannya metode ini adalah bahwa seluruh pembatas harus merupakan ketidaksamaan yang bertanda (  ), sedangkan fungsi tujuan bisa berupa maksimasi atau minimasi. Pada dasarnya metode dual simpleks ini menggunakan tabel yang sama seperti metode simpleks pada primal, tetapi leaving variable dan entering variable-nya ditentukan sebagai berikut : 1. Leaving variable (kondisi fisibilitas) Yang menjadi leaving variable pada dual simpleks adalah variabel basis yang memiliki harga negatif terbesar. Jika semua variabel basis telah berharga positif atau nol, berarti keadaan fisibel telah tercapai. 2. Entering variable (kondisi optimalitas) a. Tentukan perbandingan (rasio) antara koefisien persamaan z dengan koefisien persamaan leaving variable. Abaikan penyebut yang positif atau nol. Jika semua penyebut berharga positif atau nol, berarti persoalan yang bersangkutan tidak memiliki solusi fisibel. b. Untuk persoalan minimasi, entering variable adalah variabel dengan rasio terkecil, sedangkan untuk persoalan maksimasi, entering variable adalah variabel dengan rasio absolut terkecil. 2.2 Contoh Soal Metode Dual Simpleks Minimumkan : Z = 16 X1 + 20 X2 Kendala : 6 X1 + 12 X2 ≥ 72 15 X1 + 6 X2 ≥ 90 6 X1 + 5 X2 ≤ 60, X1, X2 ≥ 0



5



Syarat digunakan metode dual simpleks jika ada kendala yang merupakan ketidaksamaan bertanda ≥. Jadi ubahlah variabel S menjadi positif. Langkah 1: Formulasikan fungsi tujuan dan kendala Formulasi diatas menjadi: Minimumkan : Z – 16 X1 – 20 X2 = 0 Kendala: -6 X1 – 12 X2 + S1 = -72 -15 X1 – 6 X2 + S2 = -90 6 X1 + 5 X2 + S3 = 60 X1, X2, S1, S2, S3 ≥ 0 Langkah 2: Tentukan leaving variabelnya Seperti dalam metode simpleks, metode ini didasarkan pada optimality dan feasibility condition. Optimality condition menjamin bahwa solusi tetap optimum sedangkan feasibility condition memaksa agar solusi mencapai keadaan layak. Jadi, intinya metode dual simpleks mirip dengan metode simpleks biasa hanya saja ditranspose (baris jadi kolom & kolom jadi baris) Jadi berdasarkan soal diatas didapatkan tabel awal sebagai berikut : Iterasi 0



Basis Z S1 S2 S3



Z 1 0 0 0



X1 -16 -6 -15 6



X2 -20 -12 -6 5



S1 0 1 0 0



S2 0 0 1 0



S3 0 0 0 1



Solusi 0 -72 -90 60



Jadi, dalam metode dual simpleks, yang pertama ditentukan adalah leaving variabelnya dengan solusi yang memiliki angka negatif terbesar.



6



Langkah 3: Tentukan entering variabelnya Basis Z S1 S2 S3 Rasio



Z 1 0 0 0 -



X1 -16 -6 -15 6 16/15



X2 -20 -12 -6 5 20/6



S1 0 1 0 0 -



S2 0 0 1 0 -



S3 0 0 0 1 -



Solusi 0 -72 -90 60 -



Setelah itu baru hitunglah rasionya dengan membagi angka dari baris Z dengan leaving variabelnya dan pilih rasio yang terkecil. Abaikan rasio yang memiliki angka negatif atau nol. Langkah 4: Tentukan persamaan pivot baru Dari langkah ini sudah mirip dengan langkah metode simpleks biasa, untuk lebih jelasnya tentang metode simpleks dapat dilihat pada : Pemecahan Program Linear Metode Simpleks, jadi berdasarkan soal diatas didapatkan baris pivot barunya adalah : Basis Z S1 X1 S3



Z 1



X1



X2



S1



S2



S3



Solusi



0



1



2/5



0



-1/15



0



6



Langkah 5: Tentukan persamaan baru selain pivot baru Setelah mendapat persamaan pivot baru, langkah selanjutnya adalah mengisi persamaan lainya yang masih kosong. Rumus untuk menentukan persamaan baru selain persamaan pivot baru adalah sebagai berikut: Persamaan baru = (persamaan lama) – (persamaan pivot baru x koefisien kolom pivot) Persamaan Z baru : (-16) – (1 x -16) = 0 (-20) – (2/5 x -16) = -68/5 (0) – (0 x -16) = 0 (0) – (-1/15 x -16) = -16/15 (0) – (0 x -16) = 0 (0) – (6 x -16) = 96   Persamaan S1 baru : (-6) – (1 x -6) = 0



7



(-12) – (2/5 x -6) = -48/5 (1) – (0 x -6) = 1 (0) – (-1/15 x -6) = -2/5 (0) – (0 x -6) = 0 (-72) – (6 x -6) = -36   Persamaan S3 baru : (6) – (1 x 6) = 0 (5) – (2/5 x 6) = 13/5 (0) – (0 x 6) = 0 (0) – (-1/15 x 6) = 2/5 (1) – (0 x 6) = 1 (60) – (6 x 6) = 24 Setelah mencari persamaan Z, S1 dan S3 baru kemudian tabulasikan dalam tabel simpleks sebagai berikut : Iterasi 1



Basis Z S1 X1 S3



Z 1 0 0 0



X1 0 0 1 0



X2 -68/5 -48/5 2/5 13/5



S1 0 1 0 0



S2 -16/5 -2/5 -1/15 2/5



S3 0 0 0 1



Solusi 96 -36 6 24



Langkah 6: Lanjutkan Perbaikan-Perbaikan Setelah didapatkan persamaan baru, periksa kembali apakah solusi masih ada yang bertanda negatif atau tidak, jika masih ada berarti solusi belum optimal sehingga perlu diulangi kembali dari langkah ke-2.



8



Dari persamaan diatas didapatkan masih adanya solusi yang negatif, sehingga perlu dilakukan langkah-langkah perbaikan dengan mengulangi langkah ke-2.Sehingga didapatkan tabel berikut: Iterasi 2



Basis Z S1 X1 S3



Z 1 0 0 0



X1 0 0 1 0



X2 0 1 0 0



S1 -17/12 -5/48 1/24 13/48



S2 -1/2 1/24 -1/12 7/24



S3 0 0 0 1



Solusi 147 15/4 9/2 57/4



Berdasarkan iterasi awal terlihat bahwa meskipun koefisien persamaan Z sudah memenuhi kondisi optimal (barisan Z sudah nol atau negatif untuk kasus minimasi), tetapi variabelvariabel basis awalnya tidak memberikan solusi awal yang feasibel (S1, S2 berharga negatif). Solusi optimal dan feasibel tercapai pada iterasi kedua. Selain untuk menghindari perhitungan yang rumit, metode dual simpleks sangat penting untuk digunakan pada analisis sensitivitas. Hal ini terjadi apabila suatu pembatas baru ditambahkan (atau pembatas lama diubah), pada suatu persoalan yang sudah mencapai solusi optimal dan mengakibatkan solusi tidak feasibel, sehingga untuk menyelesaikannya digunakan metode dual simpleks.



9



BAB III PENUTUP 3.1 Kesimpulan Metode dual simpleks ini juga sangat penting untuk digunakan dalam analisis sensitivitas. Sebagai contoh, hal ini akan terjadi apabila suatu pembatas baru ditambahkan ke dalam persoalan semula setelah persoalan itu mencapai solusi optimum. Apabila ternyata bahwa pembatas baru ini tidak terpenuhi oleh solusi optimum yang telah dicapai itu, maka persoalannya akan menjadi optimum, tetapi tidak fisibel, sehingga untuk menyelesaikan ketidakfisibelannya ini perlu digunakan metode dual simpleks.



3.2 Saran Penulis menyadari bahwa makalah diatas banyak sekali kesalahan dan jauh dari kesempurnaan. Maka dari itu penulis mengharapkan saran dan kritik mengenai pembahasan makalah dalam kesimpulan di atas.