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
- Gunakan teknik variabel artifisial
Tambahkan variabel artifisal nonegatif pada fungsi kendala yang belum baku, dan anggaplah variabel artifial tersebut sebagai salah satu variabel slack
- 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 + ) 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
|
|
Tidak ada komentar:
Posting Komentar