Thursday, May 4, 2017

Metode Dual Simpleks

metode dual simpleks
Sebelum masuk ke materi dual simpleks ini ada baiknya anda memahami lebih lanjut mengenai Masalah Minimasi Metode Simpleks

Prosedur perhitungan yang pada bagian sebelumnya berkisar dari solusi dasar feasibel yang belum optimal menuju ke solusi feasibel optimal. Apakah proses tersebut akhirnya akan mencapai solusi feasibel optimal adalah tergantung pada kemampuan untuk mendapatkan suatu solusi dasar awal yang feasibel.

Dalam kaitan ini, variabel artificial R dapat digunakan untuk menemukan solusi awal feasibel. Jika formulasi program linear mengandung banyak variabel artificial, akan membutuhkan banyak perhitungan untuk memperoleh solusi awal feasibel.

Untuk menghindari masalah tersebut dapat digunakan suatu prosedur yang disebut metode dual simpleks. Metode ini meskipun pada solusi awalnya tidak feasibel. Pada dasarnya metode dual simpleks menggunakan tabel yang sama seperti metode dual simpleks pada primal, tetapi leaving variabel dan entering variabelnya ditentukan sebagai berikut :

1. Leaving Variabel
Sebagai leaving variabel adalah variabel basis yang memiliki harga negatif angka terbesar. Jika semua variabel basis beharga positif atau nol berarti keadaan feasibel telah tercapai.

2. Entering Variabel
  • Tentukan rasio antara koefisien persamaan Z dengan koefisien persamaan leaving variabel. Abaikan penyebut positif atau nol. Jika semua penyebut beharga positif atau nol, berarti persoalan yang bersangkutan tidak memiliki solusi feasibel.
  • Untuk persoalan minimasi, entering variabel adalah variabel dengan rasio terkecil. Sedangkan untuk persoalan maksimasi entering variabel adalah variabel dengan rasio terkecil.


Contoh :

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

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
-6 X1 -12 X2 +S1 = -72
-15 X1 -6 X2 + S2= - 90
6 X1 +5 X2 + S3= 60
X1, X2, S1, S2, S30


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 bedasarkan soal diatas didabatkan tabel awal sebagai berikut :
IterasiBasis Z X1 X2 S1 S2 S3 Solusi
0Z1 -16-200000
S10 -6-12100-72
S20 -15-6010-90
S30 6500160
Jadi, dalam metode dual simpleks, yang pertama ditentukan adalah leaving variabelnya dengan solusi yang memiliki angka negatif terbesar.

Langkah 3 : Tentukan entering variabelnya

Basis Z X1 X2 S1 S2 S3 Solusi
Z1 -16-200000
S10 -6-12100-72
S20 -15-6010-90
S30 6500160
Rasio- 16/1520/6----
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 bedasarkan soal diatas didapatkan baris pivot barunya adalah :
Basis Z X1 X2 S1 S2 S3 Solusi
Z1
S1
X10 12/50-1/1506
S3

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
(-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 :
IterasiBasis Z X1 X2 S1 S2 S3 Solusi
1Z1 0-68/50-16/15096
S100-48/51-2/50-36
X10 12/50-1/1506
S30013/502/5124

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. Dari persamaan diatas didapatkan masih adanya solusi yang negatif, sehingga perlu dilakukan langkah-langkah perbaikan dengan mengulangi langkah ke-2.Sehingga didapatkan tabel berikut :

IterasiBasis Z X1 X2 S1 S2 S3 Solusi
2Z1 00-17/12-1/20147
X20 01-5/481/24015/4
X10 101/24-1/1209/2
S30 0013/487/24157/4

Bedasarkan iterasi awal terlihat bahwa meskipun koefisien persamaan Z sudah memenuhi kondisi optimal (barisan Z sudah nol atau negatif untuk kasus minimasi), tetapi variabel-variabel basis awalnya tidak memberikan solusi awal yang feasibel (S1, S2 beharga 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 dirubah), pada suatu persoalan yang sudah mencapai solusi optimal dan mengakibatkan solusi tidak feasibel, sehingga untuk menyelesaikanya digunakan metode dual simpleks.


EmoticonEmoticon