Minggu, 11 Juni 2017

METODE DUAL SIMPLEKS

METODE DUAL SIMPLEKS


Metode dual simpleks digunakan jika tabel optimal tidak layak. Jika fungsi kendala ada yang menggunakan pertidaksamaan ≥ dan tidak ada = dalam bentuk umum PL, maka metode dual simpleks dapat digunakan. Kita selesaikan contoh di bawah ini.
Min z = 21x1 + 18x2 + 15x3
Terhadap       90x1 + 20x2 + 40x3 ≥ 200
                      30x1 + 80x2 + 60x3 ≥ 180
                      10x1 + 20x2 + 60x3 ≥ 150
                                 x1, x2, x3 ≥ 0
semua kendala menggunakan pertidaksamaan ≥. Kendala dengan pertidaksamaan ≥ dapat diubah ke pertidaksamaan ≤ dengan mengalikan pertidaksamaan dengan -1. Bentuk umum PL di atas berubah menjadi:
Min z = 21x1 + 18x2 + 15x3
Terhadap          -90x1 - 20x2 - 40x3 ≤ -200
                         -30x1 - 80x2 - 60x3 ≤ -180
                         -10x1 - 20x2 - 60x3 ≤ -150 
                                   x1, x2, x3 ≥ 0
Semua fungsi kendala sudah dalam bentuk pertidaksamaan ≤, maka kita kita hanya perlu menambahkan variabel slack untuk mengubah bentuk umum ke bentuk baku/standar. Variabel slack akan berfungsi sebagai variabel basis awal.
Bentuk Baku/standar:
Min z = 21x1 + 18x2 + 15x3 + 0s1 + 0s2 + 0s3
Terhadap -90x1 - 20x2 - 40x3 + s1 = -200
-30x1 - 80x2 - 60x3 + s2 = -180
-10x1 - 20x2 - 60x3 + s3 = -150
x1, x2, x3, s1, s2, s3 ≥ 0
METODE DUAL SIMPLEKS
Metode dual simpleks digunakan jika tabel optimal tidak layak. Jika fungsi kendala ada yang menggunakan pertidaksamaan ≥ dan tidak ada = dalam bentuk umum PL, maka metode dual simpleks dapat digunakan. Kita selesaikan contoh di bawah ini.
Min z = 21x1 + 18x2 + 15x3
Terhadap       90x1 + 20x2 + 40x3 ≥ 200
                      30x1 + 80x2 + 60x3 ≥ 180
                      10x1 + 20x2 + 60x3 ≥ 150
                                 x1, x2, x3 ≥ 0
semua kendala menggunakan pertidaksamaan ≥. Kendala dengan pertidaksamaan ≥ dapat diubah ke pertidaksamaan ≤ dengan mengalikan pertidaksamaan dengan -1. Bentuk umum PL di atas berubah menjadi:
Min z = 21x1 + 18x2 + 15x3
Terhadap          -90x1 - 20x2 - 40x3 ≤ -200
                         -30x1 - 80x2 - 60x3 ≤ -180
                         -10x1 - 20x2 - 60x3 ≤ -150 
                                   x1, x2, x3 ≥ 0
Semua fungsi kendala sudah dalam bentuk pertidaksamaan ≤, maka kita kita hanya perlu menambahkan variabel slack untuk mengubah bentuk umum ke bentuk baku/standar. Variabel slack akan berfungsi sebagai variabel basis awal.
Bentuk Baku/standar:
Min z = 21x1 + 18x2 + 15x3 + 0s1 + 0s2 + 0s3
Terhadap -90x1 - 20x2 - 40x3 + s1 = -200
-30x1 - 80x2 - 60x3 + s2 = -180
-10x1 - 20x2 - 60x3 + s3 = -150
x1, x2, x3, s1, s2, s3 ≥ 0
Tabel di atas optimal tapi tidak layak (ingat, untuk fungsi tujuan minimisasi, tabel sudah optimal jika semua koefisien baris tujuan sudah negatif atau 0). Untuk membuat tabel tersebut layak, kita harus gunakan metode dual simpleks. Langkah-langkah penyelesaian simpleks menggunakan metode dual adalah: 1.
1.      Tentukan baris pivot. Baris pivot adalah baris dengan nilai kanan negatif terbesar. Jika negatif terbesar lebih dari satu, pilih salah satu sembarang.
2.       Tentukan kolom pivot. Kolom pivot diperoleh dengan terlebih dahulu membagi nilai baris z dengan baris pivot. Dalam hal ini, semua nilai baris pivot dapat menjadi pembagi kecuali nilai 0. Kolom pivot adalah kolom dengan rasio pembagian mutlak terkecil. Jika rasio pembagian mutlak terkecil lebih dari satu, pilih salah satu secara sembarang.
3.      Pembentukan tabel berikutnya sama dengan prosedur dalam primal simpleks.
Gunakan tabel awal simpleks di atas.
Ø  Baris pivot adalah baris S1, baris dengan nilai kanan negatif terbesar.
6 photo 6_zps31l0h6sb.jpg

Ø  Kolom pivot adalah kolom X1
7 photo 7_zpsquuttkqe.jpg

Ø  Iterasi-1
 photo 8_zpsgksk6kh4.jpg

Ø  Iterasi-2
 photo 9_zpsl8dd4l2c.jpg

Ø  Iterasi-3
 photo 10_zpsmgsfevhv.jpg
Sumber :
- http://webcache.googleusercontent.com/search?q=cache:SBT9daUFw5YJ:ishaq.staff.gunadarma.ac.id/Downloads/files/43852/metode-big-m-dua-fase-dan-dual-simpleks.pdf+&cd=1&hl=id&ct=clnk&client=firefox-b

2 komentar: