√ Metode Dual Simpleks

Sebelum masuk ke bahan dual simpleks ini ada baiknya anda memahami lebih lanjut mengenai Masalah Minimasi Metode Simpleks

Prosedur perhitungan yang pada bab sebelumnya berkisar dari solusi dasar feasibel yang belum optimal menuju ke solusi feasibel optimal. Apakah proses tersebut alhasil akan mencapai solusi feasibel optimal yakni tergantung pada kemampuan untuk mendapat suatu solusi dasar awal yang feasibel.

Dalam kaitan ini, variabel artificial R sanggup dipakai untuk menemukan solusi awal feasibel. Jika formulasi aktivitas linear mengandung banyak variabel artificial, akan membutuhkan banyak perhitungan untuk memperoleh solusi awal feasibel.

Untuk menghindari masalah tersebut sanggup dipakai suatu mekanisme yang disebut metode dual simpleks. Metode ini meskipun pada solusi awalnya tidak feasibel. Pada dasarnya metode dual simpleks memakai tabel yang sama ibarat metode dual simpleks pada primal, tetapi leaving variabel dan entering variabelnya ditentukan sebagai berikut :

1. Leaving Variabel

Sebagai leaving variabel yakni variabel basis yang mempunyai harga negatif angka terbesar. Jika semua variabel basis berharga kasatmata atau nol berarti keadaan feasibel telah tercapai.

2. Entering Variabel

• Tentukan rasio antara koefisien persamaan Z dengan koefisien persamaan leaving variabel. Abaikan penyebut kasatmata atau nol. Jika semua penyebut berharga kasatmata atau nol, berarti masalah yang bersangkutan tidak mempunyai solusi feasibel.
• Untuk masalah minimasi, entering variabel yakni variabel dengan rasio terkecil. Sedangkan untuk masalah maksimasi entering variabel yakni variabel dengan rasio terkecil.

Contoh :

Minimumkan : Z = 16 X₁ + 20 X₂

Kendala :

6 X₁ + 12 X₂ ≥ 72

15 X₁ + 6 X₂ ≥ 90

6 X₁ + 5 X₂ ≤ 60

X₁, X₂ ≥ 0

Syarat dipakai metode dual simpleks jikalau ada hambatan yang merupakan ketidaksamaan bertanda ≥. Kaprikornus ubahlah variabel S menjadi positif.

Langkah 1 : Formulasikan fungsi tujuan dan kendala

Formulasi diatas menjadi :

Minimumkan : Z - 16 X₁ - 20 X₂ = 0

-6 X1 -	12 X2 +	S1			=	-72
-15 X1 -	6 X2		+ S2		=	- 90
6 X1 +	5 X2			+ S3	=	60
X1, X2, S1, S2, S3					≥	0

Langkah 2 : Tentukan leaving variabelnya

Seperti dalam metode simpleks, metode ini didasarkan pada optimality dan feasibility condition. Optimality condition menjamin bahwa solusi tetap optimum sedangkan feasibility condition memaksa semoga solusi mencapai keadaan layak. Jadi, pada dasarnya metode dual simpleks ibarat dengan metode simpleks biasa hanya saja ditranspose (baris jadi kolom & kolom jadi baris)

Kaprikornus menurut soal diatas didapatkan tabel awal sebagai berikut :

Iterasi	Basis	Z	X1	X2	S1	S2	S3	Solusi
0	Z	1	-16	-20	0	0	0	0
	S1	0	-6	-12	1	0	0	-72
	S2	0	-15	-6	0	1	0	-90
	S3	0	6	5	0	0	1	60

Jadi, dalam metode dual simpleks, yang pertama ditentukan yakni leaving variabelnya dengan solusi yang mempunyai angka negatif terbesar.

Langkah 3 : Tentukan entering variabelnya

Basis	Z	X1	X2	S1	S2	S3	Solusi
Z	1	-16	-20	0	0	0	0
S1	0	-6	-12	1	0	0	-72
S2	0	-15	-6	0	1	0	-90
S3	0	6	5	0	0	1	60
Rasio	-	16/15	20/6	-	-	-	-

Setelah itu gres hitunglah rasionya dengan membagi angka dari baris Z dengan leaving variabelnya dan pilih rasio yang terkecil. Abaikan rasio yang mempunyai angka negatif atau nol.

Langkah 4 : Tentukan persamaan pivot baru

Dari langkah ini sudah ibarat dengan langkah metode simpleks biasa, untuk lebih jelasnya perihal metode simpleks sanggup dilihat pada : Pemecahan Program Linear Metode Simpleks, jadi menurut soal diatas didapatkan baris pivot barunya yakni :

Basis	Z	X1	X2	S1	S2	S3	Solusi
Z	1
S1
X1	0	1	2/5	0	-1/15	0	6
S3

Langkah 5 : Tentukan persamaan gres selain pivot baru

Setelah mendapat persamaan pivot baru, langkah selanjutnya yakni mengisi persamaan lainya yang masih kosong. Rumus untuk memilih persamaan gres selain persamaan pivot gres yakni sebagai berikut : Persamaan gres = (persamaan lama) - (persamaan pivot gres x koefisien kolom pivot)

Persamaan Z gres :

(-16) - (1 x -16) = 0

(-20) - (2/5 x -16) = -68/5

(0) - (0 x -16) = 0

(0) - (-1/15 x -16) = -16/15

(0) - (0 x -16) = 0

(0) - (6 x -16) = 96

Persamaan S₁ gres :

(-6) - (1 x -6) = 0

(-12) - (2/5 x -6) = -48/5

(1) - (0 x -6) = 1

(0) - (-1/15 x -6) = -2/5

(0) - (0 x -6) = 0

(-72) - (6 x -6) = -36

Persamaan S₃ gres :

(6) - (1 x 6) = 0

(5) - (2/5 x 6) = 13/5

(0) - (0 x 6) = 0

(0) - (-1/15 x 6) = 2/5

(1) - (0 x 6) = 1

(60) - (6 x 6) = 24

Setelah mencari persamaan Z, S₁ dan S₃ gres lalu tabulasikan dalam tabel simpleks sebagai berikut :

Iterasi	Basis	Z	X1	X2	S1	S2	S3	Solusi
1	Z	1	0	-68/5	0	-16/15	0	96
	S1	0	0	-48/5	1	-2/5	0	-36
	X1	0	1	2/5	0	-1/15	0	6
	S3	0	0	13/5	0	2/5	1	24

Langkah 6 : Lanjutkan perbaikan-perbaikan

Setelah didapatkan persamaan baru, periksa kembali apakah solusi masih ada yang bertanda negatif atau tidak, jikalau masih ada berarti solusi belum optimal sehingga perlu diulangi kembali dari langkah ke-2. Dari persamaan diatas didapatkan masih adanya solusi yang negatif, sehingga perlu dilakukan langkah-langkah perbaikan dengan mengulangi langkah ke-2.Sehingga didapatkan tabel berikut :

Iterasi	Basis	Z	X1	X2	S1	S2	S3	Solusi
2	Z	1	0	0	-17/12	-1/2	0	147
	X2	0	0	1	-5/48	1/24	0	15/4
	X1	0	1	0	1/24	-1/12	0	9/2
	S3	0	0	0	13/48	7/24	1	57/4

Berdasarkan iterasi awal terlihat bahwa meskipun koefisien persamaan Z sudah memenuhi kondisi optimal (barisan Z sudah nol atau negatif untuk kasus minimasi), tetapi variabel-variabel basis awalnya tidak memperlihatkan solusi awal yang feasibel (S₁, S₂ berharga negatif).

Solusi optimal dan feasibel tercapai pada iterasi kedua. Selain untuk menghindari perhitungan yang rumit, metode dual simpleks sangat penting untuk dipakai pada analisis sensitivitas.

Hal ini terjadi apabila suatu pembatas gres ditambahkan (atau pembatas usang diubah), pada suatu masalah yang sudah mencapai solusi optimal dan menjadikan solusi tidak feasibel, sehingga untuk menyelesaikannya dipakai metode dual simpleks.

Sumber http://www.dounkey.com