For the linear programming problem: Maximum Z = 3X1 + 2X2 Subject to -2X1 + 3X2 ≤ 9 X1 – 5X2 ≥ - 20 X1, X2 ≥ 0 The above problem has
unbounded solution
Linear Programming Problem Analysis
The given problem is a Linear Programming Problem (LPP) where we need to maximize the objective function \( Z \) subject to a set of linear constraints and non-negativity conditions.
The problem is stated as:
Maximize \( Z = 3X_1 + 2X_2 \)
Subject to:
- Constraint 1: \( -2X_1 + 3X_2 \le 9 \)
- Constraint 2: \( X_1 - 5X_2 \ge -20 \)
- Non-negativity: \( X_1 \ge 0, X_2 \ge 0 \)
To determine the type of solution, we can use the graphical method. This involves plotting the constraints on a graph and identifying the feasible region.
Graphing the Constraints and Finding the Feasible Region
First, let's rewrite the inequality constraints as equalities to plot the boundary lines:
- \( -2X_1 + 3X_2 = 9 \)
- \( X_1 - 5X_2 = -20 \)
We also have the non-negativity constraints \( X_1 \ge 0 \) (the \( X_2 \)-axis) and \( X_2 \ge 0 \) (the \( X_1 \)-axis), which restrict the feasible region to the first quadrant.
Plotting Constraint 1: \( -2X_1 + 3X_2 \le 9 \)
Consider the line \( -2X_1 + 3X_2 = 9 \).
| \( X_1 \) | \( X_2 \) | Point |
|---|---|---|
| 0 | \( 3X_2 = 9 \implies X_2 = 3 \) | (0, 3) |
| \( -4.5 \) | \( -2X_1 = 9 \implies X_1 = -4.5 \) | (-4.5, 0) |
The line passes through (0, 3) and (-4.5, 0). To determine the feasible region for \( -2X_1 + 3X_2 \le 9 \), we can test a point like (0,0): \( -2(0) + 3(0) = 0 \le 9 \). Since this is true, the feasible region for this constraint is on the side of the line containing the origin.
Plotting Constraint 2: \( X_1 - 5X_2 \ge -20 \)
This can be rewritten as \( -X_1 + 5X_2 \le 20 \). Consider the line \( -X_1 + 5X_2 = 20 \).
| \( X_1 \) | \( X_2 \) | Point |
|---|---|---|
| 0 | \( 5X_2 = 20 \implies X_2 = 4 \) | (0, 4) |
| \( -20 \) | \( -X_1 = 20 \implies X_1 = -20 \) | (-20, 0) |
The line passes through (0, 4) and (-20, 0). To determine the feasible region for \( -X_1 + 5X_2 \le 20 \), we can test a point like (0,0): \( -0 + 5(0) = 0 \le 20 \). Since this is true, the feasible region for this constraint is on the side of the line containing the origin.
Identifying the Feasible Region
The feasible region is the area in the first quadrant (\( X_1 \ge 0, X_2 \ge 0 \)) that satisfies both \( -2X_1 + 3X_2 \le 9 \) and \( -X_1 + 5X_2 \le 20 \). Graphing these lines shows that the feasible region is bounded by the \( X_1 \)-axis, the \( X_2 \)-axis (up to (0,3)), the line segment of \( -2X_1 + 3X_2 = 9 \) from (0,3) to the intersection point of the two lines, and the line \( -X_1 + 5X_2 = 20 \) extending outwards from the intersection point.
Finding the Intersection Point
We find the intersection of \( -2X_1 + 3X_2 = 9 \) and \( -X_1 + 5X_2 = 20 \).
Multiply the second equation by 2:
\( 2 \times (-X_1 + 5X_2) = 2 \times 20 \)
\( -2X_1 + 10X_2 = 40 \)
Subtract the first equation from this result:
\( (-2X_1 + 10X_2) - (-2X_1 + 3X_2) = 40 - 9 \)
\( 7X_2 = 31 \)
\( X_2 = \frac{31}{7} \)
Substitute \( X_2 = \frac{31}{7} \) into \( -X_1 + 5X_2 = 20 \):
\( -X_1 + 5\left(\frac{31}{7}\right) = 20 \)
\( -X_1 + \frac{155}{7} = 20 \)
\( -X_1 = 20 - \frac{155}{7} \)
\( -X_1 = \frac{140 - 155}{7} \)
\( -X_1 = \frac{-15}{7} \)
\( X_1 = \frac{15}{7} \)
The intersection point is \( \left(\frac{15}{7}, \frac{31}{7}\right) \).
Analyzing the Feasible Region for Unboundedness
The feasible region has corner points at (0,0), (0,3), and \( \left(\frac{15}{7}, \frac{31}{7}\right) \). However, the feasible region does not close off after the intersection point \( \left(\frac{15}{7}, \frac{31}{7}\right) \). It extends infinitely in the direction along the line \( -X_1 + 5X_2 = 20 \) (or below it) while satisfying \( -2X_1 + 3X_2 \le 9 \) and \( X_1, X_2 \ge 0 \). Since the line \( -X_1 + 5X_2 = 20 \) has a positive slope (1/5) and extends into the first quadrant from the intersection point, the feasible region is unbounded.
Analyzing the Objective Function
The objective function is \( Z = 3X_1 + 2X_2 \). Both coefficients (3 and 2) are positive. In an unbounded feasible region, if the objective function coefficients are positive, the value of the objective function can often increase indefinitely as we move in the direction of increase of \( X_1 \) and \( X_2 \) within the feasible region.
Consider moving along the boundary line \( -X_1 + 5X_2 = 20 \) for \( X_1 > \frac{15}{7} \). On this line, \( X_2 = \frac{1}{5}X_1 + 4 \). Substituting this into the objective function:
\( Z = 3X_1 + 2\left(\frac{1}{5}X_1 + 4\right) \)
\( Z = 3X_1 + \frac{2}{5}X_1 + 8 \)
\( Z = \left(3 + \frac{2}{5}\right)X_1 + 8 \)
\( Z = \left(\frac{15+2}{5}\right)X_1 + 8 \)
\( Z = \frac{17}{5}X_1 + 8 \)
As \( X_1 \) increases towards infinity within the feasible region (along this boundary or above it), the value of \( Z \) also increases towards infinity because the coefficient \( \frac{17}{5} \) is positive.
Since the feasible region is unbounded and the objective function can be increased indefinitely within this region, the linear programming problem has an unbounded solution.
Conclusion
Based on the graphical analysis, the feasible region is unbounded, and the objective function can be arbitrarily large within this region. Therefore, the problem has an unbounded solution.
Revision Table: Key Concepts in LPP Solutions
| Solution Type | Description | Graphical Representation |
|---|---|---|
| Unbounded Solution | The feasible region is not bounded, and the objective function can be increased (for maximization) or decreased (for minimization) indefinitely within this region. | Feasible region extends infinitely in a direction where the objective function improves. |
| Infeasible Solution | No point satisfies all constraints simultaneously. The feasible region is empty. | Constraint regions do not overlap. |
| Unique Optimal Solution | A single point in the feasible region gives the maximum/minimum value for the objective function. | The optimal value occurs at a single corner point. |
| Alternative Optimum Solution | More than one point gives the maximum/minimum value. This occurs when the objective function line is parallel to a boundary of the feasible region. | The optimal value occurs along an edge of the feasible region (between two corner points). |
| Degenerate Solution | A basic feasible solution where one or more basic variables are zero. Graphically, this might occur when more than two constraint lines intersect at a single corner point in a 2D problem. | A corner point is defined by the intersection of more constraint lines than the number of variables. |
Additional Information on Linear Programming Solutions
Linear Programming Problems (LPPs) seek to optimize (maximize or minimize) a linear objective function subject to a set of linear constraints. The set of points satisfying all constraints is called the feasible region. The optimal solution, if it exists, must occur at a corner point (vertex) of the feasible region or along an edge (for alternative optimum).
Understanding the shape and extent of the feasible region is crucial. A feasible region can be bounded (enclosed) or unbounded (extends infinitely). An unbounded feasible region does not automatically mean an unbounded solution. If the objective function's direction of improvement aligns with the direction in which the feasible region is unbounded, then the solution is unbounded.
In this specific problem, the objective function \( Z = 3X_1 + 2X_2 \) seeks to increase \( X_1 \) and \( X_2 \). The feasible region extends infinitely towards larger values of \( X_1 \) and \( X_2 \) along the boundary \( -X_1 + 5X_2 = 20 \) and below it. This alignment leads to an unbounded objective function value.
The graphical method is suitable for LPPs with two variables. For problems with more variables, methods like the Simplex method are used.
Important Questions from Linear Programming
In an Linear programming problem, the restrictions or limitations under which the objective function is to be optimised are called
The headquarters of the Eastern Railway Zone is located at _______.
Consider an LPP given as
Max Z = 2x 1 - x 2+ 2x 3
Subject to the constraints
2x 1+ x 2 ≤ 10
x 1+ 2x 2 - 2x 3 ≤ 20
x 1+ 2x 3 ≤ 5
x 1, x 2, x 3 ≥ 0
What shall be the solution of the LPP after applying first iteration of the Simplex Method?
Consider the following Linear programming problem (LPP):
Maximize z = x 1+ x 2
Subject to the constraints:
x 1+ 2x 2≤ 2000
x 1+ x 2≤ 1500
x 2≤ 600
and x 1, x 2≥ 0
The solution of the above LPP is:Consider the following statements with respect to duality in LPP
(a) The final simplex table giving optimal solution of the primal also contains optimal solution of its dual in itself.
(b) If either the primal or the dual problem has a finite optimal solution, then the other problem also has a finite optimal solution.
(c) If either problem has an unbounded optimum solution, then the other problem has no feasible solution at all
Which of the statements is (are) correct?
