TEKNIK ARTIFICAL VARIABEL
DENGAN METODE M
DAN METODE DUA FASE
1.
TEKNIK M ( METODE PENALTY ) Kendala tidak
TEKNIK M ( METODE PENALTY ) Kendala tidak
2.
TEKNIK
DUA FASE Semuanya £
1.
TEKNIK M
Contoh
= Min Z
= 4 X1 + X2
Kendala 3 X1 + X2
= 3
4 X1 + 3 X2 ³ 6
X1 + 2 X2 £ 4
→ Bentuk standar
Min Z
= 4 X1 + X2
Kendala 3 X1 + X2 = 3 .........
( 1 )
4 X1 + 3 X2 - X3
= 6 ......... ( 2 )
X1 + 2 X2
+ X4 = 4
X1 , X2 , X3 , X4
³ 0
Karena ( 1 ) dan ( 2 ) tidak memiliki var slack , maka
ditambahkan R1 dan R2 sebagai var bantuan
( 1 ) 3 X1 +
X2 + R1 = 3
( 2 ) 4 X1 + 3 X2 - X3 - R2
= 6
- Pada fungsi tujuan berikan koefisien M > 0, untuk R1 dan R2 ; sehingga :
Min Z
= 4 X1 + X2 +
MR1 + MR2
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
- Subtitusikan R1 dan R2 ke fungsi tujuan :
R1 =
3 - 3 X1
- X2
R2 =
6 - 4 X1 - 3 X2 + X3
Maka :
Z
= 4 X1 + X2 +
M(3-
3 X1 - X2) + M(6
- 4 X1 - 3 X2 + X3)
=
( 4 - 7M ) X1 + ( 1 – 4M ) X2
+ M X3 + 9M
Persamaan
Z dalam tabel :
Z
+ ( 7M - 4 ) X1 + ( 4M
- 1 ) X2 - M X3 = 9M
- Solusi dasar awal ; X1 = 0, X2 = 0, X3 = 0 -> Z = 9
Tabel Metode
Big M
|
Iterasi 0
(awal) X1 (paling + ) R1 Keluar
|
Basis
|
X1
|
X2
|
X3
|
R1
|
R2
|
X4
|
Solusi
|
|
|
Z
|
(7M – 4)
|
(4M – 1)
|
-M
|
0
|
0
|
0
|
9M
|
|
|
|
R1
|
3
|
1
|
0
|
1
|
0
|
0
|
3
|
3/3 = 1
|
|
|
R2
|
4
|
3
|
-1
|
0
|
1
|
0
|
6
|
6/4
|
|
|
X4
|
1
|
2
|
0
|
0
|
0
|
1
|
4
|
4/1
|
|
|
( 1 ) X2 masuk
R2 keluar
|
Z
|
0
|
(1+5M)/3
|
-M
|
(4-7M)/3
|
0
|
0
|
4+2M
|
|
|
X1
|
1
|
1/3
|
0
|
1/3
|
0
|
0
|
1
|
1/(1/3)= 3
|
|
|
R2
|
0
|
5/3
|
-1
|
-4/3
|
1
|
0
|
2
|
2/(5/3)=6/5
|
|
|
X4
|
0
|
5/3
|
0
|
-1/3
|
0
|
1
|
3
|
8/5
|
|
|
( 2 ) X3 masuk
X4 keluar
|
Z
|
0
|
0
|
1/5
|
(8/3-M)
|
(-1/5-M)
|
0
|
18/3
|
|
|
X1
|
1
|
0
|
1/5
|
3/5
|
-1/5
|
0
|
3/5
|
3
|
|
|
X2
|
0
|
1
|
-3/5
|
-4/5
|
3/5
|
0
|
6/5
|
|
|
|
X4
|
0
|
0
|
1
|
1
|
-1
|
1
|
1
|
1
|
|
|
( 3 )
(optimum)
|
Z
|
0
|
0
|
0
|
7/3-M
|
-M
|
-1/5
|
17/5
|
|
|
X1
|
1
|
0
|
0
|
2/5
|
0
|
-1/5
|
2/5
|
|
|
|
X2
|
0
|
1
|
0
|
-1/5
|
0
|
3/5
|
9/5
|
|
|
|
X3
|
0
|
0
|
1
|
1
|
-1
|
1
|
1
|
|
2. DUA FASE
Bertujuan untuk mengurangi kesalahan perhitungan dari
pemberian nilai yg besar untuk konstanta M pada metode TEKNIK M (penalty)
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
|
Basis
|
X1
|
X2
|
X3
|
R1
|
R2
|
X4
|
Solusi
|
|
Z
|
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 ! )
|
Basis
|
X1
|
X2
|
X3
|
R1
|
R2
|
X4
|
Solusi
|
|
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
- Menyingkirkan variabel buatan ( R1 dan R2 )
- 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
- 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|
Basis
|
X1
|
X2
|
X3
|
X4
|
Solusi
|
|
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
|
Basis
|
X1
|
X2
|
X3
|
X4
|
Solusi
|
|
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
|
Bandingkan
dengan TEKNIK M!
1 komentar:
Ok.. Terima Kasih atas Postingnya !!!.....
Posting Komentar