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:
a.
Fungsi tujuan bisa memaksimalkan dan juga bisa meminimalkan
tergantung pada permasalahan yang dihadapi.
b.
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
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
|
Komentar
Posting Komentar