## 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.