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

Solution

Write the given constraint in the form of equation i.e. 3x + 5y = 15 Put x=0 then the value y=3
Put y=0 then the value x=5
Therefore the coordinates are (0, 3) and (5, 0). Thus these points are joined to form a straight line as shown in the graph.
Put x=0, y=0 in the given constraint then
0<15, the condition is true. (0, 0) is solution nearer to origin. So shade the region below the line, which is the feasible region.