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.

We now will shade the feasible region. To do that consider the constraints one by one. The first one is $6x_{1}+4x_{2}\leq 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}\leq 24$ to get $0\leq 24$. Since this is true we conclude that (0,0) lies in the region represented by $6x_{1}+4x_{2}\leq 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}\leq 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.)

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.

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 example

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.