Question

Let $(x_1^* = 1, \ x_2^* = 0, \ x_3^* = 2)$ be an optimal solution of the linear programming problem \[ \text{Minimize } \quad x_1 + 5x_2 + 2x_3 \] subject to \[ \begin{cases} x_1 - x_2 \le 1, \\ x_1 + x_2 + x_3 \ge 3, \\ x_1, x_2, x_3 \ge 0. \end{cases} \] If $(\lambda_1^*, \lambda_2^*)$ is an optimal solution of its dual, then

• A. $2\lambda_1^* = 3\lambda_2^*$
• B. $2\lambda_1^* = \lambda_2^*$
• C. $\lambda_1^* = 2\lambda_2^*$
• D. $\lambda_1^* = \lambda_2^*$

Hint:

Complementary slackness is the key to connecting primal and dual optimal solutions — binding constraints correspond to nonzero dual variables.

Answer 1

The Correct Option is B

Step 1: Write the primal in standard form.
Minimize: $Z = x_1 + 5x_2 + 2x_3$ \[ \text{subject to } \begin{cases} x_1 - x_2 \le 1, \\ - x_1 - x_2 - x_3 \le -3, \\ x_i \ge 0. \end{cases} \] This gives one “$\le$” and one “$\ge$” constraint, so the dual will have mixed sign restrictions.
Step 2: Form the dual.
For primal minimization, dual is maximization. Let $\lambda_1 \ge 0$ for the first constraint and $\lambda_2 \le 0$ for the second (since it was “$\ge$”). Dual: \[ \text{Maximize } \quad W = \lambda_1 - 3\lambda_2 \] subject to \[ \begin{cases} \lambda_1 - \lambda_2 \le 1, \\ -\lambda_1 - \lambda_2 \le 5, \\ -\lambda_2 \le 2. \end{cases} \]
Step 3: Use complementary slackness.
Active constraints in the primal correspond to nonzero dual variables. Given $x_1^* = 1, x_2^* = 0, x_3^* = 2$, check primal constraints: \[ x_1 - x_2 = 1 \text{ (binding)}, \quad x_1 + x_2 + x_3 = 3 \text{ (binding)}. \] Hence, both constraints are active, so $\lambda_1^*, \lambda_2^*$ are nonzero.
Step 4: Apply stationarity (dual equality conditions).
For each variable $x_i$: \[ \begin{cases} \lambda_1 - \lambda_2 = 1, & \text{(from coefficient of } x_1) \\ -\lambda_1 - \lambda_2 = 5, & \text{(from coefficient of } x_2) \\ -\lambda_2 = 2. & \text{(from coefficient of } x_3) \end{cases} \] From the last equation, $\lambda_2 = -2$. Substitute in the first: \[ \lambda_1 - (-2) = 1 \Rightarrow \lambda_1 = -1. \] Check the ratio: \[ 2\lambda_1^* = 2(-1) = -2 = \lambda_2^*. \] Hence, $2\lambda_1^* = \lambda_2^*$.
Step 5: Conclusion.
The correct relationship between dual variables is $2\lambda_1^* = \lambda_2^*$.