The search procedure adopted above can be simplified if we can take advantage of the first characteristics of feasible solution and the objective function. The following statements are of fundamental importance in linear programming.
- 1. The solution set for a group of linear inequalities is a convex set. Therefore, the area of feasible solution, if it exists, for a linear programming problem is a convex set.
- 2. Given a linear objective function in a linear programming problem, the optimal solution will always include a corner point on the area of feasible solutions.
The corner point method of solving LPP has the following steps.
- 1. Graphically identify the area of feasible solutions.
- 2. Determine the coordinates of each corner point on the area of feasible solutions.
- 3. Substitute the coordinates of the corner points in the objective function to determine the corresponding value of Z.
- 4. An optimal solution occurs in a maximisation problem at the corner point yielding the highest value of Z and in a minimisation problem at the corner point yielding the lowest value of Z.
Example 2.63. Determine the optimal solution to the LPP given below using the Corner Point Method.
In the figure already drawn, there are four corner points ABCD on the area of the feasible solution. The corner points BCD are clearly known and A can be read from the graph. The table below gives the coordinates of all the corner points and the value of objective function associated with the points.
Corner Point |
Coordinates |
Value of Objective function Z=3x_{1}+6x_{2} |
A |
(3, 6) |
3×3+6×6=45 |
B |
(0, 20) |
3×0+6×20=120 |
C |
(20, 0) |
3×20+6×0=60 |
D |
(10, 0) |
3×10+0×6=30 |
As we were to minimize Z, the optimal solution occurs at Z = 30.
Suppose the objective was to maximise Z, the value would have occurred at corner point B with coordinates (0, 2) i.e. Z = 120.
Recent Comments