NURHALIMA 1

TEKNIK RISET OPERASI

NURHALIMA

CHAPTER.4

NURHALIMA 2

Kasus Khusus dalam Simpleks

NURHALIMA 3

Pendahuluan Ada beberapa kasus khusus dalam simpleks.

Kadangkala kita akan menemukan bahwa iterasi tidak berhenti, karena syarat optimalitas atau syarat kelayakan tidak pernah dapat terpenuhi.

Adakalanya juga solusi yang dihasilkan antara satu iterasi dengan iterasi berikutnya tidak berbeda. Kasus khusus ini terdiri dari solusi optimal lebih dari satu, degeneracy, solusi tidak terbatas dan solusi tidak layak.

Dua yang terakhir dapat terjadi karena kesalahan baik dalam perhitungan iteratif ataupun dalam pembentukan model atau formulasi permasalahan.

NURHALIMA 4

Solusi optimal lebih dari satuKetika 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 optimal).

Perhatikan kasus berikut :

NURHALIMA 5

DegeneracyAda 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 :

NURHALIMA 6

Solusi tidak terbatasAdakalanya kita menemukan nilai variabel

meningkat tak terbatss tanpa melanggar pembatas, yaitu ruang solusi tidak terbatas paling tidak untuk satu arah.

Sebagai akibatnya, nilai tujuan akan meningkat (untuk kasus maksimasi) atau menurun (untuk kasus minimasi) tanpa ada batas.

Dalam kasus ini, kita sebut ruang solusi dan nilai tujuan optimum tidak terbatas.

Solusi tidak terbata hanya mengindikasikan satu hal, yaitu model yang dibangun salah. Mendapatkan keuntungan yang tidak terbatas misalnya tentu tidak masuk akal

NURHALIMA 7

Salah satu yang paling umum yang menyebabkan solusi tidak terbatas adalah tidak memasukkan pembatas yang bukan redundan pada model atau parameter (konstata) beberapa pembatas tidak dihitung dengan benar.

Perhatikan kasus berikut :

NURHALIMA 8

Solusi tidak layak Jika pembatas tidak dapat terpenuhi 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 desainnya tidak memberikan solusi layak bagi model awal.

NURHALIMA 9

CONT’DMeskipun 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.