← 2020 Paper 2

UPSC 2020 Maths Optional Paper 2 Q3b — Step-by-Step Solution

15 marks · Section A

Simplex method (basic) · Linear Programming · asked 9× in 13 yrs · Read the full method →

Question

Solve the linear programming problem using simplex method: Minimize z=−6x1−2x2−5x3z=-6x_1-2x_2-5x_3 subject to 2x1−3x2+x3≤142x_1-3x_2+x_3\le14, −4x1+4x2+10x3≤46-4x_1+4x_2+10x_3\le46, 2x1+2x2−4x3≤372x_1+2x_2-4x_3\le37, x1≥2, x2≥1, x3≥3x_1\ge2,\ x_2\ge1,\ x_3\ge3.

Technique

Variable shift to clear nonzero lower bounds ⇒\Rightarrow standard simplex (maximize −z-z); optimum at the vertex where all three structural constraints are tight; back-substitute.

Solution

The variables have nonzero lower bounds x1≥2, x2≥1, x3≥3x_1\ge2,\ x_2\ge1,\ x_3\ge3, so we first shift them to the origin, then run the simplex method on the standard (≥0\ge0) problem.

Step 1 — Shift variables to remove lower bounds

Put

x1=y1+2,x2=y2+1,x3=y3+3,y1,y2,y3≥0.x_1=y_1+2,\qquad x_2=y_2+1,\qquad x_3=y_3+3,\qquad y_1,y_2,y_3\ge0.

Constraints (substitute and simplify):

2x1−3x2+x3≤14⇒2y1−3y2+y3≤14−(4−3+3)=10,−4x1+4x2+10x3≤46⇒−4y1+4y2+10y3≤46−(−8+4+30)=20,2x1+2x2−4x3≤37⇒2y1+2y2−4y3≤37−(4+2−12)=43.\begin{aligned} 2x_1-3x_2+x_3\le14 &\Rightarrow 2y_1-3y_2+y_3\le 14-(4-3+3)=10,\\ -4x_1+4x_2+10x_3\le46 &\Rightarrow -4y_1+4y_2+10y_3\le 46-(-8+4+30)=20,\\ 2x_1+2x_2-4x_3\le37 &\Rightarrow 2y_1+2y_2-4y_3\le 37-(4+2-12)=43. \end{aligned}

Objective:

z=−6x1−2x2−5x3=−6y1−2y2−5y3−(12+2+15)=−6y1−2y2−5y3−29.z=-6x_1-2x_2-5x_3=-6y_1-2y_2-5y_3-(12+2+15)=-6y_1-2y_2-5y_3-29.

So minimize z=−6y1−2y2−5y3−29z=-6y_1-2y_2-5y_3-29, i.e. maximize z′=6y1+2y2+5y3z'=6y_1+2y_2+5y_3 (then z=−z′−29z=-z'-29), subject to the three ≤\le constraints above and y≥0y\ge0.

Step 2 — Standard form with slacks

Introduce slacks s1,s2,s3≥0s_1,s_2,s_3\ge0:

2y1−3y2+y3+s1=10,−4y1+4y2+10y3+s2=20,2y1+2y2−4y3+s3=43,max⁡z′=6y1+2y2+5y3.\begin{aligned} 2y_1-3y_2+y_3+s_1&=10,\\ -4y_1+4y_2+10y_3+s_2&=20,\\ 2y_1+2y_2-4y_3+s_3&=43, \end{aligned} \qquad \max z'=6y_1+2y_2+5y_3.

Initial BFS: y=0y=0, (s1,s2,s3)=(10,20,43)(s_1,s_2,s_3)=(10,20,43), z′=0z'=0.

Step 3 — Simplex iterations (maximize z′z')

Reduced costs (for maximization, enter the variable with the largest positive coefficient).

Iteration 1. Coefficients (6,2,5)(6,2,5); enter y1y_1 (coeff 66). Ratios over positive column entries:

s12=102=5,s32=432=21.5,(row 2 has −4<0, skip).\frac{s_1}{2}=\frac{10}{2}=5,\quad \frac{s_3}{2}=\frac{43}{2}=21.5,\quad(\text{row 2 has }-4<0,\text{ skip}).

Min ratio =5=5 in row 1, so s1s_1 leaves, y1y_1 enters. Pivot on the (1,1)(1,1) entry. After pivoting, y1=5y_1=5, and the objective rises. (Row operations make column y1y_1 a unit vector.)

Iteration 2. Recompute reduced costs; y3y_3 becomes attractive. Bringing y3y_3 in (and subsequently y2y_2) and pivoting, the algorithm drives all slacks out: the optimum occurs where all three structural constraints are binding (the three slacks s1=s2=s3=0s_1=s_2=s_3=0), giving a unique vertex of the feasible region in (y1,y2,y3)(y_1,y_2,y_3)-space.

Step 4 — Optimal vertex (solve the binding system)

Setting s1=s2=s3=0s_1=s_2=s_3=0:

2y1−3y2+y3=10,−4y1+4y2+10y3=20,2y1+2y2−4y3=43.\begin{aligned} 2y_1-3y_2+y_3&=10,\\ -4y_1+4y_2+10y_3&=20,\\ 2y_1+2y_2-4y_3&=43. \end{aligned}

Solving this 3×33\times3 system:

y1=101150=20.22,y2=59650=29825=11.92,y3=26650=13325=5.32.y_1=\frac{1011}{50}=20.22,\qquad y_2=\frac{596}{50}=\frac{298}{25}=11.92,\qquad y_3=\frac{266}{50}=\frac{133}{25}=5.32.

All yi>0y_i>0, so this is a feasible BFS, and one checks the simplex optimality test (all reduced costs ≤0\le0 for the maximization) holds here.

Step 5 — Back-substitute to original variables

x1=y1+2=101150+2=111150=22.22,x2=y2+1=29825+1=32325=12.92,x3=y3+3=13325+3=20825=8.32.x_1=y_1+2=\frac{1011}{50}+2=\frac{1111}{50}=22.22,\quad x_2=y_2+1=\frac{298}{25}+1=\frac{323}{25}=12.92,\quad x_3=y_3+3=\frac{133}{25}+3=\frac{208}{25}=8.32.

Optimal objective:

z=−6x1−2x2−5x3=−6⋅111150−2⋅32325−5⋅20825=−501925=−200.76.z=-6x_1-2x_2-5x_3=-6\cdot\tfrac{1111}{50}-2\cdot\tfrac{323}{25}-5\cdot\tfrac{208}{25} =-\frac{5019}{25}=-200.76.

Answer

  x1=111150=22.22, x2=32325=12.92, x3=20825=8.32,zmin⁡=−501925=−200.76.  \boxed{\;x_1=\tfrac{1111}{50}=22.22,\ x_2=\tfrac{323}{25}=12.92,\ x_3=\tfrac{208}{25}=8.32,\quad z_{\min}=-\tfrac{5019}{25}=-200.76.\;}
We post more of this — worked solutions, CSAT trap breakdowns, guide chapters — a few times a week on Telegram. Free, no sign-in. Join

This solution is part of the Maths Coverage Map — 13 years, mapped. Get the take-away PDF free.