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:

  1. The solution must be feasible (that is, all the constraints must be obeyed).
  2. 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 ROW1

2 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

Comments