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

Summary

This video tutorial, presented by Joshua Emmanuel, delves into the special cases encountered in linear programming problems. The tutorial covers four main topics: alternative optimal solutions, infeasibility, unboundedness, and redundancy. Alternative solutions occur when there are multiple points that result in the same optimal value, often due to parallel objective and constraint lines. Infeasibility arises when no region satisfies all constraints simultaneously. Unboundedness is a scenario, especially in maximization problems, where the feasible region is open-ended, allowing infinite movement of the objective function line. Lastly, redundancy refers to constraints that don't affect the feasible region or solution, as they are overshadowed by other constraints. These concepts are crucial for understanding the complexities and potential issues in linear programming.

Highlights

• Alternative solutions arise when more than one optimal point is present. 😊
• Infeasibility occurs when no feasible region exists due to conflicting constraints. 😕
• Unboundedness can lead to impractical results, suggesting a formulation mistake. 🤔
• Redundancy happens when a constraint is overshadowed and doesn't affect outcomes. 🙄

Key Takeaways

• Alternate solutions offer multiple optimal decision points due to parallel constraint and objective lines. 🎯
• Infeasibility indicates a lack of solution due to conflicting constraints. 🚫
• Unboundedness suggests infinite solutions and often hints at a formulation error. ♾️
• Redundant constraints do not affect the feasible region, as their conditions are already covered. 🗑️

Overview

In this engaging tutorial by Joshua Emmanuel, we unravel the peculiarities one might face in linear programming. By dissecting the concepts of alternative optimal solutions, infeasibility, unboundedness, and redundancy, the session promises a comprehensive understanding of these intriguing cases.

Ever wondered why sometimes there's more than one answer to a linear programming problem? This occurs when the objective line is parallel to a constraint, creating alternative optimal solutions. On the other hand, infeasibility pops up when constraints refuse to cooperate, leaving us without any solution!

Unboundedness can seem like finding a pot of gold—unlimited profit! But beware, it's often a sign of errors in your model. Finally, redundancy is the extra baggage in constraints that don't change anything. Discarding these can simplify your problem without altering the solution.

Chapters

• 00:00 - 00:30: Introduction to Special Cases in Linear Programming This chapter introduces special cases encountered in linear programming problems, including alternative optimal solutions, infeasibility, unboundedness, and redundancy. The focus initially is on alternate optimal solutions, demonstrated with an instance of a linear programming problem and its graphical representation. The tutorial begins by considering the objective function line and its implications in a maximization context.
• 00:30 - 01:30: Alternative Optimal Solutions This chapter discusses the concept of Alternative Optimal Solutions, which occurs when more than one optimal solution exists for a problem. This situation typically arises when the objective function line is parallel to a binding constraint. The parallel nature of both lines—having the same slope—results in the objective function line coinciding with the constraint line, thus leading to multiple optimal solutions.
• 01:30 - 02:00: Infeasibility in Linear Programming This chapter discusses the concept of infeasibility in linear programming. It begins by explaining the idea of alternative optimal solutions, where every point along a line between two optimal solution points is also optimal. Alternative optimal solutions allow for various combinations of decision variables yielding the same optimal result in terms of profit or cost. The chapter then shifts focus to the concept of infeasibility, introducing a linear programming problem and its graphical representation. A 'less than' constraint and a 'greater than' constraint are examined, illustrating how they interact and potentially lead to a situation where no solution satisfies all constraints simultaneously, hence leading to infeasibility.
• 02:00 - 02:30: Unboundedness in Linear Programming This chapter discusses unboundedness in linear programming, a special case that only applies to maximization problems. It begins by explaining infeasibility, where no region satisfies all constraints, and then contrasts it with unboundedness, a condition that arises due to 'greater than' constraints, leading to an unlimited feasible region.
• 02:30 - 04:00: Redundancy in Constraints In this chapter titled 'Redundancy in Constraints,' the focus is on a maximization problem where the feasible region is open-ended, leading to a situation known as 'unboundedness.' This occurs when the objective function line can move infinitely without reaching the end of the feasible region, suggesting unlimited profit, which is impractical. This typically results from formulation errors or assumptions of unlimited resources. The chapter also hints at discussing redundancy.
• 04:00 - 04:30: Conclusion The chapter discusses conditions for entering a contest, focusing on age requirements and licensing. It explains how certain constraints become redundant when overshadowed by stricter ones. The example provided involves participants needing to be at least 15 years old to enter and 16 years old to have a valid driver's license, making the former constraint redundant.

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

• 00:00 - 00:30 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
• 00:30 - 01:00 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.
• 01:00 - 01:30 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
• 01:30 - 02:00 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
• 02:00 - 02:30 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.
• 02:30 - 03:00 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
• 03:00 - 03:30 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
• 03:30 - 04:00 solution. And that concludes this video on special cases in solving linear programming problems. Thank you for watching.