Materi Bahasan ① Pengertian analisis sensitivitas ② Analisis sensitivitas dengan metode grafis ③ Analisis sensitivitas dengan metode simpleks
Analisis Sensitivitas (Sensitivity Analysis) Kuliah 07
TI2231 Penelitian Operasional I
1
TI2231 Penelitian Operasional I
2
Analisis Sensitivitas • Studi dalam perubahan solusi optimal dan nilai optimal karena perubahan dalam koefisien data input. • Perubahan:
① Pengertian Analisis Sensitivitas
– Koefisien fungsi tujuan – Konstanta ruas kanan – Koefisien matrix (koefisien teknologi) • Penambahan aktivitas atau variabel baru • Perubahan pengunaan sumber dari aktivitas (perubahan kolom) • Penambahan pembatas baru
TI2231 Penelitian Operasional I
3
TI2231 Penelitian Operasional I
4
Efek dari Perubahan • Perubahan yang mempengaruhi optimalitas
② Analisis Sensitivitas dengan Metode Grafis
– Perubahan koefisien fungsi tujuan – Penambahan aktivitas (variabel) baru – Perubahan penggunaan sumber dari aktivitas
• Perubahan yang mempengaruhi kelayakan – Perubahan konstanta ruas kanan – Penambahan pembatas baru
TI2231 Penelitian Operasional I
5
Analisis sensitivitas – Perubahan dalam sumber
6
Pembatas binding dan nonbinding (1) • Pembatas
• Masalah sensitivitas 1
– Binding → sumberdaya yang langka (scarce resource) – Nonbinding → sumberdaya yang berlebihan (abundant resource)
– Berapa banyak suatu sumber dapat ditingkatkan untuk memperbaiki nilai optimum dari fungsi tujuan Z? – Berapa banyak suatu sumber dapat diturunkan tanpa menyebabkan perubahan dalam solusi optimum saat ini?
TI2231 Penelitian Operasional I
TI2231 Penelitian Operasional I
7
TI2231 Penelitian Operasional I
8
(5)
(5)
Pembatas binding dan nonbinding (2)
x2
Peningkatan pembatas (1)
x2
Titik K : optimum yang baru Solusi optimal: x1* = 3 x2* = 2 Nilai optimal Z* = 13 Bahan A dapat ditingkatkan hingga = 3(1) + 2(2) = 7 ton
Binding Æ (1), (2) Nonbinding Æ (3), (4) (2)
(2)
(4) E (3)
D
F
E C
(1)
(3)
(1)
F
B A
B
TI2231 Penelitian Operasional I
x1
(6) 9
(5)
A
TI2231 Penelitian Operasional I
Peningkatan pembatas (2)
(2)
(3)
(4) E E
DD
E C
F
(1) B
A
(6)
10
Penurunan pembatas (3)
x2
Titik J : optimum yang baru Solusi optimal: x1* = 6 x2* = 0 Nilai optimal Z* = 18 Bahan B dapat ditingkatkan hingga = 2(6) + 1(0) = 12 ton
(2)
F
x1
(5)
x2
(3)
(4)
K
J
TI2231 Penelitian Operasional I
Konstanta ruas kanan : – x1 + x2 = -31/3 + 11/3 = -2 atau pembatas menjadi: – x1 + x2 ≤ -2 x2 - x 1 ≥ 2 ∴Solusi optimal saat ini tak berubah pada titik C walaupun selisih antara permintaan eksterior dengan interior lebih dari 2 ton.
(4)
D C
(1) B
x1
(6)
11
A
TI2231 Penelitian Operasional I
x1
(6)
12
(5)
Penurunan pembatas (4)
x2
Konstanta ruas kanan : x1 = 11/3 atau pembatas menjadi: x1 ≤ 11/3
(2)
(3)
D
F
– Sumberdaya mana yang perlu ditingkatkan?
∆max Z i yi = max ∆ bi ∆maxZi = perubahan maksimum dalam nilai Z akibat peningkatan pembatas i max ∆ bi = perubahan maksimum dari sumber/pembatas I = shadow price pembatas i yi
(4) C
(1) B
A
TI2231 Penelitian Operasional I
x1
(6)
13
Shadow price
TI2231 Penelitian Operasional I
14
Interpretasi
Perubahan maksimum dalam fungsi tujuan (dalam ribuan)
Shadow price
Sumberdaya
Jenis
Perubahan maksimum dalam sumber
1
Langka
7–6=1
13 – 122/3 = 1/3
1/ 3
2
Langka
12 – 8 = 4
18 – 122/3 = 51/3
4/ 3
3
Berlimpah
– 2 – 1 = –3
122/3 – 122/3 = 0
0
4
Berlimpah
11/3 – 2 = - 2/3
122/3 – 122/3 = 0
0
TI2231 Penelitian Operasional I
– Sumber yang diprioritaskan untuk ditingkatkan
• Masalah sensitivitas
∴Solusi optimal saat ini tak berubah pada titik C walaupun batas permintaan cat interior turun hingga 11/3 ton.
E
Analisis sensitivitas
15
• Sumber (2) (bahan B) seharusnya mendapatkan prioritas dalam pengalokasian dana • Sumber (3) dan (4) tidak perlu ditingkatkan
TI2231 Penelitian Operasional I
16
Analisis sensitivitas - Perubahan koefisien fungsi tujuan
(5)
x2 Z= c 1x 1 x2 + c2
• Perubahan dalam koefisien fungsi tujuan akan mempengaruhi slope dari garis lurus yang merepresentasikannya. • Perubahan dalam koefisien fungsi tujuan akan mengubah status dari suatu sumber (langka atau berlimpah) • Pertanyaan:
Peningkatan c2 Penurunan c1
– Berapa besar koefisien fungsi tujuan dapat diubah tanpa menyebabkan perubahan pada solusi (titik) optimal. – Berapa besar koefisien fungsi tujuan dapat diubah untuk merubah status sumber dari berlimpah ke langka, dan sebaliknya. TI2231 Penelitian Operasional I
(2)
(4) E (3)
D
F
C
(1) B
A
17
(5)
(5)
x2
x2
(4)
D
E C
(1)
(3)
F
B A
(6)
18
(2)
(4) F
x1
Slope Z sama dengan slope pembatas (2)
(2)
(3)
Peningkatan c1 Penurunan c2
TI2231 Penelitian Operasional I
Slope Z sama dengan slope pembatas (1)
E
Titik C tetap sebagai titik optimal sepanjang slope dari Z berubah antara slope pembatas (1) dan (2)
TI2231 Penelitian Operasional I
D C
(1) B
x1
(6)
19
A
TI2231 Penelitian Operasional I
x1
(6)
20
Rentang c1 untuk mempertahankan solusi optimal pada titik C
Rentang c2 untuk mempertahankan solusi optimal pada titik C
Minimum dari c1 Æ slope Z = slope pembatas (1) c1 1 = → c1 = 1 2 2 Minimum dari c1 Æ slope Z = slope pembatas (2) c1 2 = → c1 = 4 2 1
Minimum dari c2 Æ slope Z = slope pembatas (2) 3 2 = → c2 = 3 2 c2 1 Minimum dari c1 Æ slope Z = slope pembatas (1) 3 1 = → c2 = 6 c2 2
Rentang c1 agar titik C tetap sebagai titik optimal:
Rentang c2 agar titik C tetap sebagai titik optimal:
1 ≤ c1 ≤ 4
3 ≤c ≤6 2 2
TI2231 Penelitian Operasional I
21
TI2231 Penelitian Operasional I
22
Masalah Pemrograman Linier
③ Analisis Sensitivitas dalam Metode Simpleks
TI2231 Penelitian Operasional I
Memaksimumkan Z = 3x1 + 2x2 dengan pembatas-pembatas: (Bahan A) x1 + 2x2 ≤ 6 2x1 + x2 ≤ 8 (Bahan B) – x1 + x2 ≤ 1 (Selisih permintaan cat interior dan eksterior) x2 ≤ 2 (Permintaan cat interior) x1 ≥ 0 x2 ≥ 0 23
TI2231 Penelitian Operasional I
24
Tabel Awal cj
3
2
0
0
Tabel Akhir (Tabel Optimal) 0
cj
0
cB
Konstanta
Basis
x1
x2
x3
x4
x5
x6
3
2
0
0
0
0
cB
Konstanta
Basis
x1
x2
x3
x4
x5
x6
0
x3
1
2
1
0
0
0
6
2
x2
0
1
2/3
-1/3
0
0
4/3
0
x4
2
1
0
1
0
0
8
3
x1
1
0
-1/3
2/3
0
0
10/3
0
x5
-1
1
0
0
1
0
1
0
x5
0
0
-1
1
1
0
3
0
x6
0
1
0
0
0
1
2
0
x6
0
0
-2/3
1/3
0
1
2/3
Baris c
3
2
0
0
0
0
Z=0
Baris c
0
0
-1/3
-4/3
0
0
Z = 38/3
TI2231 Penelitian Operasional I
25
Perubahan dalam Koefisien Fungsi Tujuan
TI2231 Penelitian Operasional I
Perubahan dalam Koefisien Fungsi Tujuan untuk Variabel Basis ⎡ 2/3 ⎤ ⎢ −1/ 3⎥ ⎥ c3 = 0 − (c1 ,2,0,0) ⎢ ⎢ −1 ⎥ ⎢ ⎥ ⎣− 2 / 3⎦ ⎡− 1 / 3⎤ ⎢ 2/3 ⎥ ⎥ c4 = 0 − (c1 ,2,0,0) ⎢ ⎢ 1 ⎥ ⎢ ⎥ ⎣ 1/ 3 ⎦
Variabel x1:
• Perubahan koefisien fungsi tujuan untuk variabel basis • Perubahan koefisien fungsi tujuan untuk variabel non basis • Perubahan koefisien fungsi tujuan untuk variabel basis dan non basis
Æ c3 =
− 2c1 + 2 3
Æ
c1 − 4 3
c4 =
Kondisi tetap optimal : − 2c1 + 2 ≤ 0 Æ c1 ≥ 1 c3 ≤ 0 Æ 3 c4 ≤ 0 Æ
TI2231 Penelitian Operasional I
26
27
c1 − 4 ≤0 3
Æ c1 ≤ 4
TI2231 Penelitian Operasional I
1 ≤ c1 ≤ 4 28
Variabel x1:
c1 = 4 → Z = 4 x1 + 2 x2
cj
0
0
0
x1
x2
x3
x4
x5
x6
2
x2
0
1
2/3
-1/3
0
0
4/3
4
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
0
0
-2
0
0
0
Z = 16
Baris c
29
TI2231 Penelitian Operasional I
c1 = 5 → Z = 5 x1 + 2 x2
cj
30
5
2
0
0
0
0
x1
x2
x3
x4
x5
x6
cB
⎡ 2/3 ⎤ ⎢ −1/ 3⎥ ⎥ = −8 / 3 c3 = 0 − (5,2,0,0) ⎢ ⎢ −1 ⎥ ⎢ ⎥ ⎣− 2 / 3⎦
Konstanta
Basis
⎡− 1 / 3⎤ ⎢ 2/3 ⎥ ⎥ = 1/ 3 c4 = 0 − (5,2,0,0) ⎢ ⎢ 1 ⎥ ⎢ ⎥ ⎣ 1/ 3 ⎦ TI2231 Penelitian Operasional I
0
Konstanta
Basis
⎡− 1 / 3⎤ ⎢ 2/3 ⎥ ⎥=0 c4 = 0 − (4,2,0,0) ⎢ ⎢ 1 ⎥ ⎢ ⎥ ⎣ 1/ 3 ⎦
Variabel x1:
2
cB
⎡ 2/3 ⎤ ⎢ −1/ 3⎥ ⎥ = −2 c3 = 0 − (4,2,0,0) ⎢ ⎢ −1 ⎥ ⎢ ⎥ ⎣− 2 / 3⎦
TI2231 Penelitian Operasional I
4
2
x2
0
1
2/3
-1/3
0
0
4/3
5
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
0
0
-8/3
1/3
0
0
Z = 38/3
Baris c
31
TI2231 Penelitian Operasional I
32
Perubahan dalam Koefisien Fungsi Tujuan untuk Variabel Non Basis cj
5
2
0
0
0
0
cB
Konstanta
Basis
x1
x2
x3
x4
x5
x6
2
x2
0
1
0
0
0
1
2
5
x1
1
0
-1
0
0
-2
2
0
x5
0
0
1
0
1
-3
1
0
x4
0
0
-2
1
0
3
2
0
0
-2
0
0
-1
Z = 14
Baris c
TI2231 Penelitian Operasional I
Variabel x3: ⎡ 2/3 ⎤ ⎢ −1/ 3⎥ ⎥ Æ c =c −4 c3 = c3 − (3,2,0,0) ⎢ 3 3 ⎢ −1 ⎥ 3 ⎥ ⎢ ⎣− 2 / 3⎦
Kondisi tetap optimal : c3 = c3 −
4 4 4 − ∞ ≤ c3 ≤ ≤ 0 Æ c3 ≤ Æ 3 3 3
33
TI2231 Penelitian Operasional I
34
Penambahan Aktivitas Baru c7 = c7 − πP7 Memaksimumkan Z = 3x1 + 2x2 + 3/2 x7 dengan pembatas-pembatas: x1 + 2x2 + 3/4 x7 ≤ 6 (Bahan A) 2x1 + x2 + 3/4 x7 ≤ 8 (Bahan B) – x1 + x2 – x7 ≤ 1 (Selisih permintaan cat interior dan eksterior) x2 ≤ 2 (Permintaan cat interior) x1, x2, x7 ≥ 0
TI2231 Penelitian Operasional I
35
c7 = 3 / 2
⎡ 2 / 3 −1/ 3 ⎡3 / 4⎤ ⎢ −1/ 3 2 / 3 ⎢3 / 4⎥ ⎥ B −1 = ⎢ P7 = ⎢ ⎢ − 1⎥ ⎢ −1 1 ⎢ ⎥ ⎢ ⎣ 0⎦ ⎣− 2 / 3 1 / 3
⎡ 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 ⎡3 / 4⎤ ⎢3 / 4⎥ ⎥ = 1/ 4 c7 = c7 − πP7 = 3 / 2 − (1 / 3,4 / 3,0,0 )⎢ ⎢ −1 ⎥ ⎢ ⎥ ⎣ 0 ⎦
TI2231 Penelitian Operasional I
0 0 1 0
0 0⎤ 0 0⎥⎥ 1 0⎥ ⎥ 0 1⎦
0⎤ 0⎥⎥ = (1 / 3,4 / 3,0,0 ) 0⎥ ⎥ 1⎦
36
⎡ 2 / 3 −1/ 3 ⎢ −1/ 3 2 / 3 P7 = ⎢ ⎢ −1 1 ⎢ ⎣− 2 / 3 1 / 3
cj
0 0⎤ ⎡3 / 4⎤ ⎡ 1 / 4 ⎤ 0 0⎥⎥ ⎢⎢3 / 4⎥⎥ ⎢⎢ 1 / 4 ⎥⎥ = 1 0⎥ ⎢ − 1 ⎥ ⎢ − 1 ⎥ ⎥⎢ ⎥ ⎢ ⎥ 0 1 ⎦ ⎣ 0 ⎦ ⎣ − 1 / 4⎦
3
2
3/2
0
0
0
0
cB
Konstanta
Basis
TI2231 Penelitian Operasional I
37
x1
x2
x7
x3
x4
x5
x6
2
x2
0
1
1/4
2/3
-1/3
0
0
4/3
3
x1
1
0
1/4
-1/3
2/3
0
0
10/3
0
x5
0
0
-1
-1
1
1
0
3
0
x6
0
0
-1/4
-2/3
1/3
0
1
2/3
Baris c
0
0
1/4
-1/3
-4/3
0
0
Z = 38/3
TI2231 Penelitian Operasional I
38
Perubahan dalam Penggunaan Sumber dari Aktivitas cj
3
2
3/2
0
0
0
0
x1
x2
x7
x3
x4
x5
x6
cB
• Perubahan pada aktivitas (variabel) non basis Konstanta
Basis 3/2
x7
0
4
1
8/3
-4/3
0
0
16/3
3
x1
1
-1
0
-1
1
0
0
2
0
x5
0
4
0
5/3
-1/3
1
0
25/3
0
x6
0
1
0
0
0
0
1
2
Baris c
0
-1
0
-1
-1
0
0
Z = 14
TI2231 Penelitian Operasional I
– Dilakukan analisis seperti kasus penambahan aktivitas baru
• Perubahan pada aktivitas (variabel) basis – Menyelesaikan masalah pemrograman linier dari awal lagi
39
TI2231 Penelitian Operasional I
40
Perubahan yang Mempengaruhi Ketidaklayakan • Perubahan dalam konstanta ruas kanan • Penambahan pembatas baru
Perubahan dalam Konstanta Ruas Kanan Pembatas 1:
⎡b1 ⎤ ⎢8⎥ * b =⎢ ⎥ ⎢1⎥ ⎢ ⎥ ⎣2⎦
B −1b ≥ 0 ⎡ 2 / 3 −1/ 3 ⎢ −1/ 3 2 / 3 −1 B =⎢ ⎢ −1 1 ⎢ ⎣− 2 / 3 1 / 3 TI2231 Penelitian Operasional I
⎡ 2 / 3 −1/ 3 ⎢ −1/ 3 2 / 3 −1 * B b =⎢ ⎢ −1 1 ⎢ ⎣− 2 / 3 1 / 3
41
0⎤ ⎡b1 ⎤ ⎡ 2b1 / 3 − 8 / 3 ⎤ 0⎥⎥ ⎢⎢ 8 ⎥⎥ ⎢⎢ − b1 / 3 + 16 / 3 ⎥⎥ = ⎥ − b1 + 9 0⎥ ⎢ 1 ⎥ ⎢ ⎥ ⎥⎢ ⎥ ⎢ 1⎦ ⎣ 2 ⎦ ⎣− 2b1 / 3 + 14 / 3⎦
0 0 1 0
2b1 8 − ≥ 0 → b1 ≥ 4 3 3 b 16 − 1 + ≥ 0 → b1 ≤ 16 3 3
42
⎡7 ⎤ ⎢8 ⎥ * b =⎢ ⎥ ⎢1 ⎥ ⎢ ⎥ ⎣ 2⎦
⎡ 2 / 3 −1/ 3 ⎢ −1/ 3 2 / 3 B −1b* = ⎢ ⎢ −1 1 ⎢ ⎣− 2 / 3 1 / 3
− b1 + 9 ≥ 0 → b1 ≤ 9
0 0 ⎤ ⎡7 ⎤ ⎡ 2 ⎤ 0 0⎥⎥ ⎢⎢8 ⎥⎥ ⎢⎢3⎥⎥ = 1 0 ⎥ ⎢1 ⎥ ⎢ 2 ⎥ ⎥⎢ ⎥ ⎢ ⎥ 0 1 ⎦ ⎣ 2⎦ ⎣0 ⎦
Z = 3(3) + 2(2 ) + 2(0 ) + 0(0 ) = 13
− 2b1 14 + ≥ 0 → b1 ≤ 7 3 3 TI2231 Penelitian Operasional I
TI2231 Penelitian Operasional I
Pembatas 1:
4 ≤ b1 ≤ 7
0 0⎤ 0 0⎥⎥ 1 0⎥ ⎥ 0 1⎦
43
TI2231 Penelitian Operasional I
44
cj
3
2
0
0
0
Pembatas 1:
0
cB
Konstanta
Basis
x1
x2
x3
x4
x5
x6
2
x2
0
1
2/3
-1/3
0
0
2
3
x1
1
0
-1/3
2/3
0
0
3
0
x5
0
0
-1
1
1
0
2
0
x6
0
0
-2/3
1/3
0
1
0
0
0
-1/3
-4/3
0
0
Z = 13
Baris c
TI2231 Penelitian Operasional I
⎡9 ⎤ ⎢8 ⎥ * b =⎢ ⎥ ⎢1 ⎥ ⎢ ⎥ ⎣ 2⎦
⎡ 2 / 3 −1/ 3 ⎢ −1/ 3 2 / 3 B −1b* = ⎢ ⎢ −1 1 ⎢ ⎣− 2 / 3 1 / 3
45
0 0⎤ ⎡9 ⎤ ⎡ 10 / 3 ⎤ 0 0⎥⎥ ⎢⎢8 ⎥⎥ ⎢⎢ 7 / 3 ⎥⎥ = 1 0 ⎥ ⎢1 ⎥ ⎢ 0 ⎥ ⎥⎢ ⎥ ⎢ ⎥ 0 1⎦ ⎣2⎦ ⎣− 4 / 3⎦
TI2231 Penelitian Operasional I
46
Terapkan dual simplex cj
3
2
0
0
0
0
x1
x2
x3
x4
x5
x6
cB
cj Konstanta
Basis
3
2
0
0
0
0
x1
x2
x3
x4
x5
x6
cB
Konstanta
Basis
2
x2
0
1
2/3
-1/3
0
0
10/3
2
x2
0
1
0
0
0
1
2
3
x1
1
0
-1/3
2/3
0
0
7/3
3
x1
1
0
0
1/2
0
-1/2
3
0
x5
0
0
-1
1
1
0
0
0
x5
0
0
0
1/2
1
-3/2
2
0
x6
0
0
-2/3
1/3
0
1
-4/3
0
x3
0
0
1
-1/2
0
-3/2
2
0
0
-1/3
-4/3
0
0
0
0
0
-3
0
-1/2
Z = 13
Baris c
TI2231 Penelitian Operasional I
Baris c 47
TI2231 Penelitian Operasional I
48
Penambahan Pembatas Baru • Solusi optimal saat ini memenuhi pembatas baru
Pembatas baru:
ÆPembatas baru bersifat nonbinding atau redundant sehingga tidak mengubah solusi optimal saat ini.
x1 ≤ 4
Solusi optimal saat ini : x = (x1, x2, x5, x6) = (10/3, 4/3, 3, 2/3) x1 = 10/3 ≤ 4
• Solusi optimal saat ini tidak memenuhi pembatas baru Æ Pembatas baru bersifat binding
TI2231 Penelitian Operasional I
Pembatas baru:
49
x1 ≤ 3
TI2231 Penelitian Operasional I
Penambahan slack variable x7:
Solusi optimal saat ini : x = (x1, x2, x5, x6) = (10/3, 4/3, 3, 2/3)
50
x1 + x7 = 3
Solusi optimal saat ini : x = (x1, x2, x5, x6) = (10/3, 4/3, 3, 2/3)
x1 = 10/3 > 3
x1 = 10/3 > 3
TI2231 Penelitian Operasional I
51
TI2231 Penelitian Operasional I
52
Terapkan dual simplex 2
0
0
0
0
0
cj
3
Basis
x1
x2
x3
x4
x5
x6
x7
cB
Konstanta
cj
3
2
0
0
0
0
0
Basis
x1
x2
x3
x4
x5
x6
x7
cB
Konstanta
2
x2
0
1
2/3
-1/3
0
0
0
4/3
2
x2
0
1
2/3
-1/3
0
0
0
4/3
3
x1
1
0
-1/3
2/3
0
0
0
10/3
3
x1
1
0
-1/3
2/3
0
0
0
10/3
0
x5
0
0
-1
1
1
0
0
3
0
x5
0
0
-1
1
1
0
0
3
0
x6
0
0
-2/3
1/3
0
1
0
2/3
0
x6
0
0
-2/3
1/3
0
1
0
2/3
0
x7
1
0
0
0
0
0
1
3
0
x7
0
0
1/3
-2/3
0
0
1
-1/3
0
0
-1/3
4/3
0
0
0
0
0
-1/3
-4/3
0
0
0
Z = 38/3
Baris c
Baris c
TI2231 Penelitian Operasional I
0
0
0
0
0
cj
3
Basis
x1
x2
x3
x4
x5
x6
x7
cB
2
53
Konstanta
2
x2
0
1
1/2
0
0
0
-1/2
3/2
3
x1
1
0
0
0
0
0
1
3
0
x5
0
0
-1/2
0
1
0
3/2
5/2
0
x6
0
0
-1/2
0
0
1
½
½
0
x4
0
0
-1/2
1
0
0
-3/2
1/2
0
0
-1
-4/3
0
0
0
Z = 12
Baris c
TI2231 Penelitian Operasional I
55
TI2231 Penelitian Operasional I
54