√ Kasus Khusus Penggunaan Metode Simpleks

Terdapat beberapa masalah pada metode simpleks yang menimbulkan perhitungan pada metode simpleks ini menjadi sangat rumit dan tidak selesai-selesai.

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

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

Berikut ialah masalah khusus dalam penggunaan metode simpleks :

1. Degenerasi

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

Contoh :

Maksimumkan : Z = 12 X₁ + 4 X₂

Kendala :

8 X₁ + 2 X₂ ≤ 16

6 X₁ + 3 X₂ ≤ 12

X₁, X₂ ≥ 0

Berdasarkan persamaan diatas, lakukan penyelesaian dengan metode simpleks menyerupai yang sudah dijelaskan pada bab sebelumnya ihwal : Pemecahan Program Linear Metode Simpleks.

Iterasi	Basis	Z	X1	X2	S1	S2	Solusi	Rasio
0	Z	1	-12	-4	0	0	0	-
	S1	0	8	2	1	0	16	2
	S2	0	6	0	0	1	12	2

Iterasi	Basis	Z	X1	X2	S1	S2	Solusi	Rasio
1	Z	1	0	-1	3/2	0	24	-
	X1	0	1	1/4	1/8	0	2	8
	S2	0	0	3/2	-3/4	1	0	0

Iterasi	Basis	Z	X1	X2	S1	S2	Solusi
2	Z	1	0	0	1	2/3	24
	X1	0	1	0	1/4	-1/6	2
	X2	0	0	1	-1/2	2/3	0

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

Solusi optimal tercapai pada iterasi kedua (Z = 24) yang memperlihatkan solusi sama dengan iterasi 1. Disini terlihat adanya mekanisme simpleks uang berulang akan tetapi tidak memperbaiki nilai Z. Nilai variabel dan fungsi tujuan pada iterasi 1 dan 2 sama yaitu X₁ = 2, X₂ = 0, S₁ = 0, S₂ = 0, dan Z = 24.

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

Contoh :

Maksimumkan : Z = 3 X₁ + 2 X₂

Kendala :

4 X₁ + 3 X₂ ≤ 12

4 X₁ + X₂ ≤ 8

4 X₁ - X₂ ≤ 8

X₁, X₂ ≥ 0

Iterasi	Basis	Z	X1	X2	S1	S2	S3	Solusi	Rasio
0	Z	1	-3	-2	0	0	0	0	-
	S1	0	4	3	1	0	0	12	3
	S2	0	4	1	0	1	0	8	2
	S3	0	4	-1	0	0	1	8	2

Iterasi	Basis	Z	X1	X2	S1	S2	S3	Solusi	Rasio
1	Z	1	0	-5/4	0	3/4	0	6	-
	S1	0	0	2	1	-1	0	4	2
	X1	0	1	1/4	0	1/4	0	2	8
	S3	0	0	-2	0	-1	1	0	-

Iterasi	Basis	Z	X1	X2	S1	S2	S3	Solusi
2	Z	1	0	0	5/8	1/8	0	17/2
	X2	0	0	1	1/2	-1/2	0	2
	X1	0	1	0	-1/8	3/8	0	3/2
	S3	0	0	0	1	-2	1	4

Pada tabel 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 lantaran X₂, yang menjadi entering variabel atau kolom pivot pada iterasi 1 mempunyai koefisien pembatas yang berharga negatif (= -2) yang berkorespondensi dengan basis S₃ yang berharga nol.

2. Solusi Optimum Banyak

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

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

Contoh :

Maksimumkan : Z = 2 X₁ + 4 X₂

Kendala :

X₁ + 2 X₂ ≤ 5

X₁ + X₂ ≤ 4

X₁, X₂ ≥ 0

Berdasarkan persamaan dilakukan penyelesaian dengan metode simpleks menyerupai cara penyelesaian yang telah diuraikan pada bab sebelumnya ihwal : Pemecahan Program Linear Metode Simpleks.

Iterasi	Basis	Z	X1	X2	S1	S2	Solusi
0	Z	1	-2	-4	0	0	0
	S1	0	1	2	1	0	5
	S2	0	1	1	0	1	4

Iterasi	Basis	Z	X1	X2	S1	S2	Solusi
1	Z	1	0	0	2	0	10
	X2	0	1/2	1	1/2	0	5/2
	S2	0	1/2	0	-1/2	1	3/2

Iterasi	Basis	Z	X1	X2	S1	S2	Solusi
Tambahan	Z	1	0	0	2	0	10
	X2	0	0	1	1	-1	1
	X1	0	1	0	-1	2	3

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

3. Solusi Tidak Terbatas

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

Kejadian ini sanggup berarti bahwa masalah yang ada tidak dirumuskan dengan tepat. Kesalahan ini sanggup berupa :

• Adanya hambatan tak berlebih yang diikut sertakan.
• Adanya parameter dari beberapa hambatan tidak diduga dengan benar.

Contoh :

Maksimumkan : Z = 6 X₁ + 4 X₂

Kendala :

2 X₁ - 3 X₂ ≤ 12

3 X₁ ≤ 30

X₁, X₂ ≥ 0

Berdasarkan persamaan dilakukan penyelesaian dengan metode simpleks menyerupai cara penyelesaian yang telah diuraikan pada bab sebelumnya ihwal : Pemecahan Program Linear Metode Simpleks.

Iterasi	Basis	Z	X1	X2	S1	S2	Solusi
0	Z	1	-6	-4	0	0	0
	S1	0	2	-3	1	0	12
	S2	0	3	0	0	1	30

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

4. Tidak Ada Solusi Layak

Contoh : 

Maksimumkan : Z = 4 X₁ + 5 X₂

Kendala :

3 X₁ + 5 X₂ ≤ 12

X₁ ≤ 6

X₂ ≥ 0

X₁, X₂ ≥ 0

Berdasarkan persamaan dilakukan penyelesaian dengan metode simpleks minimasi menyerupai cara penyelesaian yang telah diuraikan pada bab sebelumnya ihwal : Masalah Minimasi Metode Simpleks

Iterasi	Basis	Z	X1	X2	S1	S2	R1	S3	R2	Solusi
0	Z	1	(-M-4)	-M-5	0	M	0	M	0	-10M
	S1	0	3	5	1	0	0	0	0	15
	R1	0	1	0	0	-1	1	0	0	6
	R2	0	0	1	0	0	0	-1	1	4

Iterasi	Basis	Z	X1	X2	S1	S2	R1	S3	R2	Solusi
1	Z	1	-2/5M-1	0	1/5M+1	M	0	M	0	-7M+15
	X2	0	3/5	1	1/5	0	0	0	0	3
	R1	0	1	0	0	-1	1	0	0	6
	R2	0	-3/5	0	-1/5	0	0	-1	1	1

Iterasi	Basis	Z	X1	X2	S1	S2	R1	S3	R2	Solusi
2	Z	1	0	2/3M+5/3	(M+4)/3	M	0	M	0	-5M+20
	X1	0	1	5/3	1/3	0	0	0	0	5
	R1	0	0	-5/3	-1/3	-1	1	0	0	1
	R2	0	0	1	0	0	0	-1	1	4

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

Sumber http://www.dounkey.com

Buat lebih berguna, kongsi: