Metode Simpleks Dua Fase untuk Program Linier Sebagai Pengganti Big-M

Program Linier adalah tulang punggung pengambilan keputusan di berbagai industri. Saat menyelesaikan soal dengan batasan ≥ (lebih besar dari) atau = (sama dengan), kita sering berhadapan dengan Variabel Semu (Artificial Variables). Metode klasik seperti Big-M menggunakan koefisien M (bilangan yang sangat besar) untuk variabel semu tersebut. Namun, tahukah Sixtyfourians? Pemberian nilai M yang terlalu besar ini justru bisa jadi bumerang!

Masalah Fatal Metode Big-M

Mengapa Metode Big-M bisa jadi penghambat, terutama jika diselesaikan oleh komputer?

• Akurasi Menurun: Karena komputer memiliki batasan angka yang bisa diproses, memasukkan nilai M yang jauh lebih besar dari koefisien ongkos lain dapat mengurangi ketepatan perhitungan.

• Jawaban Salah/Tidak Layak: Dalam kasus terburuk, perhitungan Big-M dapat menghasilkan jawaban yang secara numerik salah atau tidak fisibel (tidak layak).

Untuk mengatasi masalah numerik ini, lahirlah Metode Simpleks Dua Fase!

Dua Fase Penting Metode Simpleks Dua Fase

Metode ini membagi proses penyelesaian Program Linier menjadi dua fase terpisah. Setiap fase menggunakan algoritma simpleks, namun dengan fungsi tujuan yang berbeda.

Fitur	Fase 1	Fase 2
Tujuan Utama	Menentukan Kelayakan (Feasibility) solusi masalah asli.	Mencari Penyelesaian Optimal (Optimality) masalah asli.
Fungsi Tujuan	Fungsi tujuan buatan (f̅) yang HANYA melibatkan variabel semu.	Fungsi tujuan dikembalikan ke cⱼ masalah asli.

Fase 1: Menguji Kelayakan

Tujuan di fase ini adalah memastikan apakah jumlah dari semua variabel semu (Σa) dapat mencapai nilai nol. Jika Σa = 0, berarti solusi layak ditemukan. Berikut ini model simpleks fase 1:

Untuk fungsi tujuan buatan (f̅):

• Meminimumkan f̅ = Σaᵢ (Koefisien variabel semu: +1)

• Memaksimumkan f̅ = –Σaᵢ (Koefisien variabel semu: –1)

• Koefisien peubah asli dan pengetat: 0

Setelah fase 1 selesai dihitung (tabel optimal simpleks fase 1 tercapai), hanya ada tiga skenario yang mungkin terjadi:

Kondisi Akhir	Keterangan	Tindak Lanjut
Kondisi (1): f̅ = 0 dan SEMUA variabel semu non-basis.	Solusi Layak Ditemukan. Basis awal optimal sudah siap.	Lanjut ke Fase 2.
Kondisi (2): f̅ = 0 tetapi ADA variabel semu di basis (dengan nilai nol).	Solusi Layak Ditemukan. Mengindikasikan adanya kendala berlebih (redundant constraint) pada soal asli.	Lanjut ke Fase 2.
Kondisi (3): f̅ ≠ 0 (misal f̅ > 0 untuk min, atau f̅ < 0 untuk maks).	Soal ASLI TIDAK LAYAK (Infeasible). Variabel semu masih bernilai positif.	PROSES BERHENTI.

Fase 2: Mencari Nilai Terbaik

Jika fase 1 berhasil dengan Kondisi (1) atau (2), kita melanjutkan ke fase 2 dengan basis optimal dari fase 1. Berikut ini langkah-langkah kunci di fase 2:

1. Ganti Fungsi Tujuan: Koefisien ongkos cⱼ di tabel dikembalikan menggunakan nilai ongkos dari masalah asli.

2. Hapus Variabel Semu: Semua kolom variabel semu a dihapus dari tabel.

3. Penanganan Kendala Berlebih (Jika Kondisi 2): Variabel semu yang berada di basis dengan nilai nol (akibat kendala berlebih) dihilangkan beserta baris kendala yang bersesuaian (baris tersebut akan memiliki nilai nol untuk kolom peubah bukan semu).

4. Lanjutkan Simpleks: Proses dilanjutkan seperti biasa menggunakan algoritma simpleks hingga solusi optimal (p.o.) ditemukan.

Dengan Metode Simpleks Dua Fase, kita berhasil memisahkan proses pengujian kelayakan dari proses optimasi, sehingga perhitungan numerik menjadi lebih stabil dan akurat!

Contoh Soal

Cari x₁, x₂, x₃ tak negatif yang meminimumkan f = 12x₁ + 5x₂ dan memenuhi kendala:

2x₁ + x₂ ≥ 40

2x₁ + 3x₂ ≥ 90

Solusi:

Ubah kendala ke bentuk kanonik fase 1:

2x₁ + x₂ – s₁ + a₁ = 40

2x₁ + 3x₂ – s₂ + a₂ = 90

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

Ubah fungsi tujuan ke bentuk kanonik fase 1:

f = 0x₁ + 0x₂ + 0s₁ + 0s₂ + a₁ + a₂

Susun tablo awal fase 1:

cⱼ		0	0	0	0	1	1
c̅ᵢ	x̅ᵢ/xⱼ	x₁	x₂	s₁	s₂	a₁	a₂	bᵢ	Rᵢ
1	a₁	2	1	-1	0	1	0	40	20
1	a₂	2	3	0	-1	0	1	90	45
	zⱼ	4	4	-1	-1	1	1	130
	zⱼ – cⱼ	4	4	-1	-1	0	0

Kita bisa memilih kolom x₁ atau x₂, misalnya Minfor memilih kolom x₁ sebagai kolom pivot. Diperoleh Rᵢ terkecil adalah baris 1, oleh karena itu ganti a₁ dengan x₁.

Berikut ini tablo kedua:

cⱼ		0	0	0	0	1	1
c̅ᵢ	x̅ᵢ/xⱼ	x₁	x₂	s₁	s₂	a₁	a₂	bᵢ	Rᵢ
0	x₁	1	½	-½	0	½	0	20	40
1	a₂	0	2	1	-1	-1	1	50	25
	zⱼ	0	2	1	-1	-1	1	50
	zⱼ – cⱼ	0	2	1	-1	-2	0

Karena kolom x₂ memiliki zⱼ – cⱼ paling positif, pilih sebagai kolom pivot. Diperoleh Rᵢ terkecil adalah baris 2, oleh karena itu ganti a₂ dengan x₂.

Berikut ini tablo ketiga:

cⱼ		0	0	0	0	1	1
c̅ᵢ	x̅ᵢ/xⱼ	x₁	x₂	s₁	s₂	a₁	a₂	bᵢ	Rᵢ
0	x₁	1	0	-¾	¼	¾	-¼	15/2	-
0	x₂	0	1	½	-½	-½	½	25	25
	zⱼ	0	0	0	0	0	0	0
	zⱼ – cⱼ	0	0	0	0	-1	-1

Sampai disini sudah tidak ada lagi zⱼ – cⱼ positif dan tidak ada lagi variabel semu sebagai basis, ini berarti fase 1 selesai. Hapus kolom variabel semu dan lanjut ke fase 2.

Ubah fungsi tujuan ke bentuk kanonik fase 2:

f = 12x₁ + 5x₂ + 0s₁ + 0s₂

Berikut ini tablo awal fase 2:

cⱼ		12	5	0	0
c̅ᵢ	x̅ᵢ/xⱼ	x₁	x₂	s₁	s₂	bᵢ	Rᵢ
12	x₁	1	0	-¾	¼	15/2	30
5	x₂	0	1	½	-½	25	-
	zⱼ	12	5	-13/2	0,5	215
	zⱼ – cⱼ	0	0	-13/2	0,5

Karena kolom s₂ memiliki zⱼ – cⱼ paling positif, pilih sebagai kolom pivot. Diperoleh Rᵢ terkecil adalah baris 1, oleh karena itu ganti x₁ dengan s₂.

cⱼ		12	5	0	0
c̅ᵢ	x̅ᵢ/xⱼ	x₁	x₂	s₁	s₂	bᵢ	Rᵢ
0	s₂	4	0	-3	1	30
5	x₂	2	1	-1	0	40
	zⱼ	10	5	-5	0	200
	zⱼ – cⱼ	-2	0	-5	0

Tablo terakhir ini sudah selesai karena tidak ada lagi zⱼ – cⱼ positif.

Penyelesaian layak (Pl) adalah (x₁, x₂, s₁, s₂) = (0, 40, 0, 30)

Penyelesaian layak basis (Plb) adalah (x₂, s₂) = (40, 30)

Penyelesaian optimum (Po) adalah (x₁, x₂) = (0, 40)

Nilai maksimum fungsi tujuan adalah fmax = 200.