Chapter 12 Linear Programming

Short Answer Type Questions

1. Determine the maximum value of $Z=11 x+7 y$ subject to the constraints:

$2 x+y \leq 6, x \leq 2, x \geq 0, y \geq 0$

Show Answer

Solution

Given that: $Z=11 x+7 y$ and the constraints $2 x+y \leq 6, x \leq 2$,

$x \geq 0, y \geq 0$

Let $2 x+y=6$

$\begin{array}{|l|l|l|} \hline x & 0 & 3 \\ \hline y & 6 & 0 \\ \hline \end{array}$

The shaded area OABC is the feasible region determined by the constraints

$2 x+y \leq 6, x \leq 2, x \geq 0, y \geq 0$

The feasible region is bounded.

So, maximum value will occur at a corner point of the feasible region.

Corner points are $(0,0),(2,0),(2,2)$ and $(0,6)$.

Now, evaluating the value of $Z$, we get

Corner points Value of $Z$
$O(0,0)$ $11(0)+7(0)=0$
$A(2,0)$ $11(2)+7(0)=22$
$B(2,2)$ $11(2)+7(2)=36$
$C(0,6)$ $11(0)+7(6)=42$

Hence, the maximum value of $Z$ is 42 at $(0,6)$.

2. Maximise $Z=3 x+4 y$, subject to the constraints: $x+y \leq 1, x \geq 0$, $y \geq 0$.

Show Answer

Solution

Given that: $Z=3 x+4 y$ and the constraints $x+y \leq 1, x \geq 0, y \geq 0$

Let

$ x+y=1 $

$\begin{array}{|l|l|l|} \hline x & 1 & 0 \\ \hline y & 0 & 1 \\ \hline \end{array}$

The shaded area $OAB$ is the feasible region determined by $x+y \leq 1, x \geq 0, y \geq 0$.

The feasible region is bounded. So, maximum value will occur at the corner points $O(0,0)$, $A(1,0), B(0,1)$.

Now, evaluating the value of $Z$, we get

Corner points Value of Z
$O(0,0)$ $3(0)+4(0)=0$
$A(1,0)$ $3(1)+4(0)=3$
$B(0,1)$ $3(0)+4(1)=4$

Hence, the maximum value of $Z$ is 4 at $(0,1)$.

3. Maximise the function $Z=11 x+7 y$ subject to the constraints: $x \leq 3, y \leq 2, x \geq 0, y \geq 0$.

Show Answer

Solution

The shaded region is the feasible region determined by the constraints $x \leq 3, y \leq 2$, $x \geq 0, y \geq 0$.

The feasible region is bounded with four corners $O(0,0), A(3,0), B(3,2)$ and

$C(0,2)$.

So, the maximum value can occur at any corner.

Let us evaluate the value of $Z$.

Corner points Value of Z
$O(0,0)$ $11(0)+7(0)=0$
$A(3,0)$ $11(3)+7(0)=33$
$B(3,2)$ $11(3)+7(2)=47$
$C(0,2)$ $11(0)+7(2)=14$

Hence, the maximum value of the function $Z$ is 47 at $(3,2)$.

4. Minimise $Z=13 x-15 y$ subject to the constraints: $x+y \leq 7,2 x-3 y+6 \geq 0, x \geq 0, y \geq 0$.

Show Answer

Solution

Given that: $Z=13 x-15 y$ and the constraints $x+y \leq 7,2 x-3 y+6 \geq 0, x \geq 0, y \geq 0$

Let $x+y=7$

$\begin{array}{|l|l|l|} \hline x & 3 & 4 \\ \hline y & 4 & 3 \\ \hline \end{array}$

Let $2 x-3 y+6=0$

$\begin{array}{|l|l|l|} \hline x & 1 & -3 \\ \hline y & 2 & 0 \\ \hline \end{array}$

The shaded region is the feasible region determined

by the constraints $x+y \leq 7,2 x-3 y+6 \geq 0, x \geq 0, y \geq 0$

The feasible region is bounded with four corners

$O(0,0), A(7,0), B(3,4), C(0,2)$

So, the maximum value can occur at any corner.

Let us evaluate the value of $Z$.

Corner points Value of $Z$
$O(0,0)$ $13(0)-15(0)=0$
$A(7,0)$ $13(7)-15(0)=91$
$B(3,4)$ $13(3)-15(4)=-21$
$C(0,2)$ $13(0)-15(2)=-30$

Hence, the minimum value of $Z$ is -30 at $(0,2)$.

5. Determine the maximum value of $Z=3 x+4 y$ if the feasible region (shaded) for a LPP is shown in figure.

Show Answer

Solution

As shown in the figure, OAED is the feasible region.

At A, $y=0 \therefore 2 x+y=104$

$\Rightarrow x=52$

Which gives corner point $A=(52,0)$

At D, $x=0 \therefore x+2 y=76 \Rightarrow y=38$

Which gives corner point $D=(0,38)$

Now solving the given equations, we get

$ \begin{aligned} x+2 y=76 \\ 2 x+y=104 \\ 2 x+4 y=152 \\ 2 x+y=104 \\ \hline (-) \quad (-) \quad (-) \\ \qquad 3 y=48 \Rightarrow y=16 \end{aligned} $

$x+2(16) =76$

$\Rightarrow \quad x =76-32=44$

So, the corner point $E=(44,16)$

Evaluating the maximum value of $Z$, we get

Corner points $Z=3 x+4 y$
$O(0,0)$ $Z=3(0)+4(0)=0$
$A(52,0)$ $Z=3(52)+4(0)=156$
$E(44,16)$ $Z=3(44)+4(16)=196$
$D(0,38)$ $Z=3(0)+4(38)=152$

Hence, the maximum value of $Z$ is 196 at $(44,16)$.

6. Feasible region (shaded) for a LPP is shown in figure.

Maximise $Z=5 x+7 y$.

Show Answer

Solution

$OABC$ is the feasible region whose corner points are $O(0,0), A(7,0), B(3,4)$ and $C(0,2)$

Evaluating the value of $Z$, we get

Corner points Value of $Z$
$O(0,0)$ $Z=5(0)+7(0)=0$
$A(7,0)$ $Z=5(7)+7(0)=35$
$B(3,4)$ $Z=5(3)+7(4)=43$
$C(0,2)$ $Z=5(0)+7(2)=14$

Hence, the maximum value of $Z$ is 43 at $(3,4)$.

7. The feasible region for a LPP is shown in figure. Find the minimum value of $Z=11 x+7 y$.

Show Answer

Solution

As per the given figure, ABCA is the feasible region. Corner points $C(0,3), B(0,5)$ and for $A$, we have to solve equations

$ \text{ and } \quad \begin{aligned} x+3 y & =9 \\ x+y & =5 \end{aligned} $

Which gives $x=3, y=2$

i.e., $A(3,2)$

Evaluating the value of $Z$, we get

Corner points Value of $Z$
$A(3,2)$ $Z=11(3)+7(2)=47$
$B(0,5)$ $Z=11(0)+7(5)=35$
$C(0,3)$ $Z=11(0)+7(3)=21$

Hence, the minimum value of $Z$ is 21 at $(0,3)$.

8. Refer to Exercise 7 above. Find the maximum value of $Z$.

Show Answer

Solution

As per the evaluating table for the value of $Z$, it is clear that the maximum value of $Z$ is 47 at $(3,2)$.

9. The feasible region for a LPP is shown in figure. Evaluate $Z=4 x+y$ at each of the corner points of this region. Find the minimum value of $Z$, if it exists.

Show Answer

Solution

As per the given figure, $A B C$ is the feasible region which is open unbounded.

Here, we have

$$ \begin{align*} x+y & =3 \tag{i}\\ \text{ and } x+2 y & =4 \tag{ii}\\ Z & =4 x+y \end{align*} $$

Solving eq. (i) and (ii), we get

$x=2$ and $y=1$

So, the corner points are $A(4,0), B(2,1)$ and $C(0,3)$

Let us evaluate the value of $Z$

Corner points $Z=4 x+y$
$A(4,0)$ $Z=4(4)+(0)=16$
$B(2,1)$ $Z=4(2)+(1)=9$
$C(0,3)$ $Z=4(0)+(3)=3$

Now, the minimum value of $Z$ is 3 at $(0,3)$ but since, the feasible region is open bounded so it may or may not be the minimum value of $Z$.

Therefore, to face such situation, we draw a graph of $4 x+y<3$ and check whether the resulting open half plane has no point in common with feasible region. Otherwise $Z$ will have no minimum value. From the graph, we conclude that there is no common point with the feasible region.

Hence, $Z$ has the minimum value 3 at $(0,3)$.

10. In given figure, the feasible region (shaded) for a LPP is shown. Determine the maximum and minimum value of $Z=x+2 y$.

Show Answer

Solution

Here, corner points are given as follows:

$ R(\frac{7}{2}, \frac{3}{4}), Q(\frac{3}{2}, \frac{15}{4}), P(\frac{3}{13}, \frac{24}{13}) \text{ and } S(\frac{18}{7}, \frac{2}{7}) \text{. } $

Now, evaluating the value of $Z$ for the feasible region RQPS.

Corner points Value of $Z=x+2 y$
$R(\frac{7}{2}, \frac{3}{4})$ $Z=\frac{7}{2}+2(\frac{3}{4})=5$
$Q(\frac{3}{2}, \frac{15}{4})$ $Z=\frac{3}{2}+2(\frac{15}{4})=9$
$P(\frac{3}{13}, \frac{24}{13})$ $Z=\frac{3}{13}+2(\frac{24}{13})=\frac{51}{13}$
$S(\frac{18}{7}, \frac{2}{7})$ $Z=\frac{18}{7}+2(\frac{2}{7})=\frac{22}{7}$

Hence, the maximum value of $Z$ is 9 at $(\frac{3}{2}, \frac{15}{4})$ and the minimum value of $Z$ is $\frac{22}{7}$ at $(\frac{18}{7}, \frac{2}{7})$.

11. A manufacturer of electric circuits has a stock of 200 resistors, 120 transistors and 150 capacitors and is required to produce two types of circuits A and B. Type A requires 20 resistors, 10 transistors and 10 capacitors. Type B requires 10 resistors, 20 transistors and 30 capacitors. If the profit on type A circuit is ₹ 50 and that on type B circuit is ₹ 60 , formulate this problem as a LPP so that the manufacturer can maximise his profit.

Show Answer

Solution

Let $x$ units of type A and $y$ units of type B electric circuits be produced by the manufacturer.

As per the given information, we construct the following table:

Items Type $A(x)$ Type B $(y)$ Maximum stock
Resistors 20 10 200
Transistors 10 20 120
Capacitors 10 30 150
Profit $₹ 50$ $₹ 60$ $Z=50 x+60 y$

Now, we have the total profit in rupees $Z=50 x+60 y$ to maximise subject to the constraints $20 x+10 y \leq 200$ …(i);

$\quad 10 x+20 y \leq 120$…(ii)

$10 x+30 y \leq 150$ …(iii);

$\quad x \geq 0, y \geq 0$…(iv)

Hence, the required LPP is

Maximise $Z=50 x+60 y$ subject to the constraints

$20 x+10 y \leq 200 \Rightarrow 2 x+y \leq 20 ; 10 x+20 y \leq 120 \Rightarrow x+2 y \leq 12$

and $\quad 10 x+30 y \leq 150 \Rightarrow x+3 y \leq 15, x \geq 0, y \geq 0$

12. A firm has to transport 1200 packages using large vans which can carry 200 packages each and small vans which can take 80 packages each. The cost for engaging each large van is ₹ 400 and each small van is ₹ 200 . Not more than ₹ 3000 is to be spent on the job and the number of large vans cannot exceed the number of small vans. Formulate this problem as a LPP given that the objective is to minimise cost.

Show Answer

Solution

Let $x$ and $y$ be the number of large and small vans respectively. From the given information, we construct the following corresponding constraints table;

Items Large vans
$(x)$
Small vans
$(y)$
Maximum/
Minimum
Packages 200 80 1200
Cost 400 200 3000

Now the objective function for minimum cost is

$ Z=400 x+200 y $

Subject to the constraints;

$$ \begin{equation*} 200 x+80 y \geq 1200 \Rightarrow 5 x+2 y \geq 30 \tag{i} \end{equation*} $$

$$ \begin{align*} 400 x+200 y & \leq 3000 \Rightarrow 2 x+y \leq 15 \tag{ii}\\ x & \leq y \tag{iii} \end{align*} $$

and $\quad x \geq 0, y \geq 0$ (non-negative constraints)

Hence, the required LPP is to minimise $Z=400 x+200 y$

Subject to the constraints $5 x+2 y \geq 30,2 x+y \leq 15, x \leq y$ and $x \geq 0, y \geq 0$.

13. A company manufactures two types of screws A and B. All the screws have to pass through a threading machine and a slotting machine. Abox of type A screws requires 2 minutes on the threading machine and 3 minutes on the slotting machine. A box of type $B$ screws requires 8 minutes of threading on threading machine and 2 minutes on the slotting machine. In a week, each machine is available for 60 hours.

On selling these screws, the company gets a profit of ₹ 100 per box on type A screws and ₹ 170 per box on type B screws. Formulate this problem as a LPP given that the objective is to maximise profit.

Show Answer

Solution

Let the company manufactures $x$ boxes of type A screws and $y$ boxes of type B screws.

From the given information, we can construct the following table.

Items Type A
$(x)$
Type B
$(y)$
Minimum time available
on each machine
in a week
Time required on
threading machine
2 8 $60 \times 60=3600$ minutes
Time required on
slotting machine
3 2 $60 \times 60=3600$ minutes
Profit $₹ 100$ $₹ 170$

As per the information in the above table, the objective function for maximum profit $Z=100 x+170 y$

Subject to the constraints

$$ \begin{align*} 2 x+8 y & \leq 3600 \Rightarrow x+4 y \leq 1800 \tag{i}\\ 3 x+2 y & \leq 3600 \tag{ii}\\ x & \geq 0, y \geq 0 \end{align*} $$

Hence, the required LPP is

Maximise $\quad Z=100 x+170 y$

Subject to the constraints,

$x+4 y \leq 1800,3 x+2 y \leq 3600, x \geq 0, y \geq 0$.

14. A company manufactures two types of sweaters: type A and type B. It costs ₹ 360 to make a type A sweater and ₹ 120 to make a type B sweater. The company can make at most 300 sweaters and spend at most $₹ 72000$ a day. The number of sweaters of type B cannot exceed the number of sweaters of type A by more than 100. The company makes a profit of ₹ 200 for each sweater of type A and ₹ 120 for every sweater of type B.

Formulate this problem at a LPP to maximise the profit to the company.

Show Answer

Solution

Let $x$ and $y$ be the number of sweaters of type A and type B respectively.

From the given information, we have the following constraints.

$360 x+120 y \leq 72000 \Rightarrow 3 x+y \leq 600$

$x+y \leq 300 \quad \ldots$ (ii); $x+100 \geq y \Rightarrow y \leq x+100$

Profit $\quad(Z)=200 x+120 y$

Hence, the required LPP to maximise the profit is

Maximise $Z=200 x+120 y$ subject to the constraints

$3 x+y \leq 600, x+y \leq 300, y \leq x+100, x \geq 0, y \geq 0$.

15. A man rides his motorcycle at the speed of $50 km / hr$. He has to spend ₹ 2 per $km$ on petrol. If he rides it at a faster speed of 80 $km / hr$, the petrol cost increases to ₹ 3 per $km$. He has atmost ₹ 120 to spend on petrol and one hour’s time. He wishes to find the maximum distance that he can travel.

Express this problem as a linear programming problem.

Show Answer

Solution

Let the man covers $x km$ on his motorcycle at the speed of $50 km / hr$ and covers $y km$ at the speed of $80 km / hr$.

So, cost of petrol $=2 x+3 y$

The man has to spend ₹ 120 atmost on petrol

$\therefore \quad 2 x+3 y \leq 120$

Now, the man has only $1 hr$ time

$$ \begin{gather*} \therefore \quad \frac{x}{50}+\frac{y}{80} \leq 1 \Rightarrow 8 x+5 y \leq 400 \tag{ii}\\ x \geq 0, y \geq 0 \end{gather*} $$

To have maximum distance $Z=x+y$.

Hence, the required LPP to travel maximum distance is maximise $Z=x+y$, subject to the constraints $2 x+3 y \leq 120,8 x+5 y \leq 400, x \geq 0, y \geq 0$.

Long Answer Type Questions

16. Refer to Exercise 11. How many of circuits of Type A and of Type B, should be produced by the manufacturer so as to maximise his profit? Determine the maximum profit.

Show Answer

Solution

As per the solution of Question No. 11, we have Maximise $Z=50 x+60 y$ subject to the contraints $2 x+y \leq 20 \ldots(i) ; x+2 y \leq 12 \ldots$… (ii); $x+3 y \leq 15 \ldots(i i i) ; x \geq 0, y \geq 0 \ldots$… (iv)

Let us draw the table for the above statements

Table for $(i)$

$\begin{array}{|l|l|l|} \hline x & 0 & 10 \\ \hline y & 20 & 0 \\ \hline \end{array}$

Table for (ii)

$\begin{array}{|l|l|l|} \hline x & 0 & 12 \\ \hline y & 6 & 0 \\ \hline \end{array}$

Table for (ii)

$\begin{array}{|l|l|l|} \hline x & 0 & 15 \\ \hline y & 5 & 0 \\ \hline \end{array}$

Solving eq. (i) and (ii) we get,

$x=\frac{28}{3}, y=\frac{4}{3} \quad \therefore B(\frac{28}{3}, \frac{4}{3})$ is the corner

Solving eq. (ii) and (iii) we get,

$x=6, y=3 \quad \therefore C(6,3)$ is the corner

Solving eq. (i) and (iii) we get,

$x=9, y=2 \quad$ (not included in the feasible region)

Here, $OABCD$ is the feasible region.

So, the corner points are $O(0,0), A(10,0), B(\frac{28}{3}, \frac{4}{3}), C(6,3)$

and $D(0,5)$.

Let us evaluate the value of $Z$

Corner points Corresponding values of $Z=50 x+60 y$
$O(0,0)$ $Z=50(0)+60(0)=0$
$A(10,0)$ $Z=50(10)+60(0)=500$
$B(\frac{28}{3}, \frac{4}{3})$ $Z=50(\frac{28}{3})+60(\frac{4}{3})=\frac{1400}{3}+\frac{240}{3}=\frac{1640}{3}=546.6$
$C(6,3)$ $Z=50(6)+60(3)=480$
$D(0,5)$ $Z=50(0)+60(5)=300$

Here, the maximum profit is ₹ 546.6 which is not possible for number of items in fraction.

Hence, the maximum profit for the manufacturer is ₹ 480 at $(6,3)$. Type $A=6$ and Type B $=3$.

17. Refer to Exercise 12. What will be the minimum cost?

Show Answer

Solution

As per the solution of Q. 12 ., we have $Z=400 x+200 y$ Subject to the constraints

$5 x+2 y \geq 30$

$x \leq y, x \geq 0, y \geq 0$

$x-y \leq 0$

…(i); $2 x+y \leq 15$

Let $5 x+2 y=30$

$\begin{array}{|l|l|l|} \hline x & 0 & 6 \\ \hline y & 15 & 0 \\ \hline \end{array}$

Let $2 x+y=15$

$\begin{array}{|l|l|l|} \hline x & 0 & 7.5 \\ \hline y & 15 & 0 \\ \hline \end{array}$

Let $x-y=0$

$\begin{array}{|l|l|l|} \hline x & 0 & 1 \\ \hline y & 0 & 1 \\ \hline \end{array}$

Solving eq. (i) and (iii) we get; $x=\frac{30}{7}$ and $y=\frac{30}{7}$

and on solving eq. (ii) and (iii) we get, $x=5$ and $y=5$

Here, $A B C$ is the shaded feasible region whose corner points are $A(\frac{30}{7}, \frac{30}{7}), B(5,5)$ and $C(0,15)$

Evaluating the value of $Z$, we have

Corner points Value of $Z=400 x+200 y$
$A(\frac{30}{7}, \frac{30}{7})$ $Z=400(\frac{30}{7})+200(\frac{30}{7})=\frac{18000}{7}=2571.4$
$B(5,5)$ $Z=400(5)+200(5)=3000$
$C(0,15)$ $Z=400(0)+200(15)=3000$

Hence, the required minimum cost is $₹ 2571.4$ at $(\frac{30}{7}, \frac{30}{7})$.

18. Refer to Exercise 13. Solve the linear programming program and determine the maximum profit to the manufacturer.

Show Answer

Solution

As per the solution of Q. 13 , we have:

Let $3 x+2 y=3600$

$\begin{array}{|l|l|l|} \hline x & 0 & 1200 \\ \hline y & 1800 & 0 \\ \hline \end{array}$

Let $x+4 y=1800$

$\begin{array}{|l|l|l|} \hline x & 0 & 1800 \\ \hline y & 450 & 0 \\ \hline \end{array}$

Maximise $Z=100 x+170 y$ subject to the constraints

$$ \begin{align*} 3 x+2 y & \leq 3600 \quad \ldots(i) ; x+4 y \leq 1800 \tag{ii}\\ x & \geq 0, y \geq 0 \end{align*} $$

On solving eq. (i) and (ii) we get $x=1080$ and $y=180$

$OABC$ is the feasible region whose corner points are $O(0,0)$, $A(1200,0), B(1080,180), C(0,450)$.

Corner points Value of $Z=100 x+170 y$
$O(0,0)$ $Z=100(0)+170(0)=0$
$A(1200,0)$ $Z=100(1200)+0=120000$
$B(1080,180)$ $Z =100(1080)+170(180)=138600$
$C(0,450)$ $Z=170(450)=76500$

Let us evaluate the value of $Z$.

Hence, the maximum value of $Z$ is 138600 at $(1080,180)$.

19. Refer to Exercise 14. How many sweaters of each type should the company make in a day so as to get a maximum profit? What is the maximum profit?

Show Answer

Solution

Referring to the solution of Q. 14 , we have

Maximise $\quad Z=200 x+120 y$ subject to the constraints

$$ \begin{align*} x+y & \leq 300 \quad \ldots(i) ; \quad 3 x+y \leq 600 \tag{ii}\\ x-y & \geq-100 \tag{iii}\\ x & \geq 0, y \geq 0 \end{align*} $$

On solving eq. (i) and (iii) we have $x=100, y=200$

On solving eq. (i) and (ii) we get $x=150, y=150$

Let $x+y=300$

Let $3 x+y=600 \quad$ Let $x+y=-100$

$\begin{array}{|l|l|l|} \hline x & 0 & 300 \\ \hline y & 300 & 0 \\ \hline \end{array}$

$\begin{array}{|l|l|l|} \hline x & 0 & 200 \\ \hline y & 600 & 0 \\ \hline \end{array}$

$\begin{array}{|l|l|l|} \hline x & 0 & -100 \\ \hline y & 100 & 0 \\ \hline \end{array}$

Here, the shaded region is the feasible region whose corner points are $O(0,0), A(200,0), B(150,150), C(100,200), D(0,100)$. Let us evaluate the value of $Z$.

Corner points Value of $Z=200 x+120 y$
$O(0,0)$ $Z=200(0)+120(0)=0$
$A(200,0)$ $Z=200(200)+120(0)=40000$
$B(150,150)$ $Z=200(150)+120(150)=48000$
$C(100,200)$ $Z=200(100)+120(200)=44000$
$D(0,100)$ $Z=200(0)+120(100)=12000$

Hence, the maximum value of $Z$ is 48000 at $(150,150)$ i.e., 150 sweaters of each type.

20. Refer to Exercise 15, Determine the maximum distance that the man can travel.

Show Answer

Solution

Referring to the solution of Q.15 , we have Maximise $Z=x+y$ subject to the constraints Let $2 x+3 y=120 \quad$ Let $8 x+5 y=400$

$x$ 0 60
$y$ 40 0
$x$ 0 50
$y$ 80 0

$ \begin{aligned} 2 x+3 y & \leq 120 \ldots(i) ; 8 x+5 y \leq 400 \ldots(i i) \\ x & \geq 0, y \geq 0 \end{aligned} $

On solving eq. ( $i$ ) and (ii) we get; $x=\frac{300}{7}$ and $y=\frac{80}{7}$

Here, $OABC$ is the feasible region whose corner points are $O(0,0), A(50,0), B(\frac{300}{7}, \frac{80}{7})$ and $C(0,40)$.

Let us evaluate the value of $Z$

Corner points Value of $Z=x+y$
$O(0,0)$ $Z=0+0=0$
$A(50,0)$ $Z=50+0=50 km$
$B(\frac{300}{7}, \frac{80}{7})$ $Z=\frac{300}{7}+\frac{80}{7}=\frac{380}{7}=54.3 km$
$C(0,40)$ $Z=0+40=40 km$

Hence, the maximum distance that the man can travel is $54 \frac{2}{7} km$ at $(\frac{300}{7}, \frac{80}{7})$.

21. Maximise $Z=x+y$ subject to $x+4 y \leq 8,2 x+3 y \leq 12,3 x+y \leq 9$, $x \geq 0, y \geq 0$.

Show Answer

Solution

We are given that $Z=x+y$ subject to the constraints

$$ \begin{align*} x+4 y & \leq 8 \tag{i}\\ 2 x+3 y & \leq 12 \tag{ii}\\ 3 x+y & \leq 9 \tag{iii}\\ x & \geq 0, y \geq 0 \end{align*} $$

$\begin{array}{|l|l|l|} \hline x & 0 & 8 \\ \hline y & 2 & 0 \\ \hline \end{array}$

$\begin{array}{|l|l|l|} \hline x & 0 & 6 \\ \hline y & 4 & 0 \\ \hline \end{array}$

$\begin{array}{|l|l|l|} \hline x & 0 & 3 \\ \hline y & 9 & 0 \\ \hline \end{array}$

On solving eq. (i) and (iii) we get

$x=\frac{28}{11}$ and $y=\frac{15}{11}$

Here, $OABC$ is the feasible region whose corner points are $O(0,0), A(3,0), B(\frac{28}{11}, \frac{15}{11}), C(0,2)$

Let us evaluate the value of $Z$

Corner points Value of $Z=x+y$
$O(0,0)$ $Z=0+0=0$
$A(3,0)$ $Z=3+0=3$
$B(\frac{28}{11}, \frac{15}{11})$ $Z=\frac{28}{11}+\frac{15}{11}=\frac{43}{11}=3.9$
$C(0,2)$ $Z=0+2=2$

Hence, the maximum value of $Z$ is 3.9 at $(\frac{28}{11}, \frac{15}{11})$.

22. A manufacturer produces two Models of bikes-Model $X$ and Model Y. Model X takes a 6 man-hours to make per unit, while Model Y takes 10 man-hours per unit. There is a total of 450 man-hour available per week. Handling and marketing costs are ₹ 2,000 and ₹ 1,000 per unit for Models X and Y respectively. The total funds available for these purposes are ₹ 80,000 per week. Profits per unit for Models X and Y are $₹ 1,000$ and ₹ 500 respectively. How many bikes of each model should the manufacturer produce so as to yield a maximum profit? Find the maximum profit.

Show Answer

Solution

Let $x$ and $y$ be the number of Models of bike produced by the manufacturer.

Given information is

Model X takes 6 man-hours to make per unit

Model Y takes 10 man-hours to make per unit

Total man-hours available $=450$

$\therefore \quad 6 x+10 y \leq 450 \Rightarrow 3 x+5 y \leq 225$

Handling and marketing cost of Model X and Y are ₹ 2,000 and ₹ 1,000 respectively

Total funds available is ₹ 80,000 per week

$$ \begin{matrix} \therefore & 2000 x+1000 y & \leq 80,000 \\ \Rightarrow & & 2 x+y & \leq 80 \tag{ii} \end{matrix} $$

and

$ x \geq 80, y \geq 0 $

Profit (Z) per unit of models $X$ and $Y$ are $₹ 1,000$ and $₹ 500$ respectively

So,

$ Z=1000 x+500 y $

The required LPP is

Maximise $Z=1000 x+500 y$ subject to the constraints

$$ \begin{align*} 3 x+5 y & \leq 225 \tag{i}\\ 2 x+y & \leq 80 \tag{ii}\\ x & \geq 0, y \geq 0 \tag{iii} \end{align*} $$

$\begin{array}{|l|l|l|} \hline x & 0 & 40 \\ \hline y & 45 & 0 \\ \hline \end{array}$

$\begin{array}{|l|l|l|} \hline x & 1 & 40 \\ \hline y & 80 & 0 \\ \hline \end{array}$

On solving eq. (i) and (i) we get, $x=25, y=30$ Here, the feasible region is $OABC$, whose corner points are $O(0,0), A(40,0), B(25,30)$ and $C(0,45)$.

Let us evaluate the value of Z.

Corner points Value of $Z=1000 x+500 y$
$O(0,0)$ $Z=0+0=0$
$A(40,0)$ $Z=1000(40)+0=40,000$
$B(25,30)$ $Z=1000(25)+500(30)=40,000$
$C(0,45)$ $Z=0+500(45)=22500$

Hence, the maximum profit is $₹ 40,000$ by producing 25 bikes of Model X and 30 bikes of Model Y.

23. In order to supplement daily diet, a person wishes to take some $X$ and some wishes $Y$ tablets. The contents of iron, calcium and vitamins in $X$ and $Y$ (in milligram per tablet) are given as below:

Tablets Iron Calcium Vitamin
$X$ 6 3 2
$Y$ 2 3 4

The person needs atleast 18 milligrams of iron, 21 milligrams of calcium and 16 milligrams of vitamin. The price of each tablet of $X$ and $Y$ is ₹ 2 and ₹ 1 respectively. How many tablets of each should the person take in order to satisfy the above requirement at the minimum cost?

Show Answer

Solution

Let there be $x$ units of tablet $X$ and $y$ units of tablet $Y$ So, according to the given information, we have

$$ \begin{gather*} 6 x+2 y \geq 18 \quad \Rightarrow \quad 3 x+y \geq 9 \tag{i}\\ 3 x+3 y \geq 21 \quad \Rightarrow \quad x+y \geq 7 \\ 2 x+4 y \geq 16 \quad \Rightarrow \quad x+2 y \geq 8 \\ x \geq 0, y \geq 0 \end{gather*} $$

$\begin{array}{|l|l|l|} \hline x & 0 & 3 \\ \hline y & 9 & 0 \\ \hline \end{array}$

$\begin{array}{|l|l|l|} \hline x & 0 & 7 \\ \hline y & 7 & 0 \\ \hline \end{array}$

$\begin{array}{|l|l|l|} \hline x & 0 & 8 \\ \hline y & 4 & 0 \\ \hline \end{array}$

The price of each table of $X$ type is $₹ 2$ and that of $y$ is $₹ 1$. So, the required LPP is Minimise $Z=2 x+y$ subject to the constraints $3 x+y \geq 9, x+y \geq 7, x+2 y \geq 8, x \geq 0, y \geq 0$

On solving (ii) and (iii) we get $x=6$ and $y=1$

On solving (i) and (ii) we get $x=1$ and $y=6$

From the graph, we see that the feasible region $A B C D$ is unbounded whose corner points are $A(8,0), B(6,1), C(1,6)$ and $D(0,9)$.

Let us evaluate the value of $Z$

Corner points Value of $Z=2 x+y$
$A(8,0)$ $Z=2(8)+0=16$
$B(6,1)$ $Z=2(6)+1=13$
$C(1,6)$ $Z=2(1)+6=8$
$D(0,9)$ $Z=2(0)+9=9$

Here, we see that 8 is the minimum value of $Z$ at $(1,6)$ but the feasible region is unbounded. So, 8 may or may not be the minimum value of $Z$.

To confirm it, we will draw a graph of inequality $2 x+y<8$ and check if it has a common point.

We see from the graph that there is no common point on the line.

Hence, the minimum value of $Z$ is 8 at $(1,6)$.

Tablet $X=1$

Table $Y=6$.

24. A company makes 3 models of calculators: A, B and C at factory I and factory II. The company has orders for atleast 6400 calculators of model A, 4000 calculators of model B and 4800 calculators of model C. At factory I, 50 calculators of model A, 50 of model B and 30 of model C are made everyday; at factory II, 40 calculators of model A, 20 of model B and 40 of model C are made everyday. It costs $₹ 12,000$ and $₹ 15000$ each day to operate factory I and II respectively. Find the number of days each factory should operate to minimise the operating costs and still meet the demand.

Show Answer

Solution

Let factory I be operated for $x$ days and II for $y$ days

At factory I: 50 calculators of model A and at factory II, 40 calculators of model A are made everyday.

Company has orders of atleast 6400 calculators of model A.

$\therefore 50 x+40 y \geq 6400 \Rightarrow 5 x+4 y \geq 640$

Also, at factory I, 50 calculators of model B and at factory II, 20 calculators of model B are made everyday.

Company has the orders of atleast 4000 of calculators of model B. $\therefore 50 x+20 y \geq 4000 \quad \Rightarrow \quad 5 x+2 y \geq 4000$

Similarly for model C,

$30 x+40 y \geq 4800 \Rightarrow 3 x+4 y \geq 480$

and $x \geq 0, y \geq 0$

It costs ₹ 12,000 and ₹ 15000 to operate the factories I and II each day.

$\therefore$ Required LPP is

Minimise $Z=12000 x+15000 y$ subject to the constraints

$$ \begin{align*} 5 x+4 y & \geq 640 \tag{i}\\ 5 x+2 y & \geq 400 \tag{ii}\\ 3 x+4 y & \geq 480 \tag{iii}\\ x & \geq 0, y \geq 0 \tag{iv} \end{align*} $$

Table for (i) equation $5 x+4 y=640$

$\begin{array}{|l|l|l|} \hline x & 0 & 128 \\ \hline y & 160 & 0 \\ \hline \end{array}$

Table for (ii) equation $5 x+2 y=400$

$\begin{array}{|l|l|l|} \hline x & 0 & 80 \\ \hline y & 200 & 0 \\ \hline \end{array}$

Table for (iii) equation $3 x+4 y=480$

$\begin{array}{|l|l|l|} \hline x & 0 & 160 \\ \hline y & 120 & 0 \\ \hline \end{array}$

On solving eq. (i) and (iii), we get $x=80, y=60$

On solving eq. (i) and (ii) we get $x=32$ and $y=120$

From the graph, we see that the feasible region $ABCD$ is open unbounded whose corners are $A(160,0), B(80,60), C(32,120)$ and $D(0,200)$.

Let us find the values of $Z$.

Corner points Value of $Z=12000 x+15000 y$
$A(160,0)$ $Z=12000(160)+0=1920000$
$B(80,60)$ $Z=12000(80)+15000(60)=1860000$
$C(32,120)$ $Z=12000(32)+15000(120)=2184000$
$D(0,200)$ $Z=0+15000(200)=3000000$

From the above table, it is clear that the value of $Z=1860000$ may or may not be minimum for an open unbounded region.

Now, to decide this, we draw a graph of

$ 12000 x+15000 y<1860000 $

$\Rightarrow \quad 4 x+5 y<620$

and we have to check whether there is a common point in this feasible region or not.

So, from the graph, there is no common point.

$\therefore Z=12000 x+15000 y$ has minimum value 1860000 at $(80,60)$.

Factory I : 80 days

Factory II: 60 days.

25. Maximise and minimise $Z=3 x-4 y$ subject to $x-2 y \leq 0$, $-3 x+y \leq 4, x-y \leq 6$ and $x, y \geq 0$.

Show Answer

Solution

Given LPP is

Maximise and minimise $Z=3 x-4 y$ subject to

$$ \begin{matrix} x-2 y \leq 0 \qquad\text{(i)}\\ -3 x+y \leq 4 \tag{ii} \end{matrix} $$

$$ \begin{align*} & x-y \leq 6 \tag{iii}\\ & \text{ and } \quad x, y \geq 0 \tag{iv} \end{align*} $$

$\begin{array}{|l|l|l|} \hline x & 0 & 2 \\ \hline y & 0 & 1 \\ \hline \end{array}$

$\begin{array}{|l|l|l|} \hline x & 0 & -4/3 \\ \hline y & 4 & 0 \\ \hline \end{array}$

$\begin{array}{|l|l|l|} \hline x & 0 & 6 \\ \hline y & -6 & 0 \\ \hline \end{array}$

From the graph, we see that $AOB$ is open unbounded region whose corners are $O(0,0), A(0,4), B(12,6)$.

Let us evaluate the value of $Z$

Corner points Value of $Z=3 x-4 y$
$O(0,0)$ $Z=0$
$A(0,4)$ $Z=0-4(4)=-16$
$B(12,6)$ $Z=3(12)-4(6)=12$

For this unbounded region, the value of $Z$ may or may not be -16 . So to decide it, we draw a graph of inequality $3 x-4 y<-16$ and check whether the open half plane has common points with feasible region or not. But from the graph, we see that it has common points with the feasible region, so it will have not minimum value of $Z$. Similarly for maximum value, we draw the graph of inequality $3 x-4 y>12$ in which there is no common point with the feasible region.

Hence, the maximum value of $Z$ is 12 .

Objective Type Questions

26. The corner points of the feasible region determined by the system of linear constraints are $(0,0),(0,40),(20,40),(60,20)$, $(60,0)$. The objective function is $Z=4 x+3 y$. Compare the quantity in Column A and Column B

Column $A$ Column B
Maximum of $Z$ 325

(a) The quantity in column $A$ is greater.

(b) The quantity in column $B$ is greater

(c) The two quantities are equal

(d) The relationship cannot be determined on the basis of the information supplied.

Show Answer

Solution

$\begin{array}{|c|c|c|} \hline \text{Corner points} & \text{Value of} Z=4 x+3 y \\ \hline(0,0) & \mathrm{Z}=0 \\ \hline(0,40) & Z=0+3(40)=120 \\ \hline(20,40) & Z=4(20)+3(40)=200 \\ \hline(60,20) & Z=4(60)+3(20)=300\rightarrow \text{Maximum} \\ \hline(60,0) & Z=4(60)+3(0)=240 \\ \hline \end{array}$

Hence, the correct option is $(b)$.

27. The feasible solution for a LPP is shown in figure. Let $Z=3 x-4 y$ be the objective function. Minimum of $Z$ occurs at

(a) $(0,0)$

(b) $(0,8)$

(c) $(5,0)$

(d) $(4,10)$

Show Answer

Solution

Corner points Value of $Z=3 x-4 y$
$O(0,0)$ $Z=0$
$A(5,0)$ $Z=3(5)-0=15$
$B(6,5)$ $Z=3(6)-4(5)=-2$
$C(6,8)$ $Z=3(6)-4(8)=-14$
$D(4,10)$ $Z=3(4)-4(10)=-28$
$E(0,8)$ $Z=3(0)-4(8)=-32$

Hence, the correct option is $(b)$.

28. Refer to Exercise 27. Maximum of $Z$ occurs at

(a) $(5,0)$

(b) $(6,5)$

(c) $(6,8)$

(d) $(4,10)$

Show Answer

Solution

According to solution of Q. 27 , the maximum value of $Z$ is 15 at $A(5,0)$.

Hence, the correct option is $(a)$.

29. Refer to Exercise 27. (Maximum value of $Z+$ Minimum value of $Z$ ) is equal to

(a) 13

(b) 1

(c) -13

(d) -17

Show Answer

Solution

According to the solution of Q. 27 , Maximum value of $Z=15$ and Minimum value of $Z=-32$

So, the sum of Maximum value and Minimum value of $Z$

$ =15+(-32)=-17 $

Hence, the correct option is $(d)$.

30. The feasible region for an LPP is shown in the figure. Let $F=3 x-4 y$ be the objective function. Maximum value of $F$ is

(a) 0

(b) 8

(c) 12

(d) -18

Show Answer

Solution

The feasible region is shown in the figure for which the objective function $F=3 x-4 y$

Corner point Value of $F=3 x-4 y$
$O(0,0)$ $F=0$
$A(12,6)$ $F=3(12)-4(6)=12$
$B(0,4)$ $F=0-4(4)=-16$

Hence, the correct option is (c).

31. Refer to Exercise 30. Minimum value of $F$ is

(a) 0

(b) -16

(c) 12

(d) does not exist

Show Answer

Solution

According to the solution of Q.30, the minimum value of $F$ is -16 at $(0,4)$.

Hence, the correct option is (b).

32. Corner points of the feasible region for an LPP are $(0,2),(3,0)$, $(6,0),(6,8)$ and $(0,5)$.

Let $F=4 x+6 y$ be the objective function.

The minimum value of $F$ occurs at

(a) $(0,2)$ only

(b) $(3,0)$ only

(c) the mid-point of the line segment joining the points $(0,2)$ and $(3,0)$ only

(d) any point on the line segment joining the points $(0,2)$ and $(3,0)$

Show Answer

Solution

Corner points Value of $F=4 x+6 y$
$(0,2)$ $Z=4(0)+6(2)=12$
$(3,0)$ $Z=4(3)+6(0)=12$
$(6,0)$ $Z=4(6)+6(0)=24$
$(6,8)$ $Z=4(6)+6(8)=72$
$(0,5)$ $Z=4(0)+6(5)=30$

The minimum value of $F$ occurs at any point on the line segment joining the points $(0,2)$ and $(3,0)$.

Hence, the correct option is $(d)$.

33. Refer to Exercise 32, Maximum of $F-$ Minimum of $F=$

(a) 60

(b) 48

(c) 42

(d) 18

Show Answer

Solution

According to the solution of Q. 32 ,

Maximum value of $F-$ Minimum value of $F=72-12=60$

Hence, the correct option is $(a)$.

34. Corner points of the feasible region determined by the system of linear constraints are $(0,3),(1,1)$ and $(3,0)$.

Let $Z=p x+q y$, where $p, q>0$. Condition on $p$ and $q$ so that the minimum of $Z$ occurs at $(3,0)$ and $(1,1)$ is

(a) $p=2 q$

(b) $p=\frac{q}{2}$

(c) $p=3 q$

(d) $p=q$

Show Answer

Solution

Corner points Value of $Z=p x+q y ; p, q>0$
$(0,3)$ $Z=p(0)+q(3)=3 q$
$(1,1)$ $Z=p(1)+q(1)=p+q$
$(3,0)$ $Z=p(3)+q(0)=3 p$

So, condition of $p$ and $q$ so that the minimum of $Z$ occurs at $(3,0)$ and $(1,1)$ is

$p+q=3 p \Rightarrow p-3 p+q=0 \Rightarrow p=\frac{q}{2}$.

Hence, the correct option is (b).

Fillers

35. In a LPP, the linear inequalities or restrictions on the variables are called ……

Show Answer

Solution

constraints.

36. In a LPP, the objective function is always ……

Show Answer

Solution

linear.

37. If the feasible region for a LPP is …… then the optimal value of the objective function $Z=a x+b y$ may or may not exist.

Show Answer

Solution

open unbounded

38. In a LPP, if the objective function $Z=a x+b y$ has the same maximum value at two corner points of the feasible region, then every point on the line segment joining these two points give the same …… value.

Show Answer

Solution

maximum

39. A feasible region of a system of linear inequalities is said to be …… if it can be enclosed within a circle.

Show Answer

Solution

bounded

40. A corner point of a feasible region is a point in the region which is the …… of two boundary lines.

Show Answer

Solution

intersection

41. The feasible region for an LPP is always a …… polygon.

Show Answer

Solution

convex

True/False.

42. If the feasible region for a LPP is unbounded, maximum or minimum of the objective function $Z=a x+b y$ may or may not exist.

Show Answer

Solution

True.

43. Maximum value of the objective function

$Z=a x+b y$ in a LPP always occurs at only one corner point of the feasible region.

Show Answer

Solution

False.

44. In a LPP, the minimum value of the objective function $Z=a x+b y$ is always 0 if the origin is one of the corner point of the feasible region.

Show Answer

Solution

False.

45. In a LPP, the maximum value of the objective function $Z=a x+b y$ is always finite.

Show Answer

Solution

True.



Table of Contents