UPSC 2024 Maths Optional Paper 2 Q3c — Step-by-Step Solution

15 marks · Section A

Duality · Linear Programming · asked 5× in 14 yrs · Read the full method →

Question

Using duality, solve: $\text{Minimise }z=4x_1+3x_2+x_3$ subject to $x_1+2x_2+4x_3\ge 12$ , $3x_1+2x_2+x_3\ge 8$ , $x_1,x_2,x_3\ge 0$ .

Form the dual (a two-variable max LP); solve graphically; recover primal via complementary slackness.

\text{Maximise }w=12y_1+8y_2

subject to $y_1+3y_2\le 4$ , $2y_1+2y_2\le 3$ , $4y_1+y_2\le 1$ , $y_1,y_2\ge 0$ .

The third constraint $4y_1+y_2\le 1$ is the most restrictive. Feasible vertices:

$(0,0)$ : $w=0$ .
$(1/4,0)$ : $w=3$ . (Check: $4(1/4)+0=1\le 1$ ✓; others satisfied ✓.)
$(0,1)$ : $w=8$ . (Check: $4(0)+1=1\le 1$ ✓; others satisfied ✓.)
Intersection of $4y_1+y_2=1$ with $2y_1+2y_2=3$ : gives $y_1=-1/6<0$ — infeasible.

Maximum is $w=8$ at $(y_1,y_2)=(0,1)$ . By strong duality, $z_{\min}=8$ .

At $(y_1,y_2)=(0,1)$ :

Dual constraint 1: $y_1+3(1)=3<4$ (slack) → $x_1=0$ .
Dual constraint 2: $2(0)+2(1)=2<3$ (slack) → $x_2=0$ .
$y_2=1>0$ → primal constraint 2 is binding: $3(0)+2(0)+x_3=8\Rightarrow x_3=8$ .

Check primal constraint 1: $0+0+4(8)=32\ge 12$ ✓.

x_1=0,\;x_2=0,\;x_3=8,\;z_{\min}=4(0)+3(0)+1(8)=8.

\boxed{\;x_1=0,\;x_2=0,\;x_3=8,\;z_{\min}=8.\;}