27
2.3.10 Metode BIG -M
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).
1. Jika semua fungsi kendala menggunakan pertidaksamaan
= maka variabel
basis awal semuanya adalah slack variables. Penyelesaian solusi optimal
untuk kasus seperti ini dilakukan dengan cara yang sudah diperkenalkan
sebelumnya.
2. Jika fungsi kendala menggunakan pertidaksamaan
= dan/atau = maka
variabel basis awal adalah slack variables
dan/atau variabel buatan.
Penyelesaian solusi optimal untuk kasus seperti ini dilakukan dengan
memilih antara metode BIG M, Dua Fase atau Dual Simpleks.
3. Jika fungsi kendala ada yang menggunakan persamaan maka variabel
buatan akan ditemukan pada variabel basis awal. Penyelesaian solusi
optimal untuk kasus seperti ini hanya dapat dilakukan dengan memilih
antara metode BIG M atau Dua Fase.
Kita akan bahas metode BIG M
dalam sub bab ini. Perbedaan metode BIG M
dengan primal simpleks biasa (teknik penyelesaian yang sudah dipelajari
sebelumnya), terletak pada pembentukan tabel awal. Jika fungsi kendala
menggunakan bentuk pertidaksamaan
=, perubahan dari bentuk umum ke bentuk
baku memerlukan satu variabel surplus.
Variabel surplus tidak dapat berfungsi
sebagai variabel basis awal, karena koefisiennya bertanda negatif. Sebagai variabel
basis pada solusi awal, harus ditambahkan satu variabel buatan. Variabel buatan pada
solusi optimal harus bernilai 0, karena variabel ini memang tidak ada.
Teknik yang digunakan untuk memaksa variabel buatan bernilai 0 pada solusi
optimal adalah dengan cara berikut:
 |