UGC NET CSE | October 2022 | Part 1 | Question:: 13

Question

Consider the primal problem :
Maximize $z=5 x_{1}+12 x_{2}+4 x_{3}$
Subject to \[
\begin{array}{l}
x_{1}+2 x_{2}+x_{3}=10\\
2 x_{1}-x_{2}+3 x_{3}=8 \\
x_{1}, x_{2}, x_{3} \geq 0
\end{array}
\]
its dual problem is
Minimize $w=10 y_{1}+8 y_{2}$
Subject to \[
\begin{array}{l}
y_{1}+2 y_{2} \geq 5\\
2 y_{1}-y_{2} \geq 12 \\
y_{1}+3 y_{2} \geq 4
\end{array}
\]
Which of the following is correct?

• A. $y_{1} \geq 0, y_{2}$ unrestricted
• B. $y_{1} \geq 0, y_{2} \geq 0$
• C. $y_{1}$ is unrestricted, $y_{2} \geq 0$
• D. $y_{1}$ is unrestricted. $y_{2}$ restricted

Answer 1

• Write the primal problem in standard form: Maximize the objective function subject to a set of constraints. 

• Create the dual problem by converting the primal constraints into dual variables and the primal objective function into the dual objective function. The constraints in the primal problem become the objective function in the dual problem, and the objective function in the primal problem becomes the constraints in the dual problem.

• Replace each inequality constraint in the primal problem with an equality constraint, and each equality constraint with an inequality constraint.

• Change the direction of the inequality constraints in the dual problem. If the primal constraint was a less-than-or-equal-to constraint, the dual constraint should be a greater-than-or-equal- to constraint, and vice versa.

• Replace the primal variables with the dual variables, and vice versa.

• Solve the dual problem to obtain the optimal dual variables, and then use these variables to obtain the optimal primal variables. Therefore, y1 ≥ 0, y2 ≥ 0