Wednesday, April 26, 2017

Kasus Khusus Penggunaan Metode Simpleks

kasus khusus penggunaan metode simpleks
Terdapat beberapa kasus pada metode simpleks yang menyebabkan perhitungan pada metode simpleks ini menjadi sangat rumit dan tidak selesai selesai.

Kasus khusus dari penggunaan metode simpleks ini dapat berupa degenerasi, solusi optimum banyak, solusi tak terbatas, dan tidak ada solusi layak.

Berikut akan dibahas kasus khusus penggunaan metode simpleks, namun sebelum anda membaca lebih lanjut, bagi anda yang masih belum mengerti betul tentang metode simpleks, ada baiknya anda membaca artikel sebelumnya tentang : Pemecahan Program Linear Metode Simpleks.


Berikut adalah kasus khusus dalam penggunaan metode simpleks :

1. Degenerasi

Suatu program linear bersifat degenerasi apabila satu atau beberapa variabel basis beharga nol, sehingga iterasi yang dilakukan selanjutnya menjadi suatu loop yang akan kembali ke bentuk sebelumnya. 

Contoh :

Maksimumkan : Z = 12 X1 + 4 X2
Kendala :
8 X1 + 2 X2 ≤ 16
6 X1 + 3 X2 ≤ 12
X1, X2 ≥ 0

Bedasarkan persamaan diatas, lakukan penyelesaian dengan metode simpleks seperti yang sudah dijelaskan pada bagian sebelumnya tentang : Pemecahan Program Linear Metode Simpleks.
IterasiBasis Z X1 X2 S1 S2 SolusiRasio
0Z1 -12-4000-
S10 8210162
S20 6001122
IterasiBasis Z X1 X2 S1 S2 SolusiRasio
1Z1 0-13/2024-
X10 11/41/8028
S20 03/2-3/4100
IterasiBasis Z X1 X2 S1 S2 Solusi
2Z1 0012/324
X10 101/4-1/62
X20 01-1/22/30

Pada tabel diatas (iterasi 0) terdapat dua rasio minimum, maka pemilihan leaving variabel atau kolom pivot dilakukan secara sembarang. Ini menjadi sebab variabel basis bernilai nol pada iterasi pertama, yang menghasilkan solusi dasar degenerasi.

Solusi optimal tercapai pada iterasi kedua (Z = 24) yang memberikan solusi sama dengan iterasi 1. Disini terlihat adanya prosedur simpleks uang berulang akan tetapi tidak memperbaiki nilai Z. Nilai variabel dan fungsi tujuan pada iterasi 1 dan 2 sama yaitu X1 = 2, X2 = 0, S1 = 0, S2 = 0, dan Z = 24.

Meskipun pada iterasi 1 dan 2 memberikan hasil yang sama, tetapi pada iterasi 1 tetap diteruskan sampai memenuhi kondisi optimal. Mengapa kita tidak menghentikan saja perhitunganya ? Karena tidak semua persoalan degenerasi menghasilkan degenerate yang tetap, tetapi ada juga yang sifatnya temporer dimana iterasi berikutnya menghilang. Seperti yang ditunjukkan pada contoh berikut ini :

Contoh :

Maksimumkan : Z = 3 X1 + 2 X2
Kendala :
4 X1 + 3 X2 ≤ 12
4 X1 + X2 ≤ 8
4 X1 - X2 ≤ 8
X1, X2 ≥ 0

IterasiBasis Z X1 X2 S1 S2 S3 SolusiRasio
0Z1 -3-20000-
S10 43100123
S20 4101082
S30 4-100182
IterasiBasis Z X1 X2 S1 S2 S3 SolusiRasio
1Z1 0-5/403/406-
S10 021-1042
X10 11/401/4028
S30 0-20-110-
IterasiBasis Z X1 X2 S1 S2 S3 Solusi
2Z1 005/81/8017/2
X20 011/2-1/202
X10 10-1/83/803/2
S30 001-214

Pada tebel diatas, degenerasi muncul pada iterasi 1, tetapi kemudian menghilang pada iterasi kedua, dimana fungsi tujuan pun berubah dari Z = 6 menjadi Z = 17/2 pada iterasi kedua.

Degenerasi menghilang karena X2, yang menjadi entering variabel atau kolom pivot pada iterasi 1 mempunyai koefisien pembatas yang beharga negatif (= -2) yang berkorespondensi dengan basis S3 yang beharga nol.

2. Solusi Optimum Banyak

Persoalan memiliki solusi lebih dari satu apabila fungsi tujuan parallel dengan fungsi pembatas, dimana paling sedikit salah satu dari variabel non-basis (persamaan Z pada iterasi terakhir) mempunyai koefisien beharga nol.

Akibatnya walaupun variabel tersebut dinaikan harganya, harga Z tetap tidak berubah. Karena itu solusi-solusi optimum yang lain ini biasanya dapat dilakukan iterasi tambahan pada metode simpleksnya, dimana variabel-variabel non-basis berkoefisien nol itu selalu dipilih untuk menjadi entering variabel.

Contoh :

Maksimumkan : Z = 2 X1 + 4 X2
Kendala :
X1 + 2 X2 ≤ 5
X1 + X2 ≤ 4
X1, X2 ≥ 0

Bedasarkan persamaan dilakukan penyelesaian dengan metode simpleks seperti cara penyelesaian yang telah diuraikan pada bagian sebelumnya tentang : Pemecahan Program Linear Metode Simpleks.
IterasiBasis Z X1 X2 S1 S2 Solusi
0Z1 -2-4000
S10 12105
S20 11014
IterasiBasis Z X1 X2 S1 S2 Solusi
1Z1 002010
X20 1/211/205/2
S20 1/20-1/213/2
IterasiBasis Z X1 X2 S1 S2 Solusi
TambahanZ1 002010
X20 011-11
X10 10-123

Pada tabel diatas, persamaan fungsi tujuan parallel dengan persamaan pembatas pertama. Pada iterasi 1 (optimum), koefisien variabel non-basis X1 adalah nol sehingga pada iterasi berikutnya (iterasi tambahan), X1 ini dipilih menjadi entering variabel tanpa mengubah harga Z, tetapi menyebabkan berubahnya harga variabel X1 tersebut.

3. Solusi Tidak Terbatas

Penyelesaian dikatakan tidak terbatas, apabila nilai suatu fungsi tujuan dapat dibuat tak terhingga tanpa melanggar setiap batasan yang ada. Jika hal ini terjadi pada masalah maksimasi keuntungan, berarti dapat dicapai suatu tingkat keuntungan yang terbatas.

Kejadian ini dapat berarti bahwa masalah yang ada tidak dirumuskan dengan tepat. Kesalahan ini dapat berupa :
  • Adanya kendala tak berlebih yang diikut sertakan.
  • Adanya parameter dari beberapa kendala tidak diduga dengan benar.


Contoh :

Maksimumkan : Z = 6 X1 + 4 X2
Kendala :
2 X1 - 3 X2 ≤ 12
3 X1 ≤ 30
X1, X2 ≥ 0

Bedasarkan persamaan dilakukan penyelesaian dengan metode simpleks seperti cara penyelesaian yang telah diuraikan pada bagian sebelumnya tentang : Pemecahan Program Linear Metode Simpleks.
IterasiBasis Z X1 X2S1 S2 Solusi
0Z1 -6-4000
S10 2-31012
S20 300130

Pada tabel diatas X1 akan dipilih sebagai entering variabel atau kolom pivot karena memiliki koefisien negatif terbesar. Karena koefisien pembatas pada kolom X2 non-positif (negatif atau nol), berarti X2 dapat bertambah harganya secara tak terbatas, karena setiap unit penambahan X2 akan meningkatkan Z sebesar 4 (lihat persamaan fungsi tujuan) maka penambahan yang tak terbatas pada X2 akan meningkatkan harga Z secara tak terbatas.


4. Tidak Ada Solusi Layak

Contoh : 

Maksimumkan : Z = 4 X1 + 5 X2
Kendala :
3 X1 + 5 X2 ≤ 12
X1 ≤ 6
X2 ≥ 0
X1, X2 ≥ 0

Bedasarkan persamaan dilakukan penyelesaian dengan metode simpleks minimasi seperti cara penyelesaian yang telah diuraikan pada bagian sebelumnya tentang : Masalah Minimasi Metode Simpleks
IterasiBasis Z X1 X2 S1 S2 R1 S3 R2 Solusi
0Z1(-M-4) -M-50M0M0-10M
S10 351000015
R10 100-11006
R20 01000-114
IterasiBasis Z X1 X2 S1 S2 R1 S3 R2 Solusi
1Z1-2/5M-101/5M+1M0M0-7M+15
X20 3/511/500003
R10 100-11006
R20 -3/50-1/500-111
IterasiBasis Z X1 X2 S1 S2 R1 S3 R2 Solusi
2Z102/3M+5/3(M+4)/3M0M0-5M+20
X10 15/31/300005
R10 0-5/3-1/3-11001
R20 01000-114

Pada tabel terlihat bahwa pada iterasi kedua (tabel optimum), artificial variabel beharga positif (R1 = 1 dan R2 = 4). Ini sebagai indikasi ruang solusi tidak layak, dan solusi tersebut merupakan solusi optimum samaran  (pseudo optimal).


EmoticonEmoticon