The **linear programming problems (LPP)** discussed in the previous section possessed
unique solutions. This was because the optimal value occurred at one
of the extreme points (corner points). But situations may arise, when
the optimal solution obtained is not unique.

This case may arise when the line representing the objective function is parallel to one of the lines bounding the feasible region. The presence of multiple solutions is illustrated through the following graphical method example.

Maximize z = x_{1} + 2x_{2}

subject to

x_{1} ≤ 80

x_{2} ≤ 60

5x_{1} + 6x_{2} ≤ 600

x_{1} + 2x_{2} ≤ 160

x_{1}, x_{2} ≥ 0.

In the above figure, there is no unique outer most corner cut by the
objective function line. All points from P to Q lying on line PQ represent
optimal solutions and all these will give the same optimal value (maximum
profit) of Rs. 160. This is indicated by the fact that both the points
P with co-ordinates (40, 60) and Q with co-ordinates (60, 50) are on
the line x_{1} + 2x_{2 }=_{ }160. Thus, every
point on the line PQ maximizes the value of the objective function and
the problem has multiple solutions.

In some cases, there is no feasible solution area, i.e., there are no points that satisfy all constraints of the problem. An infeasible LP problem with two decision variables can be identified through its graph. For example, let us consider the following linear programming problem (LPP).

Minimize z = 200x_{1} + 300x_{2}

subject to

2x_{1} + 3x_{2} ≥
1200

x_{1} + x_{2} ≤ 400

2x_{1} + 1.5x_{2} ≥
900

x_{1}, x_{2} ≥ 0

The region located on the right of PQR includes all solutions, which satisfy the first and the third constraints. The region located on the left of ST includes all solutions, which satisfy the second constraint. Thus, the problem is infeasible because there is no set of points that satisfy all the three constraints.

It is a solution whose objective function is infinite. If the feasible region is unbounded then one or more decision variables will increase indefinitely without violating feasibility, and the value of the objective function can be made arbitrarily large. Consider the following model:

Minimize z = 40x_{1} + 60x_{2}

subject to

2x_{1} + x_{2} ≥
70

x_{1} + x_{2} ≥ 40

x_{1} + 3x_{2} ≥ 90

x_{1}, x_{2} ≥ 0

The point (x_{1}, x_{2}) must be somewhere in the
solution space as shown in the figure by shaded portion.

The three extreme points (corner points) in the finite plane are:

P = (90, 0); Q = (24, 22) and R = (0, 70)

The values of the objective function at these extreme points are:

Z(P) = 3600, Z(Q) = 2280 and Z(R) = 4200

In this case, no maximum of the objective function exists because the
region has no boundary for increasing values of x_{1} and x_{2}.
Thus, it is not possible to maximize the objective function in this
case and the solution is unbounded.

About the AuthorVinay is a Management Enthusiast. Contact him on Google+ |