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 : I_rj  intejer terbesar yang £ y_rj (I_rjº bagian intejer dari y_rj), dan

          I_r  merupakan bagian intejer dari ;

          maka F_rj dan F_r sebagai bagian non-intejernya (pecahannya) dapat

          dituliskan :

          F_rj  = y_rj - I_rj   dan  F_r  = - I_r        

          dimana 0 £ F_rj< 1 dan 0 < F_r <  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 :

        F_r <  1, F_rj  ³ 0, dan x_j  ³ 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 x_j untuk j = m+1, …, n saat ini adalah variabel non-basis (dan nilainya = 0) dan juga F_r> 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 x₁   + 4 x₂

 s/t           3 x₁  +    x₂   ³ 4

x₁   + 2 x₂  ³ 4

x₁, x₂  ³ 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 x₂.

x₂+ (1/5) s₁ - (3/5) s₂ = 8/5

Dari persamaan ini diperoleh :

I₂₃= 0,  F₂₃ = (1/5)

I₂₄= -1,  F₂₄ = (2/5)

I₂= 1,  F₂ = (3/5)

sehingga konstrain pemotongnya adalah :

(1/5) s₁ + (2/5) s₂ ³  3/5                      ……………………………………… (5)

dan dengan menambahkan Persamaan (5) ini beserta s₃ 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 c_k®c_k^’

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 : x_k º variabel non-basis

c_B tetap, ® z_j= c_B B^-1 a_jtidak berubah ∀ j.

Jadi, z_k – c_kdigantikan oleh z_k – c_k’ (catatan : z_k – c_k£ 0 karena solusi yg. ada sekarang = sol. optimum).

Jika z_k – c_k’ = (z_k – c_k) + (c_k – c_k’) positif, maka x_k 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 x₁+    x₂  -   x₃

      s/t                         x₁ +    x₂  +   x₃  £ 6

             - x₁+ 2 x₂             £ 4

      x₁, x ₂ , x₃  ³ 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 c_x2 = 1 diubah menjadi –3; maka karena x₂ merupakan variabel non-basis,  z₂ – c₂’ = (z₂ – c₂) + (c₂ – c₂‘) =  -3 + 4 = 1,  dan  semua z_j – c_j’ lainnya tetap sehingga x₂ 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 : x_k º variabel basis, misalnya x_k = x_Bt

c_Bt  diganti dengan c_Bt‘  ® z_j = z_j‘ dan  (z_j’– c_j) dihitung sebagai berikut :

z_j’– c_j = c_B‘ B^-1a_j – c_j

=    (c_B1, c_B2,…,          c_Bt, c_Bt+1,…, c_Bm).B^-1 a_j– c_j

   + (   0,    0,…, c_Bt‘– c_Bt,      0,…, 0   ).B^-1 a_j

=    (c_B B^-1 a_j – c_j)

   + (   0,    0,…, c_Bt‘– c_Bt,      0,…, 0   ).B^-1a_j

=    (c_B B^-1 a_j – c_j)

   + (   0,    0,…, c_Bt‘– c_Bt,      0,…, 0   ).y_j

=    (z_j – c_j) 

   + (c_Bt‘– c_Bt ) y_tj  utk. semua j.

Untuk  j = k,  (z_k – c_k) = 0 dan y_ik = 1 dan oleh karena itu  

                       (z_k’– c_k) = 0 + (c_k’– c_k) ®  (z_k’– c_k’) = 0.

Jadi, baris ke-0 dapat di-update dengan menambahkan perubahan ongkos dari x_k = x_bt dikalikan dengan baris ke-t dari tabel (akhir), sehingga (z_k’– c_k) berubah menjadi (z_k’– c_k’) = 0.  Nilai f.obyektif  yang baru juga diperoleh dengan operasi baris elementer menjadi :

   c_B‘ B^-1 b = c_B B^-1 b + (c_Bt‘– c_Bt) Ƃ_t.

Contoh :

Seandainya dari persoalan PL dan tabel  optimal sebelumnya c_x1= –2  diubah menjadi 0.

 

Karena x₁  merupakan variabel basis, maka baris ke-0, kecuali        z₁–c₁, diubah dengan mengalikan baris  x₁  dengan nilai perubahan   c_x1, yakni  = 0 – (–2)   = 2, dan ditambahkan pada baris ke-0 lama. Nilai  z₁ – c₁ yang baru tetap = 0. Perhatikan bahwa z₃ – c₃  baru menjadi positif sehingga x₃ 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  (z_j – c_j) £ 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  = c_BB^-1 b’.

Bila tidak, maka gunakan Dual Simplex untuk mencari solusi optimal dengan mengupayakan fisibilitasnya.

Contoh :

Dari Persoalan PL berikut :

Minimasi    - 2 x₁+    x₂  -   x₃

      s/t                         x₁ +    x₂  +   x₃  £ 6

             - x₁+ 2 x₂             £ 4

      x₁, x ₂ , x₃  ³ 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 :   x₁^*= 3, s₂^* = 7, x₂^* = x₃^*= s₁^* = 0.

C) Perubahan Matriks Konstrain A :

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

Kolom yang berubah adalah B^-1 a_j’ dan (z_j‘– c_j) = c_B B^-1a_j’ - c_j. Bila (z_j‘– c_j) £ 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 x_j.

Contoh :

Dari persoalan PL berikut :

Minimasi    - 2 x₁+    x₂  -   x₃

      s/t                         x₁+    x₂  +   x₃  £ 6

             - x₁+ 2 x₂             £ 4

      x₁, x ₂ , x₃  ³ 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 a₂ =  pada contoh dimuka diganti dengan , maka y₂’ = B^-1 a₂’ = =

c_BB^-1 a₂’ – c₂ =  (-2,0) - 1  = -5.

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

2)    Kasus II : Perubahan vektor kolom variabel basis : a_j ® a_j’

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 x_j’ ditambahkan pada persoalan dengan kolom a_j’ (dan koefisien f.obyektifnya = c_j).

·        Langkah 2 :  Hilangkan variabel lama x_j.

 

Langkah 1 dilakukan dengan menentukan y_j’ = B^-1 a_j’ dan (z_j‘– c_j) = c_B B^-1a_j’ - c_j dimana Bmerupakan basis yang ada saat ini, sehingga meng-update kolom x_j’.

 

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

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

Contoh : Bila y_jj = 0

Bila a₁ = pada contoh dimuka diganti dengan , maka

y₁’ = B^-1 a₁’ = =

c_B B^-1 a₁’ – c₁ =  (-2,0) - (-2)  = 2.

Disini nilai entri pada baris x₁ dari kolom y₁’ = 0 dan oleh karenanya kolom-kolom basis tidak lagi berdimensi m. Dengan menambahkan kolom (2, 0, -1) ^t  dari  x_j’ dan memperlakukan x_jsebagai 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 (z_x1– c_x1) =  0.

Contoh : Bila y_jj ¹ 0,

Bila a₁ = pada contoh dimuka diganti dengan , maka

y₁’ = B^-1 a₁’ = =

c_B B^-1 a₁’ – c₁ =  (-2,0) - (-2)  = - 4.

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

	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 z_n+1 – c_n+1 > 0, maka x_n+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 x₄dengan c₄ = 1, dan a₄= (-1,2) ^t.

Pertama : Hitung z_x4 – c_x4  =  w a_x4 – c_x4  = (-2, 0)  -1 =  1

y_x4 = B^-1a_x4 = =

Karena z_x4 – c_x4 = 1 > 0, maka x₄ masuk basis dan pivoting dilakukan pada baris s₂dan kolom x₄.

                                                                  ¯

	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 :

a^m+1 x £  b_m+1.

dan dari pembahasan Metoda Simplex diketahui :

z –  0 x_B+ (c_B B^-1 N – c_N )x_N  = c_B B^-1 b  …………………………..  (1)

     x_B +               B^-1 N x_N  = B^-1 b     …………………………..  (2)

Konstrain baru a^m+1 x £ b_m+1   dituliskan sebagai :

a_B^m+1 x_B + a_N^m+1 x_N  + x_n+1 = b_m+1;

dimana a^m+1 dipecah penulisannya menjadi  (a_B^m+1, a_N^m+1), dan x_n+1  º variabel slack non-negatif .

Kalikan Persamaan (2) dengan a_B^m+1 :

a_B^m+1x_B + a_B^m+1 B^-1 N x_N  = a_B^m+1 B^-1 b   …………………………..  (3)

 

dan kurangkan pada konstrain baru, akan diperoleh :

a_B^m+1x_B +          a_N^m+1x_N  + x_n+1 = b_m+1

a_B^m+1x_B + a_B^m+1B^-1 N x_N            = a_B^m+1 B^-1b   ..…………………..  (3)

¾¾¾¾¾¾¾¾¾¾¾¾¾¾¾  -

(a_N^m+1  - a_B^m+1 B^-1 N) x_N  + x_n+1 = b_m+1 - a_B^m+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 b_m+1 - a_B^m+1 B^-1 b ³ 0 maka solusi ini adalah optimal; akan tetapi bila b_m+1 - a_B^m+1 B^-1 b < 0, diperlukan Dual Simplex untuk penyelesaiannya.

Contoh :

Bila pada contoh dimuka ditambahkan konstrain baru - x₁+2x₃ ³ 2, maka titik optimal (x₁, x₂, x₃) = (6, 0 , 0) tidak memenuhi konstrain baru ini.

Konstrain baru dituliskan sebagai :  x₁ - 2 x₃ + s₃ = - 2, dimana s₃ 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 x₁ 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.