7.6. Potential Issues in Linear Programming

So, of course, you also across when a solution is exist. So, in our case we had a solution where we had a feasible region which looks like a trapezium like this. So, the first point is that the feasible region will already be convex, convex means that if you take any two points inside the region and you can connect them by a line, the entire line stays in the region. So, for instance if I have a shape which looks like this, then this is not convex, because I can pick two points inside and then connected by a line and this line in this portion leaves the region.

This chunk discusses the concept of feasibility in linear programming. A feasible region refers to the set of all possible solutions that satisfy the constraints of the problem. In a feasible region, if you draw a straight line between any two points (which represent potential solutions), that line must remain within the region for those points to be considered feasible. If it extends outside, then at least one of those points is infeasible due to the constraints. A convex region means it has no 'indentations', so every line segment between any two points inside it lies entirely within it, ensuring solutions are consistent and manageable.

Imagine you are trying to park your car in a perfectly rectangular parking lot. If the parking lot is filled to capacity, the area inside it represents your feasible parking spots. If you can freely move any point inside this area without crossing the boundary, it’s analogous to finding solutions that fit your constraints. However, if there's a wall or a part of the lot that isn’t suitable for parking (constraining), trying to park could be analogous to drawing a line that crosses outside the feasible region, indicating there's no solution for that choice.

So, the feasible space will always be convex, but it could be empty. Supposing, we are had an extra constraint in an earlier thing which says that everything must be below this line, now when addition to the orange if I had this blue constraint, then there is no point that satisfies everything. So, the constraints are unsatisfiable, the feasible region become empty and there will be no solutions.

This chunk highlights that while feasible regions are generally convex, they can also be empty if constraints conflict with each other. For instance, if you have constraints that mandate a solution must be both below a certain line and above another conflicting line, no point can fulfill both requirements. This results in no viable solutions to the linear programming problem, indicating that the constraints set up are unsatisfactory or conflicting in nature.

Consider trying to find a restaurant within a city when you have specific dietary restrictions and transportation options. If your restrictions limit you to vegan restaurants and your transportation only allows you to travel to places outside city limits, you might find that no restaurants fit within what you can reach, leaving you with no options. This is akin to having an empty feasible region in linear programming.

The other possibility is that we do not constraint it enough, so we could just say that supposing we started only, we only say that say for example, h must be less than 300, then this has an unbounded region.

In this chunk, we learn about an unbounded feasible region, where there is no upper limit on the values a variable can take. If constraints are too relaxed, it's possible to construct a feasible region that stretches infinitely in one or more directions. For example, if one of our constraints allows a variable to take exceedingly high values without a cap, then potential solutions are unbounded, and maximizing or minimizing an objective function could lead to infinitely large or small values, making it impossible to find a definitive optimal solution.

Think of a savings account where you can deposit money without limit but can only withdraw within certain constraints. If you have a rule to save money but no rule on how much you can earn, your account balance can keep growing indefinitely. In linear programming, if you create a situation where profits can continually increase without limit because you haven’t properly capped costs or production, you face an unbounded feasible region.

But, if it is bounded, then what the theory of linear programming tells us is that the objective function will lie, it is maximum or minimum will lie along on a vertex along the boundary of that bounded region and so it is sufficient to examine those and that is what simplex does.

This chunk explains that when a feasible region is bounded, the optimal solutions to the linear programming problem will always occur at the vertices (corners) of that region. This is a key principle in linear programming, as it simplifies the optimization process. Instead of having to examine every point in the region, one can simply evaluate the objective function at each vertex and identify which yields the maximum or minimum value, significantly streamlining the process. The simplex algorithm is a method that takes advantage of this concept to find solutions efficiently.

Imagine planning a road trip where you want to calculate the most efficient route to visit all the attractions. If you’re only allowed to choose stops at certain points (vertices), it becomes easier—evaluate your travel costs and distances only at those stops rather than evaluating every inch of the road. Like checking only the corners of a polygon, this method ensures you're not missing viable options while simplifying decisions.

--