Graphical Optimization - Finite Mathematics

1. In the linear programming problem: minimize $C = 3x + 4y$ subject to $x + 2y \geq 8$, $2x + y \geq 10$, $x \geq 0$, $y \geq 0$, which statement about the optimal solution is correct?
   Answer: The minimum occurs at $(4, 2)$ with value $C = 20$ For a minimization problem, we find the corner points of the feasible region. The constraints $x + 2y \geq 8$ and $2x + y \geq 10$ intersect where $x + 2y = 8$ and $2x + y = 10$. Solving: from the first equation $x = 8 - 2y$, substituting into the second: $2(8 - 2y) + y = 10$, so $16 - 4y + y = 10$, thus $y = 2$ and $x = 4$. The corner points are: $(4,2)$, $(0,10)$, and $(8,0)$. Note that $(5,0)$ doesn't satisfy $x + 2y \geq 8$ since $5 + 0 = 5 < 8$. Evaluating the objective function: at $(4,2)$: $C = 20$; at $(0,10)$: $C = 40$; at $(8,0)$: $C = 24$. The minimum value is 20.
2. The objective function $P = 6x + 4y$ is to be maximized subject to the constraints $x \ge 0$, $y \ge 0$, $3x + 2y \le 18$, and $x + 2y \le 10$. The maximum value is achieved along a line segment. Which of the following points is also an optimal solution?
   Answer: (5, 1.5) When you encounter a linear programming problem where the maximum value is achieved "along a line segment," this means multiple points yield the same optimal value. This happens when the objective function is parallel to one of the constraint boundaries. First, let's find the corner points of the feasible region by solving the constraint intersections. The constraints $3x + 2y = 18$ and $x + 2y = 10$ intersect when we solve simultaneously. Subtracting the second from the first: $2x = 8$, so $x = 4$. Substituting back: $y = 3$. So one corner point is $(4, 3)$ with $P = 6(4) + 4(3) = 36$. Other corner points are $(0, 5)$, $(6, 0)$, and $(0, 0)$. Evaluating the objective function at these points shows that $(4, 3)$ gives the maximum value of 36. However, since we're told the maximum occurs along a line segment, we need to check which constraint boundary contains this optimal line. The objective function $P = 6x + 4y$ can be rewritten as $y = -\frac{3}{2}x + \frac{P}{4}$. The constraint $x + 2y = 10$ has slope $-\frac{1}{2}$, while $3x + 2y = 18$ has slope $-\frac{3}{2}$. Since the objective function has the same slope as the second constraint, the optimal line segment lies along $3x + 2y = 18$. Checking the options: D) $(5, 1.5)$ satisfies $3(5) + 2(1.5) = 18$ and gives $P = 36$. A) gives $P = 28$, B) gives $P = 32$, and C) gives $P = 20$. When a linear programming problem has optimal solutions along a line segment, always check if answer choices lie on the same constraint boundary as your known optimal point.
3. What is the result of attempting to maximize the objective function $P = 5x + 5y$ subject to the constraints $x \ge 0$, $y \ge 0$, $x + y \le 4$, and $2x + y \ge 10$?
   Answer: The problem has no feasible solution. The constraints $x \ge 0$, $y \ge 0$, and $x + y \le 4$ define a triangular region with vertices at (0,0), (4,0), and (0,4). The fourth constraint is $2x + y \ge 10$. To determine if there is a feasible region, we can check if any points in the triangle satisfy this fourth constraint. The line $2x+y=10$ has intercepts at (5,0) and (0,10), both of which are outside the triangular region. Since all points $(x,y)$ in the triangle have $x+y \le 4$, it follows that $2x+y = x+(x+y) \le 4+4 = 8$ for a point with $x \le 4$. Because no point in the triangle can have $2x+y$ be greater than or equal to 10, the constraints are contradictory. Therefore, the feasible region is empty, and the problem has no solution.
4. The feasible region for a maximization problem is defined by $x \ge 0$, $y \ge 0$, $x + 3y \le 15$, and $2x + y \le 10$. The objective function is $P = ax + 6y$, where $a > 0$. For which range of values of $a$ is the point $(3,4)$ the unique optimal solution?
   Answer: $2 < a < 12$ When you encounter linear programming problems asking for the range of coefficients that makes a specific point optimal, you're dealing with sensitivity analysis. The key insight is that a corner point of the feasible region is optimal when the objective function's slope falls within a specific range determined by the slopes of the adjacent constraint lines. First, let's verify that $(3,4)$ is indeed a corner point. Checking the constraints: $3 + 3(4) = 15$ and $2(3) + 4 = 10$, so $(3,4)$ lies at the intersection of $x + 3y = 15$ and $2x + y = 10$. For $(3,4)$ to be the unique optimal solution, the objective function $P = ax + 6y$ must have a slope between the slopes of these two constraint lines. The line $x + 3y = 15$ can be rewritten as $y = -\frac{1}{3}x + 5$ (slope = $-\frac{1}{3}$), and $2x + y = 10$ becomes $y = -2x + 10$ (slope = $-2$). The objective function $P = ax + 6y$ has slope $-\frac{a}{6}$. For $(3,4)$ to be optimal, we need: $-2 < -\frac{a}{6} < -\frac{1}{3}$. Solving this inequality: $-2 < -\frac{a}{6}$ gives us $a < 12$, and $-\frac{a}{6} < -\frac{1}{3}$ gives us $a > 2$. Therefore, $2 < a < 12$, which is choice A. Choice B ($a = 2$) would make multiple points optimal. Choice C ($0 < a < 2$) would make a different corner point optimal. Choice D ($a > 12$) would also shift the optimal solution elsewhere. Remember: in sensitivity analysis, the optimal corner point changes when the objective function's slope crosses the slope of an adjacent constraint line.
5. Find the maximum value of the objective function $Z = 3x + 5y$ in the feasible region defined by the inequality $|x| + 2|y| \le 8$.
   Answer: 24 The feasible region defined by $|x| + 2|y| \le 8$ is a rhombus with vertices at its intercepts. To find the intercepts, set one variable to zero. If $x=0$, $2|y| \le 8$, so $|y| \le 4$, giving vertices at $(0, 4)$ and $(0, -4)$. If $y=0$, $|x| \le 8$, giving vertices at $(8, 0)$ and $(-8, 0)$. The optimal value of a linear function over a convex polygonal region must occur at a vertex. We evaluate the objective function $Z = 3x + 5y$ at each of the four vertices: $Z(8,0) = 3(8) + 5(0) = 24$. $Z(0,4) = 3(0) + 5(4) = 20$. $Z(-8,0) = 3(-8) + 5(0) = -24$. $Z(0,-4) = 3(0) + 5(-4) = -20$. The maximum value among these is 24.
6. Find the maximum value of $Z = 10x - 4y$ subject to the conditions: $x + y = 10$, $x \ge 2$, and $y \ge 3$.
   Answer: 58 The feasible region is restricted to the line $x+y=10$. The inequalities $x \ge 2$ and $y \ge 3$ further restrict the solution. Substituting $y = 10-x$ into $y \ge 3$ gives $10-x \ge 3$, which simplifies to $x \le 7$. So, the feasible region is the line segment defined by $x+y=10$ for $2 \le x \le 7$. Since the objective function is linear, the maximum value must occur at one of the endpoints of this segment. The endpoints are when $x=2$ (so $y=8$) and when $x=7$ (so $y=3$). Evaluating $Z$ at these points: $Z(2,8) = 10(2) - 4(8) = 20 - 32 = -12$. $Z(7,3) = 10(7) - 4(3) = 70 - 12 = 58$. The maximum value is 58.

Start this quiz