called an infeasible region . Feasible solutions Points within and on the boundary of the feasible region represent feasible solutions of the constraints. In Fig . , every point within and on the boundary of the feasible region OABC represents feasible solution to the problem.
For example, the point ( , ) is a feasible solution of the problem and so are the points ( , ), ( , ) etc. Any point outside the feasible region is called an infeasible solution. For example, the point ( , ) is an infeasible solution of the problem. Fig .
Optimal (feasible) solution : Any point in the feasible region that gives the optimal value (maximum or minimum) of the objective function is called an optimal solution. Now, we see that every point in the feasible region OABC satisfies all the constraints as given in ( ) to ( ), and since there are infinitely many points , it is not evident how we should go about finding a point that gives a maximum value of the objective function Z = x + y. To handle this situation, we use the following theorems which are fundamental in solving linear programming problems. The proofs of these theorems are beyond the scope of the book.
Theorem Let R be the feasible region (convex polygon) for a linear programming problem and let Z = ax + by be the objective function. When Z has an optimal value (maximum or minimum), where the variables x and y are subject to constraints described by linear inequalities, this optimal value must occur at a corner point* (vertex) of the feasible region. Theorem Let R be the feasible region for a linear programming problem, and let Z = ax + by be the objective function. If R is bounded** , then the objective function Z has both a maximum and a minimum value on R and each of these occurs at a corner point (vertex) of R.
Remark If R is unbounded , then a maximum or a minimum value of the objective function may not exist. However, if it exists,