Pengertian
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
· 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.
· 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.
· 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.
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 - x
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
|
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
optimal.
|
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
|
-6
|
0
|
0
|
1
|
-150
|
Tabel di atas optimal tapi tidak layak (ingat, untuk
fungsi tujuan minimisasi, tabel sudah optimal jika semua koefisien baris tujuan
sudah negatif atau 0). Untuk membuat tabel tersebut layak, kita harus gunakan
metode dual simpleks. Langkah-langkah penyelesaian simpleks menggunakan metode
dual adalah:
- Tentukan baris pivot. Baris pivot adalah baris dengan
nilai kanan negatif terbesar. Jika negatif terbesar lebih dari satu, pilih
salah satu sembarang.
·
Tentukan kolom pivot. Kolom pivot
diperoleh dengan terlebih dahulu membagi nilai baris z dengan baris pivot.
Dalam hal ini, semua nilai baris pivot dapat menjadi pembagi kecuali nilai 0.
Kolom pivot adalah kolom dengan rasio pembagian mutlak terkecil. Jika rasio
pembagian mutlak terkecil lebih dari satu, pilih salah satu secara sembarang
- Pembentukan tabel berikutnya sama dengan prosedur dalam
primal simpleks.
Gunakan tabel awal simpleks di atas.
➢ Baris pivot adalah
baris S1, baris dengan nilai kanan negatif terbesar.
|
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
|
➢ Kolom pivot adalah
kolom X1
|
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
|
|
Rasio
|
21/90
|
18/20
|
15/40
|
0
|
0
|
0
|
-
|
➢ Iterasi-1:
|
VB
|
X1
|
X2
|
X3
|
S1
|
S2
|
S3
|
NK
|
|
Z
|
0
|
-40/9
|
-9
|
-7/30
|
0
|
0
|
140/3
|
|
X1
|
1
|
2/9
|
4/9
|
-1/90
|
0
|
0
|
20/9
|
|
S2
|
0
|
-220/3
|
-140/3
|
-1/3
|
1
|
0
|
-340/3
|
|
S3
|
0
|
-160/9
|
-500/9
|
-1/9
|
0
|
1
|
-1150/9
|
|
Rasio
|
-
|
0.0485
|
0.19286
|
0.7
|
-
|
-
|
➢ Iterasi-2
|
VB
|
X1
|
X2
|
X3
|
S1
|
S2
|
S3
|
NK
|
|
Z
|
0
|
0
|
-611/99
|
-0.213131
|
-2/33
|
0
|
53.535
|
|
X1
|
0
|
0
|
10/33
|
0.0303
|
1/330
|
0
|
1.8788
|
|
X2
|
0
|
1
|
7/11
|
1/220
|
-3/220
|
0
|
17/11
|
|
S3
|
0
|
0
|
-44.2424
|
-0.0303
|
-0.02424
|
1
|
-100.3030
|
|
Rasio
|
-
|
-
|
0.139498
|
7.0340
|
2.500
|
0
|
-
|
➢ Iterasi-3
optimal
|
VB
|
X1
|
X2
|
X3
|
S1
|
S2
|
S3
|
NK
|
|
Z
|
0
|
0
|
0
|
-0.208934
|
-0.0572
|
-0.13948
|
67.52628
|
|
X1
|
1
|
0
|
0
|
0.00000014
|
0.00286
|
0.006848
|
1.19173
|
|
X2
|
0
|
1
|
0
|
0.0041127
|
-0.013986
|
0.01438
|
0.102818
|
|
X3
|
0
|
0
|
1
|
0.00068
|
0.00055
|
-0.0226
|
2.267
|
