Question

Consider the Linear Programming Problem, where the objective function \[ Z = x + 4y \] needs to be minimized subject to the following constraints: \[ 2x + y \geq 1000, \] \[ x + 2y \geq 800, \] \[ x \geq 0, \quad y \geq 0. \] Draw a neat graph of the feasible region and find the minimum value of $Z$.

Hint:

To find the minimum or maximum of the objective function in a linear programming problem, evaluate the objective function at each corner point of the feasible region and choose the one that gives the required extreme value.

Answer 1

The objective function $Z = x + 4y$ is to be minimized subject to given constraints. The constraints and feasible region are determined as follows: 1. Constraints are plotted: The line $y = 1000 - 2x$ represents $2x + y \geq 1000$. The line $y = \frac{800 - x}{2}$ represents $x + 2y \geq 800$. The constraints $x \geq 0$ and $y \geq 0$ confine the feasible region to the first quadrant. 2. Intersection points of the lines are found by solving the system: \[ 2x + y = 1000 \quad \text{(Equation 1)} \] \[ x + 2y = 800 \quad \text{(Equation 2)} \] Multiplying Equation 2 by 2 yields $2x + 4y = 1600$. Subtracting Equation 1 from this result gives: \[ (2x + 4y) - (2x + y) = 1600 - 1000 \] \[ 3y = 600 \quad \Rightarrow \quad y = 200. \] Substituting $y = 200$ into Equation 1: \[ 2x + 200 = 1000 \quad \Rightarrow \quad 2x = 800 \quad \Rightarrow \quad x = 400. \] The intersection point is $(400, 200)$. 3. Boundary points are checked: The feasible region is bordered by the x-axis ($y = 0$) and the y-axis ($x = 0$). Intersections of constraints with the axes are examined: - For Equation 1 with $x = 0$: \[ 2(0) + y = 1000 \quad \Rightarrow \quad y = 1000. \] The point is $(0, 1000)$. - For Equation 2 with $y = 0$: \[ x + 2(0) = 800 \quad \Rightarrow \quad x = 800. \] The point is $(800, 0)$. 4. The feasible region is graphed by plotting the lines $2x + y = 1000$ and $x + 2y = 800$. The feasible region is the area enclosed by these lines, the x-axis, and the y-axis. 5. The objective function is evaluated at the corner points: The corner points of the feasible region are $(0, 1000)$, $(400, 200)$, and $(800, 0)$. These points are substituted into $Z = x + 4y$: - At $(0, 1000)$: \[ Z = 0 + 4(1000) = 4000. \] - At $(400, 200)$: \[ Z = 400 + 4(200) = 400 + 800 = 1200. \] - At $(800, 0)$: \[ Z = 800 + 4(0) = 800. \] The minimum value of $Z$ is $800$ at $(800, 0)$. 6. Conclusion: The minimum value of the objective function $Z = x + 4y$ is $800$, occurring at the point $(800, 0)$.