Solving the LPP using the Graphical Method

This problem requires us to find the optimal solution for a Linear Programming Problem (LPP) by using the graphical solution technique. The goal is to maximize the objective function \(Z = 15x_1 + 10x_2\) subject to a set of constraints.

Understanding the Linear Programming Problem (LPP)

A Linear Programming Problem involves optimizing (maximizing or minimizing) a linear objective function, subject to linear equality or inequality constraints. In this case, we have:

• Objective Function: Maximize \(Z = 15x_1 + 10x_2\)
• Constraints:
  • \(4x_1 + 6x_2 \le 360\)
  • \(3x_1 \le 180\)
  • \(5x_2 \le 200\)
  • \(x_1 \ge 0, x_2 \ge 0\) (Non-negativity constraints)

The variables \(x_1\) and \(x_2\) are typically decision variables representing quantities of products, resources, etc.

Steps of the Graphical Solution Technique

The graphical method involves the following steps:

1. Convert the inequality constraints into equality equations to plot lines on a graph.
2. Plot each line on the \(x_1 - x_2\) coordinate system.
3. Determine the feasible region, which is the area satisfying all constraints, including non-negativity.
4. Identify the corner points (vertices) of the feasible region.
5. Evaluate the objective function at each corner point.
6. Select the corner point that yields the optimal value (maximum in this case) for the objective function.

Step 1: Convert Constraints to Equations and Find Points for Plotting

We convert each inequality constraint into an equation to find the boundary lines:

1. Constraint 1: \(4x_1 + 6x_2 \le 360\) becomes \(4x_1 + 6x_2 = 360\).
   • If \(x_1 = 0\), \(6x_2 = 360 \implies x_2 = 60\). Point: (0, 60).
   • If \(x_2 = 0\), \(4x_1 = 360 \implies x_1 = 90\). Point: (90, 0).
2. Constraint 2: \(3x_1 \le 180\) becomes \(3x_1 = 180 \implies x_1 = 60\).
   • This is a vertical line at \(x_1 = 60\).
3. Constraint 3: \(5x_2 \le 200\) becomes \(5x_2 = 200 \implies x_2 = 40\).
   • This is a horizontal line at \(x_2 = 40\).
4. Non-negativity: \(x_1 \ge 0\) and \(x_2 \ge 0\).
   • This restricts the feasible region to the first quadrant of the graph.

Step 2 & 3: Plotting the Lines and Finding the Feasible Region

Imagine plotting these lines. The non-negativity constraints \(x_1 \ge 0\) and \(x_2 \ge 0\) limit us to the first quadrant. The constraints \(x_1 \le 60\) and \(x_2 \le 40\) further restrict the area to a rectangle from \(x_1=0\) to \(x_1=60\) and \(x_2=0\) to \(x_2=40\). The constraint \(4x_1 + 6x_2 \le 360\) requires that the feasible points lie on or below the line connecting (90, 0) and (0, 60).

The feasible region is the area in the first quadrant below the line \(4x_1 + 6x_2 = 360\), to the left of the line \(x_1 = 60\), and below the line \(x_2 = 40\).

Step 4: Identifying Corner Points of the Feasible Region

The corner points of this feasible region are the intersection points of the boundary lines that define the region. These points are:

• The origin: Intersection of \(x_1=0\) and \(x_2=0\), which is (0, 0).
• Intersection of \(x_2=0\) and \(x_1=60\) (from \(3x_1 = 180\)), which is (60, 0).
• Intersection of \(x_1=0\) and \(x_2=40\) (from \(5x_2 = 200\)), which is (0, 40).
• Intersection of \(x_1 = 60\) and \(4x_1 + 6x_2 = 360\). Substitute \(x_1=60\) into the equation: \(4(60) + 6x_2 = 360 \implies 240 + 6x_2 = 360 \implies 6x_2 = 120 \implies x_2 = 20\). Point: (60, 20). Note that \(x_2=20\) is less than 40, so this point is within the \(x_2 \le 40\) boundary.
• Intersection of \(x_2 = 40\) and \(4x_1 + 6x_2 = 360\). Substitute \(x_2=40\) into the equation: \(4x_1 + 6(40) = 360 \implies 4x_1 + 240 = 360 \implies 4x_1 = 120 \implies x_1 = 30\). Point: (30, 40). Note that \(x_1=30\) is less than 60, so this point is within the \(x_1 \le 60\) boundary.

The corner points of the feasible region are (0, 0), (60, 0), (0, 40), (60, 20), and (30, 40).

Step 5: Evaluating the Objective Function at Corner Points

Now, we substitute the coordinates of each corner point into the objective function \(Z = 15x_1 + 10x_2\) to find the value of Z at each point.

Step 6: Finding the Optimal Solution

For a maximization problem, the optimal solution corresponds to the corner point where the objective function Z has the largest value. Comparing the Z values calculated:

• Z at (0, 0) = 0
• Z at (60, 0) = 900
• Z at (0, 40) = 400
• Z at (60, 20) = 1100
• Z at (30, 40) = 850

The maximum value of Z is 1100, which occurs at the corner point (\(x_1 = 60, x_2 = 20\)).

Therefore, the solution to the LPP using the graphical solution technique is \(x_1 = 60\), \(x_2 = 20\), and the maximum value of Z is 1100.

Revision Table: Key Concepts in LPP Graphical Solution

Additional Information on Graphical Method for LPP

The graphical method is a visual way to solve Linear Programming Problems, but it is practical only for problems with two decision variables (\(x_1, x_2\)). For problems with three or more variables, other techniques like the Simplex method are used.

The feasible region in an LPP is always a convex set. A set is convex if, for any two points in the set, the line segment connecting them is entirely contained within the set.

If the feasible region is empty (no points satisfy all constraints), the LPP has no solution. If the feasible region is unbounded, the objective function may be unbounded (can be increased or decreased indefinitely), or it may still have a bounded optimum value.

The optimal solution for a bounded feasible region always occurs at one of the corner points. This is a fundamental principle of linear programming.