Last modified on 8 April 2012, at 02:52

Operations Research/Graphical LP solution

We will now attempt to find an optimal solution to the linear programming model we introduced in the previous section. The method we will employ is known as the graphical method and can be applied to any problem with two decision variables. It basically consists of two steps: Finding the feasible region or the feasible space (which is the region in the plane where all the feasible solutions to the problems lie) and then identifying the optimal solution among all the feasible ones.

To begin the procedure we first graph the lines

6x_1+4x_2= 24,

x_1+2x_2= 6,

x_2-x_1= 1,

x_2= 2,

in the first quadrant. Note that for our purpose x_1=x and x_2=y on the graph.

Plottedlines.jpg

We now will shade the feasible region. To do that consider the constraints one by one. The first one is 6x_1+4x_2\le 24. To determine the region it represents, choose any point which does not pass through the line 6x_1+4x_2= 24 say (0,0). Substitute it in the constraint 6x_1+4x_2\le 24 to get 0\le 24. Since this is true we conclude that (0,0) lies in the region represented by 6x_1+4x_2\le 24. We conclude that all the points on the side of 6x_1+4x_2= 24 containing (0,0) actually represent 6x_1+4x_2\le 24. This is suggested by the fact that the line 6x_1+4x_2 = 24 divides the plane in 2 distinct halfs: One of points satisfying the inequality and one of those which don't.

In this way all the inequalities can be shaded. The region which is shaded under all inequalities is the feasible region of the whole problem. Clearly in this region all the constraints of the problem hold. (The non negativity restrictions hold since we are working in the first quadrant.)

Feasible region.jpg

We are now ready to find out the optimal solutions. To do this graph the line 5x_1+4x_2=10. Since z=5x_1+4x_2 represents the objective function so 5x_1+4x_2=10 represents the points where the objective function has value 10 (i.e. the total profit is 10). Now plot the line 5x_1+4x_2=15 which represents the points where the objective function has value 15. This gives us an idea of the direction of increase in z. The optimal solution occurs at the point X which is the point beyond which any further increase will put z outside the boundaries of the feasible region. The coordiantes of X can be found by solving 6x_1+4x_2= 24 and x_1+2x_2= 6 so that x_1=3 and x_2=1.5. This is the optimal solution to the problem and indicates that the amounts of salts X and Y should be 3 and 1.5 respectively. This will give the maximum profit of 21 which is the optimal value.

Optimal solution.jpg

A point to note is that the optimal solution in a LP model always occurs at a corner point of a feasible region. This is true even if the line z=c comes out to be parallel to one of the constraints. Although a mathematical proof of this fact would involve considerable linear algebra we will satisfy ourselves of it by noting that that any objective function in the feasible region would have glided out of the region just after touching one of the corner points.

A minimization exampleEdit

Let us look at a minimization problem. It can occur in actual practice when instead of the profits associated with the salts X and Y we are given the costs of their production. All we have to do is now move the line z=c in the direction of its decrease and we have the optimal solution at the point ((0,0) in our example) where any further decrease will take z outside the feasible region. Another way to solve the problem is to convert the min problem into a max one. To do that simple consider the negative of the objective function.