METODE BIG M
Metode Big M digunakan untuk menyelesaikan fungsi-fungsi
dalam program linier yang tidak berada dalam bentuk baku atau
standar ( bentuk standar adalah memaksimalkan Z sesuai dengan
kendala fungsional dalam bentuk ≤ dan kendala nonegativitas di semua
variabel) dan salah satu contoh masalah dalam kendala funsional adalah bila
fungsi dalam bentuk-bentuk = atau ≥ atau bahkan ruas kanan yang negatif.
Masalah ini akan muncul bila kita akan mencari basis fesibel
awal sehingga sebelum mencari variabel apa yang akan menjadi variabel nonbasis
bahkan basis perlu dilakukan suatu teknik pendekatan khusus untuk mengubah
fungsi tersebut ke bentuk baku atau standar. Teknik pendekatan khusus tersebut
dengan cara menambahkan variabel dummy (variabel artifisial) pada kendala
fungsional dan teknik ini disebut dengan teknik variabel artifisial.
Ada pun prosedur mendapatkan BF awal pada kendala fungsional
adalah
a.
Gunakan teknik variabel artifisial
Tambahkan variabel artifisal nonegatif pada fungsi kendala
yang belum baku, dan anggaplah variabel artifial tersebut sebagai salah satu
variabel slack
b.
Tugaskan pinalty yang besar
Berilah nilai variabel artifisial dengan nilai > 0
sehingga koefisien variabel artifisial menjadi M (big m) secara simbolik yang
menunjukkan bahwa variabel artifisial tersebut memiliki angka positif raksasa (
dan pengubahan atas variabel artifisial bernilai 0 (variabel nonbasis) dalam
solusi optimal disebut metode big m).
Contoh = Min Z
= 4 X1 + X2
Kendala 3 X1 + X2 =
3
4 X1 + 3 X2 = 6
X1 + 2 X2 =
4
X1 ,
X2 ³ 0
·
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 = 9M
Sehingga X1 ,
X2 , X3 var
non basis
Tabel Metode Big M
Iterasi 0
(awal)X1 (paling + ) R1Keluar
|
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 ) X2masukR2keluar
|
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 ) X3masuk
X4keluar
|
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
|
Komentar
Posting Komentar