Question

Consider the linear programming problem
\[ Z_{\max} = 2x_1 + 5x_2 \quad \text{subject to the restrictions:} \] \[ x_1 \leq 4 \] \[ x_2 \leq 3 \] \[ 2x_1 + 3x_2 \leq 14 \] and $x_1 \geq 0, x_2 \geq 0$. Then the optimal solution is.

• A. $Z_{\max} = 18$
• B. $Z_{\max} = 15$
• C. $Z_{\max} = 20$
• D. $Z_{\max} = 25$

Hint:

Notice $x_2$ has a much higher objective coefficient ($5$) than $x_1$ ($2$). To maximize $Z$, push $x_2$ to its upper bound $x_2 = 3$ first, then use $2x_1 + 3(3) = 14 \implies x_1 = 2.5$ to instantly get $Z = 2(2.5) + 5(3) = 20$!

Answer 1

The Correct Option is C

Step 1: Concept
By the Corner Point Theorem of Linear Programming, if a feasible region is convex and bounded, the maximum or minimum value of the objective function $Z = c_1 x_1 + c_2 x_2$ always occurs at one of the extreme vertices (corner points) of the feasible region.

Step 2: Key Formulas and Approach
Identify all corner points by finding the pairwise intersections of the boundary lines $x_1 = 0$, $x_2 = 0$, $x_1 = 4$, $x_2 = 3$, and $2x_1 + 3x_2 = 14$ that satisfy all constraints simultaneously. Evaluate $Z = 2x_1 + 5x_2$ at each vertex.

Step 3: Step-by-step Explanation

• Vertex 1: Origin $(0, 0)$
$Z(0, 0) = 2(0) + 5(0) = 0$.
• Vertex 2: Intersection of $x_2 = 0$ and $x_1 = 4 \implies (4, 0)$
Check $2(4) + 3(0) = 8 \leq 14$ (Valid). $Z(4, 0) = 2(4) + 5(0) = 8$.
• Vertex 3: Intersection of $x_1 = 4$ and $2x_1 + 3x_2 = 14$
$2(4) + 3x_2 = 14 \implies 3x_2 = 6 \implies x_2 = 2$. Point $(4, 2)$: Check $x_2 \leq 3 \implies 2 \leq 3$ (Valid). $Z(4, 2) = 2(4) + 5(2) = 8 + 10 = 18$.
• Vertex 4: Intersection of $x_2 = 3$ and $2x_1 + 3x_2 = 14$
$2x_1 + 3(3) = 14 \implies 2x_1 = 5 \implies x_1 = 2.5$. Point $(2.5, 3)$: Check $x_1 \leq 4 \implies 2.5 \leq 4$ (Valid). $Z(2.5, 3) = 2(2.5) + 5(3) = 5 + 15 = 20$.
• Vertex 5: Intersection of $x_1 = 0$ and $x_2 = 3 \implies (0, 3)$
Check $2(0) + 3(3) = 9 \leq 14$ (Valid). $Z(0, 3) = 2(0) + 5(3) = 15$.
• Comparing values: $Z$ takes values $\{0, 8, 18, 20, 15\}$. The maximum value is $Z_{\max} = 20$ occurring at $(2.5, 3)$.

Step 4: Final Answer
The optimal solution is $Z_{\max} = 20$. Thus, Option (C) is correct.