Metode Big M
Pada pendekatan ini, artifisial isbandi
dalam fungsi tujuan diberi suatu biaya sangat besar (biasanya 3 atau 4 kali
besarnya isbanding bilangan lain dalam model). Dalam praktek ini huruf M
digunakan sebagai biaya dalam masalah minimasi dan –M sebagai keuntungan dalam
masalah maksimasi dengan asumsi bahwa M adalah suatu bilangan positif yang
besar.
Sering kita menemukan bahwa fungsi kendala tidak hanya
dibentuk oleh pertidaksamaan ≤ tapi juga oleh pertidakasamaan ≥ dan/atau
persamaan (=). Fungsi kendala dengan pertidaksamaan ≥ mempunyai surplus
variable, tidak ada slack variables. Surplus variable tidak bisa menjadi
variabel basis awal. Dengan demikian harus ditambahkan satu variabel baru yang
dapat berfungsi sebagai variabel basis awal. Variabel yang dapat berfungsi
sebagai variabel basis awal hanya slack variables dan artificial variables
(variabel buatan).
Contoh 1 Permasalahan Maksimasi
Maks
Z = 4 x1 + 2 x2
Dengan memperhatikan kendala:
3 x1 + 2 x2 £ 8
- 4 x1
+ 3 x2 ³ - 7
8 x1 + 2 x2 = 12
dengan x1, x2 ³
0
Formulasi model di atas dikonversikan ke dalam
bentuk standar, sehingga menjadi:
Maks Z = 4 x1
+ 2 x2
Dengan memperhatikan
kendala:
3 x1 + 2 x2 + s1 =
8
4 x1 - 3 x2 + s2
= 7
8 x1 + 2 x2 = 12
dengan
x1, x2 ³ 0
s1,
s2 ³
0
Formulasi bentuk standar sistem kanonik adalah
sebagai berikut:
Maks Z = 4 x1
+ 2 x2 + 0 s1 + 0 s2 – M r1
Dengan memperhatikan
kendala:
3 x1 + 2 x2 + s1 = 8
4 x1 - 3
x2 + s2 = 7
8 x1 + 2 x2 + r1 = 12
dengan
x1, x2 ³ 0
s1, s2
³
0
r1 ³ 0
Hasil dari operasi pivot diperoleh Tabel berikut ini
¢ Sudah optimal, karena syarat optimalitas terpenuhi dan
variabel semu sudah keluar basis.
¢ Nilai
x1 = 4/5, x2 = 14/5, s1 = r1 = 0, s2
= 61/5 dan Z = 44/5.
Sumber
:
https://www.academia.edu/12146253/Riset_Operasi
Tidak ada komentar:
Posting Komentar