Analisis Sensitivitas Terdiri dari 2 macam : 1. Analisis Sensitivitas, bila terjadi perubahan parameter secara diskrit. 2. Program Linear Parametrik, bila terjadi perubahan parameter secara kontinu. Macam-macam perubahan pasca optimum: 1. Perubahan suku tetap, bi 2. Perubahan koefisien ongkos, c j 3. Perubahan koefisien teknis, aij 4. Penambahan kendala baru 5. Penambahan perubahan baru. Akibat-akibat perubahan parameter: (i) PO tetap, variabel basis dan nilainya tetap (ii) Variabel basis tetap, namun nilainya berubah (iii) Variabel basis berubah A. Perubahan suku tetap, bi . Masalah PL: Memaksimumkan f ( x j ) n
Terhadap kendala
a j 1
ij
n
c x j 1
j
j
x j (, , )bi , i 1,2, , m .
PO masalah tersebut telah diperoleh, yaitu f max pada plb x ( x1 , x2 , , xm ) D 1 B . Perubahan bi : - Nilai variabel basis dan PO terpengaruh - Membuat soal tetap layak, maka PO soal asli menjadikan plb soal baru juga tetap PO. * * * Dkl. Plb baru: x * ( x1 , x2 , , xm ) harus memenuhi x * D 1 (b b ) 0 Plb soal asli: x ( x1 , x2 , , xm ) sehingga x * D 1b D 1b x D 1b 0 . m
xi xi d ij b j 0 , i 1,2, , m *
j 1
xi di1b1 di 2 b2 dim bm 0 x x1 d11b1 d12b2 d1m bm 0 * 1
x2 x2 d 21b1 d 22b2 d 2m bm 0 *
* xm xm d m1b1 d m 2 b2 d mm bm 0
x * x D 1b x * x D 1b x D 1b , x x * x Atau m
xi d ij b j , i 1,2, , m j 1
f c x c D 1b . Jika bi mengakibatkan xi xi xi 0 , untuk suatu i 1,2, , m , maka perubahan diselesaikan melalui tablo optimum soal asli sebagai berikut: *
(a) bi tablo optimum diganti dengan bi bi bi , i 1,2, , m . Syarat bi 0 berlaku. *
*
(b) Pada keadaan bi 0 , bi dipositifkan dan kendala ditambahkan variabel artifisial. (c) Selesaikan tabel baru tersebut dengan metode simpleks atau metode simpleks 2 tahap. *
*
Contoh 1. Memaksimumkan f ( x1 , x2 , x3 ) 50 x1 45x2 30 x3 Terhadap kendala 2 x1 3x2 x3 1200
x1 4 x2 3x3 800 x1 , x2 , x3 0 . Setelah PO diperoleh, tambahkan b1 300 dan b2 200 kepada suku tetap dan selidiki pengaruhnya terhadap PO soal asli tadi. Penyelesaian: Dengan menambahkan variabel slack y1 , y2 0 , kendala menjadi
2 x1 3x2 x3 y1 1200 x1 4 x2 3x3 y2 800 x1 , x2 , x3 0 , y1 , y2 0 . Fungsi tujuan menjadi Memaksimumkan f 50 x1 45x2 30 x3 0 y1 0 y2 . Sehingga masalah sudah dalam bentuk kanonik. Tabel Simpleksnya,
cj ci
xi xj
50 x1
45 x2
30 x3
0 y1
0 y2
bi
Ri
0
y1
2
3
1
1
0
1200
600
0
y2
1
4
3
0
1
800
800
zj
0
0
0
0
0
0
z j -c j
-50
-45
-30
0
0
0
45 x2
30 x3
0 y1
0 y2
bi
Ri
Tabel kedua
cj ci
xi xj
50 x1
50
x1
1
3/2
1/2
1/2
0
600
1200
0
y2
0
5/2
5/2
-1/2
1
200
80
zj
50
75
25
25
0
30000
z j -c j
0
30
-5
25
0
0
45 x2
30 x3
0 y1
0 y2
bi
Tabel Ketiga
cj ci
xi xj
50 x1
50
x1
1
3
0
3/5
1/5
560
30
x3
0
1
1
-1/5
2/5
80
zj
50
180
30
24
22
30400
z j -c j
0
Ri
135 0 24 22 30400 Tabel sudah optimal. Plb ( x1 , x2 , x3 ) (560,0,80) , yang memaksimumkan f 30400 . Untuk PO tersebut,
x1* x1 560 2 1 3 / 5 1 / 5 x * , c * (50,30) , D * dengan ( D * ) 1 . 1 / 5 2 / 5 1 3 x2 x3 80 *
Penyelesaian soal terubah: Sekarang ditambahkan b1 300 dan b2 200 , maka diperoleh 2
* * * x1 x1 d1 j b j x1 d11b1 d12b2 560 3 .300 1 .200 700 . 5 5 j 1 2
* * * x2 x2 d 2 j b j x2 d 21b1 d 22b2 80 1 .300 2 .200 100 . 5 5 j 1
*
*
Ternyata x1 dan x2 keduanya positif, maka perubah basis optimum soal asli masih menjadi perubah basis optimum soal baru. Nilai-nilai perubah basis baru akan menjadi x1 700 dan x2 100 , berarti PO soal baru *
*
menjadi ( x1 , x2 , x3 ) (700,0,100) , dengan *
*
*
f *max f max f f max c * ( D * ) 1 B 3 / 5 1 / 5 30400 (50,30) 1 / 5 2 / 5 140 30400 (50,30) 20 38000 .
300 200
Sekarang bila b1 1180 dan b2 120 . Selidiki pengaruhnya terhadap PO soal asli. Penyelesaian: Dalam soal baru ini b1 20 dan b2 680 , maka diperoleh
2
* * * x1 x1 d1 j b j x1 d11b1 d12b2 560 3 .(20) 1 .(680) 124 . 5 5 j 1
2
* * * x2 x2 d 2 j b j x2 d 21b1 d 22b2 80 1 .(20) 2 .(680) 268 . 5 5 j 1
Ternyata x2 0 , maka perubah basis optimum soal asli tidak menjadi basis optimum soal baru. Untuk *
menyelesaikan soal baru b1 dan b2 diganti dengan 124 dan -268, kemudian baris kedua dikalikan -1 dan dengan menyisipkan variabel artifisial q1 0 pada kendala kedua tadi disusun tablo simpleks baru. Tabel Simpleks Tahap I
cj ci
xi xj
0 x1
0 x2
0 x3
0 y1
0 y2
1 q1
bi
Ri
0
x1
1
3
0
3/5
1/5
0
124
124/3
1
q1
0
-1
-1
1/5
-2/5
1
268
zj
0
-1
-1
1/5
-2/5
1
268
z j -c j
0
-1
-1
1/5
-2/5
0
268
0 x2
0 x3
0 y1
0 y2
1 q1
bi
Ri 124/3
Tabel Kedua
cj ci
xi xj
0 x1
0
x2
1/3
1
0
5
1/15
0
124/3
1
q1
1/3
0
-1
26/5
-1/3
1
1072/3
zj
1/3
0
-1
26/5
-1/3
1
1072/3
z j -c j
1/3
0
-1
26/5
-1/3
0
1072/3
Tabel tidak dapat diteruskan. Soal menjadi tidak layak. B. Perubahan Pada Koefisien Teknis aij Akan diselidiki pengaruh perubahan aij menjadi aij aij terhadap PO soal asli. 1. Jika perubahan dilakukan pada semua aij pada kolom bukan basis dalam PO soal asli. Pengaruh perubahan ini dapat dilihat pada nilai z j c j . Misalkan aik aik , i 1,2, , m , dengan xk bukan *
*
variabel basis pada PO. Dihitung z k ck yang baru: *
(i)
*
Jika z k ck 0 , maka PO lama menjadi PO baru dengan zk ck c * ( D * ) 1 Ak ck . *
*
*
*
*
Jika z k ck 0 , maka terhadap tabel optimum dilakukan operasi sebagai berikut. Dengan *
(ii)
*
mengganti Ak dengan Ak
*
1) Gantikan y k dengan yk ( D * ) 1 Ak *
*
2) Gantikan z k ck dengan zk ck c * ( D * ) 1 Ak ck Proses dilanjutkan sampai diperoleh PO yang baru. 2. Jika perubahan terjadi pada xk variabel basis pada PO. *
*
*
Pada kasus kedua ini, jika perubahan terjadi pada aij0 menjadi aij0 aij0 , maka 1) Tambahkan variabel baru xn1 pada masalah optimum dengan koefisien teknis ai ( n1) aij0 aij0 dan koefisien ongkos cn1 c j0 (milik x j0 dengan x j0 x j ). 2) Koefisien yi ( n1) ditransformasikan ke y *i ( n1) dengan rumus yi ( n1) D 1 An1 , i 1,2, , m . 3) Agar x j0 tidak lagi berada pada basis optimum, maka gantikan koefisien ongkos c j0 (milik x j0 ) dengan bilangan positif besar M (tetapi koefisien xn1 tetap c j0 ). m m * * z j c j ( z j c j ) c j ck yij ki k 1 i 1 j m 1, , n, n 1 dengan ck 0 , k 1,2, , j0 1, j0 1, , n dan c j0 M c j0 .
4) Hitung
koefisien
kontrol
terubah
,
5) Lanjutkan algoritma simpleks untuk memperoleh po yang baru.
3 4
Contoh 2. Dari Contoh 1 diadakan perubahan terhadap soal aslinya dengan mengganti A2 menjadi
5 * A2 . Tentukan pengaruhnya terhadap po soal asli. 1 Penyelesaian: Ternyata x2 bukan basis dalam po soal asli, maka perubahan pada A2 merupakan kejadian pertama, sehingga diperoleh
z2 c2 C D 1 A2 c2 3 / 5 1 / 5 5 50 30 45 1 / 5 2 / 5 1 14 5 50 30 45 3 5 140 18 45 77 . * * Karena z2 c2 77 0 , maka po lama menjadi po soal baru. *
*
*
3 4
1 7
Contoh 3. Dari Contoh 1 A2 diubah menjadi A2 . Tentukan pengaruhnya terhadap po soal asli. *
Penyelesaian: Dihitung koefisien kontrol baru, sehingga diperoleh
z2 c2 C D 1 A2 c2 3 / 5 1 / 5 1 50 30 45 1 / 5 2 / 5 7 4 5 50 30 45 13 5 40 78 45 7 . * * Karena z2 c2 7 0 , maka x2 dapat masuk menjadi basis. *
*
*
3 / 5 1 / 5 1 4 5 * D 1 A2 . 1 / 5 2 / 5 7 13 5 * Dengan mengganti Y2 dengan D 1 A2 dan z 2 c2 dengan z * c* tabel optimum soal asli berubah menjadi tabel berikut:
cj ci
xi xj
50 x1
45 x2
30 x3
0 y1
0 y2
bi
50
x1
1
-4/5
0
3/5
1/5
560
30
x3
0
13/5
1
-1/5
2/5
80
zj
50
38
30
24
22
z j -c j
0
-7
0
24
22
cj
45 x2
30 x3
0 y1
0 y2
bi
Ri
400/13
30400
ci
xi xj
50 x1
50
x1
1
0
4/13
7/13
21/65
7600/13
45
x2
0
1
5/13
-1/13
2/13
400/13
zj
50
45
425/13 305/13 300/13
z j -c j
0
0
35/13 305/13 300/13
Ri
59000/13
Tabel sudah optimum. C. Perubahan Pada Koefisien Ongkos, c j Misalkan c j diubah menjadi c j c j c j , atau C diubah menjadi C* C C dan C * C C adalah *
vektor ongkos baru untuk variabel basis tabel optimum soal asli. Dalam tabel optimum soal asli, koefisien kontrol z j c j C Y j c j . Sesudah diubah akan menjadi
z j c j C * Yj c j *
*
*
(C C )Y j c j c j C Y j C Y j c j c j
z j c j z j c j C Y j c j *
*
(1)
PO soal asli akan tetap menjadi PO soal terubah bila dipenuhi z j c j 0 atau z j c j C Y j c j 0 *
untuk x j bukan basis.
*
(2)
Khususnya, bila perubahan hanya terjadi pada c j dengan x j bukan basis dalam tabel optimum, maka C 0 dan z j c j c j 0 untuk x j bukan basis. Jika (2) dipenuhi maka variabel basis yang menyusun po tidak berubah demikian pula nilainya. Yang berubah adalah nilai program, yang semula f C X menjadi f * C * X (C C ) X , jadi ada tambahan
f C X . Bila (2) tidak dipenuhi oleh beberapa variabel bukan basis, maka proses simpleks dilanjutkan dengan mengangkat tabel optimum soal asli yang sudah terubah sebagai tabel awal dan variabel-variabel yang tidak memenuhi (2) sebagai calon basis baru sampai po baru tercapai. Contoh 4. Dari Contoh 1 bila c2 45 diubah menjadi c2 65 . Bagaimana pengaruh perubahan tersebut terhadap po soal asli. Penyelesaian: x2 pada tabel optimum bukan variabel basis. z2 c2 c2 135 20 115 0 . Berarti po soal asli masih *
* menjadi po soal terubah. Karena c1 dan c3 tidak berubah, maka C 0 berarti f max f max . Jadi nilai po juga tidak berubah.
Contoh 5. Dari Contoh 1 bila c2 45 diubah menjadi c2 25 . Bagaimana pengaruh perubahan tersebut terhadap po soal asli. Penyelesaian: x2 pada tabel optimum bukan variabel basis. z2 c2 c2 135 (70) 205 0 . Berarti po soal asli masih *
* f max . Jadi nilai po juga menjadi po soal terubah. Karena c1 dan c3 tidak berubah, maka C 0 berarti f max tidak berubah.
Contoh 6. Dari Contoh 1 bila c1 50 diubah menjadi c1 70 dan c2 45 diubah menjadi c2 75 . Bagaimana pengaruh perubahan tersebut terhadap po soal asli. Penyelesaian: c1 20 ( x1 pada tabel optimum variabel basis) *
*
c2 30 ( x2 pada tabel optimum bukan variabel basis) c3 0 ( x1 pada tabel optimum variabel basis)
Pada tabel optimum terjadi perubahan C c1 Dihitung z j c j *
*
c3 20 0 .
untuk x j bukan basis. Dalam hal ini adalah x2 .
3 * * z2 c2 z2 c2 C Y2 c2 135 20 0 30 135 60 30 165 0 . 1 * * * * Dengan cara sama diperoleh z 4 c4 36 0 untuk variabel y1 dan z5 c5 26 0 untuk variabel y 2 . Berarti po soal asli masih menjadi po soal terubah. Karena c1 berubah dan c3 tidak berubah, maka 560 * 11200 . Dan nilai f max f max f 30400 11200 41600 . f C X 20 0 80 Contoh 7. Dari Contoh 1 c3 30 diubah menjadi c3 115 . Bagaimana pengaruh perubahan tersebut terhadap po soal asli. Penyelesaian: c3 145 jadi C c1 c3 0 145 . *
Dihitung z j c j *
*
untuk x j bukan basis. Dalam hal ini adalah x2 .
3 * * z2 c2 z2 c2 C Y2 c2 135 0 145 0 135 145 0 10 0 . 1 * * * * Dengan cara sama diperoleh z 4 c4 53 0 untuk variabel y1 dan z5 c5 36 0 untuk variabel y 2 . 560 * 11600 . Dan nilai f max f max f 30400 11600 42000 . f C X 0 145 80 Karena z 2 c2 10 0 dan z5 c5 36 0 , maka tabel optimum soal asli belum optimum bagi soal *
*
*
*
terubah, sehingga perhitungan simpleks dilanjutkan, dengan memasukkan y 2 sebagai calon variabel basis baru.
cj ci
xi xj
50 x1
45 x2
-115 x3
0 y1
0 y2
bi
50
x1
1
3
0
3/5
1/5
560
-115
x3
0
1
1
-1/5
2/5
80
zj
50
35
-115
29
-220
z j -c j
0
-10
0
29
-220
Ri
400/13
5554
Berarti po soal asli masih menjadi po soal terubah. Karena c1 berubah dan c3 tidak berubah, maka
560 * 11200 . Dan nilai f max f max f 30400 11200 41600 . f C X 20 0 80
