METODE
BIG M
Sering kita menemukan bahwa fungsi
kendala tidak hanya dibentukoleh 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 dilakukandengan cara yang sudah
diperkenalkan sebelumnya.
2. Jika fungsi
kendala menggunakan pertidaksamaan ≥
dan/atau ≤ maka variabel basis awal adalah slack variables dan/atau variabel
buatan.
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.
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 Metode
Simpleks, 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:
•
Penambahan variabel buatan pada fungsi
kendala yang tidak memiliki variabel slack, menuntut penambahan variabel buatan
pada fungsi tujuan.
• Jika fungsi tujuan adalah maksimisasi, maka variabel buatan
pada fungsi tujuan mempunyai koefisien +M; jika fungsi tujuan adalah
minimisasi, maka variabel buatan pada fungsi tujuanmempunyai koefisien -M.
•
Karena koefisien variabel basis pada
tabel simpleks harus bernilai 0, maka variabel buatan pada fungsi tujuan harus digantikan
nilai dari fungsi kendala yang memuat variabel buatan tersebut.
Perhatikan contoh di
bawah ini.
Bentuk Umum
Min. z = 4 x1 + x2
Terhadap: 3x1 + x2 =
3
4x1+
3x2 ≥ 6
x1 +
2x2 ≤ 4
x1,
x2 ≥ 0
Bentuk Baku:
Min. z = 4 x1 + x2
Terhadap: 3x1 + x2 = 3
4x1 +
3x2 - s1 = 6
x1+
2x2+ s2 = 4
x1,
x2, s1, s2 ≥0
Kendala
1 dan 2 tidak mempunyai slack variabel,
sehingga tidak ada variabel basis awal. Untuk
berfungsi sebagai variabel basis awal,pada kendala 1 dan 2
ditambahkan masing-masing satu variabel buatan (artificial variable). Maka bentuk baku Big M-nya
adalah:
Min.
z = 4x1 + x2 + MA1 + MA2
Terhadap: 3x1 + x2 + A1 =
3
4x1 +
3x2 - s1 + A2 = 6
x1 +
2x2 + s2 = 4
x1,
x2, s1, s2 ≥0
Sumber : http://www.academia.edu/11623031/METODE_BIG_M
Komentar
Posting Komentar