1. Pengertian Metode Dual Simpleks
Metode simpleks adalah teknik untuk
menyelesaikan program linier yang tidak mampu diselesaikan oleh metode grafis.
Metode simpleks sendiri memiliki kerangka berpikir beberapa macam yaitu dengan
menggunakan BFS (basis fesibel solution) dan metode simpleks dengan menggunakan
tabel. Metode simpleks dengan menggunakan tabel hanya memuat tiga informasi
penting yaitu koefisien pada variabel, konstanta pada ruas kanan persamaan dan
variabel basis yang muncul untuk setiap persamaan.
Langkah langkah metode simpleks
tabel:
1) Inisialisasi
Langkah pertama yaitu memasukkan
variabel slack. Kemudian pilihlah variabel keputusan yang kemudian akan
dijadikan sebagai variabel nonbasis awal. Lalu pilihlah varibel slack yang akan
dijadikan sebagai variabel basis awal.
2) Uji Optimalitas
Dalam uji optimalitas, BFS saat ini
dapat dikatakan optimal apabila setiap koefisien dalam baris nol adalah
nonnegatif, sehingga langkah-langkah dalam metode simpleks tabel dapat selesai.
Namun apabila setiap koefisien dalam baris nol adalah bukan nonnegatif, maka langkah selanjutnya
adalah iterasi untuk mendapatkan BFS berikutnya.
3) Iterasi
- Langkah 1:
Tentukanlah variabel basis yang
masuk dengan memilih variabel dengan koefisien negatif yang mempunyai nilai
absolut paling besar (paling negatif). Kemudian letakkanlah kotak di sekitar
kolom dibawah koefisien tersebut, kolom ini sering disebut kolom sumbu atau pivot column.
- Langkah 2:
Langkah selanjutnya yaitu dengan
menentukan variabel basis yang keluar. Hal ini dapat dilakukan dengan
menerapkan uji rasio minimum yaitu dengan cara:
·
Mengambil
masing-masing koefiien dalam kolom sumbu yang positif
·
Membagi
masing-masing angka pada ruas kanan dengan koefisien pada kolom sumbu dalam
baris yang sama
·
Tentukanlah
baris mana yang mempunyai rasio yang paling kecil
·
Variabel
basis pada baris adalah variabel basis yang keluar, kemudian gantilah variabel
itu dengan variabel basis yang masuk dalam kolom variabel basis tabel simpleks
yang berikutnya.
Kemudian letakkanlah kota disekitar
baris ini yang biasa disebut baris sumbu (pivot
row) dan angka yang berada dalam baris sumbu dan kolom sumbu disebut angka
sumbu (pivot number).
- Langkah 3:
Langkah selanjutnya adalah carilah
BFS baru dengan menggunakan operasi
baris dasar. Hal ini dimaksudkan untuk membentuk tabel simpleks yang baru.
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.
2. Contoh & Kasus Metode Dual Simpleks
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. 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.
¾ Kolom pivot adalah kolom X1
sumber :
