Linear Programming

Class 12 NCERT

NCERT

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

Solution :

The feasible region determined by the constraints,$x + y \leq 4, x \geq 0, y \geq 0$ is as follows

The corner points of the feasible region are $O ( 0, 0 ) , A (4, 0 ) , \text{and }B (0, 4 )$. The values of $Z$ at these points are as follows.$\\$ $\begin{array}{|c|c|c|c|} \hline \text{Corner point} & Z=3x+4y & \\ \hline O(0,0)& 0 & \\ \hline A(4,0)& 12 &\\ \hline B(0,4) & 16 & \to \text{Maximum}\\ \hline \end{array}$$\\$ Therefore, the maximum value of $Z$ is $16$ at the point $B ( 0, 4 )$

2   Minimise $Z =- 3x + 4y$$\\$ Subject to $ x + 2 y \leq 8,3 x + 2 y \leq 12, x \geq 0, y \geq 0.$

Solution :

The feasible region determined by the system of constraints, $x +2y \leq 8,3x + 2y \geq 12, x \leq 0$ and $y \leq 0,$ is as follows.$\\$

The corner points of the feasible region are $O ( 0, 0 ) , A ( 4, 0 ) , B (2, 3 ) ,$ and $C ( 0, 4 )$ $\\$ The values of $Z$ at these corner points are as follows.$\\$ $\begin{array}{|c|c|c|c|} \hline \text{Corner point} & Z=-3x+4y & \\ \hline O(0,0)& 0 & \\ \hline A(4,0)& -12 & \to \text{Minimum}\\ \hline B(2,3) & 6 & \\ \hline C(0,4)& 16\\ \hline \end{array}$$\\$ $\\$ Therefore, the minimum value of $Z$ is $-12$ at the point $( 4, 0 ).$

3   Maximise $Z = 5x + 3y$ $\\$ Subject to $3 x + 5 y \leq 15,5 x + 2 y \leq 10, x \geq 0, y \geq 0.$

Solution :

The feasible region determined by the system of constraints, $3x + 5y \leq 15, 5x + 2y \leq 10, x \geq 0$ and $y \leq 0 $, are as follows.$\\$

The corner points of the feasible region are $O ( 0, 0 ) , A (2, 0 ) , B ( 0, 3 )$ , and $C(\dfrac{20}{19},\dfrac{45}{19})$$\\$ The values of $Z$ at these corner points are as follows.$\\$ $\begin{array}{|c|c|c|c|} \hline \text{Corner point} & Z=5x+3y & \\ \hline O(0,0)& 0 & \\ \hline A(2,0)& 10 &\\ \hline B(0,3) & 9 & \\ \hline C(\dfrac{20}{19},\dfrac{45}{19})& \dfrac{235}{19}& \to \text{Maximum}\\ \hline \end{array}$$\\$ $\\$ Therefore, the maximum value of $Z$ is $(\dfrac{235}{19})$ at the point $(\dfrac{20}{19},\dfrac{45}{19})$

4   Minimise $Z = 3x + 5y$$\\$ Such that $x + 3 y \leq 3, x + y \geq 2, x , y \geq 0$

Solution :

The feasible region determined by the system of constraints, $x + 3 y \leq 3, x + y \geq 2 $, and $x, y \geq 0 $ , is as follows.$\\$

It can be seen that the feasible region is unbounded.$\\$ The corner points of the feasible region are $A(3,0),B(\dfrac{3}{2},\dfrac{1}{2}),$ and $ C(0,2) $ $\\$ The values of $Z$ at these corner points are as follows.$\\$ $\begin{array}{|c|c|c|c|} \hline \text{Corner point} & Z=3x+5y & \\ \hline A(3,0)& 9 &\\ \hline B(\dfrac{3}{2},\dfrac{1}{2})& 7& \to \text{Smallest}\\ \hline C(0,2) & 10 & \\ \hline \end{array}$$\\$ $\\$ As the feasible region is unbounded, therefore, $7$ may or may not be the minimum value of $Z$.$\\$ For this, we draw the graph of the inequality, $3x + 5y < 7 , $and check whether the resulting half plane has points in common with the feasible region or not.$\\$ It can be seen that the feasible region has no common point with $3x + 5y < 7 $ Therefore, the minimum value of $Z$ is $7$ at $(\dfrac{3}{2},\dfrac{1}{2})$

5   Maximise $Z = 3x + 2y$$\\$ subject to $x + 2 y \leq 10,3 x + y \leq 15, x , y \geq 0 .$

Solution :

The feasible region determined by the constraints, $x + 2y \leq 10,3x + y \leq 15, x \geq 0$ and $y \geq 0$ , is as follows.$\\$

The corner points of the feasible region are $A (5, 0), B (4, 3), $and $C (0, 5).$$\\$ The values of $Z$ at these corner points are as follows.$\\$ $\begin{array}{|c|c|c|c|} \hline \text{Corner point} & Z=3x+2y & \\ \hline A(5,0)& 15 &\\ \hline B(4,3)& 18& \to \text{Maximum}\\ \hline C(0,5) & 10 & \\ \hline \end{array}$$\\$ $\\$ $\\$ Therefore, the maximum value of $Z$ is $18$ at the point $(4, 3).$

6   Minimise $Z = x + 2y$$\\$ Subject to $2 x + y \geq 3, x + 2 y \geq 6, x , y \geq 0 .$

Solution :

The feasible region determined by the constraints, $2 x + y \geq 3, x + 2 y \geq 6, x , y \geq 0 .$ , is as follows.

The corner points of the feasible region are $A ( 6,0 )$ and $B (0, 3 )$ .$\\$ The values of $Z$ at these corner points are as follows.$\\$ $\begin{array}{|c|c|c|} \hline \text{Corner point} & Z=x+2y \\ \hline A(6,0)& 6\\ \hline B(0,3) & 6 \\ \hline \end{array}$ $\\$ It can be seen that the value of $Z$ at points $A$ and $B$ is same. If we take any other point such as $(2, 2)$ on line $x + 2y = 6$, then $Z = 6$$\\$ Thus, the minimum value of $Z$ occurs for more than $2$ points.$\\$ Therefore, the value of $Z$ is minimum at every point on the line, $x + 2y = 6$

7   Minimise and Maximise $Z = 5x + 10y$$\\$ Subject to $x + 2 y \leq120, x + y \geq 60, x - 2 y \geq 0, x , y \geq 0 .$

Solution :

The feasible region determined by the constraints,$\\$ $x + 2 y \leq120, x + y \geq 60, x - 2 y \geq 0, x \text{and} y \geq 0 .$ is as follows.

The corner points of the feasible region are $A (60, 0), B (120, 0), C (60, 30)$, and $D (40, 20).$$\\$ The values of $Z$ at these corner points are as follows.$\\$ $\begin{array}{|c|c|c|c|} \hline \text{Corner point}& Z=5x+10y & \\ \hline A(60,0)&300 &\to \text{Minimum} \\ \hline B(120,0)& 600 & \to \text{Minimum} \\ \hline C(60,30) & 600 & \to \text{Minimum} \\ \hline D(40,20) & 400 & \\ \hline \end{array}$$\\$ The minimum value of $Z$ is $300$ at $(60, 0)$ and the maximum value of $Z$ is $600$ at all the points on the line segment joining $(120, 0)$ and $(60, 30)$.

8   Minimise and Maximise $Z = x + 2y$$\\$ Subject to $x + 2 y \geq 100, 2 x - y \leq 0, 2 x + y \leq 200, x , y \geq 0 $.

Solution :

The feasible region determined by the constraints,$\\$ $x + 2 y \geq 100, 2 x - y \leq 0, 2 x + y \leq 200, x \geq 0,\text{and} y \geq 0 $. is as follows.

The corner points of the feasible region are $\\$ $A ( 6, 0 ),$ and $ B ( 20, 40 ).$$\\$ . The values of $Z$ at these corner points are as follows.$\\$ $\begin{array}{|c|c|c|c|} \hline \text{Corner point} & Z=x+2y \\ \hline A(6,0) & 6 \\ \hline B(0, 3) & 6 \\ \hline \end{array}$$\\$ It can be seen that the value of $Z$ at points $ A$ and $B$ is same. If we take any other point such as $(2, 2)$ on line $ x +2y= 6, $ Then $ Z=6 $ $\\$ Thus, the minimum value of $ Z$ occurs for more than $2$ points. $\\$ Therefore, the value of $Z$ is minimum at every point on the line $, x + 2y = 6$ $\\$

9   Maximise $Z =- x + 2y$ , subject to the constraints: $x \geq 3, x + y \geq 5, x + 2 y \geq 6, y \geq 0 .$

Solution :

The feasible region determined by the constraints, $x \geq 3, x + y \geq 5, x + 2 y \geq 6, \text{and}y \geq 0 .$ is as follows

It can be seen that the feasible region is unbounded.$\\$ The values of $Z$ at corner points $A ( 6, 0 ) , B ( 4, 1 ) ,$ and $C ( 3, 2 )$ are as follows.$\\$ $\begin{array}{|c|c|c|c|} \hline \text{Corner point} & Z=-x+2y \\ \hline A(6,0)& z=-x+2y \\ \hline B(4,1) & z=-2 \\ \hline C(3,2) & z=1\\ \hline \end{array}$$\\$ As the feasible region is unbounded, therefore, $z = 1$ may or may not be the maximum value. For this, we graph the inequality, $ -x + 2y > 1$ , and check whether the resulting half plane has points in common with the feasible region or not. The resulting feasible region has points in common with the feasible region. Therefore, $z = 1$ is not the maximum value $Z$ has no maximum value.

10   Maximise $Z = x +y$ , subject to $x - y \leq - 1, - x + y \geq 0, x , y \leq 0 .$

Solution :

The region determined by the constraints, $x - y \leq - 1, - x + y \geq 0, x , y \leq 0 .$ is as follows.

There is no feasible region and thus, $Z$ has no maximum value.