Chapter 12: Linear Programming

Solution Maximise $\mathrm{Z}=3 x+4 y$ subject to the constraints:
Step 1. Since constraint (iii) states $x \geq 0, y \geq 0 \Rightarrow$ the feasible region lies in the first quadrant. We build a table of values for the line $\boldsymbol{x}+\boldsymbol{y}=\mathbf{4}$ (from constraint (ii))
$$\begin{array}{|l|l|l|} \hline x & 0 & 4 \\ \hline y & 4 & 0 \\ \hline \end{array}$$
We draw the straight line through $(0,4)$ and $(4,0)$. Now let us test for origin $(x=0, y=$ 0 ) in constraint (ii) $x+y \leq 4$. This gives us $0 \leq 4$ which is true. Therefore region for constraint (ii) is on the origin side of the line. The shaded portion of the graph is the feasible region defined by the given constraints (ii) and (iii). The feasible region OAB is bounded. Step 2. The coordinates of corner points $\mathrm{O}, \mathrm{A}$ and B are ( 0,0 ), $(4,0)$ and $(0,4)$ respectively. Step 3. We now calculate the value of Z at each corner point:
$$\begin{array}{|c|c|} \hline Corner Point & \mathrm{Z}=3 x+4 y \\ \hline \mathrm{O}(0,0) & 0 \\ \mathrm{~A}(4,0) & 12 \\ \mathrm{~B}(0,4) & 16=\mathrm{M} \\ \hline \end{array}$$
← Maximum By the Corner Point Method, Z achieves its maximum value of 16 at corner point $\mathrm{B}(0,4) . \Rightarrow$ Maximum $\mathrm{Z}=16$ at ( 0,4 ).

Solution Minimise $\mathrm{Z}=-3 x+4 y$ subject to: $x+2 y \leq 8 \ldots(i i), 3 x+2 y \leq 12 \ldots(i i i), x \geq 0, y \geq 0 . .(i v)$ Step 1. Since constraint (iv) states $x \geq 0, y \geq 0 \Rightarrow$ the feasible region lies in the first quadrant. We build a table of values for the line $\boldsymbol{x}+\mathbf{2 y}=\mathbf{8}$ (from constraint (ii))
$$\begin{array}{|l|l|l|} \hline x & 0 & 8 \\ \hline y & 4 & 0 \\ \hline \end{array}$$
Draw the line connecting $(0,4)$ and $(8,0)$. Now let us test for origin $(0,0)$ in constraint (ii) which gives $0 \leq$ 8 which is true. So the region for constraint (ii) lies on the origin-side of the line. Values table for the line $\mathbf{3} \boldsymbol{x}+\mathbf{2} \boldsymbol{y}$ = 12 of constraint (iii)
$$\begin{array}{|l|l|l|} \hline x & 0 & 4 \\ \hline y & 6 & 0 \\ \hline \end{array}$$
Draw the line connecting $(0,6)$ and $(4,0)$. Now let us test for origin ( 0,0 ) in constraint (iii) which gives $0 \leq$ 12 and which is true. Similarly, the region for constraint (iii) is on the origin side of the line. The shaded region in the graph is the feasible region formed by constraints (ii) through (iv). The region OABC is bounded. Step 2. The coordinates of corner points O , A and C are ( 0,0 ), $(4,0)$ and $(0,4)$ respectively. To find corner point B — the intersection of the lines
Subtracting gives $2 x=4 \Rightarrow x=\frac{4}{2}=2$. Putting $x=2$ in first equation $2+2 y=8$ ∴ Corner point B is $(2,3)$ Step 3. We now calculate the value of Z at each corner point:
$$\begin{array}{|c|l|} \hline Corner Point & \mathrm{Z}=-3 x+4 y \\ \hline \mathrm{O}(0,0) & 0 \\ \mathrm{~A}(4,0) & -12=m \\ \mathrm{~B}(2,3) & 6 \\ \mathrm{C}(0,4) & 16 \\ \hline \end{array}$$ $\leftarrow$ Minimum



By the Corner Point Method, the minimum value of Z equals -12, attained at $\mathrm{A}(4,0)$. ⇒ Minimum $\mathrm{Z}=-12$ at $(4,0)$.

Solution Maximise $\mathrm{Z}=5 x+3 y$ subject to:
Step 1. Since constraint (iv) states $x \geq 0$ and $y \geq 0$ the feasible region lies entirely in the first quadrant. We build a table of values for the line $3 x+5 y=15$ (from constraint (ii))
$$\begin{array}{|l|l|l|} \hline x & 0 & 5 \\ \hline y & 3 & 0 \\ \hline \end{array}$$
Draw the line connecting $(0,3)$ and $(5,0)$. Let us test for origin $(0,0)$ in constraint (ii) which gives $0 \leq 15$ and which is true. Thus, the region for constraint (ii) includes the origin. Values table for the line $5 x+2 y=$ 10 of constraint (iii).
$$\begin{array}{|l|l|l|} \hline x & 0 & 2 \\ \hline y & 5 & 0 \\ \hline \end{array}$$
Draw the line connecting $(0,5)$ and $(2,0)$. Let us test for origin $(0,0)$ in constraint (iii) which gives $0 \leq 10$ and which is true. The region for constraint (iii) likewise includes the origin. The shaded region represents the feasible area defined by constraints (ii) and (iv). Region OABC is bounded. Step 2. The coordinates of corner points $\mathrm{O}, \mathrm{A}$ and C are ( 0,0 ), $(2,0)$ and $(0,3)$ respectively. To find corner point B — the intersection of the lines
Ist eqn. $\times 2-$ IInd eqn. $\times 5$ gives $-19 x=-20 \Rightarrow x=\frac{20}{19}$ Putting $x=\frac{20}{19}$ in first eqn. $\Rightarrow \quad \frac{60}{19}+5 y=15$



Step 3. We now calculate the value of Z at each corner point:
$$\begin{array}{|c|c|} \hline Corner Point & \mathrm{Z}=5 x+3 y \\ \hline \mathrm{O}(0,0) & 0 \\ \mathrm{~A}(2,0) & 10 \\ \mathrm{~B}\left(\frac{20}{19}, \frac{45}{19}\right) & \frac{100+135}{19}=\frac{235}{19}=\mathrm{M} \\ \mathrm{C}(0,3) & 9 \\ \hline \end{array}$$ $\leftarrow$ Maximum
By the Corner Point Method, Z achieves its maximum value of $\frac{235}{19}$ at corner point $B\left(\frac{20}{19}, \frac{45}{19}\right)$. ⇒ Maximum $\mathrm{Z}=\frac{235}{19}$ at $\left(\frac{20}{19}, \frac{45}{19}\right)$.

Solution Minimise $\mathrm{Z}=3 x+5 y$ such that: $x+3 y \geq 3 \quad \ldots(i i), \quad x+y \geq 2 \ldots(i i i), \quad x, y \geq 0$
Step 1. The constraint (iv) $x, y \geq 0 \Rightarrow$ the feasible region lies in the first quadrant. We build a table of values for the line $x+3 y=3$ (from constraint (ii))
$$\begin{array}{|l|l|l|} \hline x & 0 & 3 \\ \hline y & 1 & 0 \\ \hline \end{array}$$
Draw the line connecting $(0,1)$ and $(3,0)$. Now let us test for origin ( $x=0, y=0$ ) in constraint (ii) $x+3 y \geq 3$, which gives us $0 \geq 3$ and which is not true. Hence, the region for constraint (ii) does not include the origin meaning the feasible half-plane is on the side of the line that excludes the origin. We build a table of values for the line $x+y=2$ (from constraint (iii))
$$\begin{array}{|l|l|l|} \hline x & 0 & 2 \\ \hline y & 2 & 0 \\ \hline \end{array}$$
Draw the line connecting ( 0,2 ) and ( 2,0 ). Now let us test for origin ( $x=0, y=0$ ) in constraint (iii), $x+y \geq 2$, which gives us $0 \geq 2$ and which is not true. Hence, the region for constraint (iii) does not include the origin i.e., the region is on the non-origin side.




The shaded area in the figure represents the feasible region formed by constraints (ii) to (iv). This feasible region is unbounded. Step 2. The coordinates of corner points A and C are $(3,0)$ and ( 0,2 ) respectively.
To find corner point B — the intersection of the lines
Subtracting, $2 y=1 \Rightarrow y=\frac{1}{2}$. Substituting $y = \frac{1}{2}$ into $x+y=2$, we have $x=2-y=2-\frac{1}{2}=\frac{3}{2}$ So corner point B is $\left(\frac{3}{2},\frac{1}{2})$. Step 3. Evaluating Z at every corner point:
$$\begin{array}{|c|l|} \hline Corner Point & \mathrm{Z}=3 x+5 y \\ \hline \mathrm{~A}(3,0) & 9 \\ \mathrm{~B} \left(\frac{3}{2},\frac{1}{2}) & \frac{9}{2}+\frac{5}{2}=7=m \\ \mathrm{C}(0,2) & 10 \\ \hline \end{array}$$ $\leftarrow$ Smallest
From this table, we find that 7 is the smallest value of $Z$ at the corner $\mathrm{B}\left(\frac{3}{2},\frac{1}{2})$. Since the feasible region is unbounded, 7 may or may not be the minimum value of $Z$. Step 4. To confirm, we graph the half-plane $\mathrm{Z} \lt m$ i.e., $\quad 3 x+5 y<7$. Values table for the line $\mathbf{3 x} \boldsymbol{+} \mathbf{5 y} \boldsymbol{=} \mathbf{7}$ corresponding to constraint $3 x+5 y<7$ Let us draw the dotted line joining the
$$\begin{array}{|l|l|l|} \hline x & 0 & \overline{3} \\ \hline y & \overline{7} & 0 \\ \hline \end{array}$$




points $\left(0, \frac{7}{5}\right)$ and $\left(\frac{7}{3}, 0\right)$. This line is to be shown dotted as constraint involves < and not $\leq$, so boundary of line is to be excluded. We test origin $( $x=0, y=0$ )$ in constraint $3 x+5 y<7$, we have $0<7$ which is true. Therefore region for this constraint is on the origin side of the line $3 x+5 y=7$. We observe that the half-plane determined by $\mathrm{Z}\lt m$ has no point in common with the feasible region. Hence $m=7$ is the minimum value of $Z$ attained at the point $B\left(\frac{3}{2}, \frac{1}{2}\right)$. ⇒ Minimum $\mathrm{Z}=7$ at $\left(\frac{3}{2}, \frac{1}{2}\right)$.

Solution Maximise $\mathrm{Z}=3 x+2 y$ subject to:
Step 1. Constraint (iv) $x, y \geq 0 \Rightarrow$ the feasible region lies in the first quadrant. Values table for the boundary line $x+2 y=10$ of constraint (ii):
$$\begin{array}{|c|c|c|} \hline x & 0 & 10 \\ \hline y & 5 & 0 \\ \hline \end{array}$$
Draw the line connecting $(0,5)$ and $(10,0)$. We test origin $( $x=0, y=0$ )$ in constraint (ii), we have $0 \leq 10$ which is true. Therefore, the region for constraint (ii) is on the origin side of this line. We build a table of values for the line $3 x+y=15$ (from constraint (iii))
$$\begin{array}{|c|c|c|} \hline x & 0 & 5 \\ \hline y & 15 & 0 \\ \hline \end{array}$$
Draw the line connecting $(0,15)$ and $(5,0)$. We test origin $( $x=0, y =0$ )$ in constraint (iii), we have $0 \leq 15$ which is true. Therefore, the region for constraint (iii) is on the origin side of this line. The shaded region in the graph is the feasible region formed by constraints (ii) through (iv). The region OABC is bounded.




Step 2. The coordinates of corner points O , A and C are ( 0,0 ), $(5,0)$ and $(0,5)$ respectively. We now find corner point B , intersection of the lines and $\quad 3 x+y=15$ First equation $-2 \times$ second equation gives $-5 x=10-30 \Rightarrow-5 x=-20 \Rightarrow x=4$ Substituting $x = 4$ into $x+2 y=10$, we have $4+2 y=10 \Rightarrow 2 y=6 \Rightarrow y=3$ So corner point B is $\mathrm{B}(4,3)$. Step 3. We now calculate the value of Z at each corner point:
$$\begin{array}{|c|l|} \hline Corner Point & \mathrm{Z}=3 x+2 y \\ \hline \mathrm{O}(0,0) & 0 \\ \mathrm{~A}(5,0) & 15 \\ \mathrm{~B}(4,3) & 18=\mathrm{M} \\ \mathrm{C}(0,5) & 10 \\ \hline \end{array}$$ $\quad \leftarrow$ Maximum
By the Corner Point Method, the maximum value of Z equals 18, attained at $\mathrm{B}(4,3)$. $\Rightarrow$ Maximum $\mathrm{Z}=18$ at $(4,3)$.

Solution Minimise $\mathrm{Z}=x+2 y$ subject to:
Step 1. Constraint (iv) $x, y \geq 0 \Rightarrow$ the feasible region lies in the first quadrant. Values table for the boundary line $2 x+y=3$ of constraint (ii):.
$$\begin{array}{|c|c|c|} \hline x & 0 & \frac{3}{2} \\ \hline y & 3 & 0 \\ \hline \end{array}$$
Draw the line connecting $(0,3)$ and $\left(\frac{3}{2}, 0\right)$. Now let us test for origin ( $x=0, y=0$ ) in constraint (ii) $2 x+y \geq 3$, we have $0 \geq 3$ which is not true. ∴ The region of constraint (ii) is on that side of the line which does not contain the origin meaning the feasible half-plane excludes the origin side. Values table for the boundary line $\boldsymbol{x}+\mathbf{2 y}=\mathbf{6}$ of constraint (ii):.
$$\begin{array}{|l|l|l|} \hline x & 0 & 6 \\ \hline y & 3 & 0 \\ \hline \end{array}$$
Draw the line connecting $(0,3)$ and $(6,0)$.





Now let us test for origin ( $x=0, y=0$ ) in constraint (iii) $x+2 y \geq 6$, we have $0 \geq 6$ which is not true. Hence, the region for constraint (iii) is the region other than the origin side of the line i.e., the half-plane that does not include the origin. The shaded area in the figure represents the feasible region formed by constraints (ii) to (iv). This feasible region is unbounded. Step 2. The coordinates of corner points A and B are (6, 0) and $(0,3)$ respectively.
Step 3. Evaluating Z at every corner point:
$$\begin{array}{|c|c|} \hline Corner Point & \mathrm{Z}=x+2 y \\ \hline \mathrm{~A}(6,0) & 6 \\ \mathrm{~B}(0,3) & 6 \\ \hline \end{array}$$
← Smallest
From the table, Z = 6 is equally the smallest at both corner points. Since the feasible region is unbounded, 6 may or may not be the minimum value of Z . Step 4. To confirm, we graph the half-plane $\mathrm{Z}



value of Z attained at each of the points $\mathrm{A}(6,0)$ and $\mathrm{B}(0,3)$. $\Rightarrow$ Minimum $\mathrm{Z}=6$ at ( 6,0 ) and ( 0,3 ). Note: In fact, $\mathrm{Z}=6$ at all points on the line segment AB for example $\left(1, \frac{5}{2}\right),(2,2),\left(3, \frac{3}{2}\right)$ etc.

Solution Minimise and Maximise $\mathrm{Z}=5 x+10 y$ subject to: $x+2 y \leq 120$ $x+y \geq 60 \ldots$ (iii), $x-2 y \geq 0$ …(iv),
Step 1. Constraint $(v) x, y \geq 0 \Rightarrow$ the feasible region lies in the first quadrant. We build a table of values for the line $\boldsymbol{x} \boldsymbol{+} \mathbf{2 y} \boldsymbol{=} \mathbf{1 2 0}$ (from constraint (ii))
$$\begin{array}{|c|c|c|} \hline x & 0 & 120 \\ \hline y & 60 & 0 \\ \hline \end{array}$$
Draw the line connecting $(0,60)$ and $(120,0)$. We test origin $( $x=0, y=0$ )$ in constraint (iii) $x+2 y \leq 120$ we have $0 \leq 120$ which is true. So the region for constraint (ii) lies on the origin-side of the line
We build a table of values for the line $\boldsymbol{x}+\boldsymbol{y}=\mathbf{6 0}$ (from constraint (iii))
$$\begin{array}{|c|c|c|} \hline x & 0 & 60 \\ \hline y & 60 & 0 \\ \hline \end{array}$$
Draw the line connecting $(0,60)$ and $(60,0)$. Let us test for origin $(x=0, y=0)$ in constraint (iii) $x+y \geq 60$, we have $0 \geq 60$ which is not true. Hence, the region for constraint (iii) is the half-plane on the side of the line that excludes the origin $x+y=60$ (i.e., on the side of the line opposite to the origin side). We build a table of values for the line $\boldsymbol{x} \boldsymbol{-} \mathbf{2 y} \boldsymbol{=} \mathbf{0}$ (from constraint (iv))
$$\begin{array}{|l|l|l|l|} \hline x & 0 & 0 & 60 \\ \hline y & 0 & 0 & 30 \\ \hline \end{array}$$ ( Since the line $x-2 y=0$ passes through the origin, we pick an additional point $(60,30)$ on it). Draw the line connecting $(0,0)$ and $(60,30)$. We test the point $( 60,0 )$ (a non-origin point) in constraint (iv), we have $60 \geq 0$ which is true. Hence, the region for constraint (iv) is the half-plane on that side of the line which containing the point $(60,0)$.





The shaded region in the graph is the feasible region formed by constraints (ii) through (v). The region ABCD is bounded. Step 2. The coordinates of corner points A and B are $(60,0)$ and ( 120,0 ) respectively. Corner point C is the intersection of the line $x-2 y=0$ i.e., $\quad x=2 y$ and $x+2 y=120$. Substituting $x = 2 y$ into $x+2 y=120$, we have $2 y+2 y=120 \Rightarrow 4 y=120$ $\Rightarrow y=30$ and therefore $x=2 y=60$. ∴ Corner point C (60, 30). Similarly for corner point D , putting $x=2 y$ in $x+y=60$, we have $2 y+y=60 \Rightarrow 3 y=60 \Rightarrow y=20$ and therefore $x=2 y=$ 40. Therefore corner point D is $(40,20)$.
Step 3. Evaluating Z at every corner point:
$$\begin{array}{|c|l|} \hline Corner Point & \mathrm{Z}=5 x+10 y \\ \hline { 1 – 2 } \mathrm{~A}(60,0) & 300=\mathrm{m} \\ \mathrm{B}(120,0) & 600 \\ \mathrm{C}(60,30) & 300+300=600=\mathrm{M} \\ \mathrm{D}(40,20) & 400 \\ \hline \end{array}$$ $\leftarrow$ Minimum
Hence, by Corner Point Method, Minimum $Z=300$ at $(60,0)$ Maximum $Z=600$ at $B(120,0)$ and $C(60,30)$ and hence maximum at all the points on the line segment BC joining the points $(120,0)$ and $(60,30)$.

Solution Minimise and Maximise $\mathrm{Z}=x+2 y$ subject to:
Step 1. The constraint $(v) x, y \geq 0 \Rightarrow$ the feasible region lies in the first quadrant. Values table for the line $\boldsymbol{x}+\mathbf{2 y}=\mathbf{1 0 0}$ for constraint (ii).
$$\begin{array}{|c|c|c|} \hline x & 0 & 100 \\ \hline y & 50 & 0 \\ \hline \end{array}$$
Draw the line connecting $(0,50)$ and $(100,0)$. We test origin $( $x=0, y=0$ )$ in constraint (ii) $x+2 y \geq 100$, we have $0 \geq 100$ which is not true. Hence, the region for constraint (i) is that half-plane which does not contain the origin. Values table for the boundary line $2 x-y=0$ i.e., $2 x=y$ of constraint (iii):.
$$\begin{array}{|l|l|l|} \hline x & 0 & 20 \\ \hline y & 0 & 40 \\ \hline \end{array}$$





Draw the line connecting $(0,0)$ and $(20,40)$. Because this line passes through the origin, so we shall have the test for some point say $(100,0)$ other than the origin. Substituting $x = 100$ and $y=0$ into constraint (iii) $2 x-y \leq 0$, we have $200 \leq 0$ which is not true. Hence, the region for constraint (iii) is the half plane on the side of the line which does not contain the point ( 100,0 ). Values table for the boundary line $2 x+y=200$ of constraint (iv):.
$$\begin{array}{|c|c|c|} \hline x & 0 & 100 \\ \hline y & 200 & 0 \\ \hline \end{array}$$
Draw the line connecting $(0,200)$ and $(100,0)$. We test origin $( $x=0, y=0$ )$ in constraint (iv) $2 x+y \leq 200$, we have $0 \leq 200$ which is true. Therefore region for constraint (iv) is the half-plane on origin side of the line. The shaded region in the graph is the feasible region formed by constraints (ii) through (v). The region ABCD is bounded. Step 2. The coordinates of the two corner points are $C(0,200)$ and $\mathrm{D}(0,50)$. Corner point A is the intersection of boundary lines $x+2 y=100$ and $2 x-y=0$ i.e., $y=2 x$. Solving them, putting $y=2 x, x+ 4 x=100$
Therefore corner point A(20, 40). Corner point B is the intersection of the boundary lines $2 x+y=200$ and $2 x-y=0$ i.e., $y=2 x$. Solving them, putting $y=2 x, 2 x+2 x$ $\Rightarrow x=50$ and therefore $y=2 x=100$. Therefore corner point B is $(50,100)$. Step 3. Evaluating Z at every corner point:
$$\begin{array}{|c|l|l|} \hline Corner Point & \mathrm{Z}=x+2 y & \multirow{4}{*}{\leftarrow Minimum } \\ \hline { 1 – 2 } \mathrm{A}(20,40) & 100=m & \\ \mathrm{~B}(50,100) & 250 & \\ \mathrm{C}(0,200) & 400=\mathrm{M} & \leftarrow Maximum \\ \mathrm{D}(0,50) & 100=m & \leftarrow Minimum \\ \hline \end{array}$$
By Corner Point Method, Minimum $\mathrm{Z}=100$ at all the points on the line segment joining the points $(20,40)$ and $(0,50)$. (See Step 3, Example 7, Page 770. Maximum Z = 400 at (0, 200).

Solution Maximise subject to the constraints:
Step 1. Constraint $(v), y \geq 0 \Rightarrow$ Positive side of $y$-axis ⇒ Feasible region is in first and second quadrants. Region for constraint (ii) $\boldsymbol{x} \geq \mathbf{3}$. We know that graph of the line $x=3$ is a vertical line parallel to $y$-axis at a distance 3 from origin along OX . ∴ Region for $x \geq 3$ is the half-plane on right side of the line $x=3$. We build a table of values for the line $\boldsymbol{x}+\boldsymbol{y}=\mathbf{5}$ (from constraint (iii))
$$\begin{array}{|l|l|l|} \hline x & 0 & 5 \\ \hline y & 5 & 0 \\ \hline \end{array}$$
Draw the line connecting $(0,5)$ and $(5,0)$. We test origin $( 0,0 )$ in constraint (ii). Substituting $x = 0$ and $y=0$ into $x+y \geq 5$, we have $0 \geq 5$ which is not true. Hence, the region for constraint (iii) is the half plane on the side of the line that excludes the origin $x+y=5$. Values table for the boundary line $x+2 y=6$ of constraint (iii):
$$\begin{array}{|l|l|l|} \hline x & 0 & 6 \\ \hline y & 3 & 0 \\ \hline \end{array}$$
We test origin $( 0,0 )$ in constraint (iv) $x+2 y \geq 6$, we have $0 \geq 6$ which is not true. ∴ Region for constraint (iv) is again the half plane on the side of the line that excludes the origin $x+2 y=6$. The shaded area in the figure represents the feasible region formed by constraints (ii) to (v). This feasible region is unbounded. Step 2. The coordinates of the corner point A are $(6,0)$. Corner point B is the intersection of the boundary lines
Let us solve them for x and y. Subtracting the two equations $2 y-y=6-5$ or $y=1$. Substituting $y = 1$ into $x+y=5$, we have $x+1=5$ or $x=4$. Therefore, vertex $B$ is $(4,1)$. Corner point C is the intersection of the boundary lines $x+y=5$ and $x=3$.




Solving for x and $y$; putting $x=3$ in $x+y=5 ; 3+y=5$ or $y=2$. Therefore corner point C is $(3,2)$. Step 3. Evaluating Z at every corner point:
$$\begin{array}{|c|c|} \hline Corner Point & \mathrm{Z}=-x+2 y \\ \hline \mathrm{~A}(6,0) & -6 \\ \mathrm{~B}(4,1) & -2 \\ \mathrm{C}(3,2) & 1=\mathrm{M} \\ \hline \end{array}$$
← Maximum From this table, we find that 1 is the maximum value of Z at (3,2). Step 4. Since the feasible region is unbounded, 1 may or may not be the maximum value of $Z$. To confirm, we graph the half-plane $\mathrm{Z}>\mathrm{M}$ i.e., $-x+2 y>1$. Values table for the line $-x+2 y=1$ corresponding to constraint $\mathrm{Z}>\mathrm{M}$ i.e., $-x+2 y>1$.
$$\begin{array}{|c|c|c|} \hline x & 0 & -1 \\ \hline y & \frac{1}{2} & 0 \\ \hline \end{array}$$
Draw a dotted line through $\left(0, \frac{1}{2}\right)$ and $(-1,0)$. A dashed line is used because strict inequality excludes the boundary for this constraint $\mathrm{Z}>\mathrm{M}$. We observe that the half-plane determined by $\mathrm{Z}>\mathrm{M}$ has points in common with the feasible region. Therefore, $\mathrm{Z}=-x+2 y$ has no maximum value subject to the given constraints.

Solution Maximise $\mathrm{Z}=x+y$ subject to:
Step 1. Constraint (iv) $x, y \geq 0$. the feasible region lies entirely in the first quadrant. Values table for the boundary line $x-y=-1$ of constraint (ii):
$$\begin{array}{|c|c|c|} \hline x & 0 & -1 \\ \hline y & 1 & 0 \\ \hline \end{array}$$
Draw the straight line through $(0,1)$ and $(-1,0)$. We test origin $( 0,0 )$ in constraint (ii) $x-y \leq-1$, we have $0 \leq-1$ which is not true. Therefore region for constraint (ii) is the region on that side of the line which is away from the origin (as shown shaded in the figure) Values table for the boundary line $-x+y=0$ i.e., $y=x$ of constraint (iii):
$$\begin{array}{|l|l|l|} \hline x & 0 & 2 \\ \hline y & 0 & 2 \\ \hline \end{array}$$
Draw the line connecting ( 0,0 ) and ( 2,2 ). Let us test for the point $(2,0)$ (say) [and not origin as line passes through $(0,0)]$ in constraint (iii) $-x+y \leq 0$, we have $-2 \leq 0$ which is true.





Hence, the region for constraint (iii) is towards the point $(2,0)$ side of the line shown shaded in the figure). From the figure, we observe that there is no point common in the two shaded regions. Thus, the problem has no feasible region and hence no feasible solution i.e., no maximum value of $Z$.