Question

Solve the following linear programming problem graphically :
Minimize \( Z = 13x - 15y \)
Subject to constraints
\( x + y \leq 7, \)
\( 2x - 3y + 6 \geq 0, \)
\( x \geq 0, y \geq 0 \)

Hint:

For minimization, look for the vertex furthest in the direction opposite to the gradient of \( Z \).
Always test the origin \( (0,0) \) in inequalities to quickly determine which side of the line to shade.

Answer 1

Concept:
• Graphical Method: Represent the linear inequalities as half-planes on a coordinate system and find the intersection to determine the feasible region.
• Corner Point Theorem: The optimal value of the objective function occurs at one of the vertices of the feasible region.

Step 1: Plot the boundary lines and determine the feasible region
Convert inequalities to equations to find boundary lines:
• Line 1: \( x + y = 7 \). Intersects axes at \( (7, 0) \) and \( (0, 7) \). The region \( x + y \leq 7 \) is towards the origin.
• Line 2: \( 2x - 3y + 6 = 0 \implies 3y = 2x + 6 \implies y = \frac{2}{3}x + 2 \). Intersects axes at \( (0, 2) \) and \( (-3, 0) \). Testing origin \( (0, 0) \): \( 6 \geq 0 \) (True), so the region is towards the origin side.
• Non-negative constraints: \( x \geq 0, y \geq 0 \) restrict the region to the first quadrant. \includegraphics[width=0.5\linewidth]{Q31_Sol.png}

Step 2: Identify corner points
Find the intersection of \( x + y = 7 \) and \( 2x - 3y = -6 \): \[ x = 7 - y \implies 2(7 - y) - 3y = -6 \implies 14 - 5y = -6 \implies 5y = 20 \implies y = 4, x = 3 \] The corner points of the feasible region are \( O(0, 0), A(7, 0), B(3, 4), \) and \( C(0, 2) \).

Step 3: Evaluate \( Z = 13x - 15y \) at corner points

• At \( O(0, 0) \): \( Z = 13(0) - 15(0) = 0 \)
• At \( A(7, 0) \): \( Z = 13(7) - 15(0) = 91 \)
• At \( B(3, 4) \): \( Z = 13(3) - 15(4) = 39 - 60 = -21 \)
• At \( C(0, 2) \): \( Z = 13(0) - 15(2) = -30 \) The minimum value of \( Z \) is \( -30 \) at the point \( (0, 2) \).