HAFIDH MUNAWIR
Algoritma Simpleks dalam Notasi Matriks LP Secara umum: max z c1 x1 c2 x2 ... cn xn s.t. a11 x1 a12 x2 ... a1n xn b1 a21 x1 a22 x2 ... a2 n xn b2 .
.
.
.
.
.
.
.
. . . . am1 x1 am 2 x2 ... amn xn bm xi 0(i 1,2,..., n )
LP yang bersesuaian untuk Dakota max z 60 x1 30 x2 20 x3 0s1 0s2 0s3 s.t. 8 x1 6 x2 x3 s1 4 x1 2 x2 1.5 x3
48 s2
2 x1 1.5 x2 0.5 x3 x1 , x2 , x3 , s1 , s2 , s3 0
20 s3 8
Tableau Optimal dari LP Dakota Tableau 2 Baris 0 Baris 1 Baris 2 Baris 3
z 1 0 0 0
x1 0 0 0 1
x2 5 -2 -2 1.25
x3 0 0 1 0
s1 0 1 0 0
BV s1 , x3 , x1
s2 10 2 2 -0.5
s3 10 -8 -4 1.5
NBV x2 , s2 , s3
Atau dalam bentuk lain:
z
5 x2 2 x2 2 x2 x3 x1 1.25 x2
10 s2 10 s3 280 s1 2 s2 8s3 2 s2 4 s3
24 8
0.5s2 1.5s3 2
rhs 280 24 8 2
BV z=280 s1=24 x3=8 x1=2
BeberapaBVNotasi s , x , x 1
x BV
3
s1 x3 x1
1
NBV x2 , s2 , s3
x NBV
x2 s2 s3
Koefisien untuk BV pada struktur biaya di fungsi obyektif:
z 60 x1 30 x2 20 x3 0s1 0s2 0s3 c BV 0 20 60 Koefisien untuk NBV pada struktur biaya di fungsi obyektif:
c NBV 3 0 0 0
Beberapa Notasi
Koefisien untuk BV pada kendala dapat dinyatakan dalam bentuk matriks: 8 x1 6 x2 x3
s1
4 x1 2 x2 1.5 x3
48 s2
2 x1 1.5 x2 0.5 x3
x1 1 1 8 B 0 1. 5 4 0 0.5 2
x3
20
BV s1 , x3 , x1
s3 8
s1 1 1 8 as1 0 a3 1.5 a1 4 0 0.5 2
Beberapa Notasi
Koefisien untuk NBV pada kendala dapat dinyatakan dalam bentuk matriks: 8 x1 6 x2 x3
s1
4 x1 2 x2 1.5 x3 2 x1 1.5 x2 0.5 x3
x2
6 0 0 N 2 1 0 1.5 0 1
48 s2
20
NBV x2 , s2 , s3
s3 8
s2 s3 6 0 a2 2 as2 1 1.5 0
0 as3 0 1
Beberapa Notasi
Koefisien untuk rhs pada kendala dapat dinyatakan dalam bentuk vektor: 8 x1 6 x2 x3
s1
4 x1 2 x2 1.5 x3
48 s2
2 x1 1.5 x2 0.5 x3
48 b 20 8
20 s3 8
LP Dakota dalam notasi matriks max z 60 x1 30 x2 20 x3 0 s1 0s2 0s3 s.t. 8 x1 6 x2 x3 s1
48
4 x1 2 x2 1.5 x3
s2
2 x1 1.5 x2 0.5 x3
20 s3 8
x1 , x2 , x3 , s1 , s2 , s3 0
s1 x2 max z 0 20 60 x3 30 0 0 s2 x1 s3 1 1 8 s1 6 0 0 x2 48 s.t. 0 1.5 4 x3 2 1 0 s2 20 0 0.5 2 x1 1.5 0 1 s3 8
s1 x 0, 3 x1
x2 s 0 2 s3
c BV 0 20 60 x BV
c NBV 3 0 0 0
s1 6 0 0 x2 1 1 8 48 x3 x NBV s2 B 0 1.5 4 N 2 1 0 b 20 x1 1.5 0 1 s3 0 0.5 2 8
Dengan Notasi Matriks dan vektor:
max z c BV x BV c NBV x NBV s.t. Bx BV Nx NBV b x BV , x NBV 0
Penentuan solusi dalam notasi matriks Solusi suatu sistem persamaan dalam notasi matriks adalah dengan perkalian invers matriks Kendala LP dalam notasi matriks:
Bx BV Nx NBV b Solusi diperoleh jika BV mempunyai bentuk kanonik. Matriks bagi BV dalam bentuk matriks identitas hasil perkalian dengan invers-nya. -1
B BI
Mengalikan setiap suku dengan invers dari B
B-1Bx BV B-1Nx NBV B-1b
x BV B-1Nx NBV B-1b
Penentuan solusi dalam notasi 2 1 1 1 8 matriks B 0 2 Untuk LP Dakota: B 0 1.5 4 1
0 0.5 2
8 4 0 0.5 1.5
Dengan mengalikan invers dari B pada kendala:
x BV B-1Nx NBV B-1b 8 6 0 0 x 2 1 8 48 2 2 s1 1 x 0 2 1 0 s 0 20 2 4 2 4 3 2 x1 0 0.5 1.5 1.5 0 1 s3 0 0.5 1.5 8 8 x2 24 2 s1 2 x 2 s 8 2 4 3 2 x1 1.25 0.5 1.5 s3 2
Penentuan Solusi dalam notasi Matriks: untuk Kendala Tableau 2 Baris 0 Baris 1 Baris 2 Baris 3
z 1 0 0 0
x1 0 0 0 1
x2 5 -2 -2 1.25
x3 0 0 1 0
s1 0 1 0 0
s2 10 2 2 -0.5
s3 10 -8 -4 1.5
rhs 280 24 8 2
2 8 x2 24 s1 2 s 8 x 2 2 4 2 3 x1 1.25 0.5 1.5 s3 2 -1
B aj Kolom untuk peubah xj dalam kendala di tableau optimal: Kolom untuk rhs dalam kendala di tableau optimal:
-1
B b
BV z=280 s1=24 x3=8 x1=2
Perbandingan dengan Tableu Optimal Tableau 2 Baris 0 Baris 1 Baris 2 Baris 3
z 1 0 0 0
x1 0 0 0 1
x2 5 -2 -2 1.25
x3 0 0 1 0
s1 0 1 0 0
s2 10 2 2 -0.5
s3 10 -8 -4 1.5
rhs 280 24 8 2
BV z=280 s1=24 x3=8 x1=2
Misal: Kolom untuk peubah x2 dan dalam kendala di tableau optimal:
8 2 1 4 2 B 1 0 0 0.5 1.5
6 a2 2 1.5
2 B-1a 2 2 1.25
Kolom untuk peubah s2 dalam kendala di tableau optimal:
8 2 1 4 2 B 1 0 0 0.5 1.5
0 as2 1 0
2 B-1a s2 2 0.5
B-1a 2
Dengan cara sama untuk peubah yang lain
B-1a s2
Perbandingan dengan Tableu Optimal Tableau 2 Baris 0 Baris 1 Baris 2 Baris 3
z 1 0 0 0
x1 0 0 0 1
x2 5 -2 -2 1.25
s3 10 -8 -4 1.5
rhs 280 24 8 2
Kolom untuk rhs dalam kendala di tableau optimal:
B-1b
8 2 1 4 2 B 1 0 0 0.5 1.5
x3 0 0 1 0
s1 0 1 0 0
48 b 20 8
s2 10 2 2 -0.5
24 B-1b 8 2
BV z=280 s1=24 x3=8 x1=2
Penentuan solusi dalam notasi matriks: untuk Baris Nol (fungsi obyektif =0
z c BV x BV c NBV x NBV z c BV x BV c NBV x NBV 0 Di dalam tableau optimal, koefisien BV harus sama dengan nol, koefisien NBV ≠ 0 BV s1 , x3 , x1 Tableau 2 Baris 0
z 1
x1 0
x2 5
x3 0
s1 0
s2 10
s3 10
rhs 280
Dengan memanfaatkan persamaan pada kendala: lakukan ERO Tambahkan kendala Bx BV Nx NBV byang sudah dikalikan dengan matriks yang bersesuaian pada baris nol, untuk membuat jadi nol BV
Penentuan solusi dalam notasi matriks: untuk Baris Nol (fungsi obyektif z c BV x BV c NBV x NBV 0 (*) Kendala:
Kalikan dengan:c BV B
Bx BV Nx NBV b
c BV B -1Bx BV c BV B -1Nx NBV c BV B -1b
(*) + (**)
c BV x BV c BV B -1Nx NBV c BV B -1b (**)
z c BV x BV c NBV x NBV
0
c BV x BV c BV B -1Nx NBV c BV B -1b _____________________________
-1
z c BV B 1N c NBV x NBV c BV B 1b
Penentuan solusi dalam notasi matriks: untuk Baris Nol (fungsi obyektif
z c BV B 1N c NBV x NBV c BV B 1b Pada tableau optimal, koefisien NBV ≠ 0:
c BV B 1N c NBV Komponen dari matriks N (dan B) adalah vektor (kolom) koefisien setiap peubah NBV (dan BV) pada kendala: aj Komponen dari vektor CNBV (dan CBV ) adalah koefisien fungsi obyektif setiap peubah NBV (dan BV): cj Contoh LP Dakota: 6 6 0 0 N 2 1 0 a2 2 1.5 1.5 0 1
0 as2 1 0
0 as3 0 1
c NBV 3 0 0 0 c2
cs2
c s3
Penentuan solusi dalam notasi matriks: untuk Baris Nol (fungsi obyektif Secara umum koefisien baris nol pada tableau optimal per komponen:
c j c BV B 1a j c j
RHS baris nol pada tableau optimal:
c BV B -1b
Contoh LP Dakota: 8 2 1 0 0 6 4 a2 2 as 1 as 0 2 B 1 0 1 0 0.5 1.5 0 1.5 2
Koefisien untuk x2
3
6 2 30 1 0 10 10 c2 c BV B a 2 c2 1.5
c BV 0 10 10 c NBV 30 0 0 c BV B 1 0 10 10
35 30 5
Penentuan solusi dalam notasi matriks: untuk Baris Nol (fungsi obyektif 8 2 1 0 0 6 4 a2 2 as 1 as 0 2 B 1 0 1 0 0.5 1.5 0 1.5 2
Koefisien untuk s2
cs 2 c BV B 1a s2 cs2 Koefisien untuk s3
3
0 0 10 101 0 0
c BV 0 10 10
c BV B 1 0 10 10
c NBV 30 0 0
10 0 10
0 cs 3 c BV B 1a s3 cs3 0 10 100 0 10 0 10 1 Koefisien rhs baris nol (z maks): 48 c BV B -1b 0 10 1020 0 200 80 280 8
Ringkasan solusi optimal dalam notasi matriks -1 B Kolom untuk peubah xj dalam kendala di tableau optimal: a j
Kolom untuk rhs dalam kendala di tableau optimal:
B-1b
Koefisien baris nol pada tableau optimal per komponen:
c j c BV B 1a j c j RHS baris nol pada tableau optimal: c BV B -1b
Contoh LP dan solusinya dengan notasi Matriks max z x1 4 x2 s.t. x1 2 x2 6 2 x1 x2 8 x1 , x2 0 Diketahui solusi optimal mempunyai: BV x2 , s2 Tentukan tableau optimal dengan menggunakan metode matriks! Bentuk standar LP:
max z x1 4 x2 s.t. x1 2 x2 s1 2 x1 x2
6 s2 8
x1 , x2 , s1 , s2 0
max z x1 4 x2 s.t. x1 2 x2 s1 2 x1 x2
6 s2 8
x1 , x2 , s1 , s2 0
BV x2 , s2 NBV x1 , s1
Di dalam tableau optimal, peubah BV pasti mempunyai bentuk kanonik, tinggal menentukan kolom untuk peubah NBV Tentukan matriks/vektor yang diperlukan:
2 0 B 1 1
6 b 8
c BV 4 0
c NBV 1 0
1 B 1 2 1 2
Kolom untuk peubah x1 dalam kendala di tableau optimal: 1 B-1a1 2 1 2
0 1 12 3 1 2 2
0 1
Kolom untuk peubah s1 dalam kendala di tableau optimal:
12 B a s1 1 2 -1
Tableau Optimal
z
0 1 12 1 1 0 2 x1
x2
s1
Baris 0 Baris 1
1/2
1/2
Baris 2
3/2
-1/2
s2
rhs
Tableau Optimal
z
x1
x2
s1
s2
Baris 1
1/2
1
1/2
0
Baris 2
3/2
0
-1/2
1
rhs
Baris 0
Kolom untuk peubah BV dalam kendala di tableau optimal: Bentuk kanonik BV x , s 2
Kolom untuk peubah x2 :
Cross cek dengan rumus:
1 0
2
1 B-1a2 2 1 2
0 1 0 2 1 1 1 0
12 B a s2 1 2
0 0 0 1 1 1
Kolom untuk peubah s2 :
-1
Tableau Optimal
z
x1
x2 0
s1
s2 0
rhs
Baris 1
1/2
1
1/2
0
3
Baris 2
3/2
0
-1/2
1
5
Baris 0
Kolom untuk rhs pada tableau optimal: 1 2 -1 B b 1 2
0 6 3 1 8 5
Komponen baris nol untuk BV pada tableau optimal selalu sama dengan nol. BV x2 , s2 Komponen baris nol untuk NBV pada tableau optimal memerlukan hasil perkalian: 1 c BV B-1 4 0 2 1 2
0 2 0 1
Tableau Optimal
z
x2 0
s1 2
s2 0
rhs
Baris 0
x1 1
Baris 1
1/2
1
1/2
0
3
Baris 2
3/2
0
-1/2
1
5
c BV B-1 2 0 Komponen baris nol untuk NBV pada tableau optimal:
NBV x1 , s1
c NBV 1 0
1 c1 c BV B-1a1 c1 2 0 1 2 1 1 2 1 -1 cs1 c BV B a s1 cs1 2 0 0 2 0 2 0
Tableau Optimal Baris 0
z 1
x1 1
x2 0
s1 2
s2 0
rhs 12
z=12
Baris 1
0
1/2
1
1/2
0
3
x2=3
Baris 2
0
3/2
0
-1/2
1
5
s2=5
6 b 8 Komponen baris nol untuk rhs pada tableau optimal:
6 c BV B b 2 0 8 12 -1
Lengkapi kolom z Solusi optimal: x1 0, x2 3, s1 0, s2 5, z 12(max)
BV