Tugas Riset Operasi
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:
- · 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 tujuan mempunyai 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 variables, 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 = 4 x1 + x2 + MA1 + MA2
Terhadap: 3x1 + x2 + A1 = 3
4x1 + 3x2 - s1 + A2 = 6
x1 + 2x2 + s2 = 4
x1, x2, s1, s2 ≥ 0
Kendala 1 dan 2 tidak mempunyai slack variables, 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 = 4 x1 + x2 + MA1 + MA2
Terhadap: 3x1 + x2 + A1 = 3
4x1 + 3x2 - s1 + A2 = 6
x1 + 2x2 + s2 = 4
x1, x2, s1, s2
METODE DUA
FASE
Metode dua fase digunakan jika variabel basis awal terdiri dari
variabel buatan. Disebut sebagai metode dua fase, karena proses optimasi
dilakukan dalam dua tahap. Tahap pertama merupakan proses optimasi variabel
buatan, sedangkan proses optimasi variabel keputusan dilakukan pada tahap
kedua. Karena variabel buatan sebenarnya tidak ada (hanya ada di atas kertas),
maka tahap pertama dilakukan untuk memaksa variabel buatan bernilai 0.
Perhatikan kasus berikut:
Tahap 1
Min A = A1 + A2
Terhadap: x1 + x2 + A1 = 90
0.001x1 + 0.002x2 + s1 = 0.9
0.09x1 + 0.6x2 -s2 + A2 =
27
0.02x1 + 0.06x2 + s3 = 4.5
x1, x2, s1, s2, s3 ≥ 0
karena A1 dan
A2 berfungsi sebagai variabel basis pada solusi awal, maka koefisiennya pada
fungsi tujuan harus sama dengan 0. untuk mencapai itu, gantikan nilai A1 dari
fungsi kendala pertama (kendala yang memuat A1) dan nilai A2 dari fungsi
kendala ketiga (kendala yang memuat A2).
Dari kendala -1 diperoleh :
A1 =
90 - x1 - x2
Dari kendala-3
diperoleh:
A2 = 27 - 0.09x1 -
0.6x2 + s2
Maka fungsi tujuan
tahap-1 menjadi:
Min A = (90 - x1 - x2) + (27 - 0.09x1 -
0.6x2 + s2)
=117 - 1.09x1 - 1.6x2 + s2
Solusi awal
VB
|
X1
|
X2
|
S1
|
S2
|
S3
|
A1
|
A2
|
NK
|
Rasio
|
A
|
1.09
|
1.6
|
0
|
-1
|
0
|
0
|
0
|
117
|
-
|
A1
|
1
|
1
|
0
|
0
|
0
|
1
|
0
|
90
|
90
|
S1
|
0.001
|
0.002
|
1
|
0
|
0
|
0
|
0
|
0.9
|
450
|
A2
|
0.09
|
0.6
|
0
|
-1
|
0
|
0
|
1
|
27
|
45
|
S3
|
0.02
|
0.06
|
0
|
0
|
1
|
0
|
0
|
4.5
|
75
|
Iterasi1
VB
|
X1
|
X2
|
S1
|
S2
|
S3
|
A1
|
A2
|
NK
|
Rasio
|
A
|
0.85
|
0
|
0
|
-11/3
|
0
|
0
|
-8/3
|
45
|
-
|
A1
|
0.85
|
0
|
0
|
10/6
|
0
|
1
|
-10/6
|
45
|
52.94
|
S1
|
0.0007
|
0
|
1
|
1/300
|
0
|
0
|
-1/300
|
0.81
|
1157.14
|
X2
|
0.15
|
1
|
0
|
-10/6
|
0
|
0
|
10/6
|
45
|
300
|
S3
|
0.011
|
0
|
0
|
0.1
|
1
|
0
|
-0.1
|
1.8
|
163.634
|
Iterasi2 optimal
VB
|
X1
|
X2
|
S1
|
S2
|
S3
|
A1
|
A2
|
NK
|
A
|
0
|
0
|
0
|
-4.8708
|
0
|
-1
|
-1.4625
|
0
|
X1
|
1
|
0
|
0
|
17/12
|
0
|
20/17
|
-17/12
|
52.94
|
S1
|
0
|
0
|
1
|
0.0023417
|
0
|
0.0008
|
-0.0023
|
0.772942
|
X2
|
0
|
1
|
0
|
-1.7542
|
0
|
-3/17
|
1.7542
|
37.059
|
S3
|
0
|
0
|
0
|
0.09358
|
1
|
0.01294
|
-0.084417
|
1.21766
|
Tahap 2
Min z = 2 x1 + 5.5 x2
Terhadap: tabel optimal tahap pertama
Dari tabel optimal tahap 1
diperoleh:
X1 = 52.94 – 17/12s2
X2 = 37.059 + 1.7542s2
Maka fungsi tujuan adalah:
Min z = 2(52.94 – 17/12s2) +
5.5 (37.059 + 1.7542s2)
= -17/6s2 + 9.6481s2 +
309.7045 = 6.814767s2 + 309.7045
Solusi awal
VB
|
X1
|
X2
|
S1
|
S2
|
S3
|
NK
|
z
|
0
|
0
|
0
|
-6.814767
|
0
|
309.7045
|
X1
|
1
|
0
|
0
|
17/12
|
0
|
52.94
|
S1
|
0
|
0
|
1
|
0.0023417
|
0
|
0.772942
|
X2
|
0
|
1
|
0
|
-1.7542
|
0
|
37.059
|
S3
|
0
|
0
|
0
|
0.09358
|
1
|
1.21766
|
Tabel di atas sudah optimal. Solusi
optimalnya adalah:
X1 = 52.94; x2 = 37.059; dan z = 309.7045
METODE DUAL SIMPLEKS
Metode dual simpleks digunakan
jika tabel optimal tidak layak. Jika fungsi kendala ada yang menggunakan
pertidaksamaan ≥ dan tidak ada = dalam bentuk umum PL, maka metode dual
simpleks dapat digunakan. Kita selesaikan contoh di bawah ini.
Min z = 21x1 + 18x2 + 15x3
Terhadap: 90x1 + 20x2 + 40x3 ≥ 200
30x1 + 80x2 + 60x3 ≥ 180
10x1 + 20x2 + 60x3 ≥ 150
x1, x2, x3 ≥ 0
semua kendala menggunakan pertidaksamaan ≥. Kendala dengan
pertidaksamaan ≥ dapat diubah ke pertidaksamaan ≤ dengan mengalikan
pertidaksamaan dengan -1. Bentuk umum PL di atas berubah menjadi:
Min z = 21x1 + 18x2 + 15x3
Terhadap: -90x1 - 20x2 - 40x3 ≤ -200
-30x1 - 80x2 - 60x3 ≤ -180
-10x1 - 20x2 - 60x3 ≤ -150
x1, x2, x3 ≥ 0
Semua fungsi kendala sudah dalam bentuk pertidaksamaan ≤, maka
kita kita hanya perlu menambahkan variabel slack untuk mengubah bentuk umum ke
bentuk baku/standar. Variabel slack akan berfungsi sebagai variabel basis awal.
Bentuk Baku/standar:
Min z = 21x1 + 18x2 + 15x3 + 0s1 + 0s2 + 0s3
Terhadap: -90x1 - 20x2 - 40x3 + s1 = -200
-30x1 - 80x2 - 60x3 + s2 =
-180
-10x1 - 20x2 - 60x3 + s3 =
-150
x1, x2, x3, s1, s2, s3 ≥ 0
VB
|
X1
|
X2
|
X3
|
S1
|
S2
|
S3
|
NK
|
Z
|
-21
|
-18
|
-15
|
0
|
0
|
0
|
0
|
S1
|
-90
|
-20
|
-40
|
1
|
0
|
0
|
-200
|
S2
|
-30
|
-80
|
-60
|
0
|
1
|
0
|
-180
|
S3
|
-10
|
-20
|
-60
|
0
|
0
|
1
|
-150
|
sumber : https://www.academia.edu/11623031/METODE_BIG_M?auto=download
Comments
Post a Comment