Objective Function: Maximize 5 * X + 4 * Y —9 (Obj)
subject to
X + Y < = 5 (1)
X + Y >= 3; (2)
X + Y >= 2; (3).
Let us consider the LP problem above. Let us identify what is a feasible region.
The feasible region of the linear programming (lp) problem is nothing but a convex polytope /polyhedron which is formed due to the intersection of the three straight lines in the inequalities given by (1), (2) and (3). In the case of more than one dimension in the constraint, the intersection of the hyperplanes is called as the feasible region. The above feasible region can be feasible or infeasible.
In this context we can also discuss what constitute infeasible convex sets. Let us refine the above problem and remove constraint (1). Now if you see the region enclosed by these constraints of the solution set does not have an upper bound. So the problem will have infinite as maximum. Here the set of constraints form an infinite feasible region and hence no optimum solution can be found be traversing the vertices.
Similarly we consider the lp problem with the objective function and only constraint # 1. Here if you see this problem does not have a lower bound and so the region enclosed by the constraints is infinite and the lower bound will converge at-infinity or there does not exist any solution to the linear programming problem. Here too the problem is infeasible.
Now let us analyze dead or redundant constraints. Lin Prog formulations sometimes have over specified constraints that removing one or more of them does not make any difference to the optimal solution. However while removing one of the constraints the shape of the feasible region does get altered.
Let us take the problem stated at the beginning of this paragraph as an example
Constraints 2 and 3 overspecify the linear programming problem as the feasible region of 2 is contained in 3. Such constraints are termed as Dead Constraints or Redundant constraints. An lp with an objective function and a set of constraints can be over specified
If the objective is a maximization problem then both the second and the third constraints are not required to be specified. If the objective is a minimization problem then both first and second constraints are not required.
These constraints should be removed before the linear programming problem is solved as any algorithm or a computer program will consume extra computational resources to go locate the points in the feasible convex region.