NCERT Solutions · Class 12 Mathematics Linear Programming

Corner Point Method. For a linear objective function on a bounded feasible region, the maximum and the minimum each occur at a corner (vertex) of the region.The line \(\displaystyle x+y=4\) meets the axes at \(\displaystyle (4,0)\) and \(\displaystyle (0,4)\). Testing the origin: \(\displaystyle 0+0=0\le 4\) is true, so \(\displaystyle x+y\le 4\) is the half-plane containing \(\displaystyle O\). Together with \(\displaystyle x\ge 0,\ y\ge 0\) the feasible region is the closed triangle \(\displaystyle OAB\) with \(\displaystyle O(0,0),\ A(4,0),\ B(0,4)\), which is bounded.Evaluate \(\displaystyle \mathrm{Z}=3x+4y\) at the corners: \[\mathrm{Z}(0,0)=0,\qquad \mathrm{Z}(4,0)=12,\qquad \mathrm{Z}(0,4)=16.\]The largest of these is \(\displaystyle 16\).Maximum \(\displaystyle \mathrm{Z}=16\), attained at the corner \(\displaystyle (0,4)\).

Corner Point Method on a bounded region.Boundary lines: \(\displaystyle x+2y=8\) through \(\displaystyle (8,0)\) and \(\displaystyle (0,4)\); \(\displaystyle 3x+2y=12\) through \(\displaystyle (4,0)\) and \(\displaystyle (0,6)\). The origin satisfies both inequalities \(\displaystyle (0\le 8,\ 0\le 12)\), so each feasible half-plane is the one containing \(\displaystyle O\).Which axis intercepts actually survive matters here: \(\displaystyle (8,0)\) fails \(\displaystyle 3x+2y\le 12\) and \(\displaystyle (0,6)\) fails \(\displaystyle x+2y\le 8\), so the corners on the axes are \(\displaystyle (4,0)\) and \(\displaystyle (0,4)\).The two lines meet where \[(3x+2y)-(x+2y)=12-8\ \Rightarrow\ 2x=4\ \Rightarrow\ x=2,\qquad y=\frac{8-2}{2}=3,\] giving \(\displaystyle (2,3)\).Evaluate \(\displaystyle \mathrm{Z}=-3x+4y\): \[\mathrm{Z}(0,0)=0,\quad \mathrm{Z}(4,0)=-12,\quad \mathrm{Z}(2,3)=-6+12=6,\quad \mathrm{Z}(0,4)=16.\]Minimum \(\displaystyle \mathrm{Z}=-12\), attained at \(\displaystyle (4,0)\).

Corner Point Method on a bounded region.Boundary lines: \(\displaystyle 3x+5y=15\) through \(\displaystyle (5,0)\) and \(\displaystyle (0,3)\); \(\displaystyle 5x+2y=10\) through \(\displaystyle (2,0)\) and \(\displaystyle (0,5)\). The origin satisfies both, so both feasible half-planes contain \(\displaystyle O\). On the \(\displaystyle x\)-axis \(\displaystyle (5,0)\) fails \(\displaystyle 5x+2y\le 10\), so the corner there is \(\displaystyle (2,0)\); on the \(\displaystyle y\)-axis \(\displaystyle (0,5)\) fails \(\displaystyle 3x+5y\le 15\), so the corner there is \(\displaystyle (0,3)\).Intersection of the two lines: multiply \(\displaystyle 3x+5y=15\) by \(\displaystyle 2\) and \(\displaystyle 5x+2y=10\) by \(\displaystyle 5\), \[6x+10y=30,\qquad 25x+10y=50\ \Rightarrow\ 19x=20\ \Rightarrow\ x=\frac{20}{19},\] \[y=\frac{15-3\cdot\dfrac{20}{19}}{5}=\frac{\dfrac{285-60}{19}}{5}=\frac{45}{19}.\]Evaluate \(\displaystyle \mathrm{Z}=5x+3y\): \[\mathrm{Z}(0,0)=0,\quad \mathrm{Z}(2,0)=10,\quad \mathrm{Z}\!\left(\tfrac{20}{19},\tfrac{45}{19}\right)=\frac{100+135}{19}=\frac{235}{19},\quad \mathrm{Z}(0,3)=9.\] Since \(\displaystyle \dfrac{235}{19}\approx 12.37\) exceeds \(\displaystyle 10\) and \(\displaystyle 9\):Maximum \(\displaystyle \mathrm{Z}=\dfrac{235}{19}\), attained at \(\displaystyle \left(\dfrac{20}{19},\dfrac{45}{19}\right)\).

Corner Point Method with the unbounded-region test. If the feasible region is unbounded, the smallest corner value \(\displaystyle m\) is the minimum only if the open half-plane \(\displaystyle \mathrm{Z}<m\) has no point in common with the feasible region.Boundary lines: \(\displaystyle x+3y=3\) through \(\displaystyle (3,0)\) and \(\displaystyle (0,1)\); \(\displaystyle x+y=2\) through \(\displaystyle (2,0)\) and \(\displaystyle (0,2)\). The origin fails both \(\displaystyle (0\ge 3\) and \(\displaystyle 0\ge 2\) are false\(\displaystyle )\), so the feasible half-planes lie away from the origin, and the region is unbounded.Corners: on the \(\displaystyle x\)-axis, \(\displaystyle x\ge 3\) and \(\displaystyle x\ge 2\) force \(\displaystyle (3,0)\); on the \(\displaystyle y\)-axis, \(\displaystyle y\ge 1\) and \(\displaystyle y\ge 2\) force \(\displaystyle (0,2)\); and the lines meet where \[(x+3y)-(x+y)=3-2\ \Rightarrow\ 2y=1\ \Rightarrow\ y=\tfrac12,\qquad x=2-\tfrac12=\tfrac32.\]Evaluate \(\displaystyle \mathrm{Z}=3x+5y\): \[\mathrm{Z}(3,0)=9,\qquad \mathrm{Z}\!\left(\tfrac32,\tfrac12\right)=\tfrac92+\tfrac52=7,\qquad \mathrm{Z}(0,2)=10.\]Smallest corner value \(\displaystyle m=7\). Test \(\displaystyle 3x+5y<7\): for any feasible point, \[3x+5y=(x+3y)+2(x+y)\ \ge\ 3+2(2)=7,\] so the open half-plane \(\displaystyle 3x+5y<7\) contains no feasible point and \(\displaystyle 7\) is genuinely the minimum.Minimum \(\displaystyle \mathrm{Z}=7\), attained at \(\displaystyle \left(\dfrac32,\dfrac12\right)\).

Corner Point Method on a bounded region.Boundary lines: \(\displaystyle x+2y=10\) through \(\displaystyle (10,0)\) and \(\displaystyle (0,5)\); \(\displaystyle 3x+y=15\) through \(\displaystyle (5,0)\) and \(\displaystyle (0,15)\). The origin satisfies both, so both feasible half-planes contain \(\displaystyle O\). On the \(\displaystyle x\)-axis \(\displaystyle (10,0)\) fails \(\displaystyle 3x+y\le 15\), leaving \(\displaystyle (5,0)\); on the \(\displaystyle y\)-axis \(\displaystyle (0,15)\) fails \(\displaystyle x+2y\le 10\), leaving \(\displaystyle (0,5)\).Intersection: from \(\displaystyle 3x+y=15\), \(\displaystyle y=15-3x\); substituting into \(\displaystyle x+2y=10\), \[x+2(15-3x)=10\ \Rightarrow\ -5x=-20\ \Rightarrow\ x=4,\qquad y=15-12=3.\]Evaluate \(\displaystyle \mathrm{Z}=3x+2y\): \[\mathrm{Z}(0,0)=0,\quad \mathrm{Z}(5,0)=15,\quad \mathrm{Z}(4,3)=12+6=18,\quad \mathrm{Z}(0,5)=10.\]Maximum \(\displaystyle \mathrm{Z}=18\), attained at \(\displaystyle (4,3)\).

Corner Point Method with the unbounded-region test.Boundary lines: \(\displaystyle 2x+y=3\) through \(\displaystyle \left(\tfrac32,0\right)\) and \(\displaystyle (0,3)\); \(\displaystyle x+2y=6\) through \(\displaystyle (6,0)\) and \(\displaystyle (0,3)\). The origin fails both, so the feasible half-planes lie away from the origin and the region is unbounded.Note the two lines meet on the \(\displaystyle y\)-axis: solving \(\displaystyle 2x+y=3\) and \(\displaystyle x+2y=6\) gives \(\displaystyle 4x+2y=6\), and subtracting \(\displaystyle x+2y=6\) gives \(\displaystyle 3x=0\), so \(\displaystyle x=0,\ y=3\). Also \(\displaystyle \left(\tfrac32,0\right)\) fails \(\displaystyle x+2y\ge 6\), so on the \(\displaystyle x\)-axis the corner is \(\displaystyle (6,0)\).The corners are therefore \(\displaystyle A(0,3)\) and \(\displaystyle B(6,0)\) only.Evaluate \(\displaystyle \mathrm{Z}=x+2y\): \[\mathrm{Z}(0,3)=0+6=6,\qquad \mathrm{Z}(6,0)=6+0=6.\]Smallest corner value \(\displaystyle m=6\). Test \(\displaystyle x+2y<6\): this directly contradicts the constraint \(\displaystyle x+2y\ge 6\), so the open half-plane contains no feasible point and \(\displaystyle 6\) is the minimum.Because the two corner values are equal, the minimum is attained at every point of the boundary segment \(\displaystyle AB\), which lies on the line \(\displaystyle x+2y=6\); every such point gives \(\displaystyle \mathrm{Z}=6\). For instance \(\displaystyle (0,3),\ (2,2),\ (4,1),\ (6,0)\) all give \(\displaystyle \mathrm{Z}=6\).Minimum \(\displaystyle \mathrm{Z}=6\), attained at every point of the segment joining \(\displaystyle (0,3)\) and \(\displaystyle (6,0)\) — infinitely many points, so certainly at more than two points.

Corner Point Method on a bounded region.Rewrite \(\displaystyle x-2y\ge 0\) as \(\displaystyle y\le \tfrac{x}{2}\): the feasible points lie below the line \(\displaystyle x=2y\) (test \(\displaystyle (2,0)\): \(\displaystyle 2-0=2\ge 0\), true).Boundary lines and corners: The region is bounded (it is the quadrilateral \(\displaystyle (60,0),(120,0),(60,30),(40,20)\)).Evaluate \(\displaystyle \mathrm{Z}=5x+10y\): \[\mathrm{Z}(60,0)=300,\quad \mathrm{Z}(120,0)=600,\quad \mathrm{Z}(60,30)=300+300=600,\quad \mathrm{Z}(40,20)=200+200=400.\]The maximum value \(\displaystyle 600\) occurs at two corners, so it occurs at every point of the segment joining them; that segment lies on \(\displaystyle x+2y=120\), i.e. on \(\displaystyle 5x+10y=600\).Minimum \(\displaystyle \mathrm{Z}=300\) at \(\displaystyle (60,0)\); maximum \(\displaystyle \mathrm{Z}=600\) at every point of the segment joining \(\displaystyle (120,0)\) and \(\displaystyle (60,30)\).

Corner Point Method on a bounded region.Rewrite \(\displaystyle 2x-y\le 0\) as \(\displaystyle y\ge 2x\): feasible points lie above the line \(\displaystyle y=2x\) (test \(\displaystyle (0,1)\): \(\displaystyle -1\le 0\), true). Also \(\displaystyle x+2y\ge 100\) is the side of \(\displaystyle x+2y=100\) away from the origin, and \(\displaystyle 2x+y\le 200\) is the side containing the origin.Corners (all have \(\displaystyle x\ge 0\); the constraint \(\displaystyle y\ge 2x\) keeps the region to the left of \(\displaystyle y=2x\)): The region is bounded.Evaluate \(\displaystyle \mathrm{Z}=x+2y\): \[\mathrm{Z}(0,50)=100,\quad \mathrm{Z}(20,40)=20+80=100,\quad \mathrm{Z}(50,100)=50+200=250,\quad \mathrm{Z}(0,200)=400.\]The minimum value \(\displaystyle 100\) occurs at two corners, hence at every point of the segment joining them; that segment lies on the line \(\displaystyle x+2y=100\).Minimum \(\displaystyle \mathrm{Z}=100\) at every point of the segment joining \(\displaystyle (0,50)\) and \(\displaystyle (20,40)\); maximum \(\displaystyle \mathrm{Z}=400\) at \(\displaystyle (0,200)\).

Corner Point Method with the unbounded-region test. If the region is unbounded, the largest corner value \(\displaystyle M\) is the maximum only if the open half-plane \(\displaystyle \mathrm{Z}>M\) has no point in common with the feasible region.Constraints \(\displaystyle x\ge 3,\ x+y\ge 5,\ x+2y\ge 6,\ y\ge 0\). Every constraint is a \(\displaystyle \ge\) type with no upper bound on \(\displaystyle y\), so the region is unbounded.Corners: Evaluate \(\displaystyle \mathrm{Z}=-x+2y\): \[\mathrm{Z}(6,0)=-6,\qquad \mathrm{Z}(4,1)=-4+2=-2,\qquad \mathrm{Z}(3,2)=-3+4=1.\]Largest corner value \(\displaystyle M=1\). Now apply the test on \(\displaystyle -x+2y>1\): the point \(\displaystyle (3,100)\) satisfies \(\displaystyle x\ge3,\ x+y=103\ge 5,\ x+2y=203\ge 6,\ y\ge 0\), so it is feasible, yet \(\displaystyle \mathrm{Z}=-3+200=197>1\). The open half-plane does meet the region. More generally, along \(\displaystyle x=3\) the value \(\displaystyle \mathrm{Z}=-3+2y\) increases without bound as \(\displaystyle y\to\infty\).Z has no maximum value: it is unbounded above on this feasible region.

First convert the constraints to explicit \(\displaystyle y\) form, because the two of them turn out to be incompatible. \[x-y\le -1\ \Longleftrightarrow\ y\ge x+1,\qquad -x+y\le 0\ \Longleftrightarrow\ y\le x.\]A feasible point would have to satisfy both, i.e. \[x+1\ \le\ y\ \le\ x\ \Longrightarrow\ x+1\le x\ \Longrightarrow\ 1\le 0,\] which is false. Graphically, \(\displaystyle y=x+1\) and \(\displaystyle y=x\) are parallel lines (both of slope \(\displaystyle 1\)); the shaded region for \(\displaystyle y\ge x+1\) lies above the upper line and the shaded region for \(\displaystyle y\le x\) lies below the lower line, so the two shadings never overlap — even before imposing \(\displaystyle x\ge 0,\ y\ge 0\).The feasible region is therefore empty.There is no feasible solution, so \(\displaystyle \mathrm{Z}=x+y\) has no maximum value.