Metode Big M untuk Simpleks dengan Kendala "=" atau "≥"

Pernahkah Sixtyfourians mencoba menyelesaikan masalah Program Linier (PL) dengan Metode Simpleks, tetapi hasil awalnya malah ngaco? Seringkali, saat menghadapi masalah Minimisasi atau batasan yang menggunakan tanda "≥" (lebih besar sama dengan) atau "=" (sama dengan), kita terjebak dalam apa yang disebut Penyelesaian Awal Semu (Artificial Initial Solution). Intinya, solusi awal yang kita dapatkan itu tidak fisibel (tidak valid) karena melanggar batasan non-negatif! Tapi jangan khawatir, dalam artikel ini, kita akan bongkar tuntas bagaimana cara mengatasinya menggunakan senjata rahasia bernama Variabel Semu (Artificial Variable).

Mengubah ke Bentuk Kanonik (Standard Form)

Untuk menerapkan Simpleks, kita harus mengubah semua batasan ketaksamaan menjadi persamaan (tanda "=").

• Untuk batasan ≥, kita harus mengurangi dengan sᵢ (Variabel Slack) dan menambah dengan aᵢ (Variabel Semu). Variabel Surplus (sᵢ) adalah variabel yang mewakili kelebihan di sisi kiri.

• Untuk batasan =, kita harus menambah dengan aᵢ (Variabel Semu) saja tanpa variabel surplus.

Menambahkan Variabel Semu (a)

Untuk mendapatkan solusi basis awal yang fisibel, kita perlu memperkenalkan Variabel Semu (a) di sisi kiri batasan yang bermasalah (≥ atau =). Berikut ini prinsip Utama Variabel Semu (a):

1. Bentuk Kanonik Batasan: Kita tambahkan aᵢ ke sisi kiri batasan yang sudah dikurangi variabel surplus (sᵢ). aᵢ ≥ 0.

2. Tujuan aᵢ: Variabel aᵢ ini berfungsi mirip variabel slack hanya sebagai katalisator agar kita mendapatkan Solusi Awal yang FISIBEL. Begitu Simpleks berjalan, kita harus segera mengeluarkannya dari variabel basis!

3. Penalti dalam Fungsi Tujuan: Untuk memaksa R segera menjadi nol, kita berikan "penalti" yang sangat besar dalam Fungsi Tujuan (f).

• Masalah Minimisasi: Tambahkan sebesar +aM pada fungsi f.

• Masalah Maksimisasi: Kurangi sebesar –aM pada fungsi f.

Catatan: M adalah bilangan positif yang sangat besar (M ≈ ∞). Ini adalah teknik Metode Big M.

Konsekuensi Penggunaan Variabel Semu

Penggunaan variabel a memang menyelamatkan kita, tapi ada satu aturan penting di akhir, yaitu variabel semu (a) hanya digunakan pada awal penyelesaian!

1. Selama proses Simpleks, koefisien M yang sangat besar itu akan memastikan variabel a keluar dari basis (nilainya menjadi nol) secepat mungkin.

2. Di penyelesaian akhir (solusi optimal):

• Jika SEMUA variabel a bernilai NOL, maka solusinya adalah FISIBEL.

• Jika ADA variabel a yang TIDAK SAMA DENGAN NOL (misalnya a₁ = 2), maka berarti TIDAK ADA solusi fisibel untuk masalah Program Linier tersebut (Infisible Solution).

Variabel Semu (a) adalah "pemadam kebakaran" kita saat menghadapi masalah PL dengan batasan ≥ atau =. Fungsinya adalah sementara untuk menciptakan Solusi Awal Basis yang Fisibel. Kita memberinya "penalti" dengan M yang besar di Fungsi Tujuan. Jika a masih muncul di solusi akhir, artinya masalah PL yang Anda hadapi tidak memiliki solusi yang valid.

Contoh Soal

1. Cari x₁, x₂, x₃ tak negatif yang memaksimumkan f = x₁ + x₂ + x₃ dan memenuhi kendala:

x₁ + x₂ ≥ 20

x₂ + x₃ ≤ 18

3x₁ + 2x₂ + 5x₃ ≤ 120

x₁, x₂, x₃ ≥ 0

Solusi:

Ubah kendala ke bentuk kanonik:

x₁ + x₂ – s₁ + a = 20

x₂ + x₃ + s₂ = 18

3x₁ + 2x₂ + 5x₃ + s₃ = 120

x₁, x₂, x₃, s₁, s₂, s₃, a ≥ 0

Ubah fungsi tujuan ke bentuk kanonik:

f = x₁ + 5x₂ + 8x₃ + 0s₁ + 0s₂ + 0s₃ – aM

Susun tablo awal:

	cⱼ	1	1	1	0	0	0	-M
c̅ᵢ	x̅ᵢ/xⱼ	x₁	x₂	x₃	s₁	s₂	s₃	a	bᵢ	Rᵢ
-M	a	1	1	0	-1	0	0	1	20	20
0	s₂	0	1	1	0	1	0	0	18	-
0	s₃	3	2	5	0	0	1	0	120	40
	zⱼ	-M	-M	0	M	0	0	-M	-20M
	zⱼ – cⱼ	-M-1	-M-1	-1	M	0	0	0

Kolom x₁ dan x₂ keduanya memiliki zⱼ – cⱼ paling negatif, yaitu –M–1, kita boleh memilih kolom x₁ atau kolom x₂ sebagai kolom pivot, disini Minfor akan mencoba memilih kolom x₁.

Nilai-nilai di kolom Rᵢ diperoleh dari nilai kolom bᵢ yang bersesuaian dibagi dengan nilai kolom pivot, yaitu kolom x₁.

20/1 = 20;    120/3 = 40. Adapun baris 2 dikecualikan karena pembaginya non-positif.

Baris 1 memiliki Rᵢ terkecil, yaitu 20. Oleh karena itu ganti a dengan x₁. Karena sel yang bertepatan dengan kolom x₁ adalah 1, baris ini tidak perlu diubah.

Lakukan OBE untuk baris 2 dan baris 3 sehingga sel yang bertepatan dengan kolom x₁ bernilai 0.

Berikut ini tablo kedua:

	cⱼ	1	1	1	0	0	0	-M
c̅ᵢ	x̅ᵢ/xⱼ	x₁	x₂	x₃	s₁	s₂	s₃	a	bᵢ	Rᵢ
1	x₁	1	1	0	-1	0	0	1	20	-
0	s₂	0	1	1	0	1	0	0	18	-
0	s₃	0	-1	5	3	0	1	-3	60	20
	zⱼ	1	1	0	-1	0	0	1	20
	zⱼ – cⱼ	0	0	-1	-1	0	0	M+1

Kolom x₃ dan s₁ keduanya memiliki zⱼ – cⱼ paling negatif, yaitu –1, kita boleh memilih kolom x₃ atau kolom s₁ sebagai kolom pivot, disini Minfor akan mencoba memilih kolom s₁.

Nilai-nilai di kolom Rᵢ diperoleh dari nilai kolom bᵢ yang bersesuaian dibagi dengan nilai kolom pivot, yaitu kolom x₁.

60/3 = 20. Baris 1 dan baris 2 dikecualikan karena pembaginya non-positif.

Baris 3 memiliki Rᵢ terkecil, yaitu 20. Oleh karena itu ganti s₃ dengan s₁. Sel yang bertepatan dengan kolom s₁ adalah 3, baris ini dibagi 3 agar sel tersebut menjadi 1.

Lakukan OBE untuk baris 1 dan baris 2 sehingga sel yang bertepatan dengan kolom s₁ bernilai 0.

Berikut ini tablo ketiga:

	cⱼ	1	1	1	0	0	0	-M
c̅ᵢ	x̅ᵢ/xⱼ	x₁	x₂	x₃	s₁	s₂	s₃	a	bᵢ	Rᵢ
1	x₁	1	⅔	5/3	0	0	⅓	0	40	60
0	s₂	0	1	1	0	1	0	0	18	18
0	s₁	0	-⅓	5/3	1	0	⅓	-1	20	-
	zⱼ	1	⅔	5/3	0	0	⅓	0	40
	zⱼ – cⱼ	0	-⅓	⅔	0	0	⅓	M

Kolom x₂ memiliki zⱼ – cⱼ paling negatif, yaitu –⅓, oleh karena itu dipilih sebagai kolom pivot.

Nilai-nilai di kolom Rᵢ diperoleh dari nilai kolom bᵢ yang bersesuaian dibagi dengan nilai kolom pivot, yaitu kolom x₂.

40 × 3 / 2 = 60;    18/1 = 18. Baris 3 dikecualikan karena pembaginya non-positif.

Baris 2 memiliki Rᵢ terkecil, yaitu 18. Oleh karena itu ganti s₂ dengan x₂. Sel yang bertepatan dengan kolom x₂ adalah 1, baris ini tidak perlu diubah.

Lakukan OBE untuk baris 2 sehingga sel yang bertepatan dengan kolom x₂ bernilai 0.

Berikut ini tablo keempat:

	cⱼ	1	1	1	0	0	0	-M
c̅ᵢ	x̅ᵢ/xⱼ	x₁	x₂	x₃	s₁	s₂	s₃	a	bᵢ	Rᵢ
1	x₁	1	0	1	0	-⅔	⅓	0	28
1	x₂	0	1	1	0	1	0	0	18
0	s₁	0	0	2	1	⅓	⅓	-1	26
	zⱼ	1	1	2	0	⅓	⅓	0	46
	zⱼ – cⱼ	0	0	1	0	⅓	⅓	M

Tablo terakhir sudah optimum karena semua zⱼ – cⱼ sudah bernilai non-negatif.

Penyelesaian layak (Pl) adalah (x₁, x₂, x₃, s₁, s₂, s₃, a) = (28, 18, 0, 26, 0, 0, 0)

Penyelesaian layak basis (Plb) adalah (x₁, x₂, s₁) = (28, 18, 26)

Penyelesaian optimum (Po) adalah (x₁, x₂, x₃) = (28, 18, 0)

Nilai maksimum fungsi tujuan adalah fmax = 46.

2. Cari x₁, x₂, x₃ tak negatif yang meminimumkan f = 4x₁ + 3x₂ + 6x₃ dan memenuhi kendala:

2x₁ + x₂ + x₃ ≥ 10

3x₁ + 2x₂ + x₃ ≤ 12

x₁ + x₂ + 2x₃ ≤ 14

x₁, x₂, x₃ ≥ 0

Solusi:

Ubah kendala ke bentuk kanonik:

2x₁ + x₂ + x₃ – s₁ + a = 10

3x₁ + 2x₂ + x₃ + s₂ = 12

x₁ + x₂ + 2x₃ + s₃ = 14

x₁, x₂, x₃, s₁, s₂, s₃, a ≥ 0

Ubah fungsi tujuan ke bentuk kanonik:

f = 4x₁ + 3x₂ + 6x₃ + 0s₁ + 0s₂ + 0s₃ + aM

Susun tablo awal:

cⱼ		4	3	6	0	0	0	M
c̅ᵢ	x̅ᵢ/xⱼ	x₁	x₂	x₃	s₁	s₂	s₃	a	bᵢ	Rᵢ
M	a	2	1	1	-1	0	0	1	10	5
0	s₂	3	2	1	0	1	0	0	12	4
0	s₃	1	1	2	0	0	1	0	14	14
	zⱼ	2M	M	M	-M	0	0	M	10M
	zⱼ – cⱼ	2M-4	M-3	M-6	-M	0	0	0

Kolom x₁ memiliki zⱼ – cⱼ paling positif, yaitu 2M–4, oleh karena itu dipilih sebagai kolom pivot.

Nilai-nilai di kolom Rᵢ diperoleh dari nilai kolom bᵢ yang bersesuaian dibagi dengan nilai kolom pivot, yaitu kolom x₁.

10/2 = 5;    12/3 = 4;    14/1 = 14.

Baris 2 memiliki Rᵢ terkecil, yaitu 4. Oleh karena itu ganti s₂ dengan x₁. Sel yang bertepatan dengan kolom x₁ adalah 3, baris ini dibagi 3 agar sel tersebut menjadi 1.

Lakukan OBE untuk baris 1 dan baris 3 sehingga sel yang bertepatan dengan kolom x₁ bernilai 0.

Berikut ini tablo kedua:

cⱼ		4	3	6	0	0	0	M
c̅ᵢ	x̅ᵢ/xⱼ	x₁	x₂	x₃	s₁	s₂	s₃	a	bᵢ	Rᵢ
M	a	0	-⅓	⅓	-1	-⅔	0	1	2	6
4	x₁	1	⅔	⅓	0	⅓	0	0	4	12
0	s₃	0	⅓	5/3	0	-⅓	1	0	10	6
	zⱼ	4	-⅓M+8/3	⅓M+4/3	-M	-⅔M+4/3	0	M	2M+16
	zⱼ – cⱼ	0	-M-⅓	⅓M-14/3	-M	-⅔M+4/3	0	0

Kolom x₃ memiliki zⱼ – cⱼ paling positif, yaitu ⅓M–14/3, oleh karena itu dipilih sebagai kolom pivot.

Nilai-nilai di kolom Rᵢ diperoleh dari nilai kolom bᵢ yang bersesuaian dibagi dengan nilai kolom pivot, yaitu kolom x₃.

2/(⅓) = 6;    4/(⅓) = 12;    10/(5/3) = 6.

Baris 1 dan baris 3 memiliki Rᵢ terkecil, yaitu 6. Kita dapat memilih baris 1 atau baris 3 untuk diganti. Minfor mencoba untuk memilih baris 1, ganti a dengan x₃. Sel yang bertepatan dengan kolom x₃ adalah ⅓, baris ini dikali 3 agar sel tersebut menjadi 1.

Lakukan OBE untuk baris 2 dan baris 3 sehingga sel yang bertepatan dengan kolom x₃ bernilai 0.

Berikut ini tablo ketiga:

cⱼ		4	3	6	0	0	0	M
c̅ᵢ	x̅ᵢ/xⱼ	x₁	x₂	x₃	s₁	s₂	s₃	a	bᵢ	Rᵢ
6	x₃	0	-1	1	-3	-2	0	3	6
4	x₁	1	1	0	1	1	0	-1	2
0	s₃	0	2	0	5	3	1	-5	0
	zⱼ	4	-2	6	-14	-8	0	14	44
	zⱼ – cⱼ	0	-5	0	-14	-8	0	-M+14

Tablo terakhir sudah optimum karena semua zⱼ – cⱼ sudah bernilai non-positif.

Penyelesaian layak (Pl) adalah (x₁, x₂, x₃, s₁, s₂, s₃, a) = (2, 0, 6, 0, 0, 0, 0)

Penyelesaian layak basis (Plb) adalah (x₁, x₃, s₃) = (2, 6, 0)

Penyelesaian optimum (Po) adalah (x₁, x₂, x₃) = (2, 0, 6)

Nilai maksimum fungsi tujuan adalah fmax = 44.