Example 1
Question: Solve graphically the following linear programming problem: Maximize \( z = 5x + 4y \), subject to the constraints \( 6x + y \ge 60 \), \( x + y \le 50 \), \( x + 4y \ge 80 \), \( x \ge 0 \), \( y \ge 0 \).
Solution: Step 1: Write the constraints and objective function. Objective: Maximize \( z = 5x + 4y \) Constraints: \[ 6x + y \ge 60 \] \[ x + y \le 50 \] \[ x + 4y \ge 80 \] \[ x \ge 0, \quad y \ge 0 \] Step 2: Find intercepts of each boundary line. For \( 6x + y = 60 \): x-intercept = \( (10, 0) \), y-intercept = \( (0, 60) \). For \( x + y = 50 \): x-intercept = \( (50, 0) \), y-intercept = \( (0, 50) \). For \( x + 4y = 80 \): x-intercept = \( (80, 0) \), y-intercept = \( (0, 20) \). Step 3: Determine the feasible region satisfying all constraints simultaneously (including \( x \ge 0, y \ge 0 \)). Step 4: Find the corner points of the feasible region. Intersection of \( 6x + y = 60 \) and \( x + y = 50 \): Subtracting: \( 5x = 10 \), so \( x = 2 \), \( y = 48 \). Point: \( (2, 48) \). Check all constraints for \( (2, 48) \): \( 6(2) + 48 = 60 \ge 60 \) ✓, \( 2 + 48 = 50 \le 50 \) ✓, \( 2 + 4(48) = 194 \ge 80 \) ✓. Intersection of \( x + y = 50 \) and \( x + 4y = 80 \): Subtracting: \( -3y = -30 \), so \( y = 10 \), \( x = 40 \). Point: \( (40, 10) \). Check: \( 6(40) + 10 = 250 \ge 60 \) ✓, \( 40 + 10 = 50 \le 50 \) ✓, \( 40 + 40 = 80 \ge 80 \) ✓. Intersection of \( 6x + y = 60 \) and \( x + 4y = 80 \): From first: \( y = 60 - 6x \). Substituting: \( x + 4(60 - 6x) = 80 \), so \( x + 240 - 24x = 80 \), so \( -23x = -160 \), thus \( x = \frac{160}{23} \approx 6.96 \), \( y = 60 - 6 \cdot \frac{160}{23} = \frac{420}{23} \approx 18.26 \). Check \( x + y = \frac{160}{23} + \frac{420}{23} = \frac{580}{23} = \frac{580}{23} \approx 25.2 \le 50 \) ✓. Point: \( \left(\frac{160}{23}, \frac{420}{23}\right) \). So the corner points of the feasible region are: \( A = \left(\frac{160}{23}, \frac{420}{23}\right) \), \( B = (2, 48) \), \( C = (40, 10) \). Step 5: Evaluate \( z = 5x + 4y \) at each corner point. At \( A = \left(\frac{160}{23}, \frac{420}{23}\right) \): \[ z = 5 \cdot \frac{160}{23} + 4 \cdot \frac{420}{23} = \frac{800 + 1680}{23} = \frac{2480}{23} \approx 107.8 \] At \( B = (2, 48) \): \[ z = 5(2) + 4(48) = 10 + 192 = 202 \] At \( C = (40, 10) \): \[ z = 5(40) + 4(10) = 200 + 40 = 240 \] Step 6: The maximum value is \( z = 240 \) at \( (40, 10) \).
Answer: Maximum value of \( z = 240 \) at \( x = 40 \), \( y = 10 \).
Example 2
Question: Solve graphically the following linear programming problem: Maximize \( z = 7x + 5y \), subject to the constraints \( 2x + y \ge 14 \), \( x + 2y \le 28 \), \( x + y \ge 10 \), \( x \ge 0 \), \( y \ge 0 \).
Solution: Step 1: Write the objective function and constraints. Objective: Maximize \( z = 7x + 5y \) Constraints: \[ 2x + y \ge 14 \] \[ x + 2y \le 28 \] \[ x + y \ge 10 \] \[ x \ge 0, \quad y \ge 0 \] Step 2: Find intercepts of each boundary line. For \( 2x + y = 14 \): x-intercept = \( (7, 0) \), y-intercept = \( (0, 14) \). For \( x + 2y = 28 \): x-intercept = \( (28, 0) \), y-intercept = \( (0, 14) \). For \( x + y = 10 \): x-intercept = \( (10, 0) \), y-intercept = \( (0, 10) \). Step 3: Identify the feasible region satisfying all constraints with \( x \ge 0, y \ge 0 \). Step 4: Find corner points of the feasible region. Intersection of \( 2x + y = 14 \) and \( x + y = 10 \): Subtracting: \( x = 4 \), \( y = 6 \). Point: \( (4, 6) \). Check \( x + 2y = 4 + 12 = 16 \le 28 \) ✓. Intersection of \( 2x + y = 14 \) and \( x + 2y = 28 \): From first: \( y = 14 - 2x \). Substituting: \( x + 2(14 - 2x) = 28 \), so \( x + 28 - 4x = 28 \), thus \( -3x = 0 \), giving \( x = 0 \), \( y = 14 \). Point: \( (0, 14) \). Check \( x + y = 0 + 14 = 14 \ge 10 \) ✓, \( 2(0) + 14 = 14 \ge 14 \) ✓. Intersection of \( x + 2y = 28 \) and \( x + y = 10 \): Subtracting: \( y = 18 \), \( x = -8 \). Since \( x < 0 \), this point is outside the feasible region (violates \( x \ge 0 \)). Intersection of \( x + 2y = 28 \) with \( x = 0 \): \( y = 14 \). Already found: \( (0, 14) \). Intersection of \( 2x + y = 14 \) with \( y = 0 \): \( x = 7 \). Point: \( (7, 0) \). Check \( x + y = 7 \ge 10 \)? No, \( 7 < 10 \). This violates \( x + y \ge 10 \), so \( (7, 0) \) is NOT in the feasible region. Intersection of \( x + y = 10 \) with \( y = 0 \): \( x = 10 \). Point: \( (10, 0) \). Check \( 2(10) + 0 = 20 \ge 14 \) ✓, \( 10 + 0 = 10 \le 28 \) ✓. Intersection of \( x + 2y = 28 \) with \( y = 0 \): \( x = 28 \). Point: \( (28, 0) \). Check \( 2(28) + 0 = 56 \ge 14 \) ✓, \( 28 + 0 = 28 \ge 10 \) ✓. So the feasible region is unbounded (for large \( x \)) with corner points: \( (0, 14) \), \( (4, 6) \), \( (10, 0) \), and the region extends toward \( (28, 0) \) and beyond along \( x + 2y \le 28 \). The boundary of the feasible region has vertices: \( P_1 = (0, 14) \), \( P_2 = (4, 6) \), \( P_3 = (10, 0) \), \( P_4 = (28, 0) \). Step 5: Evaluate \( z = 7x + 5y \) at each vertex. At \( P_1 = (0, 14) \): \[ z = 7(0) + 5(14) = 70 \] At \( P_2 = (4, 6) \): \[ z = 7(4) + 5(6) = 28 + 30 = 58 \] At \( P_3 = (10, 0) \): \[ z = 7(10) + 5(0) = 70 \] At \( P_4 = (28, 0) \): \[ z = 7(28) + 5(0) = 196 \] Since the region is unbounded (extending in the direction of large \( x \)) and the coefficient of \( x \) in the objective function is positive, \( z \) increases without bound as \( x \) increases. Therefore, we check whether there exists a half-plane \( 7x + 5y > 196 \) that has a common point with the feasible region. Since for any \( x > 28 \) with \( y = 0 \), both \( x + 2y \le 28 \) is violated, the feasible region is actually bounded by \( x + 2y \le 28 \) and the maximum is attained at \( P_4 = (28, 0) \). Verifying \( (28, 0) \) satisfies all constraints: \( 2(28) + 0 = 56 \ge 14 \) ✓, \( 28 + 0 = 28 \le 28 \) ✓, \( 28 + 0 = 28 \ge 10 \) ✓, \( x = 28 \ge 0 \) ✓, \( y = 0 \ge 0 \) ✓. Step 6: Maximum value is \( z = 196 \) at \( (28, 0) \).
Answer: Maximum value of \( z = 196 \) at \( x = 28 \), \( y = 0 \).