Question

Solve the following linear programming problem graphically: \[ \text{Maximise } z = 5x + 4y \] subject to the constraints: \[ x + 2y \geq 4, \quad 3x + y \leq 6, \quad x + y \leq 4, \quad x, y \geq 0. \]

Hint:

To solve a linear programming problem graphically, graph the constraints, find the feasible region, determine the corner points, and evaluate the objective function at these points.

Answer 1

1. Convert the inequalities into equations for graphing: - \( x + 2y = 4 \): Rearrange to \( y = \frac{4 - x}{2} \). - \( 3x + y = 6 \): Rearrange to \( y = 6 - 3x \). - \( x + y = 4 \): Rearrange to \( y = 4 - x \). 2. Determine the feasible region: - The feasible region is determined by the intersection of the half-planes defined by the inequalities: - \( x + 2y \geq 4 \): The region above the line \( x + 2y = 4 \). - \( 3x + y \leq 6 \): The region below the line \( 3x + y = 6 \). - \( x + y \leq 4 \): The region below the line \( x + y = 4 \). - \( x \geq 0, y \geq 0 \): The first quadrant. Graph these constraints and shade the common region that satisfies all the inequalities. 3. Identify the corner points of the feasible region: The corner points are found by solving the intersection points of the boundary lines: - Intersection of \( x + 2y = 4 \) and \( 3x + y = 6 \): Solve: \[ x + 2y = 4 \quad \text{and} \quad 3x + y = 6. \] From \( x + 2y = 4 \), \( y = \frac{4 - x}{2} \). Substitute into \( 3x + y = 6 \): \[ 3x + \frac{4 - x}{2} = 6. \] Simplify: \[ \frac{6x + 4 - x}{2} = 6 \implies \frac{5x + 4}{2} = 6 \implies 5x + 4 = 12 \implies x = \frac{8}{5}. \] Substitute \( x = \frac{8}{5} \) into \( y = \frac{4 - x}{2} \): \[ y = \frac{4 - \frac{8}{5}}{2} = \frac{\frac{20}{5} - \frac{8}{5}}{2} = \frac{\frac{12}{5}}{2} = \frac{6}{5}. \] Corner point: \( \left(\frac{8}{5}, \frac{6}{5}\right) \). - Intersection of \( x + 2y = 4 \) and \( x + y = 4 \): Solve: \[ x + 2y = 4 \quad \text{and} \quad x + y = 4. \] From \( x + y = 4 \), \( y = 4 - x \). Substitute into \( x + 2y = 4 \): \[ x + 2(4 - x) = 4 \implies x + 8 - 2x = 4 \implies -x + 8 = 4 \implies x = 4. \] Substitute \( x = 4 \) into \( y = 4 - x \): \[ y = 4 - 4 = 0. \] Corner point: \( (4, 0) \). - Intersection of \( 3x + y = 6 \) and \( x + y = 4 \): Solve: \[ 3x + y = 6 \quad \text{and} \quad x + y = 4. \] Subtract \( x + y = 4 \) from \( 3x + y = 6 \): \[ 3x + y - (x + y) = 6 - 4 \implies 2x = 2 \implies x = 1. \] Substitute \( x = 1 \) into \( x + y = 4 \): \[ y = 4 - 1 = 3. \] Corner point: \( (1, 3) \). 4. Evaluate \( z = 5x + 4y \) at the corner points: - At \( \left(\frac{8}{5}, \frac{6}{5}\right) \): \[ z = 5\left(\frac{8}{5}\right) + 4\left(\frac{6}{5}\right) = 8 + \frac{24}{5} = \frac{40}{5} + \frac{24}{5} = \frac{64}{5}. \] - At \( (4, 0) \): \[ z = 5(4) + 4(0) = 20. \] - At \( (1, 3) \): \[ z = 5(1) + 4(3) = 5 + 12 = 17. \] 5. Conclusion: - Maximum value of \( z \) is \( 20 \) at \( (4, 0) \). - Minimum value of \( z \) is \( 17 \) at \( (1, 3) \). Final Answer: - Maximum value: \( z = 20 \) at \( (4, 0) \). - Minimum value: \( z = 17 \) at \( (1, 3) \).