Example 1
Question: Solve the following linear programming problem graphically: Maximise \( z = 400x + 600y \) subject to the constraints: \( x + 2y \le 10 \), \( 3x + y \le 12 \), \( 5x + 8y \ge 40 \), \( x \ge 0 \), \( y \ge 0 \).
Solution: We need to maximise \( z = 400x + 600y \) subject to the given constraints. Step 1: Draw the boundary lines. Line 1: \( x + 2y = 10 \). When \( x = 0 \), \( y = 5 \); when \( y = 0 \), \( x = 10 \). Points: \( (0, 5) \) and \( (10, 0) \). Line 2: \( 3x + y = 12 \). When \( x = 0 \), \( y = 12 \); when \( y = 0 \), \( x = 4 \). Points: \( (0, 12) \) and \( (4, 0) \). Line 3: \( 5x + 8y = 40 \). When \( x = 0 \), \( y = 5 \); when \( y = 0 \), \( x = 8 \). Points: \( (0, 5) \) and \( (8, 0) \). Step 2: Determine the feasible region. For \( x + 2y \le 10 \): the region is on and below Line 1. For \( 3x + y \le 12 \): the region is on and below Line 2. For \( 5x + 8y \ge 40 \): the region is on and above Line 3. With \( x \ge 0 \) and \( y \ge 0 \), the feasible region lies in the first quadrant. Step 3: Find the corner points of the feasible region. Corner A: Intersection of \( x + 2y = 10 \) and \( x = 0 \): point \( (0, 5) \). Corner B: Intersection of \( x + 2y = 10 \) and \( 3x + y = 12 \). From the first equation: \( x = 10 - 2y \). Substituting: \( 3(10 - 2y) + y = 12 \), so \( 30 - 6y + y = 12 \), giving \( 5y = 18 \), hence \( y = \frac{18}{5} \) and \( x = 10 - 2 \times \frac{18}{5} = \frac{14}{5} \). Point: \( \left(\frac{14}{5},\ \frac{18}{5}\right) \). Corner C: Intersection of \( 3x + y = 12 \) and \( y = 0 \): \( x = 4 \). Point: \( (4, 0) \). Corner D: Intersection of \( 5x + 8y = 40 \) and \( y = 0 \): \( x = 8 \). But we must check \( 3x + y \le 12 \): at \( (8,0) \), \( 24 \le 12 \) is false. So \( (8, 0) \) is not feasible. Corner D (revised): Intersection of \( 5x + 8y = 40 \) and \( x = 0 \): \( y = 5 \). This coincides with Point A \( (0, 5) \). So the feasible region is bounded by the corner points \( (0, 5) \), \( \left(\frac{14}{5}, \frac{18}{5}\right) \), and \( (4, 0) \). We verify \( (4, 0) \) satisfies \( 5x + 8y \ge 40 \): \( 20 \ge 40 \) is false. So \( (4, 0) \) is NOT in the feasible region. Let us carefully re-examine: The feasible region must satisfy all three inequalities simultaneously. Checking the origin \( (0, 0) \): \( 5(0)+8(0) = 0 \ge 40 \) is false, so the origin is not feasible. The feasible region is above Line 3 and below Lines 1 and 2. Intersection of \( 5x + 8y = 40 \) and \( 3x + y = 12 \): From the second, \( y = 12 - 3x \). Substituting: \( 5x + 8(12 - 3x) = 40 \), so \( 5x + 96 - 24x = 40 \), giving \( -19x = -56 \), hence \( x = \frac{56}{19} \) and \( y = 12 - 3 \cdot \frac{56}{19} = \frac{228 - 168}{19} = \frac{60}{19} \). Point E: \( \left(\frac{56}{19}, \frac{60}{19}\right) \). The feasible corner points are: \( A = (0, 5) \), \( B = \left(\frac{14}{5}, \frac{18}{5}\right) \), \( E = \left(\frac{56}{19}, \frac{60}{19}\right) \). Step 4: Evaluate \( z = 400x + 600y \) at each corner point. At \( A = (0, 5) \): \[ z = 400(0) + 600(5) = 3000 \] At \( B = \left(\frac{14}{5}, \frac{18}{5}\right) \): \[ z = 400 \times \frac{14}{5} + 600 \times \frac{18}{5} = \frac{5600}{5} + \frac{10800}{5} = \frac{16400}{5} = 3280 \] At \( E = \left(\frac{56}{19}, \frac{60}{19}\right) \): \[ z = 400 \times \frac{56}{19} + 600 \times \frac{60}{19} = \frac{22400 + 36000}{19} = \frac{58400}{19} \approx 3073.7 \] Step 5: The maximum value of \( z \) is \( 3280 \) at \( \left(\frac{14}{5}, \frac{18}{5}\right) \).
Answer: Maximum value of \( z = 3280 \) at \( x = \frac{14}{5} \), \( y = \frac{18}{5} \).
Example 2
Question: Solve the following linear programming problem graphically: Maximise \( z = 300x + 500y \) subject to the constraints: \( x + y \le 8 \), \( x + 3y \le 18 \), \( 2x + y \ge 6 \), \( x \ge 0 \), \( y \ge 0 \).
Solution: We need to maximise \( z = 300x + 500y \) subject to the given constraints. Step 1: Draw the boundary lines. Line 1: \( x + y = 8 \). Points: \( (0, 8) \) and \( (8, 0) \). Line 2: \( x + 3y = 18 \). Points: \( (0, 6) \) and \( (18, 0) \). Line 3: \( 2x + y = 6 \). Points: \( (0, 6) \) and \( (3, 0) \). Step 2: Determine the feasible region. For \( x + y \le 8 \): region on and below Line 1. For \( x + 3y \le 18 \): region on and below Line 2. For \( 2x + y \ge 6 \): region on and above Line 3. With \( x \ge 0 \), \( y \ge 0 \): first quadrant. The origin \( (0, 0) \): check \( 2(0) + 0 = 0 \ge 6 \) is false, so the origin is not feasible. The feasible region is above Line 3. Step 3: Find the corner points. Corner A: Intersection of \( 2x + y = 6 \) and \( x = 0 \): \( y = 6 \). Point: \( (0, 6) \). Check \( x + y = 6 \le 8 \) (true) and \( x + 3y = 18 \le 18 \) (true). Feasible. Corner B: Intersection of \( x + 3y = 18 \) and \( x + y = 8 \). Subtracting: \( 2y = 10 \), so \( y = 5 \) and \( x = 3 \). Point: \( (3, 5) \). Check \( 2(3) + 5 = 11 \ge 6 \) (true). Feasible. Corner C: Intersection of \( x + y = 8 \) and \( 2x + y = 6 \). Subtracting: \( x = -2 \). Since \( x \ge 0 \), this is not feasible. Corner D: Intersection of \( 2x + y = 6 \) and \( y = 0 \): \( x = 3 \). Point: \( (3, 0) \). Check \( x + y = 3 \le 8 \) (true) and \( x + 3y = 3 \le 18 \) (true). Feasible. Corner E: Intersection of \( x + y = 8 \) and \( y = 0 \): \( x = 8 \). Point: \( (8, 0) \). Check \( 2(8) + 0 = 16 \ge 6 \) (true). Feasible. So the feasible corner points are: \( A = (0, 6) \), \( B = (3, 5) \), \( E = (8, 0) \), and \( D = (3, 0) \). Step 4: Evaluate \( z = 300x + 500y \) at each corner point. At \( A = (0, 6) \): \[ z = 300(0) + 500(6) = 3000 \] At \( B = (3, 5) \): \[ z = 300(3) + 500(5) = 900 + 2500 = 3400 \] At \( E = (8, 0) \): \[ z = 300(8) + 500(0) = 2400 \] At \( D = (3, 0) \): \[ z = 300(3) + 500(0) = 900 \] Step 5: The maximum value of \( z \) is \( 3400 \) at \( (3, 5) \).
Answer: Maximum value of \( z = 3400 \) at \( x = 3 \), \( y = 5 \).