Lecture_3_Linear Programming : Graphical Solution

3.1 Graphical Solution Procedure
The graphical solution procedure
1. Consider each inequality constraint as equation.
2. Plot each equation on the graph as each one will geometrically represent a straight line.
3. Shade the feasible region. Every point on the line will satisfy the equation of the line. If
the inequality constraint corresponding to that line is ‘?’ then the region below the line
lying in the first quadrant is shaded. Similarly for ‘?’ the region above the line is shaded.
The points lying in the common region will satisfy the constraints. This common region
is called feasible region.
4. Choose the convenient value of Z and plot the objective function line.
5. Pull the objective function line until the extreme points of feasible region.
a. In the maximization case this line will stop far from the origin and passing
through at least one corner of the feasible region.
b. In the minimization case, this line will stop near to the origin and passing through
at least one corner of the feasible region.
6. Read the co-ordinates of the extreme points selected in step 5 and find the maximum or
minimum value of Z.
3.2 Definitions
1. Solution – Any specification of the values for decision variable among (x1, x2… xn) is
called a solution.
2. Feasible solution is a solution for which all constraints are satisfied.
3. Infeasible solution is a solution for which atleast one constraint is not satisfied.
4. Feasible region is a collection of all feasible solutions.
5. Optimal solution is a feasible solution that has the most favorable value of the objective
function.
6. Most favorable value is the largest value if the objective function is to be maximized,
whereas it is the smallest value if the objective function is to be minimized.
7. Multiple optimal solution – More than one solution with the same optimal value of the
objective function.
8. Unbounded solution – If the value of the objective function can be increased or
decreased indefinitely such solutions are called unbounded solution.
9. Feasible region – The region containing all the solutions of an inequality
10. Corner point feasible solution is a solution that lies at the corner of the feasible region.
3.3 Example problems
Example 1
Solve 3x + 5y < 15 graphically