Rivised Simpleks Method (metode simpleks yang diperbaiki) Metode simpleks yang sudah kita pelajari, menunjukkan bahwa setiap perpindahan tabel baru selalu membawa semua elemen yang terdapat dalam tabel. Dalam metode simpleks yang diperbaiki, setiap perpindahan tabel baru tidak semua elemen diperlukan. Informasi yang sangat diperlukan untuk berpindah dari satu tabel ke tabel berikutnya adalah : (1) (2) (3) (4)
Nilai pada baris Zj – Cj. Kolom kunci (variabel yang akan masuk basis). Variabel basis. Nilai konstanta ruas kanan (bi) yang berkorespondensi dengan variabel basis.
Selain keempat informasi tersebut, sebenarnya yang lain tidak diperlukan (tidak memiliki peran) dalam proses perpindahan tabel simpleks. Jika persoalan linier program cukup besar, hal ini akan menjadi tidak efisien jika membawa semua elemen ke dalam tabel berikutnya. Cara yang lebih efisien yang dapat digunakan untuk mengatasi permasalahan seperti diatas adalah dengan metode simpleks yang diperbaiki atau simpleks multiplier. BENTUK UMUM METODE SIMPLEKS YANG DIPERBAIKI Matriks dari bentuk standar linier program adalah sebagai berikut : Maksimum
Z
=
cx
dk
Ax
=
x
≥
bi 0
di mana,
A= (m x m)
bi =
(m x 1)
a11 a21 .. .. am1
a12 a22 .. .. am2
b1 b2 .. .. bi
dan, c = (1 x n)
[ c1, c2, …….cn]
…. ….
….
x= (n x 1)
a1n a2n .. .. amn
x1 x2 .. .. xn
Misalkan kolom yang berkorespondensi dengan matriks (A) dinyatakan dengan : Y1, Y2, …, Yn, di mana,
a11 a21 .. .. am1
Y1 =
(m x 1)
a12 a22 .. .. am2
Y2 =
;
(m x 1)
a1n a2n .. .. amn
Y3 =
;
(m x 1)
Misalkan kita memiliki variabel basis x1, x2, …, xm, maka matriks basisnya adalah :
a11 a21 .. .. am1
B = Y1, Y2, …Ym =
(m x n)
B invers = B
-1
Misalkan vektor (B) dipecah menjadi
B11 B21 .. .. Bm1
B =
…. ….
a12 a22 .. .. am2
B12 B22 .. .. Bm2
….
…. ….
….
a1m a2m .. .. amm
B1m B2m .. .. Bmm
B1
(n x 1)
BN
di mana B1 berkorespondensi dengan variabel basis, dan BN merupakan variabel nonbasis, maka :
B1 =
(m x 1)
b1 b2 .. .. bm
dan
BN =
(n - mx1)
xm+1 xm+2 .. .. xm+n
dengan demikian solusi basis optimum adalah :
-1
BI = B b i =
B11b1 + B21b1 + .. .. Bm1b1 +
B 12b2 + B 22b2 + .. .. Bm2b2 +
…. ….
….
+ B1mbm + B2mbm .. .. + Bmmbm
Misalkan CB merupakan koefisien fungsi tujuan untuk variabel basis, maka fungsi tujuan dari variabel basis adalah : Z = Cx = CB B I = c1b1 + c2b2 + … + cmbm Untuk menguji apakah solusi telah optimum, perlu dihitung simpleks multiplier (π) = CBB . Koefisien fungsi tujuan yang baru = ĉj = πYi – cj . Oleh karena fungsi tujuan berbentuk maksimum, maka solusi optimum akan dicapai apabila ĉj ≥ 0. Jika solusi belum optimum, maka pilih salah satu nilai ĉj yang memiliki negatif terbesar, sebagai variabel masuk basis. Sedangkan variabel yang akan keluar basis perlu ditentukan kolom pivot dengan menggunakan rumus berikut : -1
Yjn = B-1Yjn =
â1n â2n .. .. âmn
Setelah itu uji perbandingan minimum untuk menentukan variabel yang akan keluar basis dengan rumus :
b2
b2 , untuk , i = 1,2, …, m.
= Minimum â2n
â2n
Proses ini diulangi sampai solusi optimum tercapai.
Contoh 1 : Penyelesaian LP dengan Rivised Simpleks, pada prinsipnya sama dengan metode simpleks terdahulu. Akan tetapi kita hanya menghitung informasi yang penting saja pada setiap perpindahan tabel baru. Maksimum Z = 40X1 + 25X2 + 0S 1 + 0S2 Dk.
[1] [2] [3]
3X1 + 2X2 + S1 = 150 8X1 + 2X2 + S2 = 200 X1, X 2, S1, S2 ≥ 0
Untuk melihat hasil perhitungan dengan Rivised Simpleks, terlebih dahulu kita akan selesaikan dengan metode simpleks biasa, sebagai perbandingan.
40 X1
25 X2
0 S1
0 S2
Indeks
150
3
2
1
0
150:3=50
S2
200
8
2
0
1
200:8=25
Zj-Cj
0
-40
-25
0
0
40 X1
25 X2
0 S1
0 S2
Indeks
CB
Basis
0
S1
0
Cj bi
Cj
CB
Basis
0
S1
75
0
5/4
1
-3/8
75:1,25=60
40
X1
25
1
¼
0
1/8
25:0,25=100
Zj-Cj
1000
0
-15
0
5
40 X1
25 X2
0 S1
0 S2
bi
Cj
CB
Basis
25
X2
60
0
1
0,8
-0,3
40
X1
10
1
0
-0,2
0,2
Zj-Cj
1900
0
0
12
0,5
bi
Indeks
Solusi optimum permasalahan diatas adalah X1 = 10, X 2 = 60 dengan nilai Z = 1.900. Dalam rivised simpleks, tidak semua angka yang terdapat dalam tabel diatas kita perlukan. Jika, kolom X1, X2, S1 dan S2 kita kita sebut Y1, Y2, Y3 dan Y4. Konstanta nilai kanan kita sebut bi, dan koefisien fungsi tujuan kita sebut C1, C2, C3, dan C4, maka angka-angka tersebut dapat dibuat sebagai berikut :
3 8
2 2
1 0
0 1
Y1 = , Y2 = , Y3 = , Y4 = .
150 ; C1 = [40], C2 = [25], C3 = [0], C4 = [0]. 200
bi =
Sehingga tabel awal metode rivesed simpleks adalah :
Tabel 1. Tabel awal simpleks diperbaiki B-1
basis
bi
S1
1
0
150
S2
0
1
200
Dalam tabel 1 variabel basis adalah S1 dan S2 dengan koefisien fungsi tujuan C3 dan C4. Simpleks multiplier = π = CBB-1, dimana CB = [C3,C4] = [0,0].
1 0 = [0,0] 0 1
Simpleks multiplier = π = [0,0]
C1 = π Y1 – C1 = [0,0]
3 8 - 40 = - 40.
C2 = π Y2 – C2 = [0,0]
2 2 - 25 = - 25.
Oleh karena C1 memiliki angka negatif terbesar, maka X1 masuk basis (menjadi kolom kunci). Untuk menentukan variabel yang akan keluar basis (baris kunci) adalah memilih angka terkecil dari (aturan perbandingan minimum) bi : Y1. bi
150 Minimum = : 200
Y1
3 50 8 = 25
S1 S 2 Keluar basis
Pada tabel berikutnya, variabel basis menjadi S 1 dan X1, oleh karena itu matriks basis berubah menjadi :
1 3 0 8
B = [Y3,Y1] =
Invers matriks basisnya adalah : B-1 =
1 8 − 3 1 − 3 8 = [1x8] − [0 x 3] 0 1 0 18
Berdasarkan teori matriks, setiap nilai pada tabel berikutnya dapat diperoleh dengan mengalikan kolom persamaan asal dengan invers matriks basisnya.
bi = B-1bi =
1 − 3 8 150 75 0 1 200 = 25 8
S1 X1
Perhitungan diatas menghasilkan tabel kedua simpleks yang diperbaiki berikut :
Tabel 2. Tabel kedua simpleks diperbaiki B-1
basis
bi
S1
1
-3/8
75
X1
0
1/8
25
Ö Apakah tabel dua tersebut sudah optimum ? Untuk menjawab pertanyaan tersebut, perlu dihitung nilai Cj baru yang berkorespondensi dengan variabel non basis yaitu X 2 dan S2 sebagai berikut. Simpleks multiplier = π = CBB-1, dimana CB = [0,40].
1 − 3 8 = [0,5] 0 18
π = [0,40]
C2 = π Y1 – C1 = [0,5]
2 2 - 25 = - 15.
C4 = π Y2 – C2 = [0,5]
0 1 - 0 = 5.
Tabel akan optimum apabila nilai C j ≥ 0. Berarti tabel 2 belum optimum, karena nilai C2 yang baru masih negatif 15 yang berkorespodensi dengan variabel keputusan X 2. Pada tabel selanjutnya X2 masuk basis (kolom kunci). Untuk menentukan variabel mana diantara S1 dan X1 yang akan keluar basis (baris kunci), dipilih dari hasil minimum bi : Y2. Nilai vektor kolom baru yang berkorespondensi dengan X2 adalah Y2 = B-1Y2.
1 − 3 8 2 5 4 = 1 2 8 14
Y2 = 0
Variabel yang akan keluar basis adalah : bi
Y2
75 5 4 60 : = 25 14 100
Minimum =
S1 Keluar basis X1
Variabel basis yang baru menjadi X 2 dan X 1, dan menghasilkan matriks basis seperti berikut :
2 3 2 8
B = [Y2,Y1] =
Invers matriks basisnya adalah :
B-1 =
8 − 3 4 5 − 3 10 1 = [2x 8] − [2x 3] − 2 2 − 15 15
Nilai konstanta ruas kanan yang baru (bi ) untuk tabel berikutnya adalah :
bi = B-1bi =
4 5 − 3 10 − 1 1 5 5
150 200 =
60 10
X2 X1
Hasil perhitngan diatas dapat dibuat dalam tabel simpleks yang diperbaiki seperti berikut ini : Tabel 3. Tabel ketiga simpleks diperbaiki B-1
basis
bi
X2
4/5
-3/10
60
X1
-1/5
1/5
10
Ö Apakah tabel tiga tersebut sudah optimum ? Untuk menjawab pertanyaan tersebut, perlu dihitung nilai Cj baru yang berkorespondensi dengan variabel non basis (S1 dan S2). Simpleks multiplier = π = CBB-1, dimana CB = [25,40].
π = [25,40]
4
5
− 15
− 3 10 = [12;0,5] 1 5
C3 = π Y3 – C3 = [12;0,5]
1 0 - 0 = 12.
C4 = π Y4 – C4 = [12;0,5]
0 1 - 0 = 0,5.
Tabel akan optimum apabila nilai Cj ≥ 0. Oleh karena nilai baru dari C3 dan C4 yang baru positif 12 dan 0,5, maka tabel 3 adalah optimum, dengan nilai X1 dan X2 masing-masing adalah 10 dan 60. Sehingga nilai Z maksimum adalah 40(10) + 25(60) = 1.900. Solusi optimum metode simpleks diperbaiki sama dengan solusi optimum metode simpleks biasa. Akan tetapi penggunaan metode simpleks yang diperbaiki jauh lebih efisien jika dikerjakan secara manual.
Contoh 2 : Maximum Z = 50X1 + 80X2 + 0S1 + 0S2 - MA1 - MA2 Dk.
[1] [2] [3] [4]
X1 +
S1 X 2 - S2 + A1 X1 + X2 + A2 X1, X 2, S1, S2, A 1, A2
= 40 = 20 = 50 ≥0
Misalkan Y1, …, Y6 menunjukkan kolom yang berkorespondensi dengan X1, X2, S1, S2, A1, A2 dan bi berkorespondensi dengan konstanta ruas kanan, maka :
1 Y1 = 0 , Y2 = 1
0 1 , Y = 3 1
1 0 , Y = 4 0
0 − 1 , Y = 5 0
0 1 , Y = 6 0
0 0 , dan b = i 1
40 20 50
Variabel basis awalnya adalah S 1, A1 dan A2, sehingga tabel awal simpleks yang diperbaiki adalah sebagai berikut : Tabel 1. Tabel awal simpleks diperbaiki B-1
basis
bi
S1
1
0
0
40
A1
0
1
0
20
A2
0
0
1
50
Variabel manakah yang masuk basis ? Karena fungsi tujuan berbentuk maximum, maka variabel yang memiliki nilai Cj negatif terbesar adalah variabel yang akan masuk basis. Simpleks multiplier = π = CBB-1, dimana CB = [0,-M,-M]
1 0 0 π = [0,-M,-M] 0 1 0 = [0,-M,-M] 0 0 1
Cj = π Yj – Cj 1 1. C 1 = [0,-M,-M] 0 - 50 = - M – 50 1 0 2. C 2 = [0,-M,-M] 1 - 80 = - 2M – 80 1
1 3. C 3 = [0,-M,-M] 0 - 0 = 0 0 0 4. C 4 = [0,-M,-M] − 1 - 0 = M 0 0 5. C 5 = [0,-M,-M] 1 - (-M) = 0 0 0 6. C 6 = [0,-M,-M] 0 - (-M) = 0 1
C2
menghasilkan angla negatif terbesar yaitu – 2M – 80, oleh karena itu variabel X2 masuk basis. Variabel manakah diantara S1, A1 dan A2 yang akan keluar basis ? adalah hasil minimum dari bi : Y2, atau
40 Minimum = 20 : 50
0 ∞ 1 = 20 1 50
S1 A1 Keluar basis A2
Pada tabel pertama variabel basisnya adalah S1, A1 dan A2 yang berarti matriks basisnya adalah Y3, Y5, dan Y6 atau :
1 0 0 B= 0 1 0 0 0 1
baris 1 baris 2 baris 3
Untuk mencari invers matriks basis (B-1) dapat dilakukan dengan operasi pivot, di mana kolom pivotnya adalah kolom Y2. 1. Kalikan baris 2 dengan nol, kemudian hasilnya tambahkan dengan baris 1. Baris 2 = [0 1 0] x 0 Baris 1
= [0 0 0] = [1 0 0]
Nilai baru
= [1 0 0]
+
2. Bagi baris 2 dengan satu. Baris 2 = [0 1 0] : 1
= [0 1 0]
3. Kalikan baris 2 dengan minus satu, kemudian hasilnya tambahkan dengan baris 3.
Baris 2 = [0 1 0] x – 1 Baris 3
= [0 -1 0] = [0 0 1]
Nilai baru baris 3
= [0 -1 1]
+
1 0 0 Dengan demikian, B = 0 1 0 0 − 1 1 -1
Nilai konstanta ruas kanan yang baru dapat dicari dengan cara :
bi = B-1bi 1 0 0 40 bi = 0 1 0 20 = 0 − 1 1 50
40 20 30
S1 X2 A2
Hasil perhitungan di atas dapat dibuat dalam tabel kedua simpleks diperbaiki seperti berikut : Tabel 2. Tabel kedua simpleks diperbaiki B-1
basis
bi
S1
1
0
0
40
X2
0
1
0
20
A2
0
-1
1
30
Apakah tabel 2 tersebut sudah optimum ?, lihat proses berikut ini : Simpleks multiplier = π = CBB-1, dimana CB = [0,80,-M]
1 0 0 [0,80,-M] 0 1 0 = [0, 80+M, -M] 0 − 1 1
