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
Tidak ada komentar:
Posting Komentar