Class 12: Linear Programming

$\displaystyle \text{Solve each of the following linear programming problems by graphical method.}$

$\displaystyle \textbf{Question 1: }~\text{Maximize }Z=5x+3y$
$\displaystyle \text{Subject to }3x+5y\le 15$
$\displaystyle 5x+2y\le 10$
$\displaystyle x,y\ge 0$
$\displaystyle \text{Answer:}$
$\displaystyle \text{Converting the inequalities into equations, we obtain the straight lines:}$
$\displaystyle 3x+5y=15,\ \ 5x+2y=10,\ \ x=0,\ \ y=0$
$\displaystyle \text{These represent straight lines in the }xy\text{-plane.}$
$\displaystyle \textbf{(1) Line }3x+5y=15\text{:}$
$\displaystyle \text{It meets the }x\text{-axis at }A_1(5,0)\text{ and the }y\text{-axis at }B_1(0,3).$
$\displaystyle \textbf{(2) Line }5x+2y=10\text{:}$
$\displaystyle \text{It meets the }x\text{-axis at }A_2(2,0)\text{ and the }y\text{-axis at }B_2(0,5).$
$\displaystyle \text{Also, }x=0\text{ is the }y\text{-axis and }y=0\text{ is the }x\text{-axis.}$
$\displaystyle \text{The feasible region lies in the first quadrant and satisfies both inequalities.}$
$\displaystyle \textbf{Corner points of the feasible region are obtained as follows:}$
$\displaystyle O(0,0)$
$\displaystyle \text{On }y=0,\ 3x\le 15\text{ and }5x\le 10\Rightarrow x\le 2\Rightarrow P(2,0)$
$\displaystyle \text{On }x=0,\ 5y\le 15\Rightarrow y\le 3\Rightarrow Q(0,3)$
$\displaystyle \text{Intersection of }3x+5y=15\text{ and }5x+2y=10:$
$\displaystyle 3x+5y=15$
$\displaystyle 5x+2y=10$
$\displaystyle \Rightarrow y=5-\frac{5}{2}x$
$\displaystyle 3x+5\left(5-\frac{5}{2}x\right)=15$
$\displaystyle 3x+25-\frac{25}{2}x=15$
$\displaystyle -\frac{19}{2}x=-10\Rightarrow x=\frac{20}{19}$
$\displaystyle y=5-\frac{5}{2}\cdot\frac{20}{19}=\frac{45}{19}$
$\displaystyle \Rightarrow R\left(\frac{20}{19},\frac{45}{19}\right)$
$\displaystyle \text{Hence the corner points are }O(0,0),\ P(2,0),\ R\left(\frac{20}{19},\frac{45}{19}\right),\ Q(0,3).$
$\displaystyle \textbf{Now, take a constant value (say }10\text{) for }Z. \text{ Putting }Z=10\text{ in }Z=5x+3y, \text{ we get }5x+3y=10.$
$\displaystyle \text{This line meets the }x\text{-axis at }(2,0)\text{ and the }y\text{-axis at }\left(0,\frac{10}{3}\right).$
$\displaystyle \text{Move this line parallel to itself in the increasing direction of }Z\text{ (away from the origin).}$
$\displaystyle \text{The last point where it touches the feasible region will be a corner point giving the maximum }Z.$
$\displaystyle \textbf{Value of }Z\text{ at corner points:}$
$\displaystyle Z(0,0)=5(0)+3(0)=0$
$\displaystyle Z(2,0)=5(2)+3(0)=10$
$\displaystyle Z(0,3)=5(0)+3(3)=9$
$\displaystyle Z\left(\frac{20}{19},\frac{45}{19}\right)=5\cdot\frac{20}{19}+3\cdot\frac{45}{19}=\frac{235}{19}$
$\displaystyle \textbf{Therefore, the maximum value is }Z_{\max}=\frac{235}{19}\approx 12.368$
$\displaystyle \textbf{at }x=\frac{20}{19}\approx 1.053,\ \ y=\frac{45}{19}\approx 2.368.$

$\displaystyle \textbf{Question 2: }~\text{Maximize }Z=9x+3y$
$\displaystyle \text{Subject to }2x+3y\le 13$
$\displaystyle 3x+y\le 5$
$\displaystyle x,y\ge 0$
$\displaystyle \text{Answer:}$
$\displaystyle \text{Converting the inequalities into equations, we obtain the straight lines:}$
$\displaystyle 2x+3y=13,\ \ 3x+y=5,\ \ x=0,\ \ y=0$
$\displaystyle \text{These represent straight lines in the }xy\text{-plane.}$
$\displaystyle \textbf{(1) Line }2x+3y=13\text{:}$
$\displaystyle \text{It meets the }x\text{-axis at }A_1\left(\frac{13}{2},0\right)\text{ and the }y\text{-axis at }B_1\left(0,\frac{13}{3}\right).$
$\displaystyle \textbf{(2) Line }3x+y=5\text{:}$
$\displaystyle \text{It meets the }x\text{-axis at }A_2\left(\frac{5}{3},0\right)\text{ and the }y\text{-axis at }B_2(0,5).$
$\displaystyle \text{Also, }x=0\text{ is the }y\text{-axis and }y=0\text{ is the }x\text{-axis.}$
$\displaystyle \text{The feasible region lies in the first quadrant and satisfies both inequalities.}$
$\displaystyle \textbf{Corner points of the feasible region are obtained as follows:}$
$\displaystyle O(0,0)$
$\displaystyle \text{On }y=0,\ 2x\le 13\text{ and }3x\le 5\Rightarrow x\le \frac{5}{3}\Rightarrow P\left(\frac{5}{3},0\right)$
$\displaystyle \text{On }x=0,\ 3y\le 13\Rightarrow y\le \frac{13}{3}\Rightarrow Q\left(0,\frac{13}{3}\right)$
$\displaystyle \text{Intersection of }2x+3y=13\text{ and }3x+y=5:$
$\displaystyle 3x+y=5\Rightarrow y=5-3x$
$\displaystyle 2x+3(5-3x)=13$
$\displaystyle 2x+15-9x=13$
$\displaystyle -7x=-2\Rightarrow x=\frac{2}{7}$
$\displaystyle y=5-3\cdot\frac{2}{7}=\frac{29}{7}$
$\displaystyle \Rightarrow R\left(\frac{2}{7},\frac{29}{7}\right)$
$\displaystyle \text{Hence the corner points are }O(0,0),\ P\left(\frac{5}{3},0\right),\ R\left(\frac{2}{7},\frac{29}{7}\right),\ Q\left(0,\frac{13}{3}\right).$
$\displaystyle \textbf{Now, take a constant value (say }15\text{) for }Z. \text{ Putting }Z=15\text{ in }Z=9x+3y, \text{ we get }9x+3y=15,$
$\displaystyle \text{i.e. }3x+y=5.$
$\displaystyle \text{Thus the objective line is parallel to (and same as) the constraint line }3x+y=5.$
$\displaystyle \text{Move the line }9x+3y=k\text{ parallel to itself away from the origin; the maximum occurs on the boundary } \\ 3x+y=5\text{ within the feasible region.}$
$\displaystyle \textbf{Value of }Z\text{ at corner points:}$
$\displaystyle Z(0,0)=9(0)+3(0)=0$
$\displaystyle Z\left(\frac{5}{3},0\right)=9\cdot\frac{5}{3}+3(0)=15$
$\displaystyle Z\left(0,\frac{13}{3}\right)=9(0)+3\cdot\frac{13}{3}=13$
$\displaystyle Z\left(\frac{2}{7},\frac{29}{7}\right)=9\cdot\frac{2}{7}+3\cdot\frac{29}{7}=\frac{105}{7}=15$
$\displaystyle \textbf{Therefore, the maximum value is }Z_{\max}=15.$
$\displaystyle \textbf{It occurs at infinitely many points on the line segment joining }P\left(\frac{5}{3},0\right)\text{ and }R\left(\frac{2}{7},\frac{29}{7}\right) \\ \text{ (i.e., on }3x+y=5\text{ within the feasible region).}$

$\displaystyle \textbf{Question 3: }~\text{Minimize }Z=18x+10y$
$\displaystyle \text{Subject to }4x+y\ge 20$
$\displaystyle 2x+3y\ge 30$
$\displaystyle x,y\ge 0$
$\displaystyle \text{Answer:}$
$\displaystyle \text{Converting the inequalities into equations, we obtain the straight lines:}$
$\displaystyle 4x+y=20,\ \ 2x+3y=30,\ \ x=0,\ \ y=0$
$\displaystyle \text{These represent straight lines in the }xy\text{-plane.}$
$\displaystyle \textbf{(1) Line }4x+y=20\text{:}$
$\displaystyle \text{It meets the }x\text{-axis at }A_1(5,0)\text{ and the }y\text{-axis at }B_1(0,20).$
$\displaystyle \textbf{(2) Line }2x+3y=30\text{:}$
$\displaystyle \text{It meets the }x\text{-axis at }A_2(15,0)\text{ and the }y\text{-axis at }B_2(0,10).$
$\displaystyle \text{Also, }x=0\text{ is the }y\text{-axis and }y=0\text{ is the }x\text{-axis.}$
$\displaystyle \text{Since both inequalities are of type }\ge,\ \text{the feasible region lies in the first quadrant and is the region \textit{above} both lines.}$
$\displaystyle \textbf{Corner points of the feasible region are obtained as follows:}$
$\displaystyle \text{Intersection of }4x+y=20\text{ and }2x+3y=30:$
$\displaystyle 4x+y=20\Rightarrow y=20-4x$
$\displaystyle 2x+3(20-4x)=30$
$\displaystyle 2x+60-12x=30$
$\displaystyle -10x=-30\Rightarrow x=3$
$\displaystyle y=20-4(3)=8$
$\displaystyle \Rightarrow P(3,8)$
$\displaystyle \text{On }y=0:\ 4x\ge 20\Rightarrow x\ge 5,\ \ 2x\ge 30\Rightarrow x\ge 15\Rightarrow Q(15,0)\text{ is a corner point.}$
$\displaystyle \text{On }x=0:\ y\ge 20,\ \ 3y\ge 30\Rightarrow y\ge 10\Rightarrow R(0,20)\text{ is a corner point.}$
$\displaystyle \textbf{Now, take a constant value (say }200\text{) for }Z. \text{ Putting }Z=200\text{ in }Z=18x+10y, \text{ we get }18x+10y=200.$
$\displaystyle \text{Move the line }18x+10y=k\text{ parallel to itself towards the origin (decreasing direction of }Z\text{).}$
$\displaystyle \text{The minimum value occurs at the first point where this line touches the feasible region, i.e., at a corner point.}$
$\displaystyle \textbf{Value of }Z\text{ at corner points:}$
$\displaystyle Z(0,20)=18(0)+10(20)=200$
$\displaystyle Z(15,0)=18(15)+10(0)=270$
$\displaystyle Z(3,8)=18(3)+10(8)=54+80=134$
$\displaystyle \textbf{Therefore, the minimum value is }Z_{\min}=134$
$\displaystyle \textbf{at }x=3,\ y=8.$

$\displaystyle \textbf{Question 4: }~\text{Maximize }Z=50x+30y$
$\displaystyle \text{Subject to }2x+y\le 18$
$\displaystyle 3x+2y\le 34$
$\displaystyle x,y\ge 0$
$\displaystyle \text{Answer:}$
$\displaystyle \text{Converting the inequalities into equations, we obtain the straight lines:}$
$\displaystyle 2x+y=18,\ \ 3x+2y=34,\ \ x=0,\ \ y=0$
$\displaystyle \text{These represent straight lines in the }xy\text{-plane.}$
$\displaystyle \textbf{(1) Line }2x+y=18\text{:}$
$\displaystyle \text{It meets the }x\text{-axis at }A_1(9,0)\text{ and the }y\text{-axis at }B_1(0,18).$
$\displaystyle \textbf{(2) Line }3x+2y=34\text{:}$
$\displaystyle \text{It meets the }x\text{-axis at }A_2\left(\frac{34}{3},0\right)\text{ and the }y\text{-axis at }B_2(0,17).$
$\displaystyle \text{Also, }x=0\text{ is the }y\text{-axis and }y=0\text{ is the }x\text{-axis.}$
$\displaystyle \text{The feasible region lies in the first quadrant and satisfies both inequalities.}$
$\displaystyle \textbf{Corner points of the feasible region are obtained as follows:}$
$\displaystyle O(0,0)$
$\displaystyle \text{On }y=0,\ 2x\le 18\Rightarrow x\le 9,\ \ 3x\le 34\Rightarrow x\le \frac{34}{3}\Rightarrow P(9,0)$
$\displaystyle \text{On }x=0,\ y\le 18,\ \ 2y\le 34\Rightarrow y\le 17\Rightarrow Q(0,17)$
$\displaystyle \text{Intersection of }2x+y=18\text{ and }3x+2y=34:$
$\displaystyle 2x+y=18\Rightarrow y=18-2x$
$\displaystyle 3x+2(18-2x)=34$
$\displaystyle 3x+36-4x=34$
$\displaystyle -x=-2\Rightarrow x=2$
$\displaystyle y=18-2(2)=14$
$\displaystyle \Rightarrow R(2,14)$
$\displaystyle \text{Hence the corner points are }O(0,0),\ P(9,0),\ R(2,14),\ Q(0,17).$
$\displaystyle \textbf{Now, take a constant value (say }300\text{) for }Z. \text{ Putting }Z=300\text{ in }Z=50x+30y, \text{ we get }50x+30y=300.$
$\displaystyle \text{Move the line }50x+30y=k\text{ parallel to itself in the increasing direction of }Z\text{ (away from the origin).}$
$\displaystyle \text{The maximum value occurs at the last point where this line touches the feasible region, i.e., at a corner point.}$
$\displaystyle \textbf{Value of }Z\text{ at corner points:}$
$\displaystyle Z(0,0)=50(0)+30(0)=0$
$\displaystyle Z(9,0)=50(9)+30(0)=450$
$\displaystyle Z(0,17)=50(0)+30(17)=510$
$\displaystyle Z(2,14)=50(2)+30(14)=100+420=520$
$\displaystyle \textbf{Therefore, the maximum value is }Z_{\max}=520$
$\displaystyle \textbf{at }x=2,\ y=14.$

$\displaystyle \textbf{Question 5: }~\text{Maximize }Z=4x+3y$
$\displaystyle \text{Subject to }3x+4y\le 24$
$\displaystyle 8x+6y\le 48$
$\displaystyle x\le 5$
$\displaystyle y\le 6$
$\displaystyle x,y\ge 0$
$\displaystyle \text{Answer:}$
$\displaystyle \text{Converting the inequalities into equations, we obtain the straight lines:}$
$\displaystyle 3x+4y=24,\ \ 8x+6y=48,\ \ x=5,\ \ y=6,\ \ x=0,\ \ y=0$
$\displaystyle \text{These represent straight lines in the }xy\text{-plane.}$
$\displaystyle \textbf{(1) Line }3x+4y=24\text{:}$
$\displaystyle \text{It meets the }x\text{-axis at }A_1(8,0)\text{ and the }y\text{-axis at }B_1(0,6).$
$\displaystyle \textbf{(2) Line }8x+6y=48\text{:}$
$\displaystyle \text{It meets the }x\text{-axis at }A_2(6,0)\text{ and the }y\text{-axis at }B_2(0,8).$
$\displaystyle \text{Also, }x=5\text{ and }y=6\text{ are the boundary lines, and }x=0,\ y=0\text{ are the coordinate axes.}$
$\displaystyle \text{The feasible region lies in the first quadrant and satisfies all the inequalities.}$
$\displaystyle \textbf{Corner points of the feasible region are obtained as follows:}$
$\displaystyle O(0,0)$
$\displaystyle \text{On }y=0:\ 3x\le 24,\ 8x\le 48,\ x\le 5\Rightarrow x\le 5\Rightarrow P(5,0)$
$\displaystyle \text{On }x=0:\ 4y\le 24,\ y\le 6\Rightarrow y\le 6\Rightarrow Q(0,6)$
$\displaystyle \text{Intersection of }x=5\text{ with }8x+6y=48:$
$\displaystyle 8(5)+6y=48\Rightarrow 40+6y=48\Rightarrow y=\frac{4}{3}$
$\displaystyle \Rightarrow R\left(5,\frac{4}{3}\right)$
$\displaystyle \text{Intersection of }3x+4y=24\text{ and }8x+6y=48:$
$\displaystyle 8x+6y=48\Rightarrow 4x+3y=24$
$\displaystyle 3x+4y=24$
$\displaystyle 4x+3y=24$
$\displaystyle \Rightarrow x=\frac{24}{7},\ y=\frac{24}{7}$
$\displaystyle \Rightarrow S\left(\frac{24}{7},\frac{24}{7}\right)$
$\displaystyle \text{Hence the corner points are }O(0,0),\ P(5,0),\ R\left(5,\frac{4}{3}\right),\ S\left(\frac{24}{7},\frac{24}{7}\right),\ Q(0,6).$
$\displaystyle \textbf{Now, take a constant value (say }24\text{) for }Z. \text{ Putting }Z=24\text{ in } \\ Z=4x+3y, \text{ we get }4x+3y=24.$
$\displaystyle \text{But }8x+6y=48\Rightarrow 4x+3y=24,\ \text{so the objective line is the same as the constraint line } \\ 8x+6y=48.$
$\displaystyle \text{Move the line }4x+3y=k\text{ parallel to itself away from the origin; the maximum} \\ \text{occurs on the boundary }4x+3y=24\text{ within the feasible region.}$
$\displaystyle \textbf{Value of }Z\text{ at corner points:}$
$\displaystyle Z(0,0)=0$
$\displaystyle Z(5,0)=4(5)+3(0)=20$
$\displaystyle Z(0,6)=4(0)+3(6)=18$
$\displaystyle Z\left(5,\frac{4}{3}\right)=4(5)+3\cdot\frac{4}{3}=20+4=24$
$\displaystyle Z\left(\frac{24}{7},\frac{24}{7}\right)=4\cdot\frac{24}{7}+3\cdot\frac{24}{7}=24$
$\displaystyle \textbf{Therefore, the maximum value is }Z_{\max}=24.$
$\displaystyle \textbf{It occurs at infinitely many points on the line segment joining }R\left(5,\frac{4}{3}\right)\text{ and } \\ S\left(\frac{24}{7},\frac{24}{7}\right)\text{ (i.e., on }4x+3y=24\text{ within the feasible region).}$

$\displaystyle \textbf{Question 6: }~\text{Maximize }Z=15x+10y$
$\displaystyle \text{Subject to }3x+2y\le 80$
$\displaystyle 2x+3y\le 70$
$\displaystyle x,y\ge 0$
$\displaystyle \text{Answer:}$ $\displaystyle \text{Converting the inequalities into equations, we obtain the straight lines:}$
$\displaystyle 3x+2y=80,\ \ 2x+3y=70,\ \ x=0,\ \ y=0$
$\displaystyle \text{These represent straight lines in the }xy\text{-plane.}$
$\displaystyle \textbf{(1) Line }3x+2y=80\text{:}$
$\displaystyle \text{It meets the }x\text{-axis at }A_1\left(\frac{80}{3},0\right)\text{ and the }y\text{-axis at }B_1(0,40).$
$\displaystyle \textbf{(2) Line }2x+3y=70\text{:}$
$\displaystyle \text{It meets the }x\text{-axis at }A_2(35,0)\text{ and the }y\text{-axis at }B_2\left(0,\frac{70}{3}\right).$
$\displaystyle \text{Also, }x=0\text{ is the }y\text{-axis and }y=0\text{ is the }x\text{-axis.}$
$\displaystyle \text{The feasible region lies in the first quadrant and satisfies both inequalities.}$
$\displaystyle \textbf{Corner points of the feasible region are obtained as follows:}$
$\displaystyle O(0,0)$
$\displaystyle \text{On }y=0:\ 3x\le 80\Rightarrow x\le \frac{80}{3},\ \ 2x\le 70\Rightarrow x\le 35\Rightarrow P\left(\frac{80}{3},0\right)$
$\displaystyle \text{On }x=0:\ 2y\le 80\Rightarrow y\le 40,\ \ 3y\le 70\Rightarrow y\le \frac{70}{3}\Rightarrow Q\left(0,\frac{70}{3}\right)$
$\displaystyle \text{Intersection of }3x+2y=80\text{ and }2x+3y=70:$
$\displaystyle 3x+2y=80$
$\displaystyle 2x+3y=70$
$\displaystyle \text{Multiply the first by }3:\ 9x+6y=240$
$\displaystyle \text{Multiply the second by }2:\ 4x+6y=140$
$\displaystyle \text{Subtract: }(9x+6y)-(4x+6y)=240-140\Rightarrow 5x=100\Rightarrow x=20$
$\displaystyle 3(20)+2y=80\Rightarrow 60+2y=80\Rightarrow y=10$
$\displaystyle \Rightarrow R(20,10)$
$\displaystyle \text{Hence the corner points are }O(0,0),\ P\left(\frac{80}{3},0\right),\ R(20,10),\ Q\left(0,\frac{70}{3}\right).$
$\displaystyle \textbf{Now, take a constant value (say }400\text{) for }Z. \text{ Putting }Z=400\text{ in }Z=15x+10y, \text{ we get }15x+10y=400.$
$\displaystyle \text{Dividing by }5,\ \ 3x+2y=80.$
$\displaystyle \text{Thus the objective line is the same as the constraint line }3x+2y=80.$
$\displaystyle \text{Move the line }15x+10y=k\text{ parallel to itself away from the origin; the maximum} \\ \text{occurs on the boundary }3x+2y=80\text{ within the feasible region.}$
$\displaystyle \textbf{Value of }Z\text{ at corner points:}$
$\displaystyle Z(0,0)=15(0)+10(0)=0$
$\displaystyle Z\left(\frac{80}{3},0\right)=15\cdot\frac{80}{3}=400$
$\displaystyle Z\left(0,\frac{70}{3}\right)=10\cdot\frac{70}{3}=\frac{700}{3}$
$\displaystyle Z(20,10)=15(20)+10(10)=300+100=400$
$\displaystyle \textbf{Therefore, the maximum value is }Z_{\max}=400.$
$\displaystyle \textbf{It occurs at infinitely many points on the line segment joining }P\left(\frac{80}{3},0\right) \\ \text{ and }R(20,10)\text{ (i.e., on }3x+2y=80\text{ within the feasible region).}$

$\displaystyle \textbf{Question 7: }~\text{Maximize }Z=10x+6y$
$\displaystyle \text{Subject to }3x+y\le 12$
$\displaystyle 2x+5y\le 34$
$\displaystyle x,y\ge 0$
$\displaystyle \text{Answer:}$ $\displaystyle \text{Converting the inequalities into equations, we obtain the straight lines:}$
$\displaystyle 3x+y=12,\ \ 2x+5y=34,\ \ x=0,\ \ y=0$
$\displaystyle \text{These represent straight lines in the }xy\text{-plane.}$
$\displaystyle \textbf{(1) Line }3x+y=12\text{:}$
$\displaystyle \text{It meets the }x\text{-axis at }A_1(4,0)\text{ and the }y\text{-axis at }B_1(0,12).$
$\displaystyle \textbf{(2) Line }2x+5y=34\text{:}$
$\displaystyle \text{It meets the }x\text{-axis at }A_2(17,0)\text{ and the }y\text{-axis at }B_2\left(0,\frac{34}{5}\right).$
$\displaystyle \text{Also, }x=0\text{ is the }y\text{-axis and }y=0\text{ is the }x\text{-axis.}$
$\displaystyle \text{The feasible region lies in the first quadrant and satisfies both inequalities.}$
$\displaystyle \textbf{Corner points of the feasible region are obtained as follows:}$
$\displaystyle O(0,0)$
$\displaystyle \text{On }y=0:\ 3x\le 12\Rightarrow x\le 4,\ \ 2x\le 34\Rightarrow x\le 17\Rightarrow P(4,0)$
$\displaystyle \text{On }x=0:\ y\le 12,\ \ 5y\le 34\Rightarrow y\le \frac{34}{5}\Rightarrow Q\left(0,\frac{34}{5}\right)$
$\displaystyle \text{Intersection of }3x+y=12\text{ and }2x+5y=34:$
$\displaystyle 3x+y=12\Rightarrow y=12-3x$
$\displaystyle 2x+5(12-3x)=34$
$\displaystyle 2x+60-15x=34$
$\displaystyle -13x=-26\Rightarrow x=2$
$\displaystyle y=12-3(2)=6$
$\displaystyle \Rightarrow R(2,6)$
$\displaystyle \text{Hence the corner points are }O(0,0),\ P(4,0),\ R(2,6),\ Q\left(0,\frac{34}{5}\right).$
$\displaystyle \textbf{Now, take a constant value (say }60\text{) for }Z. \text{ Putting }Z=60\text{ in }Z=10x+6y, \text{ we get }10x+6y=60.$
$\displaystyle \text{Move the line }10x+6y=k\text{ parallel to itself in the increasing direction of }Z \\ \text{ (away from the origin).}$
$\displaystyle \text{The maximum value occurs at the last point where this line touches the} \\ \text{feasible region, i.e., at a corner point.}$
$\displaystyle \textbf{Value of }Z\text{ at corner points:}$
$\displaystyle Z(0,0)=0$
$\displaystyle Z(4,0)=10(4)+6(0)=40$
$\displaystyle Z\left(0,\frac{34}{5}\right)=10(0)+6\cdot\frac{34}{5}=\frac{204}{5}=40.8$
$\displaystyle Z(2,6)=10(2)+6(6)=20+36=56$
$\displaystyle \textbf{Therefore, the maximum value is }Z_{\max}=56$
$\displaystyle \textbf{at }x=2,\ y=6.$

$\displaystyle \textbf{Question 8: }~\text{Maximize }Z=3x+4y$
$\displaystyle \text{Subject to }2x+2y\le 80$
$\displaystyle 2x+4y\le 120$
$\displaystyle \text{Answer:}$
$\displaystyle \text{Converting the inequalities into equations, we obtain the straight lines:}$
$\displaystyle 2x+2y=80,\ \ 2x+4y=120,\ \ x=0,\ \ y=0$
$\displaystyle \text{These represent straight lines in the }xy\text{-plane.}$
$\displaystyle \textbf{(1) Line }2x+2y=80\text{:}$
$\displaystyle \text{It meets the }x\text{-axis at }A_1(40,0)\text{ and the }y\text{-axis at }B_1(0,40).$
$\displaystyle \textbf{(2) Line }2x+4y=120\text{:}$
$\displaystyle \text{It meets the }x\text{-axis at }A_2(60,0)\text{ and the }y\text{-axis at }B_2(0,30).$
$\displaystyle \text{Also, }x=0\text{ is the }y\text{-axis and }y=0\text{ is the }x\text{-axis.}$
$\displaystyle \text{The feasible region lies in the first quadrant and satisfies both inequalities.}$
$\displaystyle \textbf{Corner points of the feasible region are obtained as follows:}$
$\displaystyle O(0,0)$
$\displaystyle \text{On }y=0:\ 2x\le 80\Rightarrow x\le 40\Rightarrow P(40,0)$
$\displaystyle \text{On }x=0:\ 4y\le 120\Rightarrow y\le 30\Rightarrow Q(0,30)$
$\displaystyle \text{Intersection of }2x+2y=80\text{ and }2x+4y=120:$
$\displaystyle 2x+2y=80\Rightarrow x+y=40$
$\displaystyle 2x+4y=120\Rightarrow x+2y=60$
$\displaystyle (x+2y)-(x+y)=60-40\Rightarrow y=20$
$\displaystyle x=40-y=20$
$\displaystyle \Rightarrow R(20,20)$
$\displaystyle \text{Hence the corner points are }O(0,0),\ P(40,0),\ R(20,20),\ Q(0,30).$
$\displaystyle \textbf{Now, take a constant value (say }120\text{) for }Z. \text{ Putting }Z=120\text{ in }Z=3x+4y, \text{ we get }3x+4y=120.$
$\displaystyle \text{Move the line }3x+4y=k\text{ parallel to itself in the increasing direction of }Z \\ \text{ (away from the origin).}$
$\displaystyle \text{The maximum value occurs at the last point where this line touches the feasible} \\ \text{region, i.e., at a corner point.}$
$\displaystyle \textbf{Value of }Z\text{ at corner points:}$
$\displaystyle Z(0,0)=0$
$\displaystyle Z(40,0)=3(40)+4(0)=120$
$\displaystyle Z(0,30)=3(0)+4(30)=120$
$\displaystyle Z(20,20)=3(20)+4(20)=60+80=140$
$\displaystyle \textbf{Therefore, the maximum value is }Z_{\max}=140$
$\displaystyle \textbf{at }x=20,\ y=20.$

$\displaystyle \textbf{Question 9: }~\text{Maximize }Z=7x+10y$
$\displaystyle \text{Subject to }x+y\le 30000$
$\displaystyle y\le 12000$
$\displaystyle x\ge 6000$
$\displaystyle x\ge y$
$\displaystyle x,y\ge 0$
$\displaystyle \text{Answer:}$
$\displaystyle \text{Converting the inequalities into equations, we obtain the straight lines:}$
$\displaystyle x+y=30000,\ \ y=12000,\ \ x=6000,\ \ x=y,\ \ x=0,\ \ y=0$
$\displaystyle \text{These represent straight lines in the }xy\text{-plane.}$
$\displaystyle \textbf{(1) Line }x+y=30000\text{:}$
$\displaystyle \text{It meets the }x\text{-axis at }A_1(30000,0)\text{ and the }y\text{-axis at }B_1(0,30000).$
$\displaystyle \textbf{(2) Line }y=12000\text{: a horizontal line parallel to the }x\text{-axis.}$
$\displaystyle \textbf{(3) Line }x=6000\text{: a vertical line parallel to the }y\text{-axis.}$
$\displaystyle \textbf{(4) Line }x=y\text{: a line making }45^\circ\text{ with the axes.}$
$\displaystyle \text{The feasible region is in the first quadrant, to the right of }x=6000,\ \text{below }y=12000,\ \text{below }x+y=30000,\ \text{and below }y=x.$
$\displaystyle \textbf{Corner points of the feasible region are obtained as follows:}$
$\displaystyle P_1=(6000,0)$
$\displaystyle P_2:\ x=6000\text{ and }x=y\Rightarrow (6000,6000)$
$\displaystyle P_3:\ y=12000\text{ and }x=y\Rightarrow (12000,12000)$
$\displaystyle P_4:\ y=12000\text{ and }x+y=30000\Rightarrow x=18000\Rightarrow (18000,12000)$
$\displaystyle P_5:\ y=0\text{ and }x+y=30000\Rightarrow (30000,0)$
$\displaystyle \textbf{Now, take a constant value (say }240000\text{) for }Z. \text{ Putting }Z=240000\text{ in }Z=7x+10y, \text{ we get }7x+10y=240000.$
$\displaystyle \text{Move the line }7x+10y=k\text{ parallel to itself in the increasing direction of }Z \\ \text{ (away from the origin).}$
$\displaystyle \text{The maximum value occurs at the last point where this line touches the feasible region,} \\ \text{i.e., at a corner point.}$
$\displaystyle \textbf{Value of }Z\text{ at corner points:}$
$\displaystyle Z(6000,0)=7(6000)+10(0)=42000$
$\displaystyle Z(6000,6000)=7(6000)+10(6000)=102000$
$\displaystyle Z(12000,12000)=7(12000)+10(12000)=204000$
$\displaystyle Z(18000,12000)=7(18000)+10(12000)=126000+120000=246000$
$\displaystyle Z(30000,0)=7(30000)+10(0)=210000$
$\displaystyle \textbf{Therefore, the maximum value is }Z_{\max}=246000$
$\displaystyle \textbf{at }x=18000,\ y=12000.$

$\displaystyle \textbf{Question 10: }~\text{Minimize }Z=2x+4y$
$\displaystyle \text{Subject to }x+y\ge 8$
$\displaystyle x+4y\ge 12$
$\displaystyle x\ge 3,\ y\ge 2$
$\displaystyle \text{Answer:}$ $\displaystyle \text{Converting the inequalities into equations, we obtain the straight lines:}$
$\displaystyle x+y=8,\ \ x+4y=12,\ \ x=3,\ \ y=2$
$\displaystyle \text{These represent straight lines in the }xy\text{-plane.}$
$\displaystyle \textbf{(1) Line }x+y=8\text{:}$
$\displaystyle \text{It meets the }x\text{-axis at }A_1(8,0)\text{ and the }y\text{-axis at }B_1(0,8).$
$\displaystyle \textbf{(2) Line }x+4y=12\text{:}$
$\displaystyle \text{It meets the }x\text{-axis at }A_2(12,0)\text{ and the }y\text{-axis at }B_2(0,3).$
$\displaystyle \textbf{(3) Line }x=3\text{: a vertical line, and (4) }y=2\text{: a horizontal line.}$
$\displaystyle \text{Since the inequalities are of type }\ge,\ \text{the feasible region lies to the right of }x=3,\ \text{above }y=2,$
$\displaystyle \text{and \textit{above} the lines }x+y=8\text{ and }x+4y=12.$
$\displaystyle \textbf{Corner points of the feasible region are obtained as follows:}$
$\displaystyle \text{Intersection of }x=3\text{ with }x+y=8:\ 3+y=8\Rightarrow y=5\Rightarrow P(3,5)$
$\displaystyle \text{Intersection of }y=2\text{ with }x+y=8:\ x+2=8\Rightarrow x=6\Rightarrow Q(6,2)$
$\displaystyle \text{Note: }(3,2)\text{ is not feasible since }3+2<8.$
$\displaystyle \text{Also, the intersection of }x+y=8\text{ and }x+4y=12\text{ gives }y=\frac{4}{3}<2,\ \text{so it is not feasible.}$
$\displaystyle \text{Hence the relevant boundary segment of the feasible region is the line segment }PQ\text{ on }x+y=8.$
$\displaystyle \textbf{Now, take a constant value (say }20\text{) for }Z. \text{ Putting }Z=20\text{ in }Z=2x+4y, \text{ we get }2x+4y=20,$
$\displaystyle \text{i.e. }x+2y=10.$
$\displaystyle \text{Move the line }2x+4y=k\text{ parallel to itself towards the origin (decreasing direction} \\ \text{of }Z\text{).}$
$\displaystyle \text{The minimum value occurs at the first point where this line touches the feasible region,} \\ \text{i.e., at a corner point.}$
$\displaystyle \textbf{Value of }Z\text{ at corner points:}$
$\displaystyle Z(3,5)=2(3)+4(5)=6+20=26$
$\displaystyle Z(6,2)=2(6)+4(2)=12+8=20$
$\displaystyle \textbf{Therefore, the minimum value is }Z_{\min}=20$
$\displaystyle \textbf{at }x=6,\ y=2.$

$\displaystyle \textbf{Question 11: }~\text{Minimize }Z=5x+3y$
$\displaystyle \text{Subject to }2x+y\ge 10$
$\displaystyle x+3y\ge 15$
$\displaystyle x\le 10$
$\displaystyle y\le 8$
$\displaystyle x,y\ge 0$
$\displaystyle \text{Answer:}$
$\displaystyle \text{Converting the inequalities into equations, we obtain the straight lines:}$
$\displaystyle 2x+y=10,\ \ x+3y=15,\ \ x=10,\ \ y=8,\ \ x=0,\ \ y=0$
$\displaystyle \text{These represent straight lines in the }xy\text{-plane.}$
$\displaystyle \textbf{(1) Line }2x+y=10\text{:}$
$\displaystyle \text{It meets the }x\text{-axis at }A_1(5,0)\text{ and the }y\text{-axis at }B_1(0,10).$
$\displaystyle \textbf{(2) Line }x+3y=15\text{:}$
$\displaystyle \text{It meets the }x\text{-axis at }A_2(15,0)\text{ and the }y\text{-axis at }B_2(0,5).$
$\displaystyle \textbf{(3) Lines }x=10\text{ and }y=8\text{ are the bounding lines, and }x=0,\ y=0\text{ are the} \\ \text{coordinate axes.}$
$\displaystyle \text{Since }2x+y\ge 10\text{ and }x+3y\ge 15,\ \text{the feasible region lies in the first quadrant,} \\ \text{inside the rectangle }0\le x\le 10,\ 0\le y\le 8,$
$\displaystyle \text{and \textit{above} both lines }2x+y=10\text{ and }x+3y=15.$
$\displaystyle \textbf{Corner points of the feasible region are obtained as follows:}$
$\displaystyle \text{Intersection of }2x+y=10\text{ with }y=8:\ 2x+8=10\Rightarrow x=1\Rightarrow P(1,8)$
$\displaystyle \text{Intersection of }x+3y=15\text{ with }x=10:\ 10+3y=15\Rightarrow y=\frac{5}{3}\Rightarrow Q\left(10,\frac{5}{3}\right)$
$\displaystyle \text{Intersection of }2x+y=10\text{ and }x+3y=15:$
$\displaystyle 2x+y=10\Rightarrow y=10-2x$
$\displaystyle x+3(10-2x)=15$
$\displaystyle x+30-6x=15$
$\displaystyle -5x=-15\Rightarrow x=3$
$\displaystyle y=10-2(3)=4$
$\displaystyle \Rightarrow R(3,4)$
$\displaystyle \text{Also, }(10,8)\text{ satisfies all constraints, so }S(10,8)\text{ is a corner point.}$
$\displaystyle \text{Hence the corner points are }P(1,8),\ S(10,8),\ Q\left(10,\frac{5}{3}\right),\ R(3,4).$
$\displaystyle \textbf{Now, take a constant value (say }30\text{) for }Z. \text{ Putting }Z=30\text{ in }Z=5x+3y, \\ \text{ we get }5x+3y=30.$
$\displaystyle \text{Move the line }5x+3y=k\text{ parallel to itself towards the origin (decreasing} \\ \text{direction of }Z\text{).}$
$\displaystyle \text{The minimum value occurs at the first point where this line touches the feasible region,} \\ \text{i.e., at a corner point.}$
$\displaystyle \textbf{Value of }Z\text{ at corner points:}$
$\displaystyle Z(1,8)=5(1)+3(8)=29$
$\displaystyle Z(10,8)=5(10)+3(8)=74$
$\displaystyle Z\left(10,\frac{5}{3}\right)=5(10)+3\cdot\frac{5}{3}=55$
$\displaystyle Z(3,4)=5(3)+3(4)=15+12=27$
$\displaystyle \textbf{Therefore, the minimum value is }Z_{\min}=27$
$\displaystyle \textbf{at }x=3,\ y=4.$

$\displaystyle \textbf{Question 12: }~\text{Minimize }Z=30x+20y$
$\displaystyle \text{Subject to }x+y\le 8$
$\displaystyle x+4y\ge 12$
$\displaystyle 5x+8y=20$
$\displaystyle x,y\ge 0$
$\displaystyle \text{Answer:}$
$\displaystyle \text{(Logical correction used: the third condition must be }5x+8y\ge 20\text{; with }5x+8y=20\text{ there is no feasible point.)}$
$\displaystyle \text{Converting the inequalities into equations, we obtain the straight lines:}$
$\displaystyle x+y=8,\ \ x+4y=12,\ \ 5x+8y=20,\ \ x=0,\ \ y=0$
$\displaystyle \text{These represent straight lines in the }xy\text{-plane.}$
$\displaystyle \textbf{(1) Line }x+y=8\text{:}$
$\displaystyle \text{It meets the }x\text{-axis at }A_1(8,0)\text{ and the }y\text{-axis at }B_1(0,8).$
$\displaystyle \textbf{(2) Line }x+4y=12\text{:}$
$\displaystyle \text{It meets the }x\text{-axis at }A_2(12,0)\text{ and the }y\text{-axis at }B_2(0,3).$
$\displaystyle \textbf{(3) Line }5x+8y=20\text{:}$
$\displaystyle \text{It meets the }x\text{-axis at }A_3(4,0)\text{ and the }y\text{-axis at }B_3\left(0,\frac{5}{2}\right).$
$\displaystyle \text{The feasible region lies in the first quadrant, \textit{below} }x+y=8,\ \textit{above} \ x+4y=12,\ \text{and \textit{above} }5x+8y=20.$
$\displaystyle \textbf{Corner points of the feasible region are obtained as follows:}$
$\displaystyle P:\ x=0\text{ and }x+4y=12\Rightarrow y=3\Rightarrow P(0,3)$
$\displaystyle Q:\ x=0\text{ and }x+y=8\Rightarrow y=8\Rightarrow Q(0,8)$
$\displaystyle R:\ x+y=8\text{ and }x+4y=12$
$\displaystyle x+y=8,\ \ x+4y=12\Rightarrow 3y=4\Rightarrow y=\frac{4}{3},\ \ x=8-\frac{4}{3}=\frac{20}{3}$
$\displaystyle \Rightarrow R\left(\frac{20}{3},\frac{4}{3}\right)$
$\displaystyle \text{Hence the corner points are }P(0,3),\ Q(0,8),\ R\left(\frac{20}{3},\frac{4}{3}\right).$
$\displaystyle \textbf{Now, take a constant value (say }120\text{) for }Z. \text{ Putting }Z=120\text{ in }Z=30x+20y, \text{ we get }30x+20y=120.$
$\displaystyle \text{Move the line }30x+20y=k\text{ parallel to itself towards the origin (decreasing direction of }Z\text{).}$
$\displaystyle \text{The minimum value occurs at the first point where this line touches the feasible region,} \\ \text{i.e., at a corner point.}$
$\displaystyle \textbf{Value of }Z\text{ at corner points:}$
$\displaystyle Z(0,3)=30(0)+20(3)=60$
$\displaystyle Z(0,8)=30(0)+20(8)=160$
$\displaystyle Z\left(\frac{20}{3},\frac{4}{3}\right)=30\cdot\frac{20}{3}+20\cdot\frac{4}{3}=200+\frac{80}{3}=\frac{680}{3}$
$\displaystyle \textbf{Therefore, the minimum value is }Z_{\min}=60$
$\displaystyle \textbf{at }x=0,\ y=3.$

$\displaystyle \textbf{Question 13: }~\text{Maximize }Z=4x+3y$
$\displaystyle \text{Subject to }3x+4y\le 24$
$\displaystyle 8x+6y\le 48$
$\displaystyle x\le 5$
$\displaystyle y\le 6$
$\displaystyle x,y\ge 0$
$\displaystyle \text{Answer:}$
$\displaystyle \text{Converting the inequalities into equations, we obtain the straight lines:}$
$\displaystyle 3x+4y=24,\ \ 8x+6y=48,\ \ x=5,\ \ y=6,\ \ x=0,\ \ y=0$
$\displaystyle \text{These represent straight lines in the }xy\text{-plane.}$
$\displaystyle \textbf{(1) Line }3x+4y=24\text{:}$
$\displaystyle \text{It meets the }x\text{-axis at }A_1(8,0)\text{ and the }y\text{-axis at }B_1(0,6).$
$\displaystyle \textbf{(2) Line }8x+6y=48\text{:}$
$\displaystyle \text{It meets the }x\text{-axis at }A_2(6,0)\text{ and the }y\text{-axis at }B_2(0,8).$
$\displaystyle \text{Also, }x=5\text{ and }y=6\text{ are the boundary lines, and }x=0,\ y=0\text{ are the coordinate axes.}$
$\displaystyle \text{The feasible region lies in the first quadrant and satisfies all the inequalities.}$
$\displaystyle \textbf{Corner points of the feasible region are obtained as follows:}$
$\displaystyle O(0,0)$
$\displaystyle \text{On }y=0:\ 3x\le 24,\ 8x\le 48,\ x\le 5\Rightarrow x\le 5\Rightarrow P(5,0)$
$\displaystyle \text{On }x=0:\ 4y\le 24,\ y\le 6\Rightarrow y\le 6\Rightarrow Q(0,6)$
$\displaystyle \text{Intersection of }x=5\text{ with }8x+6y=48:$
$\displaystyle 8(5)+6y=48\Rightarrow 40+6y=48\Rightarrow y=\frac{4}{3}$
$\displaystyle \Rightarrow R\left(5,\frac{4}{3}\right)$
$\displaystyle \text{Intersection of }3x+4y=24\text{ and }8x+6y=48:$
$\displaystyle 8x+6y=48\Rightarrow 4x+3y=24$
$\displaystyle 3x+4y=24$
$\displaystyle 4x+3y=24$
$\displaystyle \Rightarrow x=\frac{24}{7},\ y=\frac{24}{7}$
$\displaystyle \Rightarrow S\left(\frac{24}{7},\frac{24}{7}\right)$
$\displaystyle \text{Hence the corner points are }O(0,0),\ P(5,0),\ R\left(5,\frac{4}{3}\right),\ S\left(\frac{24}{7},\frac{24}{7}\right),\ Q(0,6).$
$\displaystyle \textbf{Now, take a constant value (say }24\text{) for }Z. \text{ Putting }Z=24\text{ in }Z=4x+3y, \\ \text{ we get }4x+3y=24.$
$\displaystyle \text{But }8x+6y=48\Rightarrow 4x+3y=24,\ \text{so the objective line is the same as the} \\ \text{constraint line }8x+6y=48.$
$\displaystyle \text{Move the line }4x+3y=k\text{ parallel to itself away from the origin; the maximum occurs} \\ \text{on the boundary }4x+3y=24\text{ within the feasible region.}$
$\displaystyle \textbf{Value of }Z\text{ at corner points:}$
$\displaystyle Z(0,0)=0$
$\displaystyle Z(5,0)=4(5)+3(0)=20$
$\displaystyle Z(0,6)=4(0)+3(6)=18$
$\displaystyle Z\left(5,\frac{4}{3}\right)=4(5)+3\cdot\frac{4}{3}=24$
$\displaystyle Z\left(\frac{24}{7},\frac{24}{7}\right)=4\cdot\frac{24}{7}+3\cdot\frac{24}{7}=24$
$\displaystyle \textbf{Therefore, the maximum value is }Z_{\max}=24.$
$\displaystyle \text{It occurs at infinitely many points on the line segment joining }R\left(5,\frac{4}{3}\right)\text{ and } \\ S\left(\frac{24}{7},\frac{24}{7}\right)\text{ (i.e., on }4x+3y=24\text{ within the feasible region).}$

$\displaystyle \textbf{Question 14: }~\text{Minimize }Z=x-5y+20$
$\displaystyle \text{Subject to }x-y\ge 0$
$\displaystyle -x+2y\ge 2$
$\displaystyle x\ge 3$
$\displaystyle y\le 4$
$\displaystyle x,y\ge 0 \hspace{7.0cm} \text{[CBSE 2004]}$
$\displaystyle \text{Answer:}$
$\displaystyle \text{Converting the inequalities into equations, we obtain the straight lines:}$
$\displaystyle x-y=0\ (\Rightarrow x=y),\ \ -x+2y=2\ (\Rightarrow x=2y-2),\ \ x=3,\ \ y=4,\ \ x=0,\ \ y=0$
$\displaystyle \text{These represent straight lines in the }xy\text{-plane.}$
$\displaystyle \textbf{(1) Line }x=y\text{:}$
$\displaystyle \text{This is a line at }45^\circ\text{ through the origin. The region for }x-y\ge 0\text{ is }x\ge y\text{ (below }y=x\text{).}$
$\displaystyle \textbf{(2) Line }x=2y-2\text{:}$
$\displaystyle \text{The region for }-x+2y\ge 2\text{ is }x\le 2y-2\text{ (to the left of this line).}$
$\displaystyle \textbf{(3) Line }x=3\text{: region to the right of }x=3.$
$\displaystyle \textbf{(4) Line }y=4\text{: region below }y=4.$
$\displaystyle \text{The feasible region lies in the first quadrant and satisfies }y\le x\le 2y-2,\ x\ge 3,\ y\le 4.$
$\displaystyle \textbf{Corner points of the feasible region are obtained as follows:}$
$\displaystyle \text{Intersection of }x=3\text{ and }x=2y-2:\ 3=2y-2\Rightarrow y=\frac{5}{2}\Rightarrow P\left(3,\frac{5}{2}\right)$
$\displaystyle \text{Intersection of }x=3\text{ and }x=y:\ (3,3)\Rightarrow Q(3,3)$
$\displaystyle \text{Intersection of }y=4\text{ and }x=y:\ (4,4)\Rightarrow R(4,4)$
$\displaystyle \text{Intersection of }y=4\text{ and }x=2y-2:\ x=6\Rightarrow S(6,4)$
$\displaystyle \text{Hence the corner points are }P\left(3,\frac{5}{2}\right),\ Q(3,3),\ R(4,4),\ S(6,4).$
$\displaystyle \textbf{Now, take a constant value (say }10\text{) for }Z. \text{ Putting }Z=10\text{ in }Z=x-5y+20, \text{ we get }x-5y+20=10,$
$\displaystyle \text{i.e. }x-5y=-10.$
$\displaystyle \text{Move the line }x-5y=k\text{ parallel to itself towards the origin (decreasing direction of }Z\text{).}$
$\displaystyle \text{The minimum value occurs at the first point where this line touches the feasible region,} \\ \text{i.e., at a corner point.}$
$\displaystyle \textbf{Value of }Z\text{ at corner points:}$
$\displaystyle Z\left(3,\frac{5}{2}\right)=3-5\cdot\frac{5}{2}+20=\frac{21}{2}$
$\displaystyle Z(3,3)=3-5(3)+20=8$
$\displaystyle Z(4,4)=4-5(4)+20=4$
$\displaystyle Z(6,4)=6-5(4)+20=6$
$\displaystyle \textbf{Therefore, the minimum value is }Z_{\min}=4$
$\displaystyle \textbf{at }x=4,\ y=4.$

$\displaystyle \textbf{Question 15: }~\text{Maximize }Z=3x+5y$
$\displaystyle \text{Subject to }x+2y\le 20$
$\displaystyle x+y\le 15$
$\displaystyle y\le 5$
$\displaystyle x,y\ge 0$
$\displaystyle \text{Answer:}$
$\displaystyle \text{Converting the inequalities into equations, we obtain the straight lines:}$
$\displaystyle x+2y=20,\ \ x+y=15,\ \ y=5,\ \ x=0,\ \ y=0$
$\displaystyle \text{These represent straight lines in the }xy\text{-plane.}$
$\displaystyle \textbf{(1) Line }x+2y=20\text{:}$
$\displaystyle \text{It meets the }x\text{-axis at }A_1(20,0)\text{ and the }y\text{-axis at }B_1(0,10).$
$\displaystyle \textbf{(2) Line }x+y=15\text{:}$
$\displaystyle \text{It meets the }x\text{-axis at }A_2(15,0)\text{ and the }y\text{-axis at }B_2(0,15).$
$\displaystyle \textbf{(3) Line }y=5\text{: a horizontal line. Also }x=0\text{ and }y=0\text{ are the coordinate axes.}$
$\displaystyle \text{The feasible region lies in the first quadrant and satisfies all the inequalities.}$
$\displaystyle \textbf{Corner points of the feasible region are obtained as follows:}$
$\displaystyle O(0,0)$
$\displaystyle \text{On }y=0:\ x\le 20,\ x\le 15\Rightarrow x\le 15\Rightarrow P(15,0)$
$\displaystyle \text{On }x=0:\ 2y\le 20\Rightarrow y\le 10,\ \text{and }y\le 5\Rightarrow y\le 5\Rightarrow Q(0,5)$
$\displaystyle \text{Intersection of }y=5\text{ with }x+y=15:\ x+5=15\Rightarrow x=10\Rightarrow R(10,5)$
$\displaystyle \text{(Also, }y=5\text{ with }x+2y=20\Rightarrow x+10=20\Rightarrow x=10,\ \text{so the same point }R(10,5)\text{.)}$
$\displaystyle \text{Hence the corner points are }O(0,0),\ P(15,0),\ R(10,5),\ Q(0,5).$
$\displaystyle \textbf{Now, take a constant value (say }30\text{) for }Z. \text{ Putting }Z=30\text{ in }Z=3x+5y, \text{ we get }3x+5y=30.$
$\displaystyle \text{Move the line }3x+5y=k\text{ parallel to itself in the increasing direction of }Z\text{ (away from the origin).}$
$\displaystyle \text{The maximum value occurs at the last point where this line touches the feasible region,} \\ \text{i.e., at a corner point.}$
$\displaystyle \textbf{Value of }Z\text{ at corner points:}$
$\displaystyle Z(0,0)=0$
$\displaystyle Z(15,0)=3(15)+5(0)=45$
$\displaystyle Z(0,5)=3(0)+5(5)=25$
$\displaystyle Z(10,5)=3(10)+5(5)=30+25=55$
$\displaystyle \textbf{Therefore, the maximum value is }Z_{\max}=55$
$\displaystyle \textbf{at }x=10,\ y=5.$

$\displaystyle \textbf{Question 16: }~\text{Minimize }Z=3x_{1}+5x_{2}$
$\displaystyle \text{Subject to }x_{1}+3x_{2}\ge 3$
$\displaystyle x_{1}+x_{2}\ge 2$
$\displaystyle x_{1},x_{2}\ge 0\ \hspace{7.0cm} \text{[CBSE\ 2005]}$
$\displaystyle \text{Answer:}$
$\displaystyle \text{Converting the inequalities into equations, we obtain the straight lines:}$
$\displaystyle x_1+3x_2=3,\ \ x_1+x_2=2,\ \ x_1=0,\ \ x_2=0$
$\displaystyle \text{These represent straight lines in the }x_1x_2\text{-plane.}$
$\displaystyle \textbf{(1) Line }x_1+3x_2=3\text{:}$
$\displaystyle \text{It meets the }x_1\text{-axis at }A_1(3,0)\text{ and the }x_2\text{-axis at }B_1(0,1).$
$\displaystyle \textbf{(2) Line }x_1+x_2=2\text{:}$
$\displaystyle \text{It meets the }x_1\text{-axis at }A_2(2,0)\text{ and the }x_2\text{-axis at }B_2(0,2).$
$\displaystyle \text{Also, }x_1=0\text{ is the }x_2\text{-axis and }x_2=0\text{ is the }x_1\text{-axis.}$
$\displaystyle \text{Since both inequalities are of type }\ge,\ \text{the feasible region lies in the first quadrant} \\ \text{and is the region \textit{above} both lines.}$
$\displaystyle \textbf{Corner points of the feasible region are obtained as follows:}$
$\displaystyle \text{Intersection of }x_1+3x_2=3\text{ and }x_1+x_2=2:$
$\displaystyle (x_1+3x_2)-(x_1+x_2)=3-2\Rightarrow 2x_2=1\Rightarrow x_2=\frac{1}{2}$
$\displaystyle x_1+x_2=2\Rightarrow x_1=2-\frac{1}{2}=\frac{3}{2}$
$\displaystyle \Rightarrow P\left(\frac{3}{2},\frac{1}{2}\right)$
$\displaystyle \text{On }x_2=0:\ x_1\ge 3\Rightarrow Q(3,0)\text{ is a corner point.}$
$\displaystyle \text{On }x_1=0:\ x_2\ge 2\Rightarrow R(0,2)\text{ is a corner point.}$
$\displaystyle \text{Hence the corner points are }P\left(\frac{3}{2},\frac{1}{2}\right),\ Q(3,0),\ R(0,2).$
$\displaystyle \textbf{Now, take a constant value (say }10\text{) for }Z. \text{ Putting }Z=10\text{ in }Z=3x_1+5x_2, \text{ we get }3x_1+5x_2=10.$
$\displaystyle \text{Move the line }3x_1+5x_2=k\text{ parallel to itself towards the origin (decreasing direction of }Z\text{).}$
$\displaystyle \text{The minimum value occurs at the first point where this line touches the feasible region,} \\ \text{i.e., at a corner point.}$
$\displaystyle \textbf{Value of }Z\text{ at corner points:}$
$\displaystyle Z\left(\frac{3}{2},\frac{1}{2}\right)=3\cdot\frac{3}{2}+5\cdot\frac{1}{2}=\frac{9}{2}+\frac{5}{2}=7$
$\displaystyle Z(3,0)=3(3)+5(0)=9$
$\displaystyle Z(0,2)=3(0)+5(2)=10$
$\displaystyle \textbf{Therefore, the minimum value is }Z_{\min}=7$
$\displaystyle \textbf{at }x_1=\frac{3}{2},\ x_2=\frac{1}{2}.$

$\displaystyle \textbf{Question 17: }~\text{Maximize }Z=2x+3y$
$\displaystyle \text{Subject to }x+y\ge 1$
$\displaystyle 10x+y\ge 5$
$\displaystyle x+10y\ge 1$
$\displaystyle x,y\ge 0$
$\displaystyle \text{Answer:}$ $\displaystyle \textbf{Question 17: Solve the following LPP graphically}$
$\displaystyle \textbf{Maximize } Z=2x+3y$
$\displaystyle \textbf{Subject to } x+y\ge 1$
$\displaystyle 10x+y\ge 5$
$\displaystyle x+10y\ge 1$
$\displaystyle x\ge 0,\ y\ge 0$
$\displaystyle \textbf{Solution:}$
$\displaystyle \text{Converting the inequalities into equations, we obtain the straight lines:}$
$\displaystyle x+y=1,\ \ 10x+y=5,\ \ x+10y=1,\ \ x=0,\ \ y=0$
$\displaystyle \text{These represent straight lines in the }xy\text{-plane.}$
$\displaystyle \textbf{(1) Line }x+y=1\text{:}$
$\displaystyle \text{It meets the }x\text{-axis at }A_1(1,0)\text{ and the }y\text{-axis at }B_1(0,1).$
$\displaystyle \textbf{(2) Line }10x+y=5\text{:}$
$\displaystyle \text{It meets the }x\text{-axis at }A_2\left(\frac{1}{2},0\right)\text{ and the }y\text{-axis at }B_2(0,5).$
$\displaystyle \textbf{(3) Line }x+10y=1\text{:}$
$\displaystyle \text{It meets the }x\text{-axis at }A_3(1,0)\text{ and the }y\text{-axis at }B_3\left(0,\frac{1}{10}\right).$
$\displaystyle \text{Since all inequalities are of type }\ge,\ \text{the feasible region lies in the first quadrant} \\ \text{and is the region \textit{above} all these lines.}$
$\displaystyle \textbf{Corner points of the feasible region (lower boundary) are:}$
$\displaystyle \text{Intersection of }x+y=1\text{ and }10x+y=5:$
$\displaystyle (10x+y)-(x+y)=5-1\Rightarrow 9x=4\Rightarrow x=\frac{4}{9},\ y=1-\frac{4}{9}=\frac{5}{9}$
$\displaystyle \Rightarrow P\left(\frac{4}{9},\frac{5}{9}\right)$
$\displaystyle \text{Intersection of }x+y=1\text{ and }x+10y=1:$
$\displaystyle (x+10y)-(x+y)=1-1\Rightarrow 9y=0\Rightarrow y=0,\ x=1$
$\displaystyle \Rightarrow Q(1,0)$
$\displaystyle \text{On }x=0:\ 10x+y\ge 5\Rightarrow y\ge 5\Rightarrow R(0,5)$
$\displaystyle \text{Thus the feasible region has boundary through }Q(1,0),\ P\left(\frac{4}{9},\frac{5}{9}\right), \\ R(0,5)\text{ and then extends indefinitely upward/rightward.}$
$\displaystyle \textbf{Unboundedness:}$
$\displaystyle \text{For example, take }(x,y)=(1,t)\text{ with }t\ge 5.\ \text{Then }x+y=1+t\ge 1,\ 10x+y=10+t\ge 5,\ x+10y=1+10t\ge 1.$
$\displaystyle \text{So }(1,t)\text{ is feasible for all }t\ge 5,\ \text{and }Z=2(1)+3t=2+3t\to \infty\text{ as }t\to \infty.$
$\displaystyle \textbf{Therefore, the LPP has no finite maximum value (it is unbounded).}$

$\displaystyle \textbf{Question 18: }~\text{Maximize }Z=-x_{1}+2x_{2}$
$\displaystyle \text{Subject to }-x_{1}+3x_{2}\le 10$
$\displaystyle x_{1}+x_{2}\le 6$
$\displaystyle x_{1}-x_{2}\le 2$
$\displaystyle x_{1},x_{2}\ge 0$
$\displaystyle \text{Answer:}$
$\displaystyle \text{Converting the inequalities into equations, we obtain the straight lines:}$
$\displaystyle -x_1+3x_2=10,\ \ x_1+x_2=6,\ \ x_1-x_2=2,\ \ x_1=0,\ \ x_2=0$
$\displaystyle \text{These represent straight lines in the }x_1x_2\text{-plane.}$
$\displaystyle \textbf{(1) Line }-x_1+3x_2=10\text{:}$
$\displaystyle \text{It meets the }x_1\text{-axis at }A_1(-10,0)\text{ and the }x_2\text{-axis at }B_1\left(0,\frac{10}{3}\right).$
$\displaystyle \textbf{(2) Line }x_1+x_2=6\text{:}$
$\displaystyle \text{It meets the }x_1\text{-axis at }A_2(6,0)\text{ and the }x_2\text{-axis at }B_2(0,6).$
$\displaystyle \textbf{(3) Line }x_1-x_2=2\text{:}$
$\displaystyle \text{It meets the }x_1\text{-axis at }A_3(2,0)\text{ and passes through }(0,-2).$
$\displaystyle \text{Also, }x_1=0\text{ is the }x_2\text{-axis and }x_2=0\text{ is the }x_1\text{-axis.}$
$\displaystyle \text{The feasible region lies in the first quadrant and satisfies all the inequalities.}$
$\displaystyle \textbf{Corner points of the feasible region are obtained as follows:}$
$\displaystyle O(0,0)$
$\displaystyle P:\ x_2=0\text{ and }x_1-x_2=2\Rightarrow P(2,0)$
$\displaystyle Q:\ x_1+x_2=6\text{ and }x_1-x_2=2\Rightarrow 2x_1=8\Rightarrow x_1=4,\ x_2=2\Rightarrow Q(4,2)$
$\displaystyle R:\ -x_1+3x_2=10\text{ and }x_1+x_2=6$
$\displaystyle -x_1+3x_2=10,\ x_1+x_2=6\Rightarrow 4x_2=16\Rightarrow x_2=4,\ x_1=2\Rightarrow R(2,4)$
$\displaystyle S:\ x_1=0\text{ and }-x_1+3x_2=10\Rightarrow 3x_2=10\Rightarrow S\left(0,\frac{10}{3}\right)$
$\displaystyle \text{Hence the corner points are }O(0,0),\ P(2,0),\ Q(4,2),\ R(2,4),\ S\left(0,\frac{10}{3}\right).$
$\displaystyle \textbf{Now, take a constant value (say }6\text{) for }Z. \text{ Putting }Z=6\text{ in }Z=-x_1+2x_2, \text{ we get }-x_1+2x_2=6.$
$\displaystyle \text{Move the line }-x_1+2x_2=k\text{ parallel to itself in the increasing direction of }Z.$
$\displaystyle \text{The maximum value occurs at the last point where this line touches the feasible region, i.e., at a corner point.}$
$\displaystyle \textbf{Value of }Z\text{ at corner points:}$
$\displaystyle Z(0,0)=0$
$\displaystyle Z(2,0)=-2$
$\displaystyle Z(4,2)=-4+4=0$
$\displaystyle Z(2,4)=-2+8=6$
$\displaystyle Z\left(0,\frac{10}{3}\right)=0+2\cdot\frac{10}{3}=\frac{20}{3}$
$\displaystyle \textbf{Therefore, the maximum value is }Z_{\max}=\frac{20}{3}$
$\displaystyle \textbf{at }x_1=0,\ x_2=\frac{10}{3}.$

$\displaystyle \textbf{Question 19: }~\text{Maximize }Z=x+y$
$\displaystyle \text{Subject to }-2x+y\le 1$
$\displaystyle x\le 2$
$\displaystyle x+y\le 3$
$\displaystyle x,y\ge 0$
$\displaystyle \text{Answer:}$
$\displaystyle \text{Converting the inequalities into equations, we obtain the straight lines:}$
$\displaystyle -2x+y=1,\ \ x=2,\ \ x+y=3,\ \ x=0,\ \ y=0$
$\displaystyle \text{These represent straight lines in the }xy\text{-plane.}$
$\displaystyle \textbf{(1) Line }-2x+y=1\text{:}$
$\displaystyle \text{It meets the }y\text{-axis at }A_1(0,1)\text{ and the }x\text{-axis at }\left(-\frac{1}{2},0\right).$
$\displaystyle \textbf{(2) Line }x=2\text{: a vertical line.}$
$\displaystyle \textbf{(3) Line }x+y=3\text{:}$
$\displaystyle \text{It meets the }x\text{-axis at }A_2(3,0)\text{ and the }y\text{-axis at }B_2(0,3).$
$\displaystyle \text{The feasible region lies in the first quadrant, satisfies }x\le 2,\ x+y\le 3,\ \text{and lies \textit{below} }-2x+y=1\ (\Rightarrow y\le 1+2x).$
$\displaystyle \textbf{Corner points of the feasible region are obtained as follows:}$
$\displaystyle O(0,0)$
$\displaystyle P(2,0)$
$\displaystyle Q:\ x=2\text{ and }x+y=3\Rightarrow y=1\Rightarrow Q(2,1)$
$\displaystyle R:\ -2x+y=1\text{ and }x+y=3\Rightarrow 1+2x=3-x\Rightarrow 3x=2\Rightarrow x=\frac{2}{3},\ y=\frac{7}{3}$
$\displaystyle \Rightarrow R\left(\frac{2}{3},\frac{7}{3}\right)$
$\displaystyle S:\ x=0\text{ and }-2x+y=1\Rightarrow S(0,1)$
$\displaystyle \text{Hence the corner points are }O(0,0),\ P(2,0),\ Q(2,1),\ R\left(\frac{2}{3},\frac{7}{3}\right),\ S(0,1).$
$\displaystyle \textbf{Now, take a constant value (say }3\text{) for }Z. \text{ Putting }Z=3\text{ in }Z=x+y, \text{ we get }x+y=3.$
$\displaystyle \text{Move the line }x+y=k\text{ parallel to itself in the increasing direction of }Z\text{ (away} \\ \text{from the origin).}$
$\displaystyle \text{The maximum occurs when the line }x+y=k\text{ is farthest from the origin but still} \\ \text{meets the feasible region.}$
$\displaystyle \text{Here, the feasible region has an entire boundary segment on }x+y=3\text{ (from } \\R\left(\frac{2}{3},\frac{7}{3}\right)\text{ to }Q(2,1)\text{).}$
$\displaystyle \textbf{Value of }Z\text{ at corner points:}$
$\displaystyle Z(0,0)=0$
$\displaystyle Z(2,0)=2$
$\displaystyle Z(2,1)=3$
$\displaystyle Z\left(\frac{2}{3},\frac{7}{3}\right)=3$
$\displaystyle Z(0,1)=1$
$\displaystyle \textbf{Therefore, the maximum value is }Z_{\max}=3.$
$\displaystyle \textbf{It occurs at infinitely many points on the line segment joining }R\left(\frac{2}{3},\frac{7}{3}\right) \\ \text{ and }Q(2,1)\text{ (i.e., on }x+y=3\text{ within the feasible region).}$

$\displaystyle \textbf{Question 20: }~\text{Maximize }Z=3x_{1}+4x_{2},\ \text{if possible,}$
$\displaystyle \text{Subject to the constraints }x_{1}-x_{2}\le -1$
$\displaystyle -x_{1}+x_{2}\le 0$
$\displaystyle x_{1},x_{2}\ge 0$
$\displaystyle \text{Answer:}$
$\displaystyle \text{Convert the inequalities into a convenient form:}$
$\displaystyle x_1-x_2\le -1\ \Rightarrow\ x_2\ge x_1+1$
$\displaystyle -x_1+x_2\le 0\ \Rightarrow\ x_2\le x_1$
$\displaystyle \text{So we must have simultaneously }x_2\ge x_1+1\text{ and }x_2\le x_1.$
$\displaystyle \text{But }x_2\ge x_1+1\text{ implies }x_2>x_1,\ \text{which contradicts }x_2\le x_1.$
$\displaystyle \text{Therefore, there is no point }(x_1,x_2)\textbf{ satisfying all the constraints.}$
$\displaystyle \text{Hence, the feasible region is empty and the LPP has no solution (maximum not defined).}$

$\displaystyle \textbf{Question 21: }~\text{Maximize }Z=3x+3y,\ \text{if possible,}$
$\displaystyle \text{Subject to the constraints }x-y\le 1$
$\displaystyle x+y\ge 3$
$\displaystyle x,y\ge 0$
$\displaystyle \text{Answer:}$ $\displaystyle \text{Convert the inequalities into equations/half-planes:}$
$\displaystyle x-y\le 1\ \Rightarrow\ y\ge x-1$
$\displaystyle x+y\ge 3\ \Rightarrow\ y\ge 3-x$
$\displaystyle x\ge 0,\ y\ge 0$
$\displaystyle \text{So the feasible region is in the first quadrant and lies \textit{above} the lines }y=x-1\text{ and }y=3-x.$
$\displaystyle \textbf{Intersection (corner) point of the boundary lines:}$
$\displaystyle y=x-1,\ \ y=3-x\Rightarrow x-1=3-x\Rightarrow 2x=4\Rightarrow x=2,\ y=1$
$\displaystyle \Rightarrow P(2,1)$
$\displaystyle \text{Also, on the }y\text{-axis (}x=0\text{), }x+y\ge 3\Rightarrow y\ge 3,\ \text{so }Q(0,3)\text{ lies on the boundary.}$
$\displaystyle \textbf{Unboundedness:}$
$\displaystyle \text{Take }(x,y)=(t,t)\text{ with }t\ge \frac{3}{2}.\ \text{Then }x-y=0\le 1,\ x+y=2t\ge 3,\ x,y\ge 0.$
$\displaystyle \text{So }(t,t)\text{ is feasible for all }t\ge \frac{3}{2},\ \text{and }Z=3t+3t=6t\to \infty\text{ as }t\to \infty.$
$\displaystyle \text{Therefore, the LPP has no finite maximum value (it is unbounded).}$

$\displaystyle \textbf{Question 22: }~\text{Show the solution zone of the following inequalities on a graph paper:}$
$\displaystyle 5x+y\ge 10$
$\displaystyle x+y\ge 6$
$\displaystyle x+4y\ge 12$
$\displaystyle x\ge 0,\ y\ge 0$
$\displaystyle \text{Find }x\text{ and }y\text{ for which }3x+2y\text{ is minimum subject to these inequalities. Use a graphical method.}$
$\displaystyle \text{Answer:}$
$\displaystyle \text{Convert inequalities into boundary lines:}$
$\displaystyle 5x+y=10,\ \ x+y=6,\ \ x+4y=12,\ \ x=0,\ \ y=0$
$\displaystyle \text{These represent straight lines in the }xy\text{-plane.}$
$\displaystyle \textbf{(1) Line }5x+y=10\text{:}$
$\displaystyle \text{It meets the }x\text{-axis at }A_1(2,0)\text{ and the }y\text{-axis at }B_1(0,10).$
$\displaystyle \textbf{(2) Line }x+y=6\text{:}$
$\displaystyle \text{It meets the }x\text{-axis at }A_2(6,0)\text{ and the }y\text{-axis at }B_2(0,6).$
$\displaystyle \textbf{(3) Line }x+4y=12\text{:}$
$\displaystyle \text{It meets the }x\text{-axis at }A_3(12,0)\text{ and the }y\text{-axis at }B_3(0,3).$
$\displaystyle \text{Since all inequalities are of type }\ge,\ \text{the solution zone (feasible region) is in} \\ \text{the first quadrant and lies \textit{above} all three lines.}$
$\displaystyle \text{Corner points of the feasible region (lower boundary) are obtained as follows:}$
$\displaystyle \text{Intersection of }5x+y=10\text{ and }x+y=6:$
$\displaystyle (5x+y)-(x+y)=10-6\Rightarrow 4x=4\Rightarrow x=1,\ y=5$
$\displaystyle \Rightarrow P(1,5)$
$\displaystyle \text{Intersection of }x+y=6\text{ and }x+4y=12:$
$\displaystyle (x+4y)-(x+y)=12-6\Rightarrow 3y=6\Rightarrow y=2,\ x=4$
$\displaystyle \Rightarrow Q(4,2)$
$\displaystyle \text{(Intersection of }5x+y=10\text{ and }x+4y=12\text{ gives }x=\frac{28}{19},y=\frac{50}{19} \\ \text{ but it does not satisfy }x+y\ge 6,\ \text{so it is not feasible.)}$
$\displaystyle \textbf{Now, take a constant value (say }13\text{) for }Z. \text{ Putting }Z=13\text{ in }Z=3x+2y, \\ \text{ we get }3x+2y=13.$
$\displaystyle \text{Move the line }3x+2y=k\text{ parallel to itself towards the origin (decreasing direction of }Z\text{).}$
$\displaystyle \text{The minimum value occurs at the first point where this line touches the feasible region,} \\ \text{i.e., at a corner point.}$
$\displaystyle \textbf{Value of }Z\text{ at corner points:}$
$\displaystyle Z(1,5)=3(1)+2(5)=13$
$\displaystyle Z(4,2)=3(4)+2(2)=16$
$\displaystyle \textbf{Therefore, the minimum value is }Z_{\min}=13$
$\displaystyle \textbf{at }x=1,\ y=5.$

$\displaystyle \textbf{Question 23: }~\text{Find the maximum and minimum value of }2x+y\text{ subject to the constraints:}$
$\displaystyle x+3y\ge 6$
$\displaystyle x-3y\le 3$
$\displaystyle 3x+4y\le 24$
$\displaystyle -3x+2y\le 6$
$\displaystyle 5x+y\ge 5$
$\displaystyle x,y\ge 0$
$\displaystyle \text{Answer:}$
$\displaystyle \text{Convert the inequalities into boundary lines:}$
$\displaystyle x+3y=6,\ \ x-3y=3,\ \ 3x+4y=24,\ \ -3x+2y=6,\ \ 5x+y=5,\ \ x=0,\ \ y=0$
$\displaystyle \text{These represent straight lines in the }xy\text{-plane and the feasible region is the} \\ \text{common region satisfying all the inequalities in the first quadrant.}$
$\displaystyle \text{Corner points of the feasible region (by intersection of boundary lines) are:}$
$\displaystyle P:\ (x+3y=6)\ \text{and}\ (5x+y=5)$
$\displaystyle x=6-3y,\ 5(6-3y)+y=5\Rightarrow 30-14y=5\Rightarrow y=\frac{25}{14},\ x=\frac{9}{14}$
$\displaystyle \Rightarrow P\left(\frac{9}{14},\frac{25}{14}\right)$
$\displaystyle Q:\ (x+3y=6)\ \text{and}\ (x-3y=3)$
$\displaystyle 2x=9\Rightarrow x=\frac{9}{2},\ y=\frac{1}{2}$
$\displaystyle \Rightarrow Q\left(\frac{9}{2},\frac{1}{2}\right)$
$\displaystyle R:\ (x-3y=3)\ \text{and}\ (3x+4y=24)$
$\displaystyle x=3+3y,\ 3(3+3y)+4y=24\Rightarrow 9+13y=24\Rightarrow y=\frac{15}{13},\ x=\frac{84}{13}$
$\displaystyle \Rightarrow R\left(\frac{84}{13},\frac{15}{13}\right)$
$\displaystyle S:\ (3x+4y=24)\ \text{and}\ (-3x+2y=6)$
$\displaystyle -3x+2y=6\Rightarrow y=3+\frac{3}{2}x$
$\displaystyle 3x+4\left(3+\frac{3}{2}x\right)=24\Rightarrow 9x+12=24\Rightarrow x=\frac{4}{3},\ y=5$
$\displaystyle \Rightarrow S\left(\frac{4}{3},5\right)$
$\displaystyle T:\ (-3x+2y=6)\ \text{and}\ (5x+y=5)$
$\displaystyle y=5-5x,\ -3x+2(5-5x)=6\Rightarrow -13x=-4\Rightarrow x=\frac{4}{13},\ y=\frac{45}{13}$
$\displaystyle \Rightarrow T\left(\frac{4}{13},\frac{45}{13}\right)$
$\displaystyle \text{Thus the corner points are }T\left(\frac{4}{13},\frac{45}{13}\right),\ P\left(\frac{9}{14},\frac{25}{14}\right),\ Q\left(\frac{9}{2},\frac{1}{2}\right),\ R\left(\frac{84}{13},\frac{15}{13}\right),\ S\left(\frac{4}{3},5\right).$
$\displaystyle \textbf{Now compute }Z=2x+y\textbf{ at each corner point:}$
$\displaystyle Z\left(T\right)=2\cdot\frac{4}{13}+\frac{45}{13}=\frac{53}{13}$
$\displaystyle Z\left(P\right)=2\cdot\frac{9}{14}+\frac{25}{14}=\frac{43}{14}$
$\displaystyle Z\left(Q\right)=2\cdot\frac{9}{2}+\frac{1}{2}=\frac{19}{2}$
$\displaystyle Z\left(R\right)=2\cdot\frac{84}{13}+\frac{15}{13}=\frac{183}{13}$
$\displaystyle Z\left(S\right)=2\cdot\frac{4}{3}+5=\frac{23}{3}$
$\displaystyle \textbf{Therefore,}$
$\displaystyle \textbf{Minimum value }Z_{\min}=\frac{43}{14}\textbf{ at }\left(x,y\right)=\left(\frac{9}{14},\frac{25}{14}\right).$
$\displaystyle \textbf{Maximum value }Z_{\max}=\frac{183}{13}\textbf{ at }\left(x,y\right)=\left(\frac{84}{13},\frac{15}{13}\right).$

$\displaystyle \textbf{Question 24: }~\text{Find the minimum value of }3x+5y\text{ subject to the constraints:}$
$\displaystyle -2x+y\le 4$
$\displaystyle x+y\ge 3$
$\displaystyle x-2y\le 2$
$\displaystyle x,y\ge 0$
$\displaystyle \text{Answer:}$
$\displaystyle \text{Convert the inequalities into boundary lines:}$
$\displaystyle -2x+y=4\ (\Rightarrow y=4+2x),\ \ x+y=3\ (\Rightarrow y=3-x),\ \ x-2y=2\ \\ (\Rightarrow y=\frac{x-2}{2}),\ \ x=0,\ \ y=0$
$\displaystyle \text{Since }-2x+y\le 4,\ \text{the region lies below }y=4+2x.$
$\displaystyle \text{Since }x+y\ge 3,\ \text{the region lies above }y=3-x.$
$\displaystyle \text{Since }x-2y\le 2,\ \text{we have }y\ge \frac{x-2}{2}.$
$\displaystyle \text{Also }x\ge 0,\ y\ge 0,\ \text{so the region is in the first quadrant.}$
$\displaystyle \textbf{Corner points of the feasible region:}$
$\displaystyle \text{On }x=0:\ x+y\ge 3\Rightarrow y\ge 3,\ \ -2x+y\le 4\Rightarrow y\le 4$
$\displaystyle \Rightarrow A(0,3),\ B(0,4)$
$\displaystyle \text{Intersection of }x+y=3\text{ and }x-2y=2:$
$\displaystyle y=3-x$
$\displaystyle x-2(3-x)=2$
$\displaystyle x-6+2x=2$
$\displaystyle 3x=8\Rightarrow x=\frac{8}{3},\ y=3-\frac{8}{3}=\frac{1}{3}$
$\displaystyle \Rightarrow C\left(\frac{8}{3},\frac{1}{3}\right)$
$\displaystyle \text{Thus the feasible region is the triangle with vertices }A(0,3),\ B(0,4),\ C\left(\frac{8}{3},\frac{1}{3}\right).$
$\displaystyle \textbf{Now compute }Z=3x+5y\textbf{ at the corner points:}$
$\displaystyle Z(A)=3(0)+5(3)=15$
$\displaystyle Z(B)=3(0)+5(4)=20$
$\displaystyle Z(C)=3\cdot\frac{8}{3}+5\cdot\frac{1}{3}=8+\frac{5}{3}=\frac{29}{3}$
$\displaystyle \text{Therefore, the minimum value is }Z_{\min}=\frac{29}{3}$
$\displaystyle \text{at }x=\frac{8}{3},\ y=\frac{1}{3}.$

$\displaystyle \textbf{Question 25: }~\text{Solve the following linear programming problem graphically:}$
$\displaystyle \text{Maximize }Z=60x+15y$
$\displaystyle \text{Subject to constraints }x+y\le 50$
$\displaystyle 3x+y\le 90$
$\displaystyle x,y\ge 0\ \hspace{7.0cm} \text{[CBSE\ 2005]}$
$\displaystyle \text{Answer:}$ $\displaystyle \text{Converting the inequalities into equations, we obtain the straight lines:}$
$\displaystyle x+y=50,\ \ 3x+y=90,\ \ x=0,\ \ y=0$
$\displaystyle \text{These represent straight lines in the }xy\text{-plane.}$
$\displaystyle \textbf{(1) Line }x+y=50\text{:}$
$\displaystyle \text{It meets the }x\text{-axis at }A_1(50,0)\text{ and the }y\text{-axis at }B_1(0,50).$
$\displaystyle \textbf{(2) Line }3x+y=90\text{:}$
$\displaystyle \text{It meets the }x\text{-axis at }A_2(30,0)\text{ and the }y\text{-axis at }B_2(0,90).$
$\displaystyle \text{Since both inequalities are of type }\le,\ \text{the feasible region lies in the first quadrant and is} \\ \text{below both lines.}$
$\displaystyle \textbf{Corner points of the feasible region are obtained as follows:}$
$\displaystyle O(0,0)$
$\displaystyle P:\ x=0\Rightarrow y\le 50\Rightarrow P(0,50)$
$\displaystyle Q:\ y=0\Rightarrow x\le 50,\ 3x\le 90\Rightarrow x\le 30\Rightarrow Q(30,0)$
$\displaystyle R:\ \text{Intersection of }x+y=50\text{ and }3x+y=90:$
$\displaystyle (3x+y)-(x+y)=90-50\Rightarrow 2x=40\Rightarrow x=20$
$\displaystyle y=50-20=30$
$\displaystyle \Rightarrow R(20,30)$
$\displaystyle \text{Hence the corner points are }O(0,0),\ P(0,50),\ R(20,30),\ Q(30,0).$
$\displaystyle \textbf{Now, take a constant value (say }1800\text{) for }Z. \text{ Putting }Z=1800\text{ in }Z=60x+15y, \text{ we get }60x+15y=1800.$
$\displaystyle \text{Move the line }60x+15y=k\text{ parallel to itself in the increasing direction of }Z \\ \text{ (away from the origin).}$
$\displaystyle \text{The maximum value occurs at the last point where this line touches the feasible region,} \\ \text{i.e., at a corner point.}$
$\displaystyle \textbf{Value of }Z\text{ at corner points:}$
$\displaystyle Z(0,0)=0$
$\displaystyle Z(0,50)=60(0)+15(50)=750$
$\displaystyle Z(20,30)=60(20)+15(30)=1200+450=1650$
$\displaystyle Z(30,0)=60(30)+15(0)=1800$
$\displaystyle \textbf{Therefore, the maximum value is }Z_{\max}=1800$
$\displaystyle \textbf{at }x=30,\ y=0.$

$\displaystyle \textbf{Question 26: }~\text{Find graphically, the maximum value of }z=2x+5y, \\ \text{ subject to constraints given below:}$
$\displaystyle 2x+4y\le 8$
$\displaystyle 3x+y\le 6$
$\displaystyle x+y\le 4$
$\displaystyle x\ge 0,\ y\ge 0\ \hspace{7.0cm} \text{[CBSE\ 2015]}$
$\displaystyle \text{Answer:}$
$\displaystyle \text{Convert the inequalities into equations (boundary lines):}$
$\displaystyle 2x+4y=8,\ \ 3x+y=6,\ \ x+y=4,\ \ x=0,\ \ y=0$
$\displaystyle \text{These represent straight lines in the }xy\text{-plane.}$
$\displaystyle \textbf{(1) Line }2x+4y=8\ (\Rightarrow x+2y=4)\text{:}$
$\displaystyle \text{It meets the }x\text{-axis at }A_1(4,0)\text{ and the }y\text{-axis at }B_1(0,2).$
$\displaystyle \textbf{(2) Line }3x+y=6\text{:}$
$\displaystyle \text{It meets the }x\text{-axis at }A_2(2,0)\text{ and the }y\text{-axis at }B_2(0,6).$
$\displaystyle \textbf{(3) Line }x+y=4\text{:}$
$\displaystyle \text{It meets the }x\text{-axis at }A_3(4,0)\text{ and the }y\text{-axis at }B_3(0,4).$
$\displaystyle \text{Since all inequalities are of type }\le,\ \text{the feasible region lies in the first quadrant and is} \\ \text{below these lines.}$
$\displaystyle \textbf{Corner points of the feasible region are obtained as follows:}$
$\displaystyle O(0,0)$
$\displaystyle \text{On }y=0:\ 2x\le 8,\ 3x\le 6,\ x\le 4\Rightarrow x\le 2\Rightarrow P(2,0)$
$\displaystyle \text{On }x=0:\ 4y\le 8,\ y\le 6,\ y\le 4\Rightarrow y\le 2\Rightarrow Q(0,2)$
$\displaystyle \text{Intersection of }(2x+4y=8)\text{ and }(3x+y=6):$
$\displaystyle x+2y=4$
$\displaystyle 3x+y=6$
$\displaystyle y=6-3x$
$\displaystyle x+2(6-3x)=4$
$\displaystyle x+12-6x=4$
$\displaystyle -5x=-8\Rightarrow x=\frac{8}{5}$
$\displaystyle y=6-3\cdot\frac{8}{5}=\frac{6}{5}$
$\displaystyle \Rightarrow R\left(\frac{8}{5},\frac{6}{5}\right)$
$\displaystyle \text{Hence the corner points are }O(0,0),\ P(2,0),\ R\left(\frac{8}{5},\frac{6}{5}\right),\ Q(0,2).$
$\displaystyle \textbf{Now, take a constant value (say }10\text{) for }Z. \text{ Putting }Z=10\text{ in }Z=2x+5y,\text{ we get }2x+5y=10.$
$\displaystyle \text{Move the line }2x+5y=k\text{ parallel to itself in the increasing direction of } \\ Z\text{ (away from the origin).}$
$\displaystyle \text{The maximum value occurs at the last point where this line touches the feasible region,} \\ \text{i.e., at a corner point.}$
$\displaystyle \textbf{Value of }Z\text{ at corner points:}$
$\displaystyle Z(0,0)=0$
$\displaystyle Z(2,0)=2(2)+5(0)=4$
$\displaystyle Z\left(\frac{8}{5},\frac{6}{5}\right)=2\cdot\frac{8}{5}+5\cdot\frac{6}{5}=\frac{16}{5}+6=\frac{46}{5}$
$\displaystyle Z(0,2)=2(0)+5(2)=10$
$\displaystyle \textbf{Therefore, the maximum value is }Z_{\max}=10$
$\displaystyle \textbf{at }x=0,\ y=2.$

$\displaystyle \textbf{Question 27: }~\text{Solve the following LPP graphically:}$
$\displaystyle \text{Maximize }Z=20x+10y$
$\displaystyle \text{Subject to the following constraints }x+2y\le 28$
$\displaystyle 3x+y\le 24$
$\displaystyle x\ge 2$
$\displaystyle x,y\ge 0\ \hspace{7.0cm} \text{[CBSE\ 2017]}$
$\displaystyle \text{Answer:}$ $\displaystyle \text{Boundary lines are }x+2y=28,\ 3x+y=24,\ x=2,\ x=0,\ y=0.$
$\displaystyle \text{Feasible region is in the first quadrant, to the right of }x=2\text{ and below both lines.}$
$\displaystyle \textbf{Corner points of the feasible region:}$
$\displaystyle A(2,0)$
$\displaystyle B(8,0)\ \ (\text{from }y=0,\ 3x+y=24\Rightarrow x=8)$
$\displaystyle C(2,13)\ \ (\text{from }x=2,\ x+2y=28\Rightarrow 2+2y=28\Rightarrow y=13)$
$\displaystyle D:\ \text{Intersection of }x+2y=28\text{ and }3x+y=24$
$\displaystyle y=24-3x$
$\displaystyle x+2(24-3x)=28$
$\displaystyle x+48-6x=28$
$\displaystyle -5x=-20\Rightarrow x=4,\ y=12$
$\displaystyle \Rightarrow D(4,12)$
$\displaystyle \textbf{Now compute }Z=20x+10y\textbf{ at each corner point:}$
$\displaystyle Z(2,0)=20(2)+10(0)=40$
$\displaystyle Z(8,0)=20(8)+10(0)=160$
$\displaystyle Z(2,13)=20(2)+10(13)=40+130=170$
$\displaystyle Z(4,12)=20(4)+10(12)=80+120=200$
$\displaystyle \textbf{Therefore, the maximum value is }Z_{\max}=200\textbf{ at }(x,y)=(4,12).$

$\displaystyle \textbf{Question 28: }~\text{Solve the following linear programming problem graphically:}$
$\displaystyle \text{Minimize }z=6x+3y$
$\displaystyle \text{Subject to the constraints: }4x+y\ge 80$
$\displaystyle x+5y\ge 115$
$\displaystyle 3x+2y\le 150$
$\displaystyle x\ge 0,\ y\ge 0\ \hspace{7.0cm} \text{[CBSE\ 2017]}$
$\displaystyle \text{Answer:}$
$\displaystyle \text{Convert the constraints into boundary lines:}$
$\displaystyle 4x+y=80,\ \ x+5y=115,\ \ 3x+2y=150,\ \ x=0,\ \ y=0$
$\displaystyle \text{Since }4x+y\ge 80\text{ and }x+5y\ge 115,\text{ the feasible region lies above these two lines.}$
$\displaystyle \text{Since }3x+2y\le 150,\text{ the feasible region lies below the line }3x+2y=150.$
$\displaystyle \text{Thus the feasible region is the shaded triangular region }ABC\text{ (as in the reference figure).}$
$\displaystyle \textbf{Corner points (vertices) of the feasible region:}$
$\displaystyle \text{(i) Intersection of }4x+y=80\text{ and }3x+2y=150:$
$\displaystyle y=80-4x$
$\displaystyle 3x+2(80-4x)=150$
$\displaystyle 3x+160-8x=150$
$\displaystyle -5x=-10\Rightarrow x=2,\ y=72$
$\displaystyle \Rightarrow A(2,72)$
$\displaystyle \text{(ii) Intersection of }4x+y=80\text{ and }x+5y=115:$
$\displaystyle y=80-4x$
$\displaystyle x+5(80-4x)=115$
$\displaystyle x+400-20x=115$
$\displaystyle -19x=-285\Rightarrow x=15,\ y=20$
$\displaystyle \Rightarrow B(15,20)$
$\displaystyle \text{(iii) Intersection of }x+5y=115\text{ and }3x+2y=150:$
$\displaystyle x=115-5y$
$\displaystyle 3(115-5y)+2y=150$
$\displaystyle 345-15y+2y=150$
$\displaystyle -13y=-195\Rightarrow y=15,\ x=40$
$\displaystyle \Rightarrow C(40,15)$
$\displaystyle \textbf{Now compute }Z=6x+3y\textbf{ at the corner points:}$
$\displaystyle Z(A)=6(2)+3(72)=12+216=228$
$\displaystyle Z(B)=6(15)+3(20)=90+60=150$
$\displaystyle Z(C)=6(40)+3(15)=240+45=285$
$\displaystyle \textbf{Therefore, the minimum value is }Z_{\min}=150$
$\displaystyle \textbf{at }(x,y)=(15,20).$