Metode Simpleks untuk Program Linear

Apakah Sixtyfourians pernah menemui masalah optimasi dengan banyak variabel yang tidak bisa diselesaikan hanya dengan metode grafik? Metode Simpleks adalah jawabannya! Teknik ini menjadi tulang punggung dalam ilmu Riset Operasi untuk menyelesaikan masalah Program Linear (PL) dengan tiga variabel atau lebih. Berikut adalah panduan lengkap, mulai dari persiapan model hingga algoritma penyelesaiannya.

1. Konsep Dasar & Persiapan Model (Bentuk Kanonik)

Metode Simpleks beroperasi berdasarkan konsep bahwa solusi optimal (maksimum atau minimum) dari suatu PL selalu berada pada titik ekstrem (sudut) dari daerah solusi yang layak.

A. Model Standar Simpleks (Bentuk Kanonik)

Sebelum memulai perhitungan, model PL harus diubah ke dalam Bentuk Kanonik (atau Bentuk Standar Simpleks) agar siap diolah. Bentuk kanonik harus memenuhi 4 syarat utama:

1. Semua batasan harus berupa PERSAMAAN.

2. Semua variabel harus NON-NEGATIF (xⱼ ≥ 0).

3. Nilai Kanan (NK) batasan harus NON-NEGATIF (bᵢ ≥ 0).

4. Mengoptimalkan Fungsi Tujuan (Maksimisasi atau Minimisasi).

B. Mengubah Bentuk Batasan dan Variabel

Model PL seringkali tidak langsung dalam bentuk kanonik, sehingga diperlukan beberapa penyesuaian:

• Untuk tanda "≤", tambahkan variabel slack. Sebagai contoh 2x₁ ≤ 8 menjadi 2x₁ + s₁ = 8.

• Untuk tanda "≥", kurangkan variabel slack, diikuti penambahan variabel semu. Sebagai contoh 2x₁ ≥ 8 menjadi 2x₁ – s₁ + a₁ = 8, dengan s₁ variabel slack dan a₁ variabel semu.

• Untuk nilai kanan negatif, kalikan seluruh batasan tersebut dengan –1.

• Kasus minimasi ekivalen dengan memaksimumkan negatif dari fungsi tujuan tersebut. Contoh: Minimalkan f = 3a – 5b ekivalen dengan  maksimalkan g = –3a + 5b.

2. Algoritma dan Langkah-Langkah Simpleks

Setelah model diubah ke Bentuk Kanonik, proses dilanjutkan dengan Tablo Simpleks melalui serangkaian iterasi. Bentuk awal tablo simpleks adalah:

	cⱼ	c₁	c₂	⋯	cₙ
c̅ᵢ	x̅ᵢ/xⱼ	x₁	x₂	⋯	xₙ	bᵢ	Rᵢ
c̅₁	x̅₁	a₁₁	a₁₂	⋯	a₁ₙ	b₁	R₁
c̅₂	x̅₂	a₂₁	a₂₂	⋯	a₂ₙ	b₂	R₂
⋮	⋮	⋮	⋮	⋱	⋮	⋮	⋮
c̅ₘ	x̅ₘ	aₘ₁	aₘ₂	⋯	aₘₙ	bₘ	Rₘ
	zⱼ	z₁	z₂	⋯	zₙ	Z
	zⱼ – cⱼ	z₁ – c₁	z₂ – c₂	⋯	zₙ – cₙ

Nilai zⱼ diperoleh dengan rumus zⱼ = a₁ⱼc̅₁ + a₂ⱼc̅₂ + ... + aₘⱼc̅ₘ dan nilai Rᵢ = bᵢ/aᵢⱼ dengan aᵢⱼ dipilih dari kolom pivot.

1. Penentuan Penyelesaian Basis Awal (PBA)

• Variabel Basis (VB): Variabel yang memiliki nilai (biasanya variabel slack / semu di iterasi awal).

• Variabel Non-Basis (VNB): Variabel yang disamakan dengan nol. Banyak VNB adalah n – m, di mana n adalah banyak variabel dan m adalah banyak batasan.

• Tujuan: Mendapatkan Penyelesaian Basis Fisibel Awal (PBFA), yaitu penyelesaian basis yang memenuhi semua batasan (tidak ada variabel yang bernilai negatif).

2. Uji Keoptimanan (Kriteria Simpleks)

Uji ini dilakukan pada Baris Fungsi Tujuan (Z) di Tablo Simpleks.

• Kondisi optimum untuk maksimasi adalah semua koefisien zⱼ – cⱼ non-negatif.

Jika belum optimum, pilih koefisien yang paling negatif sebagai ev (entering variable) dan kolomnya menjadi kolom pivot.

• Kondisi optimum untuk minimasi adalah semua koefisien zⱼ – cⱼ non-positif.

Jika belum optimum, pilih koefisien yang paling positif sebagai ev (entering variable) dan kolomnya menjadi kolom pivot.

3. Penentuan Variabel Keluar (lv)

Jika belum optimum, tentukan Leaving Variable (lv) untuk menjaga solusi tetap layak.

• Hitung rasio untuk setiap baris batasan dengan Rᵢ = bᵢ/aᵢⱼ dan aᵢⱼ dipilih dari kolom pivot.

• Kriteria Pemilihan: lv adalah VB yang berada pada baris dengan Nilai Rasio Positif Terkecil.

• Pengecualian: Jangan hitung rasio jika elemen di Kolom ev bernilai 0 atau negatif.

• Baris Pivot: Baris yang memuat lv disebut Baris Pivot.

• Elemen Pivot: Angka yang berada di irisan Kolom ev dan Baris lv disebut Elemen Pivot.

4. Perbaikan Tabel (Pivotasi)

Lakukan operasi baris elementer (OBE) untuk mempersiapkan tabel iterasi berikutnya:

• Baris pivot baru: buat elemen pivot menjadi bernilai 1.

• Baris lain baru: buat elemen lain di kolom ev menjadi bernilai 0.

5. Ulangi

Setelah perbaikan tabel, kembali ke Uji Keoptimalan, dan ulangi proses hingga kondisi optimum tercapai.

3. Catatan

Metode simpleks biasa ini hanya bisa digunakan untuk kasus yang semua kendalanya bertanda "≤". Adapun untuk kasus yang ada kendala bertanda "=" atau "≥" tidak bisa menggunakan metode ini, melainkan diperlukan metode Big M atau Dua Fase, yang melibatkan variabel semu.

Contoh Soal

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

2x₁ + x₂ + 2x₃ ≤ 10

–2x₁ + 2x₂ + x₃ ≤ 5

x₁ – 5x₂ + x₃ ≤ 15

x₁, x₂, x₃ ≥ 0

Solusi:

Ubah kendala ke bentuk kanonik:

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

–2x₁ + 2x₂ + x₃ + s₂ = 5

x₁ – 5x₂ + x₃ + s₃ = 15

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

Ubah fungsi tujuan ke bentuk kanonik:

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

Susun tablo awal:

	cⱼ	1	5	8	0	0	0
c̅ᵢ	x̅ᵢ/xⱼ	x₁	x₂	x₃	s₁	s₂	s₃	bᵢ	Rᵢ
0	s₁	2	1	2	1	0	0	10	5
0	s₂	–2	2	1	0	1	0	5	5
0	s₃	1	–5	1	0	0	1	15	15
	zⱼ	0	0	0	0	0	0	0
	zⱼ – cⱼ	–1	–5	–8	0	0	0

Kolom x₃ memiliki zⱼ – cⱼ paling negatif, yaitu –8, sehingga 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;    5/1 = 5;    15/1 = 15.

Baris 1 dan baris 2 keduanya memiliki Rᵢ yang sama-sama terkecil, yaitu 5. Kita boleh memilih baris 1 atau baris 2, disini Minfor akan mencoba memilih baris 2.

Ganti s₂ dengan x₃, karena sel yang bertepatan dengan kolom x₃ adalah 1, baris ini tidak perlu diubah.

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

Berikut ini tablo kedua:

	cⱼ	1	5	8	0	0	0
c̅ᵢ	x̅ᵢ/xⱼ	x₁	x₂	x₃	s₁	s₂	s₃	bᵢ	Rᵢ
0	s₁	6	–3	0	1	–2	0	0	0
8	x₃	–2	2	1	0	1	0	5	-
0	s₃	3	–7	0	0	–1	1	10	10/3
	zⱼ	–16	16	8	0	8	0	40
	zⱼ – cⱼ	–17	11	0	0	8	0

Kolom x₁ memiliki zⱼ – cⱼ paling negatif, yaitu –17, sehingga dipilih sebagai kolom pivot.

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

0/6 = 0;    10/3 = 10/3. Adapun baris 2 dikecualikan karena sel yang bertepatan dengan kolom x₁ non-positif.

Baris 1 memiliki Rᵢ terkecil, yaitu 0. Oleh karena itu ganti s₁ dengan x₁.

Bagi baris 1 dengan 6 sehingga sel yang bertepatan dengan kolom x₁ menjadi 1 dan lakukan OBE untuk baris lainnya sehingga sel yang bertepatan dengan kolom x₁ bernilai 0.

Berikut ini tablo ketiga:

	cⱼ	1	5	8	0	0	0
c̅ᵢ	x̅ᵢ/xⱼ	x₁	x₂	x₃	s₁	s₂	s₃	bᵢ	Rᵢ
1	x₁	1	–½	0	⅙	–⅓	0	0
8	x₃	0	1	1	⅓	⅓	0	5
0	s₃	0	–11/2	0	–½	0	1	10
	zⱼ	1	15/2	8	17/6	7/3	0	40
	zⱼ – cⱼ	0	5/2	0	17/6	7/3	0

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

Penyelesaian layak (Pl) adalah (x₁, x₂, x₃, s₁, s₂, s₃) = (0, 0, 5, 0, 0, 10)

Penyelesaian layak basis (Plb) adalah (x₁, x₃, s₃) = (0, 5, 10)

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

Nilai maksimum fungsi tujuan adalah fmax = 40.