Thursday, September 29, 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.


0 Reactions to this post

Add Comment

    Post a Comment