Optimisation Problems are concerned with finding the optimal solution of an objective function. Objective function to be optimised is associated with some conditions or constraints.
Linear Programming Problems are a special case of optimisation problems. Every mathematical relation defined in such problems is a linear relation.
Graphical Method of Solving LPP is found by plotting all the constraints graphically and finding the common region to all the constraints.
Feasible region is the common region determined by all the constraints including the non-negativity constraints of an LPP. It is also called the solution region of the LPP.
A point within or in the boundary of feasible region is called the feasible solution.
A point in the feasible region which gives the optimal (maximum or minimum) value of the objective function is called the optimal solution to the LPP.
Corner Point Method (for bounded region):
1. Find the feasible region of LPP and find its vertices.
2. Evaluate the objective function Z = ax + by at each corner point.
3. Let M and m respectively be the largest and the smallest values at these points.
4. If the feasible region is bounded, M and m are respectively the maximum and the minimum values of the objective function.
If the feasible region is unbounded, then:
1. M is the maximum value of the objective function if the open half plane determined by ax + by > M has no point in common with the feasible region. Otherwise, the objective function has no maximum value.
2. m is the minimum value of the objective function if the open half plane determined by ax + by < m has no point in common with the feasible region. Otherwise, the objective function has no minimum value.
If two corner points of the feasible region 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. This fact is known as alternate optimal solution.