Wednesday, September 28, 2011

CARA PEMBUATAN KONSTRAIN “PEMOTONG” Analisis Sensitivitas


CARA PEMBUATAN KONSTRAIN “PEMOTONG” :

Dari tabel optimal simplex yang tidak menghasilkan nilai intejer, misalnya , maka persamaan  ini adalah (dan asumsikan variabel basis memiliki indeks 1 s/d m),  :  
        ……………………………..…………………….. (1)

Bila : Irj  intejer terbesar yang £ yrj (Irjยบ bagian intejer dari yrj), dan
          Ir  merupakan bagian intejer dari ;
          maka Frj dan Fr sebagai bagian non-intejernya (pecahannya) dapat
          dituliskan :

          Frj  = yrj - Irj   dan  Fr  = - Ir        

          dimana 0 £ Frj< 1 dan 0 < Fr <  1  sehingga Persamaan (1) dapat
          dituliskan :
            ……..……...…………………. (2)

         dan dengan mengubah susunannya, diperoleh :
           …..………...………………. (3)

Ruas kiri akan intejer untuk setiap solusi fisibel yang intejer, dan nilai ruas kanan lebih kecil dari 1, karena :

        Fr <  1, Frj  ³ 0, dan xj  ³ 0,

Bila ruas kiri bernilai intejer, maka ruas kanan juga harus intejer (karena nilainya sama dengan ruas kiri yang intejer); jadi ruas kanan harus £ 0, sehingga dapat dituliskan :

                               ……………………………………… (4)
Namun, karena xj untuk j = m+1, …, n saat ini adalah variabel non-basis (dan nilainya = 0) dan juga Fr> 0, maka solusi optimal (non-intejer) yang ada tidak memenuhi persamaan (4) ini. 
 
Jadi, konstrain tambahan dengan persamaan (4) akan memotong solusi optimal (non-intejer) yang ada bila ditambahkan pada tabel optimal PL.
 
Dengan Dual Simplex, dicari solusi optimal persoalan PL yang baru tersebut dan periksa apakah telah diperoleh solusi optimal yang intejer. 
Bila tidak, ulangi dengan pembuatan konstrain “pemotong” baru.


    Contoh:

Minimasi       3 x1   + 4 x2
 s/t           3 x1  +    x2   ³ 4
x1   + 2 x2  ³ 4
x1, x2  ³ 0 dan intejer.

Tanpa memperhatikan persyaratan intejernya, solusi PL (kontinyu) adalah :


z
x1
x2
s1
s2
RHS
z
1
0
0
-2/5
-9/5
44/5
x1
0
1
0
-2/5
1/5
4/5
x2
0
0
1
1/5
-3/5
8/5

Karena solusi optimum PL kontinyu ini belum intejer, maka dapat dipilih sembarang variabel non-intejer untuk membuat konstrain “pemotong”, dan dalam kasus ini yang dipilih adalah x2.

x2+ (1/5) s1 - (3/5) s2 = 8/5

Dari persamaan ini diperoleh :

I23= 0,  F23 = (1/5)
I24= -1,  F24 = (2/5)
I2= 1,  F2 = (3/5)

sehingga konstrain pemotongnya adalah :

(1/5) s1 + (2/5) s2 ³  3/5                      ……………………………………… (5)

dan dengan menambahkan Persamaan (5) ini beserta s3 sebagai variabel slack-nya, diperoleh :


z
x1
x2
s1
s2
s3
RHS
z
1
0
0
-2/5
-9/5
0
44/5
x1
0
1
0
-2/5
1/5
0
4/5
x2
0
0
1
1/5
-3/5
0
8/5
s3
0
0
0
-1/5
-2/5
1
-3/5
Rasio



-(2/5)/(-1/5)
-(9/5)/(-2/5)



dan dengan Dual Simplex, diperoleh solusi PL (kontinyu) seperti berikut :


z
x1
x2
s1
s2
s3
RHS
z
1
0
0
0
- 1
-2
10
x1
0
1
0
0
1
-2
2
x2
0
0
1
0
-1
1
1
s1
0
0
0
1
2
-5
3

 Note:
Butuh file asli. kontak pemilik blog dengan mengirimkan email lewat contact us. file akan dikirim ke email anda.


Analisis Sensitivitas Statistika Teknik Industri


ANALISIS  SENSITIVITAS


¨       Nilai-nilai parameter jarang diketahui secara pasti
¨       Bila terjadi perubahan nilai-nilai parameter, ingin diketahui pengaruhnya terhadap solusi optimal yg. ada;  tanpa mengulangi (perhitungannya)  dari awal.

¨       Dari persoalan PL berikut :

Minimasi :    cx
      s/t            Ax = b 
    x ³ 0

telah diperoleh solusi optimalnya melalui metoda simplex dengan basis optimal B.

Akan dibahas bagaimana kondisi optimalitas (hubungan primal-dual) digunakan utk. memperoleh solusi optimal baru, bila terjadi perubahan beberapa data, tanpa menyelesaikannya dari awal.

Perubahan data ini berupa :

a)      Koefisien ongkos c

b)      Vektor ruas kanan  b

c)      Matriks konstrain  A

d)     Penambahan aktivitas baru

e)      Penambahan konstrain baru



A) Perubahan koefisien ongkos c : berubah dari ck®ck

Pengaruh perubahan satu atau beberapa koefisien ongkos ini pada tabel akhir (optimal) terjadi pada baris ke-0 : yakni fisibilitas dual dapat terganggu.

1) Kasus I : xk ยบ variabel non-basis
cB tetap, ® zj= cB B-1 ajtidak berubah j.
Jadi, zk – ckdigantikan oleh zk – ck’ (catatan : zk – ck£ 0 karena solusi yg. ada sekarang = sol. optimum).

Jika zk – ck’ = (zk – ck) + (ck – ck’) positif, maka xk harus masuk basis dan selanjutnya digunakan metoda simplex (primal) seperti biasa.
Namun bila tidak, solusi yg. ada tetap merupakan solusi optimum untuk persoalan PL baru.

Contoh :
Dari persoalan PL berikut :

Minimasi    - 2 x1+    x2  -   x3
      s/t                         x1 +    x2  +   x3  £ 6
             - x1+ 2 x2             £ 4
      x1, x 2 , x3  ³ 0

dengan tabel optimal


z
x1
x2
x3
s1
s2
RHS
z
1
0
-3
-1
-2
0
-12
x1
0
1
1
1
1
0
6
s2
0
0
3
1
1
1
10

Andaikata cx2 = 1 diubah menjadi –3; maka karena x2 merupakan variabel non-basis,  z2 – c2’ = (z2 – c2) + (c2 – c2‘) =  -3 + 4 = 1,  dan  semua zj – cj’ lainnya tetap sehingga x2 masuk basis.


z
x1
x2
x3
s1
s2
RHS
z
1
0
1
-1
-2
0
-12
x1
0
1
1
1
1
0
6
s2
0
0
3
1
1
1
10

Tabel selanjutnya tidak diberikan disini.

2) Kasus II : xk ยบ variabel basis, misalnya xk = xBt
cBt  diganti dengan cBt  ® zj = zj‘ dan  (zj’– cj) dihitung sebagai berikut :

zj’– cj = cB‘ B-1aj – cj
=    (cB1, cB2,…,          cBt, cBt+1,…, cBm).B-1 aj– cj
   + (   0,    0,…, cBt‘– cBt,      0,…, 0   ).B-1 aj
=    (cB B-1 aj – cj)
   + (   0,    0,…, cBt‘– cBt,      0,…, 0   ).B-1aj
=    (cB B-1 aj – cj)
   + (   0,    0,…, cBt‘– cBt,      0,…, 0   ).yj
=    (zj – cj) 
   + (cBt‘– cBt ) ytj  utk. semua j.

Untuk  j = k,  (zk – ck) = 0 dan yik = 1 dan oleh karena itu  
                       (zk’– ck) = 0 + (ck’– ck) ®  (zk’– ck’) = 0.

Jadi, baris ke-0 dapat di-update dengan menambahkan perubahan ongkos dari xk = xbt dikalikan dengan baris ke-t dari tabel (akhir), sehingga (zk’– ck) berubah menjadi (zk’– ck’) = 0.  Nilai f.obyektif  yang baru juga diperoleh dengan operasi baris elementer menjadi :
   cB‘ B-1 b = cB B-1 b + (cBt‘– cBt) ฦ‚t.

Contoh :

Seandainya dari persoalan PL dan tabel  optimal sebelumnya cx1= –2  diubah menjadi 0.
 
Karena x1  merupakan variabel basis, maka baris ke-0, kecuali        z1–c1, diubah dengan mengalikan baris  x1  dengan nilai perubahan   cx1, yakni  = 0 – (–2)   = 2, dan ditambahkan pada baris ke-0 lama. Nilai  z1 – c1 yang baru tetap = 0. Perhatikan bahwa z3 – c3  baru menjadi positif sehingga x3 masuk basis.

Tabel Optimal (Persoalan Asli) :

z
x1
x2
x3
s1
s2
RHS
z
1
0
-3
-1
-2
0
-12
x1
0
1
1
1
1
0
6
s2
0
0
3
1
1
1
10


z
x1
x2
x3
s1
s2
RHS
z
1
0
-1
1
0
0
0
x1
0
1
1
1
1
0
6
s2
0
0
3
1
1
1
10

dan tabel selanjutnya tidak dibahas.


B.   Perubahan Vektor Ruas Kanan  (RHS) b :


Vektor ruas kanan b diganti dengan b’ ® B-1 b berubah menjadi B-1 b’.

Karena  (zj – cj) £ 0  untuk semua variabel non-basis (Kasus Minimasi), maka satu-satunya kemungkinan bahwa solusi yang ada menjadi tidak optimal  adalah vektor baru B-1 b’ memiliki salah satu unsur yang negatif.

Bila B-1 b’ ³ 0, maka basis yang ada tetap optimum dengan nilai = B-1 b’ dan nilai f. obyektifnya  = cBB-1 b’.
Bila tidak, maka gunakan Dual Simplex untuk mencari solusi optimal dengan mengupayakan fisibilitasnya.

Contoh :

Dari Persoalan PL berikut :
Minimasi    - 2 x1+    x2  -   x3
      s/t                         x1 +    x2  +   x3  £ 6
             - x1+ 2 x2             £ 4
      x1, x 2 , x3  ³ 0

dengan tabel optimal :

z
x1
x2
x3
s1
s2
RHS
z
1
0
-3
-1
-2
0
-12
x1
0
1
1
1
1
0
6
s2
0
0
3
1
1
1
10

Bila RHS  diganti maka dengan  B-1 =  diperoleh  B-1 b’ = = . Jadi B-1 b’ ³ 0  dan dengan demikian solusi optimal baru adalah :   x1*= 3, s2* = 7, x2* = x3*= s1* = 0.



C) Perubahan Matriks Konstrain A :

1)    Kasus I : Perubahan vector kolom variabel non-basis : aj ® aj

Kolom yang berubah adalah B-1 aj’ dan (zj‘– cj) = cB B-1aj’ - cj. Bila (zj‘– cj) £ 0, maka solusi yang ada tetap optimal; namun bila tidak, maka gunakan Metoda Simplex untuk menyelesaikannya setelah kolom j di-update dengan memasukkan variabel non-basis xj.

Contoh :
Dari persoalan PL berikut :
Minimasi    - 2 x1+    x2  -   x3
      s/t                         x1+    x2  +   x3  £ 6
             - x1+ 2 x2             £ 4
      x1, x 2 , x3  ³ 0

dengan tabel optimal :

z
x1
x2
x3
s1
s2
RHS
z
1
0
-3
-1
-2
0
-12
x1
0
1
1
1
1
0
6
s2
0
0
3
1
1
1
10

Bila a2 =  pada contoh dimuka diganti dengan , maka y2’ = B-1 a2’ = =

cBB-1 a2– c2 =  (-2,0) - 1  = -5.

Jadi, tabel optimal yang ada tetap merupakan tabel optimum dengan kolom x2 diganti dengan (-5,2,7)t




2)    Kasus II : Perubahan vektor kolom variabel basis : aj ® aj

Boleh jadi akibat perubahan ini, vektor-vektor basis yang ada tidak lagi membentuk basis. Andaipun tetap basis, perubahan satu vektor kolom basis akan mengubah B-1 dan oleh karenanya juga setiap angka yang ada pada tiap kolom.

·        Langkah 1 : Asumsikan suatu aktivitas baru xj’ ditambahkan pada persoalan dengan kolom aj’ (dan koefisien f.obyektifnya = cj).
·        Langkah 2 :  Hilangkan variabel lama xj.
 
Langkah 1 dilakukan dengan menentukan yj’ = B-1 aj’ dan (zj‘– cj) = cB B-1aj’ - cj dimana Bmerupakan basis yang ada saat ini, sehingga meng-update kolom xj’.

 

Bila elemen yjj pada baris basis xj dan kolom xj¹ 0, maka xj’ dapat menggantikan xj  sebagai basis dan kolom xjdaat dihilangkan. Pivoting dapat menyebabkan fisibilitas Primal maupun Dual dilanggar, namun dengan menggunakan variabel artifisial, hal ini dapat diatasi.


Namun bila yjj= 0, maka set vektor basis yang ada dengan kolom baru xj tidak lagi membentuk basis. Salah satu cara menghilangkan xj dapat dilakukan dengan memperlakukannya sebagai variabel artifisial yang berada dalam basis dan gunakan Metoda Big-M.

Contoh : Bila yjj = 0
Bila a1 = pada contoh dimuka diganti dengan , maka
y1’ = B-1 a1’ = =
cB B-1 a1– c1 =  (-2,0) - (-2)  = 2.
Disini nilai entri pada baris x1 dari kolom y1’ = 0 dan oleh karenanya kolom-kolom basis tidak lagi berdimensi m. Dengan menambahkan kolom (2, 0, -1) t  dari  xj’ dan memperlakukan xjsebagai variabel artificial dalam basis dengan koefisien ongkos Big-M, diperoleh tabel berikut.


z
x1
x1
x2
x3
s1
s2
RHS
z
1
-M
2
-3
-1
-2
0
-12
x1
0
1
0
1
1
1
0
6
S2
0
0
-1
3
1
1
1
10

Dan gunakan Metoda Big-M setelah menjadikan (zx1– cx1) =  0.

Contoh : Bila yjj ¹ 0,
Bila a1 = pada contoh dimuka diganti dengan , maka
y1’ = B-1 a1’ = =

cB B-1 a1– c1 =  (-2,0) - (-2)  = - 4.

Pada kasus ini, nilai entri baris x1 dan kolom y1¹ 0, sehingga tambahkan sehingga tambahkan kolom (-4, 3, 9)t  sebagai kolom x1’, lakukan pivoting kolom x1’ baris x1 & hilangkan x1.


z
x1
x2
x3
s1
s2
RHS
z
1
-4
-3
-1
-2
0
-12
x1
0
3
1
1
1
0
6
s2
0
9
3
1
1
1
10
Tabel berikutnya tidak diberikan disini.


D) Penambahan Aktivitas (Variabel) Baru :

Andaikata suatu aktivitas atau variabel baru xn+1  ditambahkan pada persoalan asli, dengan koefisien ongkos cn+1 dan kolomnya an+1, maka dapat ditentukan apakah hal ini menguntungkan atau tidak.  

Pertama : Hitung zn+1 – cn+1, bila zn+1 – cn+1 £ 0 (untuk kasus minimasi), maka x*n+1 = 0 dan solusi yang ada saat ini tetap merupakan solusi optimum.  
Sebaliknya, bila zn+1 – cn+1 > 0, maka xn+1  akan masuk basis dan gunakan Metoda Simplex untuk mencari solusi optimalnya.

Contoh :
Diinginkan solusi optimal yang baru bila pada contoh dimuka ditambahkan variabel baru x4dengan c4 = 1, dan a4= (-1,2) t.
Pertama : Hitung zx4 – cx4  =  w ax4 – cx4  = (-2, 0)  -1 =  1
yx4 = B-1ax4 = =

Karena zx4 – cx4 = 1 > 0, maka x4 masuk basis dan pivoting dilakukan pada baris s2dan kolom x4.
                                                                  ¯

z
x1
x2
x3
s1
s2
x4
RHS

z
1
0
-3
-1
-2
0
1
-12

x1
0
1
1
1
1
0
-1
6

s2
0
0
3
1
1
1
1
10
®

          Tabel berikutnya tidak diberikan disini.


E) Penambahan Konstrain Baru :

1)     “Membuang”  solusi optimal yang ada, atau
2)    Tidak mempengaruhi solusi optimal yang ada

Bila B ยบ basis optimal sebelum ditambahkannya konstrain baru :
am+1 x £  bm+1.

dan dari pembahasan Metoda Simplex diketahui :

z –  0 xB+ (cB B-1 N cN )xN  = cB B-1 b  …………………………..  (1)
     xB +               B-1 N xN  = B-1 b     …………………………..  (2)

Konstrain baru am+1 x £ bm+1   dituliskan sebagai :

aBm+1 xB + aNm+1 xN  + xn+1 = bm+1;

dimana am+1 dipecah penulisannya menjadi  (aBm+1, aNm+1), dan xn+1  ยบ variabel slack non-negatif .

Kalikan Persamaan (2) dengan aBm+1 :

aBm+1xB + aBm+1 B-1 N xN  = aBm+1 B-1 b   …………………………..  (3)
 
dan kurangkan pada konstrain baru, akan diperoleh :

aBm+1xB +          aNm+1xN  + xn+1 = bm+1
aBm+1xB + aBm+1B-1 N xN            = aBm+1 B-1b   ..…………………..  (3)
¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾  -
(aNm+1  - aBm+1 B-1 N) xN  + xn+1 = bm+1 - aBm+1 B-1 b   ..……..……..  (4)
 
sehingga penambahan konstrain baru menjadikan persoalan PL-nya adalah   Persamaan-Persamaan  (1),  (2), dan (4).
 
Persamaan (2) dan (4) merupakan solusi basis (belum tentu fisibel); dan bila bm+1 - aBm+1 B-1 b ³ 0 maka solusi ini adalah optimal; akan tetapi bila bm+1 - aBm+1 B-1 b < 0, diperlukan Dual Simplex untuk penyelesaiannya.

Contoh :
Bila pada contoh dimuka ditambahkan konstrain baru - x1+2x3 ³ 2, maka titik optimal (x1, x2, x3) = (6, 0 , 0) tidak memenuhi konstrain baru ini.

Konstrain baru dituliskan sebagai :  x1 - 2 x3 + s3 = - 2, dimana s3 adalah variabel slack yang non-negatif  dan ditambahkan pada tabel optimal yang ada menjadi :


z
x1
x2
x3
s1
s2
s3
RHS
z
1
0
-3
-1
-2
0
0
-12
x1
0
1
1
1
1
0
0
6
s2
0
0
3
1
1
1
0
10
s3
0
1
0
-2
0
0
1
-2

Kalikan Baris ke-1 dengan (-1) dan tambahkan pada Baris ke-3 untuk menjadikan Kolom x1 sebagai unit vektor.


z
x1
x2
x3
s1
s2
s3
RHS
z
1
0
-3
-1
-2
0
0
-12
x1
0
1
1
1
1
0
0
6
s2
0
0
3
1
1
1
0
10
s3
0
0
-1
-3
-1
0
1
-8

     Dengan menggunakan Dual Simplex, solusi optimumnya adalah sebagai
     berikut :  


z
x1
x2
x3
s1
s2
s3
RHS
z
1
0
-3
-1
-2
0
0
-12
x1
0
1
1
1
1
0
0
6
s2
0
0
3
1
1
1
0
10
s3
0
0
-1
-3
-1
0
1
-8
Rasio


-3/-1
-1/-3
-2/-1




      

z
x1
x2
x3
s1
s2
s3
RHS
z
1
0
-8/3
0
-5/3
0
-1/3
-28/3
x1
0
1
2/3
0
2/3
0
1/3
10/3
s2
0
0
8/3
0
2/3
1
1/3
22/3
x3
0
0
1/3
1
1/3
0
-1/3
8/3












APLIKASI PENAMBAHAN KONSTRAIN PADA PEMROGRAMAN INTEJER :

Bila solusi optimal dari PL kontinyu menghasilkan solusi optimal yang intejer, maka solusi optimum (intejer) yang diinginkan telah diperoleh.

Bila tidak, dapat digunakan cara penambahan konstrain yang memotong daerah fisibel dan solusi optimal (non-intejer) yang ada, tanpa menghilangkan solusi intejer yang terkandung dalam daerah fisibelnya.

Penambahan konstrain seperti ini terus diulang, sampai diperoleh solusi intejer optimum, atau diketahui tidak ada solusi (intejer) yang fisibel.'

Note:
Butuh file asli. kontak pemilik blog dengan mengirimkan email lewat contact us. file akan dikirim ke email anda.