20
Aug

Linear Programming 5: Alternate solutions, Infeasibility, Unboundedness, & Redundancy


Welcome to this tutorial as we discuss special
cases encountered while solving some linear programming problems. The special cases we’ll discuss include
Alternative optimal solutions Infeasibility
Unboundedness, and Redundancy. Let’s begin with alternate optimal solutions.
Consider this linear programming problem and its graph. Here is an instance of the objective function
line. Since this is a maximization problem, moving
this line shows that the optimal solutions occur at these two extreme points. That is,
more than one optimal solution exists. We refer to these as Alternative or Multiple
Optimal Solutions. Generally, this situation occurs when the
objective function line is parallel to a binding constraint.
Note that the objective function and the first constraint line have the same slope. So they
are parallel. That is why the objective function line coincides
with the constraint line here. In fact, not only these 2 points are optimal
solution points. Every single point between them on the line is also optimal. There’s nothing wrong with alternative optimal
solutions. In fact, they offer the benefit of different combinations of the decision
variables that produce the same optimal profit or cost. The next special case is Infeasibility
Consider this linear programming problem and its graph. The first constraint is a “less than”
constraint and is satisfied in the region here towards the origin while the second is
a “greater than” constraint satisfied here away from the origin. As you can see, there is no region satisfying
both constraints at the same time. So we say there is no feasible solution or no feasible
region, or we have a condition referred to as “infeasibility”. The next special case is Unboundedness.
This is a situation that applies only to maximization problem. Because all these 3 constraints are “greater
than” constraints, the feasible region is this region shaded here. Since this is a maximization problem, and
the feasible region is open ended, we can move the objective function line infinitely
without reaching the end of the feasible region. As a result, this situation is called “unboundedness”.
It suggests that we can make unlimited profit which is impractical. It is usually due to
a formulation error or by assuming a resource could be unlimited in supply. The last special case we’ll discuss here
is redundancy. Suppose you’re applying to enter a contest
where applicants have to be at least 15 years old. If X represents age, then we have X ≥ 15.
Suppose also that applicants must also have a valid driver’s license.
If the minimum licensing age is 16, then applicants must be at least 16 years old and we have
X ≥ 16. So we will call this first constraint redundant
because its effect has been overshadowed by the second constraint. Now consider this minimization problem. Here’s a graph showing its constraint lines.
Since these are all “greater than” constraints, here’s the feasible region. As you can see here, constraint 3 line does
not touch the feasible region at all. Therefore it is redundant. So a redundant constraint is one that does
not affect the feasible region. In essence we could remove a redundant constraint
without changing the feasible region or optimal solution. And that concludes this video on special cases
in solving linear programming problems. Thank you for watching.

Tags: , , , , , , , , , , , , , , , , , , , , , ,

43 Comments

Leave a Reply

Your email address will not be published. Required fields are marked *