Chapter 12 Linear Programming EXERCISE 12.1
EXERCISE 12.1
Solve the following Linear Programming Problems graphically:
1. Maximise $Z=3 x+4 y$
subject to the constraints : $x+y \leq 4, x \geq 0, y \geq 0$.
Show Answer
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)$, and $B(0,4)$. The values of $Z$ at these points are as follows.
| Corner point | $\mathbf{Z}=\mathbf{3 x}+\mathbf{4} \boldsymbol{{}y}$ | |
|---|---|---|
| $O(0,0)$ | 0 | |
| $A(4,0)$ | 12 | |
| $B(0,4)$ | 16 | $\longleftarrow$ Maximum |
Therefore, the maximum value of $Z$ is 16 at the point $B(0,4)$.
2. Minimise $Z=-3 x+4 y$
subject to $x+2 y \leq 8,3 x+2 y \leq 12, x \geq 0, y \geq 0$.
Show Answer
Solution
The feasible region determined by the system of constraints, $x+2 y \leq 8,3 x+2 y \leq 12, x \geq$ 0 , and $y \geq 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.
| Corner point | $\mathbf{Z}=\mathbf{- 3 x + 4 y}$ | |
|---|---|---|
| $0(0,0)$ | 0 | |
| $A(4,0)$ | -12 | $\longleftarrow$ Minimum |
| $B(2,3)$ | 6 | |
| $C(0,4)$ | 16 |
Therefore, the minimum value of $Z$ is -12 at the point $(4,0)$.
3. Maximise $Z=5 x+3 y$
subject to $3 x+5 y \leq 15,5 x+2 y \leq 10, x \geq 0, y \geq 0$.
Show Answer
Solution
The feasible region determined by the system of constraints, $3 x+5 y \leq 15$, $5 x+2 y \leq 10, x \geq 0$, and $y \geq 0$, are as follows.
The corner points of the feasible region are $O(0,0), A(2,0), B(0,3)$, and $C(\frac{20}{19}, \frac{45}{19})$. The values of $Z$ at these corner points are as follows.
| Corner point | $\mathbf{Z}=\mathbf{5} \boldsymbol{{}x}+\mathbf{3} \boldsymbol{{}y}$ | |
|---|---|---|
| $O(0,0)$ | 0 | |
| $A(2,0)$ | 10 | |
| $B(0,3)$ | 9 | |
| $C(\frac{20}{19}, \frac{45}{19})$ | $\frac{235}{19}$ | $\longleftarrow$ Maximum |
4. Minimise $Z=3 x+5 y$
such that $x+3 y \geq 3, x+y \geq 2, x, y \geq 0$.
Show Answer
Solution
The feasible region determined by the system of constraints, $x+3 y \geq 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(\frac{3}{2}, \frac{1}{2})$, and $C(0,2)$.
The values of $Z$ at these corner points are as follows.
| Corner point | $\mathbf{Z}=\mathbf{3} \boldsymbol{{}x}+\mathbf{5} \boldsymbol{{}y}$ | |
|---|---|---|
| $A(3,0)$ | 9 | |
| $B(\frac{3}{2}, \frac{1}{2})$ | 7 | $\longleftarrow$Smallest |
| $C(0,2)$ | 10 |
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, $3 x+5 y<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 $3 x+5 y<7$ Therefore,
the minimum value of $Z$ is 7 at $(\frac{3}{2}, \frac{1}{2})$.
5. Maximise $Z=3 x+2 y$
subject to $x+2 y \leq 10,3 x+y \leq 15, x, y \geq 0$.
Show Answer
Solution
The feasible region determined by the constraints, $x+2 y \leq 10,3 x+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.
| Corner point | $\mathbf{Z}=\mathbf{3 x}+\mathbf{2} \boldsymbol{{}y}$ | |
|---|---|---|
| $A(5,0)$ | 15 | |
| $B(4,3)$ | 18 | $\longleftarrow$ Maximum |
| $C(0,5)$ | 10 |
Therefore, the maximum value of $Z$ is 18 at the point $(4,3)$.
6. Minimise $Z=x+2 y$
subject to $2 x+y \geq 3, x+2 y \geq 6, x, y \geq 0$.
Show that the minimum of $Z$ occurs at more than two points.
Show Answer
Solution
The feasible region determined by the constraints, $2 x+y \geq 3, x+2 y \geq 6, x \geq 0$, and $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.
| Corner point | $Z=x+2 y$ |
|---|---|
| $A(6,0)$ | 6 |
| $B(0,3)$ | 6 |
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+2 y=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+2 y=6$
7. Minimise and Maximise $Z=5 x+10 y$
subject to $x+2 y \leq 120, x+y \geq 60, x-2 y \geq 0, x, y \geq 0$.
Show Answer
Solution
The feasible region determined by the constraints, $x+2 y \leq 120, x+y \geq 60, x-2 y \geq$ $0, x \geq 0$, 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.
| Corner point | $\mathbf{Z}=\mathbf{5} \boldsymbol{{}x}+\mathbf{1 0} \boldsymbol{{}y}$ | |
|---|---|---|
| $A(60,0)$ | 300 | $\longleftarrow$ Minimum |
| $B(120,0)$ | 600 | $\longleftarrow$ Maximum |
| $C(60,30)$ | 600 | $\longleftarrow$ Maximum |
| $D(40,20)$ | 400 |
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+2 y$
subject to $x+2 y \geq 100,2 x-y \leq 0,2 x+y \leq 200 ; x, y \geq 0$.
Show Answer
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$, and $y \geq 0$, is as follows.
The corner points of the feasible region are $A(0,50), B(20,40), C(50,100)$, and $D(0$, 200).
The values of $Z$ at these corner points are as follows.
| Corner point | $\mathbf{Z}=\boldsymbol{{}x}+\mathbf{2} \boldsymbol{{}y}$ | |
|---|---|---|
| $A(0,50)$ | 100 | $\longleftarrow$ Minimum |
| $B(20,40)$ | 100 | $\longleftarrow$ Minimum |
| $C(50,100)$ | 250 | |
| $D(0,200)$ | 400 | $\longleftarrow$ Maximum |
The maximum value of $Z$ is 400 at $(0,200)$ and the minimum value of $Z$ is 100 at all the points on the line segment joining the points $(0,50)$ and $(20,40)$.
9. Maximise $Z=-x+2 y$, subject to the constraints:
$$x \geq 3, x+y \geq 5, x+2 y \geq 6, y \geq 0$$
Show Answer
Solution
The feasible region determined by the constraints, $x \geq 3, x+y \geq 5, x+2 y \geq 6$, 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.
| Corner point | $Z=-\boldsymbol{{}x}+\mathbf{2} \boldsymbol{{}y}$ |
|---|---|
| $A(6,0)$ | $Z=-6$ |
| $B(4,1)$ | $Z=-2$ |
| $C(3,2)$ | $Z=1$ |
As the feasible region is unbounded, therefore, $Z=1$ may or may not be the maximum value.
For this, we graph the inequality, $-x+2 y>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 \leq 0, x, y \geq 0$.
Show Answer
Solution
The region determined by the constraints, $x-y \leq-1,-x+y \leq 0, x, y \geq 0$, is as follows.
There is no feasible region and thus, $Z$ has no maximum value.
