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.
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.
KASUS KHUSUS DALAM SIMPLEKS
Ada
beberapa kasus khusus dalam simpleks.
Kadang kala kita akan menemukan bahwa iterasi tidak berhenti, karena
syarat optimalitas atau syarat kelayakan tidak pernah dapat dipenuhi. Adakalanya juga solusi yang dihasilkan antara
satu iterasi dengan iterasi berkutnya tidak berbeda. Kasus khusus ini terdiri dari solusi optimal
lebih dari satu, degeneracy, solusi tidak terbatas dan solusi tidak layak. Dua terakhir dapat terjadi karena kesalahan
baik dalam perhitungan iteratif ataupun dalam pembentukan model atau formulasi
permasalahan.
Solusi
Optimal Lebih dari satu Ketika fungsi objektif paralel terhadap pembatas yang
dipenuhi dalam arti persamaan oleh solusi optimal, fungsi objektif akan
mengasumsikan nilai optimal sama pada lebih dari satu titik solusi.
Kondisi
seperti ini kita kenal dengan solusi optimal lebih dari satu (alternative
optima). Perhatikan kasus berikut:
Maks z = 2x1 +
4x2
Terhadap x1
+ 2x2 ≤ 5
x1
+ x2 ≤ 4
x1,
x2 ≥ 0
Perhatikan nilai baris z untuk variabel x1 juga menjadi nol saat x2 berubah menjadi variabel masuk. Jika iterasi tersebut kita lanjutkan dengan memilih x1 sebagai variabel masuk, maka akan didapatkan tabel hasil iterasi kedua berikut:
Dalam praktek, pengetahuan akan solusi optimum yang lebih dari satu akan sangat bermanfaat karena manajemen mempunyai kesempatan untuk memilih salah satu sesuai dengan situasi yang mereka miliki tanpa harus merusak nilai tujuan.
Degeneracy
Pada bagian di atas,
ada kemungkinan saat akan menentukan sel keluar, rasio pembagian terkecil lebih
dari satu, dan kita akan memilih salah satu secara sembarang. Jika hal ini terjadi, satu atau lebih
variabel akan sama dengan nol (0) pada iterasi selanjutnya. Solusi pada iterasi dimana satu atau lebih
variabel mempunyai nilai nol (0) kita sebut sebagai degeneracy. Degeneracy
terjadi secara praktek karena ada minimum satu fungsi kendala yang
redundan. Dalam iterasi, kita dapat
mengenalinya dengan cara berikut:
Maks z = 3x1
+ 9x2
Terhadap x1
+ 4x2 ≤ 8
x1
+ 2x2 ≤ 4
x1,
x2 ≥ 0
Kalau anda perhatikan tabel di atas, ada dua kandidat baris pivot, sehingga ada dua kandidat variabel keluar. Kita dapat memilih salah satu. Jika kita pilih baris s1 maka solusi pada iterasi pertama adalah sebagai berikut:
Nilai kanan s2 menjadi 0 dan tabel belum optimum. Variabel x1 menjadi variabel masuk dan s2 menjadi variabel keluar. Iterasi berikutnya sebenarnya tidak mengubah solusi optimal, seperti yang ditunjukkan tabel di bawah ini.
Melihat pembatas yang redundan sangat mudah menggunakan solusi grafik. Garis dari fungsi pembatas yang redundan melewati hanya salah satu titik pada daerah penyelesaian yaitu solusi optimal, dan hal ini sebenarnya tidak berarti dalam penentuan solusi optimal.
Karena
tanpa garis fungsi pembatas itupun, solusi optimal sudah dapat diidentifikasi
menggunakan fungsi pembatas yang lain. Dari sudut pandang teoritis, degeneracy mempunyai implikasi dua. Pertama, berhubungan dengan fenomena
pengulangan. Iterasi 1 dan 2 di atas
hanya merupakan pengulangan yang memberikan nilai tujuan sama, yaitu 18. Secara umum dapat diterima, pada kasus ini
prosedur simpleks akan terus berulang tanpa ada akhir tapi tidak memperbaiki
solusi. Kedua, meskipun variabel basis
dan non basis berbeda pada setiap iterasi, tetapi nilai semua variabel dalam
iterasi adalah sama, yaitu x1 = 0, x2 = 2, s1
= 0, s2 = 0 dan z = 18.
Solusi
Tidak Terbatas
Ada
kalanya kita menemukan nilai variabel meningkat tak terbatas tanpa melanggar
pembatas, artinya ruang solusi tidak terbatas paling tidak untuk satu
arah. Sebagai akibatnya, nilai tujuan
akan meningkat (untuk kasus maksimisasi) atau menurun (untuk kasus minimisasi)
tanpa ada batas. Dalam kasus kita sebut
ruang solusi dan nilai tujuan optimum tidak terbatas. Solusi tidak terbatas
hanya mengindikasikan satu hal, yaitu model myang dibangun salah. Mendapatkan keuntungan yang tidak terbatas
misalnya tentunya tidak masuk akal.
Salah satu yang paling umum yang menyebabkan solusi tidak terbatas adalah
tidak memasukan pembatas yang bukan redundan pada model atau parameter
(konstanta) beberapa pembatas tidak dihitung dengan benar. Perhatikan kasus berikut:
Maks z = 2x1
+ x2
Terhadap x1
- x2 ≤ 10
2x1 ≤ 40
x1,
x2 ≥ 0
Jika iterasi itu diteruskan, tidak akan pernah berhenti. Nilai z akan meningkat terus. Pada tabel awal sebenarnya kita sudah dapat mengidentikasi bahwa nilai tujuan akan meningkat terus tanpa ada batas dengan memperhatikan koefisien pembatas kolom x2 yang bernilai -1 dan 0. Nilai koefisien pembatas ini menunjukkan bahwa x2 dapat dinaikkan tanpa ada batas, sehingga nilai z juga akan meningkat tanpa ada batas.
Solusi
Tidak Layak
Jika
pembatas tidak dapat dipenuhi secara bersamaan, maka kita berhadapan dengan
solusi tidak layak. Solusi tidak layak
tidak akan pernah terjadi jika semua fungsi kendala menggunakan pertidaksamaan ≤ (asumsikan nilai kanan adalah positif),
karena variabel slack selalu memberikan solusi layak. Solusi optimal dapat terjadi jika fungsi
pembatas ada yang menggunakan pertidaksamaan ≥, kita menggunakan variabel buatan sebagai
variabel basis awal, dimana variabel buatan berdasarkan desainnay tidak
memberikan solusi layak bagi model awal.
Meskipun dalam prosedur iterasinya kita memaksa variabel buatan bernilai
0 pada solusi optimum, hal ini hanya akan terjadi jika model mempunyai ruang
solusi layak. Sering juga terjadi,
minimum satu variabel buatan bernilai positif pada solusi optimum. Hal ini mengindikasikan bahwa permasalahan
tidak mempunyai solusi layak.
Dari sudut pandang praktikal, solusi tidak
layak terjadi karena model tidak diformulasikan dengan benar, dimana beberapa
pembatas saling bertentangan. Hal lain
yang menyebabkan solusi tidak layak adalah bahwa pembatas tidak dimaksudkan
untuk dipenuhi secara bersamaan.
Perhatikan kasus berikut:
Maks z = 3x1
+ 2x2
Terhadap 2x1
+ x2 ≤ 2
3x1
+ 4x2 ≥ 12
x1,
x2 ≥ 0
Pada
iterasi optimal, variabel buatan A1 masih bernilai positif dan ≥
dari 0. Hal ini mengindikasikan bahwa
ruang solusi tidak layak.
Sumber : http://www.academia.edu/11623031/METODE_BIG_M
Komentar
Posting Komentar