METODE SIMPLEKS YANG DIREVISI 1. Bentuk Standar Dalam Matriks Maksimumkan atau minimumkan:
Z = CX
Batasan:
(A,I)X = b
Contoh: Maksimumkan:
Z = 3X1 + 2X2
Batasan:
X1 + 2X2 ≤ 6 2X1 + X2 ≤ 8 -X1 + X2 ≤ 1 X2 ≤ 2
Bentuk standar simpleks: Maksimumkan:
Z = 3X1 + 2X2 + 0X3 – 0X4 + 0X5 + 0X6
Batasan:
X1 + 2X2 + X3 = 6 2X1 + X2 + X4 = 8 -X1 + X2 + X5 = 1 X2 + X6 = 2
Bentuk standar matriks:
Maksimumkan:
Batasan:
⎡X1 ⎤ ⎢X ⎥ ⎢ 2⎥ ⎢X 3 ⎥ Z = (3 2 0 0 0 0 ) ⎢ ⎥ ⎢X 4 ⎥ ⎢X ⎥ ⎢ 5⎥ ⎣⎢ X 6 ⎦⎥ ⎡1 ⎢2 ⎢ ⎢− 1 ⎢ ⎣0
2 1 0 0 0⎤ 1 0 1 0 0⎥⎥ 1 0 0 1 0⎥ ⎥ 1 0 0 0 1⎦
⎡X1 ⎤ ⎢X ⎥ ⎢ 2 ⎥ ⎡6 ⎤ ⎢ X 3 ⎥ ⎢8 ⎥ ⎢ ⎥=⎢ ⎥ ⎢ X 4 ⎥ ⎢1 ⎥ ⎢ X ⎥ ⎢⎣2⎥⎦ ⎢ 5⎥ ⎢⎣ X 6 ⎥⎦
2. Pemecahan Dasar dan Basis (A,I)X = b memiliki m persamaan dan n variable yang tidak diketahui. Sebuah pemecahan dasar diperoleh dengan menetapkan n – m variable sama dengan nol dan
JHON HENDRI – RISET OPERASIONAL – UNIVERSITAS GUNADARMA ‐ 2009
Page 1
lalu memecahkan m persamaan dengan m variable yang tidak diketahui. Secara matematis anggaplah: n
( A, I )X = ∑ Pj X J j
Dimana Pj adalah vector kolom ke – j dari (A,I). Dari contoh diatas, dimana kita memiliki m = 4 dan n = 6. Ini berarti basis terdiri dari m = 4 vektor dan n – m = (6 – 4 = 2) variable yang berkaitan, dengan vector sisanya ditetapkan sama dengan nol. Dengan menganggap X3 = X4 = X5 = X6 = 0, kita menemukan bahwa vector: ⎡1 ⎤ ⎢0 ⎥ P3 = ⎢ ⎥ ⎢0 ⎥ ⎢ ⎥ ⎣0 ⎦
⎡0 ⎤ ⎢1 ⎥ P4 = ⎢ ⎥ ⎢0 ⎥ ⎢ ⎥ ⎣0 ⎦
⎡1 ⎢0 B = (P3 , P4 , P5 , P6 ) = ⎢ ⎢0 ⎢ ⎣0
⎡0 ⎤ ⎢0 ⎥ P5 = ⎢ ⎥ ⎢1 ⎥ ⎢ ⎥ ⎣0 ⎦
⎡0 ⎤ ⎢0 ⎥ P6 = ⎢ ⎥ ⎢0 ⎥ ⎢ ⎥ ⎣1 ⎦
0 0 0⎤ 1 0 0⎥⎥ 0 1 0⎥ ⎥ 0 0 1⎦
3. Table Simpleks Dalam Bentuk Matriks Maksimumkan atau minimumkan:
Z = CX
Batasan:
(A,I)X = b
Bagi vector X kedalam XI dan XII, dimana XII bersesuaian dengan elemen-elemen dari X yang berkaitan dengan basis awal B = I. Bagi C kedalam CI dan CII untuk bersesuaianan dengan XI dan XII. Jadi bentuk standar dapat ditulis sebagai: Maksimumkan :
Z = CX; menjadi: Z – CIXI – CIIXII = 0
Batasan:
(A,I)X = b;
Karena XII bersesuaian dengan elemen-elemen dari X yang berkaitan dengan basis awal B = I, sehingga:
AXI + IXII = b ⎡1 − C I ⎢0 A ⎣
− C II ⎤ I ⎥⎦
⎡Z ⎤ ⎢ X ⎥ = ⎡0 ⎤ ⎢ I ⎥ ⎢b ⎥ ⎢⎣ X II ⎥⎦ ⎣ ⎦
Disetiap iterasi, anggaplah XB mewakili variable dasar saat ini dengan B basis yang berkaitan dengannya. Berarti XB mewakili m elemen dari X dengan B mewakili vector
JHON HENDRI – RISET OPERASIONAL – UNIVERSITAS GUNADARMA ‐ 2009
Page 2
(A,I) yang berkaitan dengan XB. Anggaplah CB adalah elemen C yang berkaitan dengan XB, sehingga: Z = CBXB; sama dengan Z - CBXB = 0, dan BXB = b ⎡1 − C B ⎤ ⎢0 B ⎥ ⎣ ⎦
⎡ Z ⎤ ⎡0 ⎤ ⎢ X ⎥ = ⎢b ⎥ sama dengan: ⎣ B⎦ ⎣ ⎦
−1 −1 ⎡ Z ⎤ ⎡1 C B B ⎤ ⎡0⎤ ⎡C B B b ⎤ = = ⎢ −1 ⎥ ⎢X ⎥ ⎢ −1 ⎥ ⎢ ⎥ ⎣ B ⎦ ⎢⎣0 B ⎥⎦ ⎣b⎦ ⎢⎣ B b ⎥⎦
Table simpleks yang bersesuaian dengan XB diperoleh dengan mempertimbangkan:
⎡1 C B B −1 ⎤ ⎢ −1 ⎥ ⎢⎣0 B ⎥⎦
⎡1 − C I ⎢0 A ⎣
− C II ⎤ I ⎥⎦
⎡Z ⎤ −1 ⎢ X ⎥ = ⎡1 C B B ⎤ ⎢ I ⎥ ⎢⎢0 B −1 ⎥⎥ ⎦ ⎢⎣ X II ⎥⎦ ⎣
⎡1 − C i + C B B −1 A − C II + C B B −1 I ⎤ ⎢ ⎥ B −1 A B −1 I ⎢⎣0 ⎥⎦
⎡0 ⎤ ⎢b ⎥ ⎣ ⎦
⎡Z ⎤ −1 ⎢ X ⎥ = ⎡C B B b ⎤ ⎢ I ⎥ ⎢⎢ B −1b ⎥⎥ ⎦ ⎢⎣ X II ⎥⎦ ⎣
Ingat: XII bersesuaian dengan elemen-elemen dari X yang berkaitan dengan basis awal B = I, sehingga iterasi simpleks umum dalam bentuk matriks: Dasar
XII
XI
Pemecahan
Z
CBB-1A - CI
CBB-1 – CII
CBB-1b
XB
B-1A
B-1
B-1b
4. Langkah-Langkah Metode Simpleks Primal Yang Direvisi.
Langkah 1: Penentuan variable masuk Pj. Hitung Y = CBB-1 untuk setiap vector non dasar Pj, hitung Zj – Cj = YPj - Cj Untuk program maksimalisasi (minimalisasi), vector Pj dipilih yang memiliki Zj – Cj paling negative (positif) (tentukan sembarang jika terdapat lebih dari satu yang sama). Jika semua Zj – Cj ≥ 0 (≤ = 0), pemecahan optimal telah dicapai dan diketahui dengan XB = B-1b dan Z = CBXB
JHON HENDRI – RISET OPERASIONAL – UNIVERSITAS GUNADARMA ‐ 2009
Page 3
Langkah 2. Penentuan variable keluar Pr. a. Nilai variable dasar saat ini yaitu: XB = B-1b b. Koefisien batasan dari variable masuk yaitu: αj = B-1Pj variable keluar Pr (baik maksimalisasi maupun minimalisasi) harus berkaitan dengan:
(
⎡ B −1b
θ = min ⎢
⎣ α
j k
)
k
⎤ , α kj ≥ 0⎥ ⎦
Langkah 3. Penentuan basis berikutnya.
dimana:
⎡− α 1j / α rj ⎤ ⎢ ⎥ j j ⎢− α 2 / α r ⎥ ⎢ ⎥ M ⎥ ξ =⎢ ⎢+ 1 / α rj ⎥ ⎢ ⎥ M ⎢ ⎥ ⎢− α j / α j ⎥ ⎣ m r⎦
Dari contoh berikut, maka langkah-langkah perhitungan metode simpleks primal yang direvisi adalah sebagai berikut: Maksimumkan:
Z = 3X1 + 2X2 + 0X3 – 0X4 + 0X5 + 0X6
Batasan:
X1 + 2X2 + X3 = 6 2X1 + X2 + X4 = 8 -X1 + X2 + X5 = 1 X2 + X6 = 2
Pemecahan Awal:
XB = (X3,X4,X5,X6) CB = (0,0,0,0) ⎡1 ⎢0 B = (P3 , P4 , P5 , P6 ) = ⎢ ⎢0 ⎢ ⎣0
0 1 0 0
0 0 1 0
0⎤ 0⎥⎥ =I 0⎥ ⎥ 1⎦
B-1 = I
JHON HENDRI – RISET OPERASIONAL – UNIVERSITAS GUNADARMA ‐ 2009
Page 4
Iterasi Pertama:
Langkah 1. Perhitungan Zj – Cj untuk non dasar P1 dan P2 ⎡1 ⎢0 -1 Y = C B B = (0, 0, 0, 0) ⎢ ⎢0 ⎢ ⎣0
0 1 0 0
0 0 1 0
0⎤ 0⎥⎥ = [0, 0, 0, 0] 0⎥ ⎥ 1⎦
Z1 – C1, Z2 – C2 = Y(P1,P2) – (C1,C2) ⎡1 ⎢2 Z1 - C1 , Z 2 - C 2 = [0,0,0,0] ⎢ ⎢- 1 ⎢ ⎣0
2⎤ 1⎥⎥ − [3,2] 1⎥ ⎥ 1⎦
Z1 – C1, Z2 – C2 = (-3,-2) Karena P1 memiliki nilai paling negative, maka P1 ditetapkan sebagai vector masuk. Langkah 2. Penentuan vector keluar dengan diketahui bahwa P1 memasuki basis. ⎡1 0 0 0⎤ ⎡6⎤ ⎡6⎤ ⎢0 1 0 0⎥ ⎢8 ⎥ ⎢8 ⎥ −1 ⎥⎢ ⎥=⎢ ⎥ X B = B b = Ib = b = ⎢ ⎢0 0 1 0⎥ ⎢1 ⎥ ⎢1 ⎥ ⎥⎢ ⎥ ⎢ ⎥ ⎢ ⎣0 0 0 1⎦ ⎣2⎦ ⎣2⎦ ⎡1 0 0 0⎤ ⎡1 ⎤ ⎡1 ⎤ ⎢0 1 0 0 ⎥ ⎢ 2 ⎥ ⎢ 2 ⎥ ⎥⎢ ⎥=⎢ ⎥ α 1 = B −1 P1 = IP1 = P1 = ⎢ ⎢0 0 1 0⎥ ⎢− 1⎥ ⎢− 1⎥ ⎥⎢ ⎥ ⎢ ⎥ ⎢ ⎣0 0 0 1⎦ ⎣0 ⎦ ⎣0 ⎦
Perhitungan untuk langkah 1 dan 2 dapat diringkaskan sebagai berikut: Dasar
X1
X2
X3
X4
X5
X6
Pemecahan
Z
-3
-2
0
0
0
0
0
X3
1
6
X4
2
8
X5
-1
1
X6
0
2
Jadi: θ = min (6/1, 8/2, --, --) = (6, 4, --, --) = 4, yang bersesuaian dengan X4, dengan demikian P4 adalah vector keluar dengan nilai α 21 = 2 , sehingga:
JHON HENDRI – RISET OPERASIONAL – UNIVERSITAS GUNADARMA ‐ 2009
Page 5
Langkah 3. Penentuan inverse basis berikutnya. ⎡ − 1 / 2 ⎤ ⎡ − 1 / 2⎤ ⎢+ 1 / 2 ⎥ ⎢1 / 2 ⎥ ⎥ ⎥=⎢ ξ =⎢ ⎢− (− 1 / 2)⎥ ⎢1 / 2 ⎥ ⎥ ⎥ ⎢ ⎢ ⎦ ⎣ − 0 / 2 ⎦ ⎣0 Maka basis berikutnya:
−1 Bnext = EB −1
⎡1 ⎢0 = EI = E = ⎢ ⎢0 ⎢ ⎣0
0 1 0 0
0 0 1 0
0⎤ 0⎥⎥ 0⎥ ⎥ 1⎦
⎡1 ⎢0 ⎢ ⎢0 ⎢ ⎣0
− 1/ 2 1/ 2 1/ 2 0
0 0 1 0
0 ⎤ ⎡1 0⎥⎥ ⎢⎢0 = 0 ⎥ ⎢0 ⎥ ⎢ 1 ⎦ ⎣0
− 1/ 2 1/ 2 1/ 2 0
0 0 1 0
0⎤ 0⎥⎥ 0⎥ ⎥ 1⎦
Basis baru ini berkaitan dengan vector dasar: XB = (X3,X1,X5,X6) CB = (0,3,0,0) ⎡1 ⎢0 B = (P3 , P1 , P5 , P6 ) = ⎢ ⎢0 ⎢ ⎣0
− 1/ 2 1/ 2 1/ 2 0
0 0 1 0
0⎤ 0⎥⎥ −1 = Bnext 0⎥ ⎥ 1⎦
Iterasi Kedua:
Langkah 1. Perhitungan Zj – Cj untuk non dasar P2 dan P4 ⎡1 ⎢0 -1 Y = C B B = (0, 3, 0, 0) ⎢ ⎢0 ⎢ ⎣0 Y = C B B-1 =
− 1/ 2 1/ 2 1/ 2 0
0 0 1 0
0⎤ 0⎥⎥ 0⎥ ⎥ 1⎦
{(0*1 + 3*0 + 0*0 + 0*0), (3*-1/2 + 3*1/2 + 3*1/2 + 3*0), (0*0 + 0*0 + 0*1 + 0*0), (0*0 + 0*0 + 0*0 + 0*1)}
Y = C B B-1 =
(0, 3/2, 0, 0)
Z2 – C2, Z4 – C4 = Y(P2,P4) – (C2,C4) ⎡2 ⎢1 Z 2 - C 2 , Z 4 - C 4 = [0, 3/2, 0, 0] ⎢ ⎢1 ⎢ ⎣1
0⎤ 1 ⎥⎥ − [2, 0] 0⎥ ⎥ 0⎦
Z2 – C2, Z4 – C4 = {(0*2 + 3/2*1 + 0*1 + 0*1), (0*0 + 3/2*1 + 0*0 + 0*0)} – (2, 0) Z2 – C2, Z4 – C4 = (3/2, 3/2) – (2, 0) = (-1/2, 3/2) JHON HENDRI – RISET OPERASIONAL – UNIVERSITAS GUNADARMA ‐ 2009
Page 6
Karena P2 memiliki nilai paling negative, maka P2 merupakan vector masuk. Langkah 2. Penentuan vector keluar dengan diketahui bahwa P2 memasuki basis. ⎡1 ⎢0 −1 XB = B b = ⎢ ⎢0 ⎢ ⎣0 ⎡1 ⎢0 α 2 = B −1 P2 = ⎢ ⎢0 ⎢ ⎣0
− 1 / 2 0 0 ⎤ ⎡6 ⎤ ⎡(1 * 6) + (−1 / 2 * 8) + (0 * 1) + (0 * 2)⎤ ⎡2⎤ 1/ 2 0 0⎥⎥ ⎢⎢8 ⎥⎥ ⎢⎢(0 * 6) + (1 / 2 * 8) + (0 * 1) + (0 * 2) ⎥⎥ ⎢⎢4⎥⎥ = = 1 / 2 1 0 ⎥ ⎢1 ⎥ ⎢(0 * 6) + (1 / 2 * 8) + (1 * 1) + (0 * 2) ⎥ ⎢5 ⎥ ⎥⎢ ⎥ ⎢ ⎥ ⎢ ⎥ 0 0 1 ⎦ ⎣2⎦ ⎣(0 * 6) + (0 * 8) + (0 * 1) + (1 * 2) ⎦ ⎣ 2⎦ − 1 / 2 0 0 ⎤ ⎡2⎤ ⎡(1 * 2) + (−1 / 2 * 1) + (0 * 1) + (0 * 1)⎤ ⎡3 / 2⎤ 1/ 2 0 0⎥⎥ ⎢⎢1 ⎥⎥ ⎢⎢(0 * 2) + (1 / 2 * 1) + (0 * 1) + (0 * 1) ⎥⎥ ⎢⎢1 / 2 ⎥⎥ = = 1 / 2 1 0 ⎥ ⎢1 ⎥ ⎢(0 * 2) + (1 / 2 * 1) + (1 * 1) + (0 * 1) ⎥ ⎢3 / 2⎥ ⎥ ⎥ ⎢ ⎥⎢ ⎥ ⎢ 0 0 1 ⎦ ⎣1 ⎦ ⎣(0 * 2) + (0 * 1) + (0 * 1) + (1 * 1) ⎦ ⎣1 ⎦
Perhitungan untuk langkah 1 dan 2 dapat diringkaskan sebagai berikut: Dasar
X1
X2
X3
X4
X5
X6
Z
0
-1/2
0
3/2
0
0
Pemecahan
X3
3/2
2
X1
1/2
4
X5
3/2
5
X6
1
2
Jadi: θ = min (2/(3/2), 4/(1/2), 5/(3/2), 2/1) = (4/3, 8, 10/3, 2) = 4/3, yang bersesuaian dengan X3, dengan demikian P3 adalah vector keluar dengan nilai α 12 = 4 / 3 , sehingga: Langkah 3. Penentuan inverse basis berikutnya. ⎡+ 1 /(3 / 2) ⎤ ⎡2 / 3 ⎤ ⎢− 1 / 2 /(3 / 2) ⎥ ⎢− 1 / 3 ⎥ ⎥ ⎥=⎢ ξ =⎢ ⎢− 3 / 2 / (3 / 2)⎥ ⎢− 1 ⎥ ⎥ ⎥ ⎢ ⎢ ⎣− 1 /(3 / 2) ⎦ ⎣− 2 / 3⎦ Maka basis berikutnya:
−1 Bnext
0 0 ⎡2 / 3 ⎢− 1 / 3 1 0 =⎢ ⎢− 1 0 1 ⎢ ⎣− 2 / 3 0 0
0⎤ 0 ⎥⎥ 0⎥ ⎥ 1⎦
⎡1 ⎢0 ⎢ ⎢0 ⎢ ⎣0
− 1/ 2 1/ 2 1/ 2 0
0 0 1 0
0⎤ 0⎥⎥ 0⎥ ⎥ 1⎦
JHON HENDRI – RISET OPERASIONAL – UNIVERSITAS GUNADARMA ‐ 2009
Page 7
= (2/3*1+0+0+0), (2/3*-1/2+0+0+0), (0), (0) = (-1/3*1+0+0+0), (-1/3*-1/2+1*1/2+0+0), (0), (0) = (-1*1+0+0+0), (-1*-1/2+0+1*1/2+0), (0+0+1+0), (0) = (-2/3*1+0+0+0), (-2/3*-1/2+0+0+0), (0), (1) −1 = Sehingga: Bnext
2/3
-1/3
0
0
-1/3
2/3
0
0
-1
1
1
0
-2/3
1/3
0
1
Basis baru ini berkaitan dengan vector dasar: XB = X2, X1, X5, X6 CB = (2, 3, 0, 0) Iterasi Ketiga:
Langkah 1. Perhitungan Zj – Cj untuk non dasar P3 dan P4 ⎡2 / 3 − 1 / 3 ⎢− 1 / 3 2 / 3 -1 Y = C B B = (2, 3, 0, 0 ) ⎢ ⎢− 1 1 ⎢ ⎣− 2 / 3 1 / 3
0 0 1 0
0⎤ 0⎥⎥ 0⎥ ⎥ 1⎦
Y = C B B-1 =
{(2*2/3 + 3*-1/3 + 0 + 0), (2*-1/3 + 3*2/3 + 0 + 0), (0), (0)}
Y = C B B-1 =
(1/3, 4/3, 0, 0)
Z3 – C3, Z4 – C4 = Y(P3,P4) – (C3,C4) ⎡1 ⎢0 Z 3 - C 3 , Z 4 - C 4 = [1/3, 4 / 3, 0, 0] ⎢ ⎢0 ⎢ ⎣0
0⎤ 1 ⎥⎥ − [0, 0] 0⎥ ⎥ 0⎦
Z3 – C3, Z4 – C4 = {(1/3*1 + 0 + 0 + 0), (0 + 4/3*1 + 0 + 0)} – (0, 0) Z3 – C3, Z4 – C4 = (1/3, 4/3) – (0, 0) = (1/3, 4/3) Karena semua Zj – Cj ≥ 0, basis terakhir ini optimal.
JHON HENDRI – RISET OPERASIONAL – UNIVERSITAS GUNADARMA ‐ 2009
Page 8
Pemecahan Optimal: ⎡X 2 ⎤ ⎡2 / 3 − 1 / 3 ⎢X ⎥ ⎢ ⎢ 1 ⎥ = B −1b = ⎢− 1 / 3 2 / 3 ⎢X 5 ⎥ ⎢− 1 1 ⎢ ⎥ ⎢ ⎣− 2 / 3 1 / 3 ⎣X 6 ⎦
0 0⎤ 0 0⎥⎥ 1 0⎥ ⎥ 0 1⎦
⎡6 ⎤ ⎡(2 / 3 * 6 + −1 / 3 * 8 + 0 + 0) ⎤ ⎡4 / 3 ⎤ ⎢8 ⎥ ⎢(−1 / 3 * 6 + 2 / 3 * 8 + 0 + 0) ⎥ ⎢10 / 3⎥ ⎢ ⎥=⎢ ⎥=⎢ ⎥ ⎢1 ⎥ ⎢(−1 * 6 + 1 * 8 + 1 * 1 + 0) ⎥ ⎢3 ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎣ 2 ⎦ ⎣ ( − 2 / 3 * 6 + 1 / 3 * 8 + 0 + 1 * 2) ⎦ ⎣ 2 / 3 ⎦
⎡4 / 3 ⎤ ⎢10 / 3⎥ ⎥ = [2 * 4 / 3 + 3 * 10 / 3 + 0 + 0] = 38 / 3 = 12 2 Z = C B X B = (2, 3, 0, 0) ⎢ ⎢3 ⎥ 3 ⎥ ⎢ ⎣2 / 3 ⎦ Kesimpulan: X1 = 10/3 X2 = 4/3 Z = 38/3 REFERENSI 1. Taha, Hamdy A., Riset Operasi – Jilid 1, Jakarta: Binarupa Aksara, 1996
JHON HENDRI – RISET OPERASIONAL – UNIVERSITAS GUNADARMA ‐ 2009
Page 9
