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.

Perbedaan metode Big M dengan primal simpleks, 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 kasus dibawah 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


1.   Nilai A1 digantikan dari fungsi kendala pertama. A1 = 3 - 3x1 - x2

MA1  berubah menjadi M(3 - 3x1 - x2) -->3M-3Mx1-Mx2

2.   Nilai A2 digantikan dari fungsi kendala ketiga.

A2 = 6 - 4x1 - 3x2  + s1

MA2 berubah menjadi M(6 - 4x1 - 3x2 + s1) 6M- 4Mx1 - 3Mx2 + Ms1

3.   Fungsi tujuan berubah menjadi

Min z = 4x1 + x2 + 3M-3Mx1-Mx2 +6M-4Mx1-3Mx2+Ms1

=  (4 -7M)x1+(1 - 4M)x2 + Ms1 +9M
 
 
4.   Tabel awal simpleks

VB
X1
X2
S1
A1
A2
S2
Solusi








z
-4 +7M
-1 +4M
-M
0
0
0
9M








A1
3
1
0
1
0
0
3
A2
4
3
-1
0
1
0

6









S2
1
2
0
0
0
1
4










5. Perhitungan iterasinya sama dengan simpleks sebelumnya.


Iterasi-0
VB

X1
X2
S1

A1

A2
S2

Solusi
Rasio























z
-4 +7M
-1 +4M
-M
0

0

0


9M
-























A1

3
1
0
1

0

0


3
1

A2

4
3
-1
0

1

0












6
3/2

S2

1
2
0
0

0

1


4
2


























Iterasi-1





































VB
X1

X2
S1
A1

A2
S2

Solusi
Rasio




















z
0
(1 +5M)/3
-M   (4-7M)/3

0

0

4+2M
-























X1
1

1/3
0
1/3

0

0


1
3

A2
0

5/3
-1
-4/3

1

0












2
6/5

S2
0

5/3
0
-1/3

0

1


3
9/5


























Iterasi-2





































VB
X1
X2
S1
A1

A2


S2

Solusi
Rasio




















z
0
0
1/5
8/5 – M
-1/5 – M
0


18/5
-





















X1
1
0
1/5
3/5

-1/5

0


3/5
25/3

X2
0
1
-3/5
-4/5
3/5

0










6/5
-

S2
0
0
1
1
-1


1


1
1

























Iterasi-3
 --> Optimal





































VB
X1
X2
S1

A1


A2

S2

Solusi























z
0
0
0

7/5-M


-M

-1/5

17/5






























X1
1
0
0
2/5
0
-1/5
2/5

X2
0
1
0
-1/5
0
3/5


9/5

S1
0
0
1
1
-1
1
1











Daftar Pustaka :


https://www.academia.edu/11623031/METODE_BIG_M