Operations Management: An Integrated Approach, 5th Edition

OUTCOMES OF LINEAR PROGRAMMING PROBLEMS

Infeasible problem

An LP in which it is impossible for all the constraints to be satisfied simultaneously.

When an LP is solved, there are several possible outcomes. One outcome is an optimal solution, as we have seen for the example. Solver shows a Solver Results box (see Figure B-10) saying that “Solver found a solution. All constraints and optimality conditions are satisfied.” This is what we usually hope for when setting up and solving an LP. However, there are two additional possible outcomes when solving an LP. One occurs when Solver cannot find any feasible solution to the problem. Suppose we had these two constraints:

x₁ + x₂ ≥ 10

x₁ + x₂ ≤ 3

There is no combination of values for x₁ and x₂ that satisfies both constraints. When an LP does not have a feasible solution, we say the problem is infeasible. When this is discovered by Solver, Solver displays the Solver Results box shown in Figure B-14. If you get this message, the values of the decision variables are not meaningful. Be careful to always read the Solver Results message.

Some problems indeed are infeasible, but many times this box is obtained when the modeler has made an error in the model itself or in how the constraints were submitted to Solver. Even a small, simple error, such as entering a ≤ constraint incorrectly as a ≥ constraint, can cause the model to be infeasible. ...