Metode
2 Fase
Dalam
menyelesaiakan suatu persoalan dimana variabelnya lebih dari dua, juga
menggunakan suatu metode yang bertahap. Metode ini disebut sebagai metode dua
phase.
Pada dasarnya Metode dua fase (phase)
sama seperti metode big M yang juga digunakan untuk menyelesaikan persoalan
pemrograman linier yang memiliki bentuk yang tidak standar. Berikut
ini adalah prosedur menggunakan metode dua fase.
1.
Inisialisasi
Menambahkan
variabel-variabel artifisal pada fungsi kendala yang memiliki bentuk tidak
standar. Variabel artificial ini ditambahkan pada fungsi batasan yang pada
mulanya memiliki tanda (³). Hal ini digunakan agar dapat mencari solusi basic
fesibel awal.
2.
Fase 1
Digunakan untuk
mencari basic fesibel awal. Pada fase 1 memiliki langkah-langkah
dimana tujuannya adalahm meminimalkan variabel artifisial ( Min Y= Xa)
s.t : Ax = b
X
= 0
Pada fase
pertama bertujuan untuk memperoleh penyelesaian yang optimum dari suatu
permasalahan. Pada fase pertama fungsi tujuan selalu minimum variabel
artificial, meskipun permasalahan yang ada adalah permasalahan yang maksimum.
Dalam meyelesaiakan pada fase pertama, yaitu membuat nilai nol dulu pada
variabel artifisial, kemudian melanjutkan iterasi seperti proses iterasi
biasanya(dengan aturan meminimumkan). Berhenti ketika pada baris ke-0
bernilai £ 0.
Fase pertama
dianggap telah selesai atau memperoleh penyelesaian yang optimal adalah apabila
variabel artifisial adalah merupakan variabel basis. Sedangkan apabila variabel
artifisial adalah variabel non basis, maka masalah dianggap tidak mempunyai
penyelesaian yang optimal, sehingga harus dilanjutkan ke fase yang kedua.
Pada fase
kedua, tujuannya sama seperti fase pertama, yaitu untuk mendapatkan
penyelesaian yang optimal dari suatu permasalahan yang ada. Fase dua berhenti
sesuai dengan tujuan awal permasalahan.
3. Fase 2
Digunakan untuk
mencari solusi optimum pada permasalahan riil. Karena variabel artifisial bukan
merupakan termasuk variabel dalam permasalahan riil, variabel artifisial
tersebut dapat dihilangkan ( Xa=0). Bermula dari solusi BF yang didapatkan dari
akhir fase 1. Pada fase 2 ini memiliki langkah-langkah sebagai berikut:
1.
Fungsi tujuan bisa memaksimalkan dan juga bisa
meminimalkan tergantung pada
permasalahan yang dihadapi.
2.
Menggunakan fungsi batasan (s.t) dari fase 1, melakukan
proses iterasi seperti biasanya
dan berhenti sesuai funsi obyektif awal
Contoh persoalan:
Metode ini digunakan untuk
menyelesaikan persoalan PL yang memuat variabel buatan
Contoh = Min Z = 4 X1 +
X2
Kendala 3 X1 + X2 =
3
4 X1 + 3 X2 ³
6
X1 +
2 X2 £ 4
X1 , X2 ³
0
Tahap 1 :
Bentuk dengan var buatan : R1 dan
R2
Min
r = R1 + R2
Kendala 3 X1 +
X2 + R1 = 3
4 X1 + 3 X2 -
X3 - R2 = 6
X1 + 2 X2 +
X4 = 4
X1 ,
X2 , X3 , R1 ,
R2 , X4 ³ 0
Fungsi tujuan r
= R1 + R2
= ( 3 – 3 X1 -
X2 ) + ( 6 - 4 X1 - 3 X2 +
X3 )
= -7 X1
- 4 X2 + X3 +
9
Tabel Awal
|
VB
|
X1
|
X2
|
X3
|
R1
|
R2
|
X4
|
NK
|
|
r
|
7
|
4
|
-1
|
0
|
0
|
0
|
9
|
|
R1
|
3
|
1
|
0
|
1
|
0
|
0
|
3
|
|
R2
|
4
|
3
|
-1
|
0
|
1
|
0
|
6
|
|
X4
|
1
|
2
|
0
|
0
|
0
|
1
|
4
|
Tabel
optimum : setelah 2 iterasi ( periksa ! )
|
VB
|
X1
|
X2
|
X3
|
R1
|
R2
|
X4
|
NK
|
|
r
|
0
|
0
|
0
|
-1
|
-1
|
0
|
0
|
|
X1
|
1
|
0
|
1/5
|
3/5
|
-1/5
|
0
|
3/5
|
|
X2
|
0
|
1
|
-3/5
|
-4/5
|
3/5
|
0
|
6/5
|
|
X4
|
0
|
0
|
1
|
1
|
-1
|
1
|
1
|
Karena
minimum solusi r = 0, masalah ini memiliki pemecahan ( solusi ) layak.
Lanjutkan ke tahap( Fase )kedua.
Tahap 2
F Menyingkirkan
variabel buatan ( R1 dan R2 )
F Dari tabel
optimum tahap 1 didapatkan :
X1 + 1/5X3 = 3/5
X2 - 3/5X3 = 6/5
X3 + X4 =
1
Masalah semula ditulis :
Min
Z = 4 X1 + X2
Kendala X1 + 1/5X3 = 3/5 ......... ( 1 )
X2 - 3/5X3 = 6/5 ......... ( 2 )
X3 +
X4 = 1
X1 ,
X2 , X3 , R1 ,
R2 , X4 ³ 0
Maka
terdapat 3 persamaan dan 4 variabel sehingga solusi dasar layak didapat dg
membuat (4 – 3) = 1 variabel dibuat nol
X3 =
0 -> X1 = 3/5
; X2 = 6/5
; X4 = 1
F Fungsi
tujuan Z = 4 X1 +
X2
=
4 ( 3/5 + 1/5 X3 ) + (6/5 + 3/5X3 )
= - 1/5 X3 + 18/5
Tabel Awal
Var msk
|
VB
|
X1
|
X2
|
X3
|
X4
|
NK
|
|
Z
|
0
|
0
|
1/5
|
0
|
18/5
|
|
X1
|
1
|
0
|
1/5
|
0
|
3/5
|
|
X2
|
0
|
1
|
-3/5
|
0
|
6/5
|
|
X4
|
0
|
0
|
1
|
1
|
1
|
Tabel optimum
|
VB
|
X1
|
X2
|
X3
|
X4
|
NK
|
|
Z
|
0
|
0
|
0
|
-1/5
|
17/5
|
|
X1
|
1
|
0
|
0
|
-1/5
|
2/5
|
|
X2
|
0
|
1
|
0
|
3/5
|
9/5
|
|
X3
|
0
|
0
|
1
|
1
|
1
|
Sumber :
Tidak ada komentar:
Posting Komentar