1. **State the problem:** We want to derive the dual problem of the given primal linear program: $$\min \{-x_1 + 2x_2 - 38x_3\}$$ subject to $$3x_1 - 4x_2 + 5x_3 \leq -6$$ $$-7x_1 + 8x_2 - 9x_3 \geq 10$$ $$11x_1 - 12x_2 + 13x_3 = 14$$ with variable constraints: $$x_1 \geq 0, \quad x_2 \leq 0, \quad x_3 \text{ free}$$ 2. **Recall the dual formulation rules:** - Each primal constraint corresponds to a dual variable. - Inequality constraints \(\leq\) correspond to dual variables \(\geq 0\). - Inequality constraints \(\geq\) correspond to dual variables \(\leq 0\). - Equality constraints correspond to free dual variables. - Primal variables with sign restrictions affect the dual constraints: - If primal variable \(x_j \geq 0\), dual constraint \(\leq\). - If primal variable \(x_j \leq 0\), dual constraint \(\geq\). - If primal variable free, dual constraint equality. 3. **Assign dual variables:** Let dual variables be \(y_1, y_2, y_3\) corresponding to the three constraints in order. - Since first constraint is \(\leq\), \(y_1 \geq 0\). - Second constraint is \(\geq\), so \(y_2 \leq 0\). - Third constraint is equality, so \(y_3\) is free. 4. **Form the dual objective:** Primal RHS vector is \([-6, 10, 14]^T\), so dual objective is: $$\max \{-6y_1 + 10y_2 + 14y_3\}$$ 5. **Form dual constraints:** The coefficient matrix \(A\) is: $$\begin{bmatrix}3 & -4 & 5 \\ -7 & 8 & -9 \\ 11 & -12 & 13\end{bmatrix}$$ Dual constraints come from: $$A^T y \leq c$$ where \(c = [-1, 2, -38]^T\) is the primal objective coefficients. But the inequalities depend on primal variable signs: - For \(x_1 \geq 0\), dual constraint is \(\leq\): $$3y_1 -7y_2 + 11y_3 \leq -1$$ - For \(x_2 \leq 0\), dual constraint is \(\geq\): $$-4y_1 + 8y_2 - 12y_3 \geq 2$$ - For \(x_3\) free, dual constraint is equality: $$5y_1 - 9y_2 + 13y_3 = -38$$ 6. **Summary of dual problem:** $$\max \{-6y_1 + 10y_2 + 14y_3\}$$ subject to $$3y_1 -7y_2 + 11y_3 \leq -1$$ $$-4y_1 + 8y_2 - 12y_3 \geq 2$$ $$5y_1 - 9y_2 + 13y_3 = -38$$ with $$y_1 \geq 0, \quad y_2 \leq 0, \quad y_3 \text{ free}$$ 7. **Answer to multiple choice:** The dual has 3 variables \(y_1, y_2, y_3\) with: - \(y_1 \geq 0\) (non-negative) - \(y_2 \leq 0\) (non-positive, but not non-negative) - \(y_3\) free So the dual has 3 variables, 1 of them free. **Final answer:** The dual problem has 3 variables, 1 of them is free.