Dualitas dan Metode Membaca Tabel Optimal

Halo Sixtyfourians! Pernahkah ada yang merasa buntu saat mengerjakan masalah Program Linear yang variabelnya terlalu banyak? Atau mungkin penasaran, ada nggak sih cara lain untuk melihat sebuah masalah optimasi dari sudut pandang berbeda? Jawabannya ada di Dualitas.

Dalam dunia Riset Operasi (Operations Research), setiap masalah punya "kembaran" yang disebut Dual. Memahami dualitas bukan hanya soal matematika, tapi soal melihat hubungan erat antara sumber daya dan keuntungan. Yuk, kita bedah langkah demi langkah!

1. Apa Itu Dualitas?

Secara sederhana, Dualitas adalah masalah program linear yang didefinisikan secara langsung dan sistematik dari model aslinya (yang kita sebut sebagai model Primal). Poin penting yang perlu diingat:

• Bentuk dualitas sangat bergantung pada jenis batasan, tanda variabel, dan fungsi tujuan dari masalah Primal-nya.

• Syarat Mutlak: Sebelum diubah ke bentuk Dual, masalah Primal harus sudah dalam Bentuk Standar/Kanonik.

2. Langkah-Langkah Membentuk Dualitas

Bagaimana cara mengubah masalah Primal menjadi Dual? Jangan pusing dulu, kita bisa memecahnya menjadi mudah.

A. Ubah ke Bentuk Standar

Pastikan masalah Primal sudah rapi dalam bentuk standar atau kanonik. Artinya, semua pertidaksamaan sudah jelas dan siap diolah.

B. Tabel Primal-Dual & Transpose Matriks

Bayangkan Sixtyfourians memutar tabel masalahmu. Apa yang tadinya baris, menjadi kolom. Berikut aturan mainnya:

1. Variabel & Batasan

• Setiap kendala pada Primal menjadi sebuah variabel pada Dual.

• Setiap variabel pada Primal menjadi sebuah kendala pada Dual.

• Simpelnya: Jika Primal punya n variabel dan m kendala, maka Dual akan punya m variabel dan n kendala.

2. Koefisien (Nilai Angka)

• Koefisien variabel Primal menjadi koefisien pada batasan Dual.

• Koefisien fungsi tujuan Primal menjadi Nilai Kanan (RHS) pada Dual.

• Nilai Kanan (RHS) Primal menjadi Koefisien fungsi tujuan Dual.

C. Tentukan Arah Optimasi (Penting!)

Ini adalah bagian yang sering mengecoh. Perhatikan perubahan tandanya:

Masalah Primal	Masalah Dual	Tanda Batasan Dual
Memaksimumkan	Meminimumkan	≥
Meminimumkan	Memaksimumkan	≤

Intinya: Kalau Primal mencari untung maksimal (Max), maka Dual mencari biaya minimal (Min), dan sebaliknya.

3. Hubungan Spesial: Mencari Solusi Tanpa Menghitung Ulang

Salah satu keajaiban dualitas adalah kita tidak perlu menghitung ulang dari nol untuk mencari solusi Dual jika kita sudah menyelesaikan tabel Simplex masalah Primal.

Penyelesaian optimal dari masalah primal dapat dengan segera dicari dari tabel simplex optimal masalah dualnya, begitu juga sebaliknya.

4. Metode Membaca Tabel Optimal

Informasi solusi Dual tersembunyi di baris Z (baris fungsi tujuan) pada tabel optimal Primal, khususnya pada kolom Variabel Slack (S₁, S₂, ...). Rumus praktisnya:

Koefisien persamaan optimal Z dari variabel basis awal = Solusi Variabel Dual (y)

Contoh Soal

Diberikan masalah primal meminimumkan f = –6x₁ + 12x₂ + 6x₃ dengan kendala

x₁ + x₂ – x₃ ≤ 10

–x₁ + 3x₂ – 3x₃ ≥ 20

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

Untuk mengubahnya menjadi bentuk dual, sesuaikan kendalanya, karena meminimumkan balik tanda kendalanya yang "≤" menjadi "≥".

–x₁ – x₂ + x₃ ≥ –10

–x₁ + 3x₂ – 3x₃ ≥ 20

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

Bentuk dual dari masalah primal ini adalah memaksimumkan g = –10w₁ + 20w₂ – 5w₃ dengan kendala

–w₁ – w₂ – 5w₃ ≤ –6

–w₁ + 3w₂ + w₃ ≤ 12

w₁ – 3w₂ – 2w₃ ≤ 6

Sesuaikan agar ruas kanan tidak ada yang negatif, menjadi

w₁ + w₂ + 5w₃ ≥ 6

–w₁ + 3w₂ + w₃ ≤ 12

w₁ – 3w₂ – 2w₃ ≤ 6

Perhatikan bahwa bentuk kanonik masalah primal tersebut adalah:

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

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

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

f = –6x₁ + 12x₂ + 6x₃ + 0s₁ + 0s₂ + 0s₃ + aM

Tablo terakhir dari masalah primal ini adalah:

	cⱼ	–6	12	6	0	0	0	M
cᵢ	xᵢ/xⱼ	x₁	x₂	x₃	s₁	s₂	s₃	a	bᵢ
–6	x₁	1	0	0	¾	¼	0	–¼	5/2
12	x₂	0	1	–1	¼	–¼	0	¼	15/2
0	s₃	0	0	1	–7/2	–3/2	1	3/2	0
	zⱼ	–6	12	–12	–3/2	–9/2	0	9/2	75
	zⱼ–cⱼ	0	0	–18	–3/2	–9/2	0	9/2–M

Dari tablo terakhir masalah primal ini kita bisa melihat zⱼ–cⱼ untuk variabel slack, sehingga diperoleh solusi dualnya adalah:

(w₁, w₂, w₃) = (3/2, 9/2, 0)

g max = f min = 75.