Example 1
Question: Determine graphically the minimum value of the objective function \[Z = -40x + 30y\] subject to the constraints: \[x + y \ge 4\] \[2x + y \ge 6\] \[x + 2y \le 14\] \[x \ge 0,\quad y \ge 0\]
Solution: We identify and graph the boundary lines of each constraint. Constraint 1: \(x + y = 4\). Intercepts: \((4, 0)\) and \((0, 4)\). Test \((0,0)\): \(0 + 0 = 0 \not\ge 4\), so the feasible side is away from the origin. Constraint 2: \(2x + y = 6\). Intercepts: \((3, 0)\) and \((0, 6)\). Test \((0,0)\): \(0 \not\ge 6\), so the feasible side is away from the origin. Constraint 3: \(x + 2y = 14\). Intercepts: \((14, 0)\) and \((0, 7)\). Test \((0,0)\): \(0 \le 14\), so the feasible side includes the origin. Now we find the corner points of the feasible region. Intersection of \(2x + y = 6\) and \(x \ge 0, y = 0\): Setting \(y = 0\) gives \(x = 3\). Check \(x + y \ge 4\): \(3 \ge 4\) is false, so \((3, 0)\) is not in the feasible region. Intersection of \(x + y = 4\) and \(x = 0\): \(y = 4\), giving point \((0, 4)\). Check constraint 2: \(0 + 4 = 4 \not\ge 6\). Not feasible. Intersection of \(2x + y = 6\) and \(x = 0\): \(y = 6\), giving \((0, 6)\). Check \(x + y \ge 4\): \(6 \ge 4\) ✓. Check \(x + 2y \le 14\): \(12 \le 14\) ✓. Feasible. Intersection of \(2x + y = 6\) and \(x + y = 4\): Subtract the second from the first: \(x = 2\), then \(y = 2\). Check \(x + 2y \le 14\): \(2 + 4 = 6 \le 14\) ✓. Corner point: \((2, 2)\). Intersection of \(x + y = 4\) and \(x + 2y = 14\): Subtract: \(-y = -10\), so \(y = 10\), \(x = -6\). Since \(x < 0\), this is not feasible. Intersection of \(2x + y = 6\) and \(x + 2y = 14\): Multiply the first by 2: \(4x + 2y = 12\). Subtract: \(3x = -2\), so \(x = -\frac{2}{3}\). Not feasible. Intersection of \(x + 2y = 14\) and \(x = 0\): \(y = 7\). Check both \(\ge\) constraints: \(0 + 7 = 7 \ge 4\) ✓ and \(0 + 7 = 7 \ge 6\) ✓. Corner point: \((0, 7)\). The feasible region is unbounded above-left. The identified corner points are \((2, 2)\), \((0, 6)\), and \((0, 7)\). Now evaluate \(Z = -40x + 30y\) at each corner point. At \((2, 2)\): \[Z = -40(2) + 30(2) = -80 + 60 = -20\] At \((0, 6)\): \[Z = -40(0) + 30(6) = 0 + 180 = 180\] At \((0, 7)\): \[Z = -40(0) + 30(7) = 0 + 210 = 210\] The smallest value is \(Z = -20\) at \((2, 2)\). Since the feasible region is unbounded and the coefficient of \(x\) in \(Z\) is negative, we check whether there exist points in the feasible region with \(Z < -20\), i.e., \(-40x + 30y < -20\). This simplifies to \(4x - 3y > 2\). Checking whether this half-plane has a common point with the feasible region: take \((3, 0)\): it satisfies \(4(3) - 3(0) = 12 > 2\), but \((3,0)\) must satisfy all constraints. Check \(2(3) + 0 = 6 \ge 6\) ✓, \(3 + 0 = 3 \not\ge 4\). Not feasible. Try \((5, 2)\): \(2(5)+2 = 12 \ge 6\) ✓, \(5+2 = 7 \ge 4\) ✓, \(5+4 = 9 \le 14\) ✓. Check \(4(5)-3(2) = 14 > 2\) ✓. So there exist feasible points with \(Z < -20\), meaning the objective function has no finite minimum over this unbounded region. Hence, the minimum value of \(Z\) does not exist (the objective function is unbounded below over the feasible region).
Answer: The minimum value of \(Z = -40x + 30y\) does not exist; the objective function is unbounded below over the feasible region.
Example 2
Question: Determine graphically the minimum value of the objective function \[Z = -30x + 10y\] subject to the constraints: \[x - y \ge -3\] \[x + 2y \ge 6\] \[x + y \le 10\] \[x \ge 0,\quad y \ge 0\]
Solution: We graph the boundary lines. Constraint 1: \(x - y = -3\), i.e., \(y = x + 3\). Intercepts: \((0, 3)\) and \((-3, 0)\) (outside first quadrant). Test \((0,0)\): \(0 - 0 = 0 \ge -3\) ✓, so the feasible side includes the origin. Constraint 2: \(x + 2y = 6\). Intercepts: \((6, 0)\) and \((0, 3)\). Test \((0,0)\): \(0 \not\ge 6\), feasible side is away from origin. Constraint 3: \(x + y = 10\). Intercepts: \((10, 0)\) and \((0, 10)\). Test \((0,0)\): \(0 \le 10\) ✓, feasible side includes origin. Now find the corner points of the feasible region (first quadrant). Intersection of \(x + 2y = 6\) and \(y = 0\): \(x = 6\). Check all: \(6 - 0 = 6 \ge -3\) ✓, \(6 + 0 = 6 \le 10\) ✓. Corner point: \((6, 0)\). Intersection of \(x + 2y = 6\) and \(x - y = -3\): From \(x = y - 3\), substitute: \((y-3) + 2y = 6\), so \(3y = 9\), \(y = 3\), \(x = 0\). Check \(x + y = 3 \le 10\) ✓ and \(x \ge 0\) ✓. Corner point: \((0, 3)\). Intersection of \(x - y = -3\) and \(x + y = 10\): Add: \(2x = 7\), \(x = 3.5\), \(y = 6.5\). Check \(x + 2y = 3.5 + 13 = 16.5 \ge 6\) ✓. Corner point: \((3.5, 6.5)\). Intersection of \(x + 2y = 6\) and \(x + y = 10\): Subtract: \(y = -4\). Not feasible. Intersection of \(x + y = 10\) and \(x = 0\): \(y = 10\). Check \(0 - 10 = -10 \ge -3\)? No. Not feasible. Intersection of \(x + y = 10\) and \(y = 0\): \(x = 10\). Check \(10 + 0 = 10 \ge 6\) ✓ and \(10 - 0 = 10 \ge -3\) ✓. Corner point: \((10, 0)\). The feasible region is bounded. Corner points are \((6, 0)\), \((10, 0)\), \((3.5, 6.5)\), and \((0, 3)\). Evaluate \(Z = -30x + 10y\) at each corner point. At \((6, 0)\): \[Z = -30(6) + 10(0) = -180\] At \((10, 0)\): \[Z = -30(10) + 10(0) = -300\] At \((3.5, 6.5)\): \[Z = -30(3.5) + 10(6.5) = -105 + 65 = -40\] At \((0, 3)\): \[Z = -30(0) + 10(3) = 0 + 30 = 30\] The minimum value is \(Z = -300\) at the corner point \((10, 0)\).
Answer: The minimum value of \(Z = -30x + 10y\) is \(-300\), attained at \((10, 0)\).