GATE 2020 MA – Question 58
For α∈R, (3,0,0,β) is optimal for minimizing $x_1+x_2+x_3-\alpha x_4$, subject to $2x_1-x_2+x_3=6$, $-x_1+x_2+x_4=3$, all variables nonnegative. Find the maximum of β − α.
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 7 to 7
Explanation
Feasibility gives β = 6. Use the basic variables x₁,x₄. For a minimization optimum, dual equalities give $2y_1-y_2=1$ and $y_2=-\alpha$, so $y_1=(1-\alpha)/2$. The nonbasic reduced costs are $r_2=(3+\alpha)/2$ and $r_3=(1+\alpha)/2$. Both must be nonnegative, requiring α ≥ −1. Thus β − α = 6 − α is maximized at α = −1, with value 7.