The solution space of a single inequality constraint
Consider the constraint:
The solution space of this constraint is one of the closed half-planes
defined by the equation:
. To show this, let us consider a point
which satsifies Equation10
as equality, and another point
for which Equation10
is also valid. For any such pair of points, it holds that:
Interpreting the left side of Eq.11
as the inner (dot) product of the two vectors
and
, and recognizing that
, it follows that line
, itself, can be defined by point
and the set of points
such that vector
is at right angles with vector
. Furthermore, the set of points
that satisfy the > (<) part of Equation11
have the vector
forming an acute (obtuse) angle with vector
, and therefore, they are ``above'' (``below'') the line. Hence, the set of
points satisfying each of the two inequalities implied by Equation10
is given by one of the two half-planes the boundary of which is defined by the
corresponding equality constraint. Figure1
summarizes the above discussion.
Figure 1: Half-planes: the feasible region of a linear
inequality
An easy way to determine the half-plane depicting the solution space of a
linear inequality, is to draw the line depicting the solution space of the
corresponding equality constraint, and then test whether the point (0,0)
satisfies the inequality. In case of a positive answer, the solution space is
the half-space containing the origin, otherwise, it is the other one.
From the above discussion, it follows that the feasible region for the
prototype LP of Equation5
is the shaded area in the following figure:
Figure 2: The feasible region of the prototype example LP
|
