4/7/2008
Metode Simpleks Diperbaiki (Revised Simplex Method) Kuliah 05
TI2231 Penelitian Operasional I
1
Materi Bahasan ① Dasar-dasar aljabar dari metode simpleks ② Metode simpleks yang diperbaiki
TI2231 Penelitian Operasional I
2
1
4/7/2008
① Dasar-dasar Aljabar Metode Simpleks
TI2231 Penelitian Operasional I
3
Dasar-dasar Metode Simpleks • Dalam PL, ruang solusi layak (feasible solution space) dikatakan membentuk himpunan konveks (convex set) jika segmen garis yang menghubungkan dua titik yang layak terletak dalam himpunan tersebut. • Suatu titik ekstrem (extreme point) dari himpunan konveks adalah titik layak yang tidak dapat terletak pada suatu segmen garis yang menghubungkan dua titik sebarang yang layak dalam himpunan tersebut. • Titik ekstrem sama dengan titik pojok (corner point). TI2231 Penelitian Operasional I
4
2
4/7/2008
Convex dan Nonconvex Set
x’ x”
x’ x”
Convex set
Nonconvex set
TI2231 Penelitian Operasional I
5
Convex Combination • Dalam solusi PL secara grafis, telah ditunjukkan bahwa solusi optimal selalu berkaitan dengan titik ekstrem (pojok) yang layak dari ruang solusi. • Tiap titik yang layak dapat ditentukan sebagai fungsi dari titik-titik ekstrem.
TI2231 Penelitian Operasional I
6
3
4/7/2008
• Diberikan titik-titik ekstrem x1, x2, x3, x4, x5 dan x6 titik yang layak x dapat dinyatakan sebagai kombinasi konveks (convex combination) dari titik-titik ekstrem menggunakan x 1x1 2 x 2 3x 3 4 x 4 5 x 5 6 x 6 dimana 1 2 3 4 5 6 1 1 , 2 , 3 , 4 , 5 , 6 0 TI2231 Penelitian Operasional I
7
Dari Titik-Titik Ekstrem ke Solusi Basis • Notasi matriks dari PL x : vektor n dari variabel A : matriks (m x n) dari koefisien pembatas c : vektor n dari koefisien fungsi tujuan • Masalah PL
Max (Min) z cx Ax b x0
TI2231 Penelitian Operasional I
8
4
4/7/2008
• Solusi basis dari Ax = b ditentukan dengan menetapkan n – m variabel sama dengan 0 dan memecahkan m persamaan dalam m variabel yang tak diketahui. • Hubungan antara definisi geometris dari titik-titik ekstrem dan definisi aljabar dari solusi basis: Titik-titik ekstrem {x| Ax = b} Solusi basis Ax = b
• Dengan menetapkan pembatas tak negatif x 0,
TI2231 Penelitian Operasional I
9
• Sistem Ax = b dapat dinyatakan dalam bentuk vektor n
P x b j 1
j
• Vektor Pj adalah kolom ke j dari A. • Himpunan bagian dari m vektor dikatakan membentuk suatu basis B jika dan hanya jika m vektor adalah independen linier. • Matriks B adalah nonsingular. • Jika xB adalah himpunan dari m variabel yang berkaitan dengan vektor nonsingular B, maka xB harus merupakan solusi basis. TI2231 Penelitian Operasional I
10
5
4/7/2008
• Dalam kasus ini Bx B b
• Diberikan B-1 adalah invers dari B, solusi basis dinyatakan dengan x B B 1b
• Jika B-1b 0, maka xB adalah layak.
TI2231 Penelitian Operasional I
11
• Definisi mengasumsikan bahwa terdapat n – m variabel sebagai nonbasis pada level 0. • Sistem dengan m persamaan dan n variabel tak diketahui, jumlah maksimum dari solusi basis (layak dan tak layak) adalah
Cnm
n! m!m n !
TI2231 Penelitian Operasional I
12
6
4/7/2008
Tentukan dan klasifikasikan (sebagai layak dan tak layak) dari semua solusi basis untuk sistem persamaan linier berikut:
x1 3 1 4 1 x2 2 2 2 x 2 3
TI2231 Penelitian Operasional I
B
BxB = b
(P1, P2)
1 3 x1 4 2 2 x2 2
(P1, P3) (P2, P3)
Solusi
x1 1 / 4 3 / 8 4 7 / 4 x2 1 / 4 1 / 8 2 3 / 4
13
Status Layak
Bukan basis
3 1 x2 4 2 2 x3 2
x2 1 / 4 1 / 8 4 3 / 4 x3 1 / 4 3 / 8 2 7 / 4
TI2231 Penelitian Operasional I
Tak layak
14
7
4/7/2008
1 3 1 4 x1 x2 x3 2 2 2 2
a2
P1
b
a1
P3
P2
TI2231 Penelitian Operasional I
15
Tabel Simpleks dalam Bentuk Matriks (1) • Misalkan diberikan PL sebagai berikut:
Max z cx Ax b x0 • Misalkan B adalah basis layak dari sistem Ax = b, x 0. • Misalkan xB berkaitan dengan himpunan variabel basis dengan cB adalah vektor koefisien fungsi tujuannya. TI2231 Penelitian Operasional I
16
8
4/7/2008
Tabel Simpleks dalam Bentuk Matriks (2) • Diberikan Pj adalah vektor ke j dari A, kolom tabel simpleks yang berkaitan dengan variabel xj dapat dinyatakan dengan
Basis
xj
Solusi
xB
B 1P j
B 1b
c j c B B 1P j TI2231 Penelitian Operasional I
c B B 1b 17
② Metode Simpleks yang Diperbaiki
TI2231 Penelitian Operasional I
18
9
4/7/2008
Metoda Simpleks yang Diperbaiki • Metoda simplex melakukan perhitungan pada seluruh tabel pada tiap iterasi. • Padahal, informasi yang dibutuhkan hanya: – Koefisien fungsi tujuan relatif – Kolom yang berkaitan dengan variabel yang masuk basis (kolom pivot) – Variabel basis saat ini dan nilainya (konstanta ruas kanan) TI2231 Penelitian Operasional I
19
Masalah PL Memaksimumkan Z = 3x1 + 2x2 dengan pembatas-pembatas: x1 + 2x2 6 2x1 + x2 8 – x1 + x2 1 x2 2 x1 ≥ 0, x2 ≥ 0
TI2231 Penelitian Operasional I
20
10
4/7/2008
Rumusan Bentuk Baku Memaksimumkan Z = 3x1 + 2x2 dengan pembatas-pembatas: x1 + 2x2 + x3 =6 2x1 + x2 + x4 =8 – x1 + x2 + x5 =1 x2 + x6 = 2 x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0, x5 ≥ 0, x6 ≥ 0
TI2231 Penelitian Operasional I
21
Solusi Basis Layak Awal (1) 1 2 P1 1 0
2 1 P2 1 1
1 0 P3 0 0
0 1 P4 0 0
0 0 P5 1 0
0 0 P6 0 1
6 8 b 1 2
TI2231 Penelitian Operasional I
22
11
4/7/2008
Solusi Basis Layak Awal (2) c B 0,0,0,0
xB = (x3, x4, x5, x6)
B P3
P4
Maka,
P5
1 0 P6 0 0
1 0 B 1 I 0 0
0 0 0 1 0 0 I 0 1 0 0 0 1
0 0 0 1 0 0 0 1 0 0 0 1
6 8 b B 1b 1 2
TI2231 Penelitian Operasional I
23
Pemeriksaan optimalitas (1)
Pengali simplex (simplex multiplier): 1 0 1 π 3 , 4 , 5 , 6 c B B 0,0,0,0 0 0
TI2231 Penelitian Operasional I
0 0 0 1 0 0 0,0,0,0 0 1 0 0 0 1
24
12
4/7/2008
Pemeriksaan optimalitas (2) Koefisien fungsi tujuan relatif untuk variabel non basis: 1 2 c1 c1 πP1 3 0,0,0,0 3 1 0 1 2 c2 c2 πP2 2 0,0,0,0 2 1 0
Karena terdapat c j 0 maka solusi belum optimal. TI2231 Penelitian Operasional I
25
Penentuan variabel yang masuk basis
Variabel yang masuk basis: x1 karena mempunyai koefisien fungsi tujuan relatif paling positif
TI2231 Penelitian Operasional I
26
13
4/7/2008
Penentuan variabel yang keluar basis 1 0 b B 1b 0 0
0 0 0 6 6 1 0 0 8 8 0 1 0 1 1 0 0 1 2 2
1 0 P1 B 1P1 0 0
0 0 0 1 1 1 0 0 2 2 0 1 0 1 1 0 0 1 0 0
6 8 1 2
min , , , 4
bersesuaian dengan variabel x4
TI2231 Penelitian Operasional I
27
Penentuan basis baru 1 0 0 0
1 1 0 0 2 0 1 0 1 0 0 1 0 0 0 0
1 1 / 2 0 1 / 2 1 B 0 1 / 2 0 0
1 1 / 2 0 1 / 2 0 1 / 2 0 0
0 0 0 0 0 1 1 0 0 0 1 0
0 0 0 0 1 0 0 1
x B x3 , x1 , x5 , x6 TI2231 Penelitian Operasional I
c B 0,3,0,0 28
14
4/7/2008
Solusi baru x B x3 , x1 , x5 , x6 x2 x 1 1 xB bB b x5 x6
c B 0,3,0,0 1 0 0 0
1 2 1/ 2 1/ 2 0
1 2 1 0 12 1 Z c B B b 0,3,0,0 0 1/ 2 0 0 TI2231 Penelitian Operasional I
6 2 8 4 1 5 2 2
0 0 1 0
0 0 0 1
0 0 1
6 8 12 1 1 2 29
0
0 0 0
Pemeriksaan optimalitas (1)
Pengali simplex (simplex multiplier): 1 1 / 2 0 1 / 2 π 3 , 1 , 5 , 6 c B B 1 0,3,0,0 0 1 / 2 0 0
TI2231 Penelitian Operasional I
0 0 0 0 0,3 / 2,0,0 1 0 0 1
30
15
4/7/2008
Pemeriksaan optimalitas (2) Koefisien fungsi tujuan relatif untuk variabel non basis: 2 1 c2 c2 πP2 2 0,3 / 2,0,0 1 / 2 1 1 0 1 c4 c4 πP4 0 0,3 / 2,0,0 3 / 2 0 0
Karena terdapat c j 0 maka solusi belum optimal. TI2231 Penelitian Operasional I
31
Penentuan variabel yang masuk basis
Variabel yang masuk basis: x2 karena mempunyai koefisien fungsi tujuan relatif paling positif
TI2231 Penelitian Operasional I
32
16
4/7/2008
Penentuan variabel yang keluar basis 1 1 / 2 0 1 / 2 b B 1b 0 1 / 2 0 0 1 1 / 2 0 1 / 2 P2 B 1P2 0 1 / 2 0 0
0 0 6 2 0 0 8 4 1 0 1 5 0 1 2 2 0 0 2 3 / 2 0 0 1 1 / 2 1 0 1 3 / 2 0 1 1 1
4 5 2 2 , , , 4/3 3 / 2 1/ 2 3 / 2 1
min
bersesuaian dengan variabel x3
TI2231 Penelitian Operasional I
33
Penentuan basis baru
1
1 2
0
0
0
12
0
0
0
12
1
0
0
0
0
1
2 3 1 3 1 3 2 3 B 1 1 1 2 3 1 3
2 3 1 3 1 3 2 3 1 1 2 3 1 3
32 1 2 32 1
0 0 1 0
0
0
0
0
1
0
0
1
1 0 0 0
0 0 0 1
x B x2 , x1 , x5 , x6 TI2231 Penelitian Operasional I
c B 2,3,0,0 34
17
4/7/2008
Solusi baru x B x2 , x1 , x5 , x6
c B 2,3,0,0
x2 2 3 1 3 x 1 3 2 3 1 1 xB b B b x5 1 1 2 3 1 3 x6
0 0 1 0
2 3 1 3 1 3 2 3 1 Z c B B b 2,3,0,0 1 1 2 3 1 3
0 0 1 0
0 6 4 3 0 8 10 3 0 1 3 1 2 2 3
0 6 0 8 38 3 0 1 1 2
TI2231 Penelitian Operasional I
35
Pemeriksaan optimalitas (1)
Pengali simplex (simplex multiplier): 2 / 3 1/ 3 1/ 3 2 / 3 π 2 , 1 , 5 , 6 c B B 1 2,3,0,0 1 1 2 / 3 1 / 3
TI2231 Penelitian Operasional I
0 0 0 0 1 / 3,4 / 3,0,0 1 0 0 1
36
18
4/7/2008
Pemeriksaan optimalitas (2) Koefisien fungsi tujuan relatif untuk variabel non basis: 1 0 c3 c3 πP3 0 1 / 3,4 / 3,0,0 1 / 3 0 0 0 1 c4 c4 πP4 0 1 / 3,4 / 3,0,0 4 / 3 0 0
Karena semua c j 0 maka solusi optimal. TI2231 Penelitian Operasional I
37
Solusi optimal x2 2 / 3 1/ 3 x 1/ 3 2 / 3 1 1 xB bB b x5 1 1 2 / 3 1 / 3 x6
0 0 1 0
0 6 4 / 3 0 8 10 / 3 0 1 3 1 2 2 / 3
4/3 10 / 3 38 / 3 Z c B b 2,3,0,0 3 2/3 TI2231 Penelitian Operasional I
38
19
4/7/2008
Keuntungan Metode Simpleks yang Diperbaiki • Mengurangi waktu komputasi • Menghemat memori komputer • Mempermudah pemahaman untuk topik lanjutan dari pemrograman linier (teori dualitas, analisis sensitivitas)
TI2231 Penelitian Operasional I
39
Hubungan Tabel Simpleks dengan Matriks B-1 (Iterasi 0)
cj
3
2
0
0
0
0
cB
Konstanta
Basis
x1
x2
x3
x4
x5
x6
0
x3
1
2
1
0
0
0
6
0
x4
2
1
0
1
0
0
8
0
x5
-1
1
0
0
1
0
1
0
x6
0
1
0
0
0
1
2
Baris c
3
2
0
0
0
0
Z=0
TI2231 Penelitian Operasional I
40
20
4/7/2008
Hubungan Tabel Simpleks dengan Matriks B-1 (Iterasi 1)
cj
3
2
0
0
0
0
x1
x2
x3
x4
x5
x6
cB
Konstanta
Basis 0
x3
0
3/2
1
-1/2
0
0
2
3
x1
1
1/2
0
1/2
0
0
4
0
x5
0
3/2
0
1/2
1
0
5
0
x6
0
1
0
0
0
1
2
Baris c
0
1/2
0
-3/2
0
0
Z = 12
TI2231 Penelitian Operasional I
41
Hubungan Tabel Simpleks dengan Matriks B-1 (Iterasi 2)
cj
3
2
0
0
0
0
cB
Konstanta
Basis
x1
x2
x3
x4
x5
x6
2
x2
0
1
2/3
-1/3
0
0
4/3
3
x1
1
0
-1/3
2/3
0
0
10/3
0
x5
0
0
-1
1
1
0
3
0
x6
0
0
-2/3
1/3
0
1
2/3
Baris c
0
0
-1/3
-4/3
0
0
Z = 122/3
TI2231 Penelitian Operasional I
42
21
