next up previous
Next: Polytope Convexity and Extreme Up: Generalization to the n-var Previous: Generalization to the n-var

The geometry of n-var LP's

n-var LP's require an n-dimensional space to ``geometrically'' represent a vector corresponding to a pricing of their decision variables. However, the concepts and techniques that allowed the geometric representation of the 2-var LP's in the previous section, generalize quite straightforwardly in this more complicated case.

Hence, given a linear constraint:


and a point tex2html_wrap_inline1687 satisfying Equation 14 as equality, we can perceive the solution space of

From the above description, it follows that the solution space of the equation tex2html_wrap_inline1713 , i.e., the 3-dim case, is a plane perpendicular to vector tex2html_wrap_inline1715 , which is characterized as the plane normal. Since this normality concept carries over to the more general n-dim case, we characterize the solution space of an n-var linear equation as a hyperplane. Furthermore, similar to the 2-var LP case, a hyperplane defined by the equation tex2html_wrap_inline1689 , divides the n-dim space into two half-spaces: one of them is the solution space of the inequality tex2html_wrap_inline1725 , and the other one is the solution space of the inequality tex2html_wrap_inline1727 .

Hence, the solution space (feasible region) of an n-var LP is geometrically defined by the intersection of a number of half-spaces and/or hyperplanes equal to the LP constraints, including the sign restrictions. Such a set is characterized as a polytope. In particular, a bounded polytope is called a polyhedron.

Two other concepts of interest in the following discussion are those of the straight line and the line segment. Given two points tex2html_wrap_inline1731 and tex2html_wrap_inline1733 , the straight line passing through them is algebraicaly defined by the set of points


Figure 7 provides a visualization of this definition.

Figure 7: The equation of a straight line

As it is seen in the figure above, the line segment between points tex2html_wrap_inline1735 and tex2html_wrap_inline1737 is analytically defined by:


Notice that Equation 16 can be rewritten as:






We say that Equations 17 and 18 define a convex combination of points tex2html_wrap_inline1735 and tex2html_wrap_inline1737 .

next up previous
Next: Polytope Convexity and Extreme Up: Generalization to the n-var Previous: Generalization to the n-var

UAL Data
Fri Jun 20 15:03:05 CDT 1997