Graphical Method(using Corner Point) for LP Problems

[Home Page]  [Back]  [Content of Contributions]  [Movement: Green Leaf World]

The graphic solution procedure is one method for solving two(2) variable linear programming problems.

The graphical method involves following steps:

1. Formulate the Problem: Obtain the objective function & constraints.
2. Plot each constraints: Consider each inequations as equation. Then plot each constraints. 
3. Identify the feasible region: The area that satisfies all the constraints is called feasible region.
4. Calculate the optimal solution using Corner Point Method: 
1. Identify each of the corner or extreme points of the feasible region either by visual inspection or the method of simultaneous equations.
2. Compute the objective function at each point.
3. Identify the optimal solution by comparing the values of the objective function at each extreme point.

Example 01

Consider the following problem,

Objective function: maximize Z= 1000X + 850Y

Subject to,

 X +  Y <= 11.............................................(1)

6X + 5Y <= 60.............................................(2)

   X, Y >= 0..............................................(3)

Constraint (1) is assumed to be X + Y = 11. Figure 1a shows the region satisfying constraint (1) & (3). Point A(0, 11) on Y axis and point B(11, 0) on X  axis satisfies the constraint (1). Now draw a straight line connecting A and B. Consider the origin is at C(0, 0). So, the area bounded by A, B & C is the region satisfying constraint (1) & (3).

Again, constraint (2) is assumed to be 6X + 5Y = 60. In the X-axis the point D, where, Y=0, so, X=10 and in the Y-axis the point E, where, X=0, so, Y=12. Thus, point D(10, 0) on the X-axis and point E(0, 12) on the Y-axis satisfies constraint (2). The area bounded by C, D, E is the region satisfies constraint (2) & (3) is shown in figure 1b. 

The intersection point of both the straight line is assumed as F. We can calculate the value of X and Y at the point F by solving the following two equations,

X + y = 11...................................................(4)

6X + 5Y = 60.................................................(5)

Multiplying, equation (4) by 6 we get, 6X + 6Y = 66..........(6)

Now, subtracting equation (5) from equation (6) we get, Y= 6.

Putting the value of Y=6 in equation (4) we get, X= 5.

So, at point F, X=5 and Y=6.

The area bounded by the points CAFD is the feasible region as shown in the figure 1c that satisfies all the constraints which are subject to satisfy.

Now, calculate the objective function at each of the extreme points(Corner Point Method) in the region specified by CAFD.

Points       Objective Value(Z)

C(0,  0)    1000*0 + 850*0  = 0

A(0, 11)    1000*0 + 850*11 = 9350

F(5,  6)    1000*5 + 850*6  = 5,000 + 5100 = 10,100      

D(10, 0)    1000*10 + 850*0 = 10,000

Here, we can see that, the maximum value is obtained at F(5, 6). So, X=5 and Y=6 is the optimal solution to maximize the objective function.

Try Your Own

Problem 01: 

Consider, a factory manufactures article(product) A and B. A certain machine requires 1.5 hours and in addition a craftsman requires 2 hours to manufacture article A. Similarly, the machine requires 2.5 hours and in addition the craftsman requires 1.5 hours to manufacture article B.In a week the factory can avail 80hours of machine and 70 hours for craftsman's time. The profit on each article A is Rs. 5/- and on each article B is Rs. 4/-. Assume that, all the articles produced can be sold away. Find how many of each kind of articles should be produced to earn maximum profit per week.

Problem 02: 

Consider, vitamin A and B are found in two different foods F1 and F2. One unit of F1 contains 2 units of vitamin A and 3 units of vitamin B. One unit of F2 contains 4 units of vitamin A and 2 units of vitamin B.One unit of food F1 and F2 cost Rs. 5 and Rs. 2.5 respectively. Minimum daily requirement of vitamin A and B for a person is 40 and 50 units respectively. Find the optimal mix of food F1 & F2 that satisfy the requirement with minimum cost.

Problem 03: 

There are two products A and B. Cost of production(per unit) of A and B are Rs. 60 and Rs. 80, respectively. The company has to supply at least 200 units of B. One unit of product A requires 1 machine hour whereas B has a machine hours available abundantly within the company. Total machine hour available for product A is 400 hours. One unit of each product requires 1 labour hour. Total labour hour available are 500. Formulate the LP problem to minimize production cost & solve it.

Problem 04:  
A firm produces two types of gadgets A and B. Both are first processed in foundary and the goes to machine shop for finishing. The number of man hours required in each shop for the production of each unit of A and B are given in the table. Total amount of available man hours of the firm is also given.

---------------------------------------------------

                     Foundary          Machine shop

---------------------------------------------------

Gadget A               10                   5

Gadget B                6                   4

Capacity(per week)   1000                 600

---------------------------------------------------

Profit on the sale of gadget A and B are Rs. 30 and Rs. 20 respectively. Find the optimal solution.

Problem 05: 

A firm has an advertising budget 7,20,000. They need to allocate the total budget to magazine & television media. Estimated exposure in each page of a magazine is 60,000 and in television it is 1,20,000. Cost of each page in magazine is 9,000 and cost of each spot in television is 12,000. The firm has to advertise in at least two pages in magazine and at least three spots in television. Formulate the problem to utilize the budget with best exposure.