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.