Dualitas: Metode Perkalian Matriks

Halo kembali, Sixtyfourians! Setelah sebelumnya kita belajar cara shortcut membaca solusi Dual lewat Metode Membaca Tabel Primal, sekarang kita akan masuk ke Metode Perkalian Matriks. Jangan khawatir, meski terlihat banyak rumus, konsepnya sebenarnya sangat logis. Metode ini sering disebut sebagai pendekatan aljabar matriks dalam Riset Operasi.

Metode Perkalian Matriks adalah metode yang paling sering digunakan dalam algoritma komputer. Metode ini menggunakan prinsip aljabar linear.

(Nilai Optimal Dual) = (Vektor Baris Koef Basis Optimal di Fungsi Asli) × (Matriks Invers pada Tabel Optimal)

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

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

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 mendapati Vektor Baris Koef Basis Optimal di Fungsi Asli adalah (–6, 12, 0); sedangkan matriks variabel slack adalah:

s₁	s₂	s₃
¾	¼	0
¼	–¼	0
–7/2	–3/2	1

Kalikan vektor baris dengan matriks tersebut:

solusi dualnya adalah (w₁, w₂, w₃) = (3/2, 9/2, 0).