### 4.2 Geometrical Description of LP Solution

 Terminology 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 infeasible. Example Problem 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: Minimize `- 6 x1 - x2 OBJ` subject to `3 x1 + 5 x2 ≤ 15 ROW12 x1 + x2 ≤ 4 ROW2 x1 - x2 ≤ 1 ROW3 x1 ≥ 0, x2 ≥ 0` Figure 1 represents the problem graphically. Figure 1: Graphical Representation of a 2-variable Problem Geometrical Interpretation The shaded area covers all the possible sets of values for x1 and x2 which satisfy the constraints. This is called the feasible region. The boundaries of the feasible region are straight lines representing the constraints and bounds on the variables. A point where the lines intersect is called a vertex of the feasible region. 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 (x1 = 5/3, x2 = 2/3 and the objective function value is -32/3). 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 ` Minimize x1 - x2` 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). `previous contents next`