To solve an LP problem, a set of values must be found for the decision variables, which satisfies the following requirements: - The solution must be
*feasible*(that is, all the constraints must be obeyed). - The solution must be
*optimal*(that is, no other feasible solutions give a better value for the objective function).
A solution which violates any of the constraints is called
The terminology used to explain how a solution is obtained is based on a geometrical description of the LP model. A model containing only two variables can be represented by a diagram in which the constraints are shown as straight lines. Beware, however, that LP problems exist in many dimensions and wrong inferences can be drawn if too great a weight is placed on the 2-dimensional analogy. For example, consider the following problem:
Figure 1 represents the problem graphically.
The shaded area covers all the possible sets of values for x Possible
values of the objective function are shown by broken lines. It can be
seen that the optimal value is at the point where ROW2 and ROW3
intersect (x In fact, the optimal solution can always be found at a vertex of the feasible region (unless there is no optimal solution - see section 4.4). This is true even if the objective function is parallel to one of the constraints. For example, if the objective function were
it would take its optimal value of 1 at any point on ROW3, including the vertices which lie on ROW3. The geometrical description can be generalised to problems with more than two variables, but it is more difficult to understand, because a problem in n variables has its feasible region defined in n-dimensional space. (Also large LP problems generally contain far more decision variables than the number of constraints. The sort of 2-dimensional example shown here is atypical, because there are more constraints than variables). |

LP Training > 4. Interpretation of Results >