3.5 Definitions and Theorems 127
Figure 3.6 Unbounded solution.
can be taken as an optimum solution with a profit value of $20,000. There are three
other possibilities. In some problems, the feasible region may not be a closed convex
polygon. In such a case, it may happen that the profit level can be increased to an
infinitely large value without leaving the feasible region, as shown in Fig. 3.6. In this
case the solution of the linear programming problem is said to be unbounded. On the
other extreme, the constraint set may be empty in some problems. This could be due
to the inconsistency of the constraints; or, sometimes, even though the constraints may
be consistent, no point satisfying the constraints may also satisfy the nonnegativity
restrictions. The last possible case is when the feasible region consists of a single
point. This can occur only if the number of constraints is at least equal to the number
of variables. A problem of this kind is of no interest to us since there is only one
feasible point and there is nothing to be optimized.
Thus a linear programming problem may have (1) a unique and finite optimum
solution, (2) an infinite number of optimal solutions, (3) an unbounded solution, (4) no
solution, or (5) a unique feasible point. Assuming that the linear programming problem
is properly formulated, the following general geometrical characteristics can be noted
from the graphical solution:
1.The feasible region is a convex polygon.†
- he optimum value occurs at an extreme point or vertex of the feasible region.T
3.5 Definitions and Theorems
The geometrical characteristics of a linear programming problem stated in Section 3.4
can be proved mathematically. Some of the more powerful methods of solving linear
programming problems take advantage of these characteristics. The terminology used
in linear programming and some of the important theorems are presented in this section.
†A convex polygon consists of a set of points having the property that the line segment joining any two
points in the set is entirely in the convex set. In problems having more than two decision variables, the
feasible region is called aconvex polyhedron, which is defined in the next section.
