UPSC 2013 Maths Optional Paper 2 Q1e — Step-by-Step Solution

10 marks · Section A

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

Question

Maximize $z=2x_1+3x_2-5x_3$ subject to $x_1+x_2+x_3=7$ and $2x_1-5x_2+x_3\ge 10$ , $x_i\ge 0$ .

Eliminate the equality constraint to reduce dimension; graphical 2-variable analysis of the reduced LPP.

Strategy. The equality constraint reduces dimensionality by 1. Eliminate $x_3$ , reducing to a 2-variable LPP that can be solved graphically.

From $x_1+x_2+x_3=7$ : $x_3=7-x_1-x_2$ . Non-negativity $x_3\ge 0$ gives the new constraint

x_1+x_2\le 7. \tag{C1}

Substitute into the objective:

z=2x_1+3x_2-5(7-x_1-x_2)=7x_1+8x_2-35.

So maximise $z'=7x_1+8x_2$ (and report $z=z'-35$ at the end).

$2x_1-5x_2+x_3\ge 10$ with $x_3=7-x_1-x_2$ :

2x_1-5x_2+7-x_1-x_2\ge 10\;\Longrightarrow\;x_1-6x_2\ge 3,\;\text{i.e.}\;x_1\ge 3+6x_2. \tag{C2}

Maximise $z'=7x_1+8x_2$ subject to:

Combining (C1) and (C2): $3+6x_2\le x_1\le 7-x_2$ , so

3+6x_2\le 7-x_2\;\Longrightarrow\;7x_2\le 4\;\Longrightarrow\;x_2\le\tfrac{4}{7}.

Range of $x_2$ : $[0,\,4/7]$ .

For each fixed $x_2$ , $z'=7x_1+8x_2$ is increasing in $x_1$ , so the optimum at fixed $x_2$ is on the upper boundary $x_1=7-x_2$ :

z'(x_2)=7(7-x_2)+8x_2=49+x_2.

This is maximised at $x_2=4/7$ (the upper end of the feasible $x_2$ range):

z'_{\max}=49+4/7=\tfrac{343+4}{7}=\tfrac{347}{7}.

Therefore $z_{\max}=z'_{\max}-35=\tfrac{347}{7}-\tfrac{245}{7}=\tfrac{102}{7}$ .

At the optimum: $x_2=4/7$ , $x_1=7-4/7=45/7$ , $x_3=7-45/7-4/7=0$ .

\boxed{\;z_{\max}=\dfrac{102}{7}\approx 14.57\;\text{at}\;(x_1,x_2,x_3)=\bigl(\tfrac{45}{7},\tfrac{4}{7},0\bigr).\;}