Example 1
Question: Solve the following Linear Programming Problem graphically: Maximize \[Z = 150x + 250y\] Subject to constraints: \[2x + y \le 500\] \[x + 3y \le 600\] \[x - y \ge -50\] \[x, y \ge 0\]
Solution: We maximize \(Z = 150x + 250y\) subject to the given constraints. Step 1: Find the boundary lines and their intercepts. For \(2x + y = 500\): intercepts are \((250, 0)\) and \((0, 500)\). For \(x + 3y = 600\): intercepts are \((600, 0)\) and \((0, 200)\). For \(x - y = -50\), i.e., \(y = x + 50\): intercepts are \((0, 50)\) and \((-50, 0)\) — but since \(x \ge 0\), relevant point is \((0, 50)\). Step 2: Determine the feasible region by checking which side of each boundary satisfies the inequality. Step 3: Find corner points of the feasible region. Corner Point A — intersection of \(x = 0\) and \(x - y = -50\): Setting \(x = 0\): \(-y = -50\), so \(y = 50\). Point: \((0, 50)\). Corner Point B — intersection of \(x = 0\) and \(x + 3y = 600\): Setting \(x = 0\): \(3y = 600\), so \(y = 200\). Point: \((0, 200)\). Corner Point C — intersection of \(2x + y = 500\) and \(x + 3y = 600\): From first equation: \(y = 500 - 2x\). Substituting: \[x + 3(500 - 2x) = 600\] \[x + 1500 - 6x = 600\] \[-5x = -900\] \[x = 180, \quad y = 500 - 360 = 140\] Point: \((180, 140)\). Corner Point D — intersection of \(2x + y = 500\) and \(y = 0\): Setting \(y = 0\): \(2x = 500\), so \(x = 250\). Point: \((250, 0)\). Corner Point E — intersection of \(x - y = -50\) and \(y = 0\): gives \(x = -50\), not valid since \(x \ge 0\). So the feasible region does not include this. We also check \(x = 0, y = 0\): \(x - y = 0 \ge -50\) (satisfied), \(2(0)+0 = 0 \le 500\) (satisfied), \(0 + 0 = 0 \le 600\) (satisfied). So origin is feasible, but let us verify all listed corners are vertices. The corner points of the feasible region are: \(A(0, 50)\), \(B(0, 200)\), \(C(180, 140)\), \(D(250, 0)\), and we check if \((0,0)\) is a vertex — it is not, because the constraint \(x - y \ge -50\) at \((0,0)\) gives \(0 \ge -50\) (satisfied) but the region boundary \(x - y = -50\) cuts the \(y\)-axis at \((0,50)\), so the lower part of the \(y\)-axis from \(0\) to \(50\) lies below the line \(y = x+50\) in the sense that \(x - y = -50\) is the lower limit. Actually at \((0,0)\): \(0 - 0 = 0 \ge -50\) is satisfied. So \((0,0)\) is in the feasible region but is it a corner? The region is bounded by \(x=0\), \(y=0\), and \(x - y \ge -50\). At \((0,0)\), \(x-y=0\) which is strictly \(\ge -50\), so \((0,0)\) is interior to that constraint — it is a corner of the region formed by \(x=0\) and \(y=0\). Let us list all corners carefully: The feasible region is bounded by \(x \ge 0\), \(y \ge 0\), \(2x+y \le 500\), \(x+3y \le 600\), \(x - y \ge -50\). On the \(x\)-axis (\(y=0\)): \(x - 0 \ge -50\) always for \(x \ge 0\). So the segment from \((0,0)\) to \((250,0)\) is feasible. On the \(y\)-axis (\(x=0\)): \(-y \ge -50 \Rightarrow y \le 50\) is required for \(x-y \ge -50\). Also \(3y \le 600 \Rightarrow y \le 200\) and \(y \le 500\). So on \(y\)-axis the feasible part is \(0 \le y \le 50\), giving vertex \((0,50)\) where \(x-y=-50\) meets \(x=0\). So corners are: \(O(0,0)\), \(A(0,50)\), then along \(x-y=-50\) to intersection with \(x+3y=600\). Intersection of \(x - y = -50\) and \(x + 3y = 600\): From first: \(x = y - 50\). Substituting: \[(y-50) + 3y = 600\] \[4y = 650\] \[y = 162.5, \quad x = 112.5\] Point: \((112.5,\ 162.5)\). Check \(2x+y\): \(2(112.5)+162.5 = 225+162.5 = 387.5 \le 500\). Valid. Corner Point E: \((112.5,\ 162.5)\). Then from E along \(x+3y=600\) to intersection with \(2x+y=500\): already found as \(C(180,140)\). Check \(x-y\) at C: \(180-140=40 \ge -50\). Valid. Then from C along \(2x+y=500\) to \(D(250,0)\). Check \(x+3y\) at D: \(250 \le 600\). Valid. Check \(x-y\): \(250 \ge -50\). Valid. From D along \(y=0\) back to \(O(0,0)\). So the corner points are: \(O(0,0)\), \(A(0,50)\), \(E(112.5,\ 162.5)\), \(C(180,\ 140)\), \(D(250,\ 0)\). Step 4: Evaluate \(Z = 150x + 250y\) at each corner. At \(O(0,0)\): \(Z = 0\). At \(A(0,50)\): \(Z = 150(0) + 250(50) = 12500\). At \(E(112.5,\ 162.5)\): \(Z = 150(112.5) + 250(162.5) = 16875 + 40625 = 57500\). At \(C(180,\ 140)\): \(Z = 150(180) + 250(140) = 27000 + 35000 = 62000\). At \(D(250,\ 0)\): \(Z = 150(250) + 250(0) = 37500\). Step 5: The maximum value of Z is at corner C. Maximum \(Z = 62000\) at \(x = 180,\ y = 140\).
Answer: Maximum \(Z = 62000\) at \(x = 180,\ y = 140\).
Example 2
Question: Solve the following Linear Programming Problem graphically: Maximize \[Z = 300x + 180y\] Subject to constraints: \[x + y \le 400\] \[2x + y \le 600\] \[x - 2y \le 200\] \[x, y \ge 0\]
Solution: We maximize \(Z = 300x + 180y\) subject to the given constraints. Step 1: Find boundary intercepts. For \(x + y = 400\): intercepts \((400, 0)\) and \((0, 400)\). For \(2x + y = 600\): intercepts \((300, 0)\) and \((0, 600)\). For \(x - 2y = 200\): intercepts \((200, 0)\) and \((0, -100)\) — the \(y\)-intercept is negative, so relevant in first quadrant only near \(x\)-axis. Step 2: Identify the feasible region satisfying all constraints and \(x, y \ge 0\). Step 3: Find corner points. Corner A — origin \((0, 0)\): Check \(x - 2y = 0 \le 200\) ✓, \(x+y=0\le 400\) ✓, \(2x+y=0\le600\) ✓. Valid. Corner B — intersection of \(x - 2y = 200\) and \(y = 0\): Setting \(y=0\): \(x = 200\). Point: \((200, 0)\). Check: \(200+0=200\le400\) ✓, \(400+0=400\le600\) ✓. Corner C — intersection of \(2x + y = 600\) and \(y = 0\): Setting \(y=0\): \(x=300\). Point: \((300, 0)\). Check \(x+y\): \(300\le400\) ✓. Check \(x-2y\): \(300\le200\)? No, \(300 > 200\). Not feasible. So \((300,0)\) is NOT in the feasible region. Let us find the intersection of \(x-2y=200\) and \(2x+y=600\): From first: \(x = 200 + 2y\). Substituting: \[2(200+2y)+y = 600\] \[400+4y+y = 600\] \[5y = 200\] \[y = 40, \quad x = 200+80 = 280\] Point: \((280, 40)\). Check \(x+y\): \(320\le400\) ✓. Corner C: \((280, 40)\). Corner D — intersection of \(2x+y=600\) and \(x+y=400\): Subtracting second from first: \(x = 200\), \(y = 200\). Point: \((200,200)\). Check \(x-2y\): \(200-400=-200\le200\) ✓. Corner D: \((200, 200)\). Corner E — intersection of \(x+y=400\) and \(x=0\): Setting \(x=0\): \(y=400\). Point: \((0,400)\). Check \(2x+y\): \(400\le600\) ✓. Check \(x-2y\): \(-800\le200\) ✓. Corner E: \((0, 400)\). Corner F — \(y\)-axis and \(y=0\): \((0,0)\) already listed as A. Also check if there is a corner between B and C along \(x-2y=200\): we already found \(C(280,40)\) is the intersection with \(2x+y=600\). Between B\((200,0)\) and C\((280,40)\) the boundary is \(x-2y=200\). The corner points of the feasible region are: \(A(0,0)\), \(B(200,0)\), \(C(280,40)\), \(D(200,200)\), \(E(0,400)\). Step 4: Evaluate \(Z = 300x + 180y\) at each corner. At \(A(0,0)\): \(Z = 0\). At \(B(200,0)\): \(Z = 300(200)+180(0) = 60000\). At \(C(280,40)\): \(Z = 300(280)+180(40) = 84000+7200 = 91200\). At \(D(200,200)\): \(Z = 300(200)+180(200) = 60000+36000 = 96000\). At \(E(0,400)\): \(Z = 300(0)+180(400) = 72000\). Step 5: The maximum value of Z occurs at D. Maximum \(Z = 96000\) at \(x = 200,\ y = 200\).
Answer: Maximum \(Z = 96000\) at \(x = 200,\ y = 200\).