1. Misalkan kita pilih soal (a): Maksimumkan fungsi tujuan $$f = 5x + 4y + 6z$$ terhadap kendala: $$x + y + z \leq 25$$ $$2x + y + 3z \leq 51$$ $$x, y, z \geq 0$$ 2. Menentukan masalah Dual dari primal ini. Primal adalah masalah maksimasi dengan kendala \( \leq \), variabel non-negatif. Dual akan menjadi masalah minimasi dengan variabel dual \(u_1, u_2 \geq 0\) untuk tiap kendala: Dual: Minimalkan $$g = 25u_1 + 51u_2$$ Dengan kendala: $$u_1 + 2u_2 \geq 5$$ $$u_1 + u_2 \geq 4$$ $$u_1 + 3u_2 \geq 6$$ $$u_1, u_2 \geq 0$$ 3. Menyelesaikan masalah primal dengan metode simpleks. Karena masalah maksimasi dengan dua kendala dan tiga variabel, kita cek titik potong kendala: Kendala 1: $$x + y + z = 25$$ Kendala 2: $$2x + y + 3z = 51$$ Variabel non-negatif. Coba substitusi beberapa titik: - Jika \(z=0\): \(x + y = 25\) dan \(2x + y = 51\) Kurangi kedua persamaan: $$2x + y - (x + y) = 51 - 25$$ $$x = 26$$, yang tidak mungkin karena \(x + y = 25\) membutuhkan \(x \leq 25\). Jadi \(z=0\) tidak memungkinkan. - Jika \(y=0\): $$x + z = 25$$ $$2x + 3z = 51$$ Substitusi \(z = 25 - x\): $$2x + 3(25 - x) = 51$$ $$2x + 75 - 3x = 51$$ $$-x = -24$$ $$x=24$$, maka \(z = 1\). Evaluasi fungsi tujuan: $$f = 5(24) + 4(0) + 6(1) = 120 + 6 = 126$$ - Jika \(x=0\): $$y + z = 25$$ $$y + 3z = 51$$ Kurangi: $$y + 3z - (y + z) = 51 - 25$$ $$2z = 26$$ $$z = 13$$, maka \(y = 12\). Fungsi tujuan: $$f = 5(0) + 4(12) + 6(13) = 48 + 78 = 126$$ - Jika \(z=5\): $$x + y = 20$$ $$2x + y + 15 = 51 => 2x + y = 36$$ Kurangi kedua: $$2x + y - (x + y) = 36 - 20$$ $$x = 16$$, maka \(y = 4\). Fungsi tujuan: $$f = 5(16) + 4(4) + 6(5) = 80 + 16 + 30 = 126$$ Semua titik ini menghasilkan nilai fungsi tujuan maksimum 126. 4. Jadi solusi optimal primal adalah di titik \((x,y,z)=(24,0,1)\) atau \((0,12,13)\) atau \((16,4,5)\) dengan nilai maksimum: $$f_{max} = 126$$ 5. Menggunakan dualitas kuat, nilai minimum fungsi dual juga 126. Dual: Cari solusi memenuhi: $$u_1 + 2u_2 \geq 5$$ $$u_1 + u_2 \geq 4$$ $$u_1 + 3u_2 \geq 6$$ $$u_1, u_2 \geq 0$$ Coba titik potong: - Dari dua kendala pertama, $$u_1 + 2u_2 = 5$$ $$u_1 + u_2 = 4$$ Kurangi: $$u_2 = 1$$ $$u_1 = 4 - 1 = 3$$ Periksa kendala ketiga: $$3 + 3(1) = 6 \, \text{memenuhi}$$ Hitung fungsi tujuan dual: $$g = 25(3) + 51(1) = 75 + 51 = 126$$ 6. Kesimpulan: - Optimal Primal: \((x,y,z)=(24,0,1)\) dengan $$f_{max} = 126$$ - Optimal Dual: \((u_1,u_2)=(3,1)\) dengan $$g_{min} = 126$$ Nilai optimum primal dan dual sama, sesuai prinsip dualitas pada pengerjaan PL.