12.1.4 Decision Variables: In the objective function and y are called decision variables.
12.1.5 Constraints The linear inequalities or restrictions on the variables of an LPP are called constraints. The conditions are called non-negative constraints.
12.1.6 Feasible Region The common region determined by all the constraints including non-negative constraints of an LPP is called the feasible region for the problem.
12.1.7 Feasible Solutions Points within and on the boundary of the feasible region for an LPP represent feasible solutions.
12.1.8 Infeasible Solutions: Any Point outside feasible region is called an infeasible solution.
12.1.9 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.
Following theorems are fundamental in solving LPPs.
12.1.10 Theorem 1: Let R be the feasible region (convex polygon) for an LPP and let be the objective function. When Z has an optimal value (maximum or minimum), where x and are subject to constraints described by linear inequalities, this optimal value must occur at a corner point (vertex) of the feasible region.
Theorem 2: Let R be the feasible region for a LPP and let 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 occur at a corner point of R.
If the feasible region R is unbounded, then a maximum or a minimum value of the objective function may or may not exist. However, if it exits, it must occur at a corner point of R.
12.1.11 Corner point method for solving a LPP
The method comprises of the following steps:
(1) Find the feasible region of the LPP and determine its corner points (vertices) either by inspection or by solving the two equations of the lines intersecting at that point.
(2) Evaluate the objective function at each corner point.
Let M and m, respectively denote the largest and the smallest values of Z.
(3) (i) When the feasible region is bounded, M and are, respectively, the maximum and minimum values of Z.
(ii) In case, the feasible region is unbounded.
(a) M is the maximum value of Z, if the open half plane determined by has no point in common with the feasible region. Otherwise, Z has no maximum value.
(b) Similarly, is the minimum of Z, if the open half plane determined by has no point in common with the feasible region? Otherwise, Z has no minimum value.
12.1.12 Multiple optimal points If two corner points of the feasible region are optimal solutions of the same type, i.e., both produce the same maximum or minimum, then any point on the line segment joining these two points is also an optimal solution of the same type.
Question 1:
Determine the maximum value of if the feasible region for an LPP is shown in Fig. 12.1.
Answer:
The feasible region is bounded. Therefore, maximum of Z must occur at the corner point of the feasible region (Fig. 12.1).
Corner Point | Value of Z |
Hence, the maximum value of Z is 112.