KEMEROSOTAN(DEGENERACY)
A. Pendahuluan
Dalam penyelesaian masalah program linear,
kadang-kadang terjadi beberapa hal yang menyebalkan. Misalnya ketika pada masalah maksimasi,
perbaikan yang dilakukan ternyata tidak menyebabkan peningkatan nilai fungsi tujuan.
Atau bahkan dengan perbaikan yang berulang-ulang justru menyebabkan program
kembali ke program awal. Nah, hal yang demikian yang akan kita pelajari pada
bab ini. Kita akan mempelajari masalah
kemerosotan, ciri-ciri suatu masalah program linear mungkin mengalami
kemerosotan, serta cara penanggulangannya.
Setelah mempelajari bab ini, anda diharapkan memahami
penyebab kemerosotan pada masalah program linear serta mampu menanggulangi maslah kemerosotan tersebut. Sebagai
penjabaran tujuan tersebut Anda diharapkan dapat:
1. mengenali “keterikatan” dalam metode simpleks yang
menyebabkan kemerosotan;
2. mengenali
nilai nol dalam kolom kuantitas pada tabel simpleks yang menyebabkan
kemerosotan; dan
3. menanggulangi
kemerosotan pada masalah program linear.
B. Materi Pokok dan Uraian Materi
Materi Pokok: Kemerosotan
Sub Materi Pokok
1. Kemerosotan pada Masalah Program Linear
2. Penanggulangan Kemerosotan
Uraian Materi
1. Kemerosotan
pada Masalah Program Linear
Dalam bab sebelumnya telah
dipelajari bahwa metode simpleks didasarkan pada beberapa aturan yang diproses
dari program awal yang memenuhi syarat,
diperbaiki, dan diperbaiki lagi
sampai diperoleh suatu penyelesaian optimal.
Kemerosotan terjadi ketika melalui proses perbaikan tidak diperoleh
peningkatan nilai fungsi tujuan, bahkan mengalami penurunan, atau setelah melalui
perbaikan berulang-ulang ternyata program kembali ke program awal. Kasus yang
ketiga ini disebut sebagai siklus.
Program simpleks hasil perbaikan diperoleh dengan memilih sekumpulan variabel
dalam basis yang baru. Basis baru
dipilih dengan menggantikan paling sedikit satu variabel yang masih dalam
program dengan satu variabel bukan anggota basis. Variabel yang masuk dalam program perbaikan
berkaitan dengan kolom kunci dan variabel yang keluar dari basis berkaitan
dengan baris kunci.
Pemilihan kolom kunci dan
baris kunci merupakan salah satu bagian dalam algoritma simpleks. Pemilihan
kolom kunci terkait dengan tugas metode simpleks yaitu mengenali kolom dengan
nilai Zj-Cj negatif dan harga mutlaknya terbesar. Tetapi,
dalam memilih baris kunci dengan tujuan menggantikan satu variabel dalam basis
kita kadang dihadapkan pada dua kesulitan.
a.
Dalam program awal ada satu atau lebih variabel dalam
kolom kuantitas bernilai nol(ada bi dalam tabel simplek bernilai nol).
Jika ada nilai bi sama dengan nol dapat menyebabkan nilai Z
pada tabel baru tidak meningkat. Jika
ini terjadi, tidak ada jaminan bahwa
proses iterasi algoritma simpleks akan berhenti karena ada variabel yang sudah
keluar dari basis masuk lagi ke dalam program.
b.
Dalam kolom penentuan, ada nilai hasil bagi untuk dua
atau lebih variabel dalam basis bernilai sama.
Jika demikian maka akan ada “keterikatan” dalam memilih baris
kunci. Pemilihan baris kunci yang tepat
akan menyebabkan program tidak mengalami kemerosotan. pada kolom penilaian.
Perhatikan masalah program linear berikut.
Zmaks = 5X + 8Y
Hm. 4X + 6Y ≤ 24
2X
+ Y ≤ 18
3X
+ 9Y ≤ 36
X,
Y ≥ 0
Berikut ditunjukkan hasil perhitungan dengan
tabel simpleks.
Tabel 5.1.1. Tabel program Awal
|
|
|
|
5
|
8
|
0
|
0
|
0
|
24/6
= 4
18/1
= 18
 36/9 = 4 |
|
CB
|
VDB
|
B
|
X
|
Y
|
S1
|
S2
|
S3
|
|
|
0
|
S1
|
24
|
4
|
6
|
1
|
0
|
0
|
|
|
0
|
S2
|
18
|
2
|
1
|
0
|
1
|
0
|
|
|
0
|
S3
|
36
|
3
|
9*
|
0
|
0
|
1
|
|
|
Zj
– cj
|
0
|
-5
|
-8
|
0
|
0
|
0
|
||
Tabel 5.1.2. Tabel Perbaikan 1 dengan Memilih
Baris 3 Sebagai Baris Kunci
|
|
|
|
5
|
8
|
0
|
0
|
0
|
 0/2 = 4 |
|
CB
|
VDB
|
B
|
X
|
Y
|
S1
|
S2
|
S3
|
|
|
0
|
S1
|
0
|
2*
|
0
|
1
|
0
|
-2/3
|
|
|
0
|
S2
|
14
|
5/3
|
0
|
0
|
1
|
-1/9
|
|
|
8
|
Y
|
4
|
1/3
|
1
|
0
|
0
|
1/9
|
|
|
Zj
– cj
|
32
|
-7/3
|
0
|
0
|
0
|
8/9
|
||
Tabel 5.1.3. Tabel Optimal
|
|
|
|
5
|
8
|
0
|
0
|
0
|
|
CB
|
VDB
|
B
|
X
|
Y
|
S1
|
S2
|
S3
|
|
0
|
X
|
0
|
1
|
0
|
½
|
0
|
-1/3
|
|
0
|
S2
|
14
|
0
|
0
|
-5/6
|
1
|
4/9
|
|
8
|
Y
|
4
|
0
|
1
|
-1/6
|
0
|
2/9
|
|
Zj
– cj
|
32
|
0
|
0
|
7/6
|
0
|
1/9
|
|
Tampak bahwa program Optimal
dengan Zmaks = 32 dengan penyelesaian optimal X = 0 dan Y = 4. Pada tabel
perbaikan 1 ada dua pilihan untuk menjadi baris kunci, yaitu baris 1 dan baris
3, dalam hal ini dipilih baris ketiga sebagai baris kunci. Tabel perbaikan 2 merupakan contoh kemerosotan
yaitu Nilai Z pada tabel perbaikan 1 dan tabel perbaikan 2 sama yaitu Z = 32.
Pemilihan baris ketiga sebagai
baris kunci misal disebut cara I. Akan ditunjukkan pemilihan baris pertama
sebagai baris kunci yang disebut cara II. Perhatikan penyelesaian dengan cara
kedua berikut.
Tabel 5.1.4. Tabel Perbaikan dengan memilih
Baris 1 Sebagai Baris Kunci
|
|
|
|
5
|
8
|
0
|
0
|
0
|
|
CB
|
VDB
|
B
|
X
|
Y
|
S1
|
S2
|
S3
|
|
8
|
Y
|
4
|
2/3
|
1
|
1/6
|
0
|
0
|
|
0
|
S2
|
14
|
4/3
|
0
|
-1/6
|
1
|
0
|
|
0
|
S3
|
0
|
-3
|
0
|
-3/2
|
0
|
1
|
|
Zj
– cj
|
32
|
1/3
|
0
|
4/3
|
0
|
0
|
|
Tabel tersebut menunjukkan program optimal hanya
dengan satu kali perbaikan dengan nilai Z sama yaitu 32. Hal itu menunjukkan bahwa pemilihan baris
kunci yang tepat menyebabkan peogram tidak mengalami kemerosotan atau proses
iterasi yang lebih singkat.
2. Penanggulangan Kemerosotan
Untuk menanggulangi
kemerosotan, ada dua metode yang dapat digunakan. Metode tersebut adalah Aturan
Lexicographic dan Aturan Antisiklus dari Bland.
Aturan yang pertama yaitu
Aturan Lexicographic. Berikut ini adlah langkah-langkah yang diikuti
pada aturan tersebut.
a.
Pada kolom kunci, tentukan “bilangan pada kolom kuantitas
dibagi dengan elemen-elemen positip pada kolom kunci menurut baris yang sama”
dan pilih baris yang memuat hasil bagi terkecil.
b.
i. Jika hasil bagi minimal terdapat pada satu baris,
maka pilih baris tersebut sebagai baris
kunci.
ii. Jika hasil bagi minimal
terdapat pada lebih dari satu baris, maka elemen kolom ke-1 matriks identitas dibagi dengan elemen-elemen
baris tersebut pada kolom kunci.
c.
i. Jika langkah
tersebut memberi hasil bagi minimal pada
satu baris, maka pilih baris tersebut sebagai
baris kunci.
ii. Jika hasil bagi minimal
terdapat pada lebih dari satu baris, maka elemen kolom ke-2 matriks identitas
dibagi dengan elemen baris yang bersesuaian
pada kolom kunci .
d.
Langkah ke-b diulangi sampai diperoleh hasil bagi yang minimal.
Aturan yang kedua adalah
aturan antisiklus dari Bland. Aturan
tersebut adalah sebagai berikut.
a.
Menggunakan aturan simpleks biasa.
b.
Jika nol muncul pada kolom B dan aturan simpleks untuk
memilih baris kunci jatuh di baris dengan b=0 maka cara memilih elemen kuncinya
adalah sbb:
i.
Jika ada elemen negatif pada baris Zj-cj maka pilih
kolom dengan indeks terkecil untuk variabel yang bersesuaian dengan kolom itu sebagai kolom kunci.
ii.
Jika ada elemen positif dalam kolom itu dan pada baris
yang memuat elemen itu b=0 , pilih baris yang elemennya positif dalam kolom
kunci dan indeks terkecil untuk variabel yang bersesuaian dengan baris itu sebagai
baris kunci.
Berikut ditunjukkan penyelesaian masalah tersebut
dengan menggunakan metode simpleks biasa.
Tabel 5.2.1. Tabel Program Awal
|
|
|
|
¾
|
-20
|
½
|
-6
|
0
|
0
|
0
|
|
CB
|
VDB
|
B
|
X1
|
X2
|
X3
|
X4
|
S1
|
S2
|
S3
|
|
0
|
S1
|
0
|
¼
|
-8
|
-1
|
9
|
1
|
0
|
0
|
|
0
|
S2
|
0
|
½
|
-12
|
-½
|
3
|
0
|
1
|
0
|
|
0
|
S3
|
1
|
0
|
0
|
1
|
0
|
0
|
0
|
1
|
|
Zj
- cj
|
0
|
-¾
|
20
|
-½
|
6
|
0
|
0
|
0
|
|
Tabel 5.2.2. Tabel Perbaikan 1
|
|
|
|
¾
|
-20
|
½
|
-6
|
0
|
0
|
0
|
|
CB
|
VDB
|
B
|
X1
|
X2
|
X3
|
X4
|
S1
|
S2
|
S3
|
|
¾
|
X1
|
0
|
1
|
-32
|
-4
|
36
|
4
|
0
|
0
|
|
0
|
S2
|
0
|
0
|
4
|
3/2
|
-15
|
-2
|
1
|
0
|
|
0
|
S3
|
1
|
0
|
0
|
1
|
0
|
0
|
0
|
1
|
|
Zj
- cj
|
0
|
0
|
-4
|
-7/2
|
33
|
3
|
0
|
0
|
|
Tabel 5.2.3. Tabel Perbaikan 2
|
|
|
|
¾
|
-20
|
½
|
-6
|
0
|
0
|
0
|
|
CB
|
VDB
|
B
|
X1
|
X2
|
X3
|
X4
|
S1
|
S2
|
S3
|
|
¾
|
X1
|
0
|
1
|
0
|
8
|
-2
|
-12
|
8
|
0
|
|
-20
|
X2
|
0
|
0
|
1
|
3/8
|
-15/4
|
-½
|
¼
|
0
|
|
0
|
S3
|
1
|
0
|
0
|
1
|
0
|
0
|
0
|
1
|
|
Zj
- cj
|
0
|
0
|
0
|
-2
|
18
|
1
|
1
|
0
|
|
Tabel 5.2.4. Tabel Perbaikan 3
|
|
|
|
¾
|
-20
|
½
|
-6
|
0
|
0
|
0
|
|
CB
|
VDB
|
B
|
X1
|
X2
|
X3
|
X4
|
S1
|
S2
|
S3
|
|
½
|
X3
|
0
|
1/8
|
0
|
1
|
-21/4
|
-3/2
|
1
|
0
|
|
-20
|
X2
|
0
|
-3/64
|
1
|
0
|
3/16
|
1/16
|
-1/8
|
0
|
|
0
|
S3
|
1
|
-1/8
|
0
|
0
|
21/2
|
3/2
|
-1
|
1
|
|
Zj
- cj
|
0
|
¼
|
0
|
0
|
-3
|
-2
|
3
|
0
|
|
Tabel 5.2.5. Tabel Perbaikan 4
|
|
|
|
¾
|
-20
|
½
|
-6
|
0
|
0
|
0
|
|
CB
|
VDB
|
B
|
X1
|
X2
|
X3
|
X4
|
S1
|
S2
|
S3
|
|
½
|
X3
|
0
|
-5/2
|
56
|
1
|
0
|
2
|
-6
|
0
|
|
-6
|
X4
|
0
|
-¼
|
16/3
|
0
|
1
|
1/3
|
2/3
|
0
|
|
0
|
S3
|
1
|
5/2
|
-56
|
0
|
0
|
-2
|
6
|
1
|
|
Zj
- cj
|
0
|
-½
|
16
|
0
|
0
|
-1
|
1
|
0
|
|
Tabel 5.2.6. Tabel Perbaikan 5
|
|
|
|
¾
|
-20
|
½
|
-6
|
0
|
0
|
0
|
|
CB
|
VDB
|
B
|
X1
|
X2
|
X3
|
X4
|
S1
|
S2
|
S3
|
|
0
|
S1
|
0
|
-5/4
|
28
|
½
|
0
|
1
|
-3
|
0
|
|
-6
|
X4
|
0
|
1/6
|
-4
|
-1/6
|
1
|
0
|
1/3
|
0
|
|
0
|
S3
|
1
|
0
|
0
|
1
|
0
|
0
|
1/3
|
1
|
|
Zj
- cj
|
0
|
-7/4
|
44
|
½
|
0
|
0
|
-2
|
0
|
|
Tabel 5.2.7. Tabel Perbaikan 6
|
|
|
|
¾
|
-20
|
½
|
-6
|
0
|
0
|
0
|
|
CB
|
VDB
|
B
|
X1
|
X2
|
X3
|
X4
|
S1
|
S2
|
S3
|
|
0
|
S1
|
0
|
¼
|
-8
|
-1
|
9
|
1
|
0
|
0
|
|
0
|
S2
|
0
|
½
|
-12
|
-½
|
3
|
0
|
1
|
0
|
|
0
|
S3
|
1
|
0
|
0
|
1
|
0
|
0
|
0
|
1
|
|
Zj
- cj
|
0
|
-¾
|
20
|
-½
|
6
|
0
|
0
|
0
|
|
Tabel tersebut menunjukkan siklus.
Perbaikan yang menggunakan metode simpleks ternyata menyebabkan terjadinya
siklus, yaitu program kembali ke program awal.
Berikut ini ddiberikan penyelesaian masalah tersebut dengan menggunakan
aturan lexicographic.
Tabel 5.2.8. Tabel Perbaikan 1
|
|
|
|
¾
|
-20
|
½
|
-6
|
0
|
0
|
0
|
|
CB
|
VDB
|
B
|
X1
|
X2
|
X3
|
X4
|
S1
|
S2
|
S3
|
|
0
|
S1
|
0
|
0
|
-2
|
-3/4
|
15/2
|
1
|
-1/2
|
0
|
|
¾
|
X1
|
0
|
1
|
-24
|
-1
|
6
|
0
|
2
|
0
|
|
0
|
S3
|
1
|
0
|
0
|
1
|
0
|
0
|
0
|
1
|
|
Zj
- cj
|
0
|
0
|
2
|
-5/4
|
21/2
|
0
|
3/2
|
0
|
|
Tabel 5.2.9. Tabel Perbaikan 2
|
|
|
|
¾
|
-20
|
½
|
-6
|
0
|
0
|
0
|
|
CB
|
VDB
|
B
|
X1
|
X2
|
X3
|
X4
|
S1
|
S2
|
S3
|
|
0
|
S1
|
¾
|
0
|
-2
|
0
|
15/2
|
1
|
-1/2
|
-3/4
|
|
¾
|
X1
|
1
|
1
|
-24
|
0
|
6
|
0
|
2
|
1
|
|
½
|
X3
|
1
|
0
|
0
|
1
|
0
|
0
|
0
|
1
|
|
Zj
- cj
|
5/4
|
0
|
2
|
0
|
21/2
|
0
|
3/2
|
5/4
|
|
Tabel tersebut menunjukkan penyelesaian dengan eturan lexicographic
memberikan program optimal dengan dengan Zmaks = 5/4. Bandingkan dengan penggunaan metode simpleks
yang mengalami siklus setelah perbaikan ke-6.
C.
Rangkuman
1.
Kemerosotan adalah masalah yang terjadi ketika pada
program perbaikan tidak terjadi peningkatan nilai fungsi tujuan.
2.
Kemerosotan pada masalah program linear mempunyai
cirri-ciri berikut.
a.
Dalam program awal ada satu atau lebih variabel dalam
kolom kuantitas bernilai nol(ada bi dalam tabel simplek bernilai nol).
b.
Dalam kolom penentuan, ada nilai hasil bagi untuk dua
atau lebih variabel dalam basis bernilai sama.
3.
Kemerosotan dapat ditanggulangi dengan aturan lexicographic
dan aturan antisiklus dari Bland,
4.
Aturan Lexicographic :
a.
Pada kolom kunci, tentukan “bilangan pada kolom
kuantitas dibagi dengan elemen-elemen positip pada kolom kunci menurut baris
yang sama” dan pilih baris yang memuat hasil bagi terkecil.
b.
i. Jika hasil
bagi minimal terdapat pada satu baris, maka pilih baris tersebut sebagai
baris kunci.
ii. Jika
hasil bagi minimal terdapat pada lebih dari satu baris, maka elemen kolom
ke-1 matriks identitas dibagi dengan
elemen-elemen baris tersebut pada kolom kunci.
c.
i. Jika langkah
tersebut memberi hasil bagi minimal pada
satu baris, maka pilih baris tersebut sebagai
baris kunci.
ii. Jika hasil bagi minimal
terdapat pada lebih dari satu baris, maka elemen kolom ke-2 matriks identitas
dibagi dengan elemen baris yang
bersesuaian pada kolom kunci .
d.
Langkah ke-b diulangi sampai diperoleh hasil bagi yang minimal.
5.
Aturan antisiklus dari Bland:
a.
Menggunakan aturan simpleks biasa.
b.
Jika nol muncul pada kolom B dan aturan simpleks untuk
memilih baris kunci jatuh di baris dengan b=0 maka cara memilih elemen kuncinya
adalah sbb:
i.
Jika ada elemen negatif pada baris Zj-cj maka pilih
kolom dengan indeks terkecil untuk variabel yang bersesuaian dengan kolom itu sebagai kolom kunci.
ii.
Jika ada elemen positif dalam kolom itu dan pada baris
yang memuat elemen itu b=0 , pilih baris yang elemennya positif dalam kolom
kunci dan indeks terkecil untuk variabel yang bersesuaian dengan baris itu
sebagai baris kunci.
D.
Latihan
1.
Kemerosotan terjadi ketika pada beberapa iterasi …
A.
Nilai fungsi tujuan naik
B.
Program optimal
C.
Program tidak optimal
D.
Nilai fungsi tujuan tidak meningkat
2.
Penyelesaian masalah program linear terlibat dalam
siklus, jika setelah beberapa proses iterasi
ternyata program …
A.
kehilangan satu baris
B.
bertambah satu baris
C.
mencapai nilai optimal
D.
kembali pada basis yang sama
3.
Pernyataan berikut yang benar adalah …
Pemilihan salah satu variabel terikat secara secara sembarang
..
A.
merupakan cara penyelesaian paling tepat
B.
menghindarkan proses yang melibatkan siklus
C.
dapat mengakibatkan proses iterasi yang lebih panjang
D.
merupakan satu-satunya jalan yang dapat ditempuh
Diberikan masalah program linear yang memaksimumkan fungsi
f = 20X + 30Y + 22Z harus memenuhi:
2X + 2Y ≤ 100
2X + Y + Z ≤ 100
X + 2Y + 2Z ≤ 100
X, Y, Z ≥0
4.
Setelah disusun program awal , pada table dijumpai
suatu kemerosotan yaitu keterikatan antara …
A.
S1 dan S2
B.
S1 dan S3
C.
S2 dan S3
D.
X dan Y
5.
Program diperbaiki dengan memasukkan variabel Y ke
dalam program maka variabel yang akan keluar dari basis adalah …
A.
X
B.
Z
C.
S1
D.
S2
6.
Program tersebut memiliki penyelesaian optimal dengan
nilai fungsi tujuan sebesar …
A.
1650
B.
2200/3
C.
1250/3
D.
1500/3
Cocokkan jawaban Anda
dengan kunci jawab yang ada di bagian
akhir bab ini. Hitunglah jawaban benar
Anda, kemudian gunakan rumus di bawah ini
untuk mengetahui tingkat penguasaan Anda
terhadap materi pokok bahasan tersebut.
Rumus:
Jika tingkat penguasaan Anda ≥
80% maka Anda dapat melanjutkan mempelajari bab berikutnya. Jika belum, Anda harus mengulangi mempelajari
bab ini terutama pada bagian yang belum Anda kuasai.
E.
Kunci Jawab
1.
D 2.
D 3.C 4.B 5.C 6.
A
Tidak ada komentar:
Posting Komentar