Sering kita menemukan bahwa fungsi kendala tidak hanya dibentuk
oleh pertidaksamaan ≤ tapi juga oleh pertidakasamaan ≥ dan/atau
persamaan (=). Fungsi kendala dengan pertidaksamaan ≥ mempunyai
surplus variable, tidak ada slack variables. Surplus variable tidak bisa
menjadi variabel basis awal. Dengan demikian harus ditambahkan
satu variabel baru yang dapat berfungsi sebagai variabel basis awal.
Variabel yang dapat berfungsi sebagai variabel basis awal hanya
slack variables dan artificial variables (variabel buatan).
Big M vs Simpleks
• Perbedaan antara metode Big M dengan metode Simpleks terletak
pada pembentukan tabel awal.
• Jika fungsi kendala menggunakan bentuk pertidaksamaan ≥,
perubahan bentuk umum ke bentuk baku memerlukan satu variabel
surplus.
• Variabel surplus tidak dapat berfungsi sebagai variabel basis awal,
karena koefisiennya bertanda negatif.
• Sebagai variabel basis pada solusi awal harus ditambahkan satu
variabel buatan
• Variabel buatan pada solusi optimal harus bernilai 0, karena variabel
ini memang tidak ada.
Teknik Riset Operasi 13.12.11
5
• Teknik yang digunakan untuk memaksa variabel buatan bernilai 0
adalah dengan cara sebagai berikut :
• Penambahan variabel buatan pada fungsi kendala yang tidak
memiliki variabel slack, menuntut penambahan variabel buatan pada
fungsi tujuan.
• Jika fungsi tujuan adalah maksimasi, maka variabel buatan pada
fungsi tujuan mempunyai koefisien +M; jika fungsi tujuan adalah
minimasi, maka variabel buatan pada fungsi tujuan mempunyai
koefisien –M.
• Karena koefisien variabel basis pada tabel simpleks harus bernilai 0,
maka variabel buatan pada fungsi tujuan harus digantikan nilai dari
fungsi kendala yang memuat variabel buatan tersebut.
CONTOH KASUS
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 4.4 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
