Question

Consider a linear programming problem (𝑃) min 𝑧 = 4𝑥₁ + 6𝑥₂ + 6𝑥₃ subject to
𝑥₁+3𝑥₂≥3
𝑥₁+2𝑥₃ ≥5 
𝑥₁, 𝑥₂, 𝑥₃ ≥ 0 
If \(𝑥^∗ = (𝑥^∗_1 , 𝑥^∗_2 , 𝑥^∗_3 )\) is an optimal solution and 𝑧^∗ is an optimal value of (𝑃) and 𝑤^∗ =\((𝑤^∗_1 , 𝑤^∗_2 )\) is an optimal solution of the dual of (𝑃) then

• A. \(𝑥^∗_2 + 𝑥^∗_3 = 𝑤^∗_1 + 𝑤^∗_2\)
• B. \(𝑧^∗ = 4(𝑥^∗_1 + 𝑤^∗_2 )\)
• C. \(𝑧^∗ = 6(𝑤^∗_1 + 𝑥^∗_3 )\)
• D. \(𝑥^∗_1 + 𝑥^∗_3 = 𝑤^∗_1 + 𝑤^∗_2\)

Answer 1

The Correct Option is D

The given problem is a linear programming problem (P) with the objective to minimize \(z = 4x_1 + 6x_2 + 6x_3\) subject to the constraints:

• \(x_1 + 3x_2 \ge 3\)
• \(x_1 + 2x_3 \ge 5\)
• \(x_1, x_2, x_3 \ge 0\)

We are also given certain expressions involving the solutions of the primal and its dual, where \(x^*\) is the optimal solution and \(w^*\) is the optimal solution for the dual. The dual of a linear programming problem is formed by using the constraints of the primal as the coefficients in the objective function of the dual and vice versa.

Step-by-Step Solution

1. The primal constraints can be written as:
   • \(x_1 + 3x_2 \ge 3\)
   • \(x_1 + 2x_3 \ge 5\)
2. The corresponding dual problem will be:
   • Maximize: \(3w_1 + 5w_2\)
   • Subject to:
     • \(w_1 + w_2 \le 4\)
     • \(3w_1 \le 6\)
     • \(2w_2 \le 6\)
     • \(w_1, w_2 \ge 0\)
3. The complementary slackness conditions for the primal and dual are critical to relate primal and dual solutions. These conditions hold when a solution is optimal in both the primal and dual problems.
4. Given options need to be assessed on these grounds:
   • \(x^*_2 + x^*_3 = w^*_1 + w^*_2\) - No direct relation.
   • \(z^* = 4(x^*_1 + w^*_2)\) and \(z^* = 6(w^*_1 + x^*_3)\) - Do not directly align with primal-dual complementary conditions.
   • \(x^*_1 + x^*_3 = w^*_1 + w^*_2\) - This aligns with the complementary slackness conditions involving the sum of certain primal and dual variables equating.
5. Thus, the correct relation based on the dual formulation and complementary slackness is:
   • \(x^*_1 + x^*_3 = w^*_1 + w^*_2\)

Therefore, the correct option is \(x^*_1 + x^*_3 = w^*_1 + w^*_2\), which satisfies the complementary slackness condition associated with solving linear programming problems with their duals.