Graphical Method for Linear Programming Problem
Graphical method to solve a linear programming problem (LPP) is used to solve a linear programming problem with two variables only. It help us to visualize the the procedure of finding the optimal solution to a linear programming problem.
Step 1
Given a LPP, consider each inequality (say, $ax+by \leq c$) as equality ($ax+by =c$) from a given LPP (which represents a straight line in $xy$-plane).
Step 2
Put $y=0$ in $ax+by=c$ to get point where the line meets $x$-axis. Similarly put $x=0$ to obtain a point where line meets $y$-axis. Joint these two points to obtain the graph of the line $ax+by=c$.
Step 3
Choose a point [if possible (0,0)], not lying on this line. Substitute its coordinates in the inequality. If the inequality is satisfied, then shade the portion of the plane which contains the chosen point; otherwise shade the portion which does not contain this point. The shaded portion represents the solution set for that inequality.
Step 4
Repeat Step 2 and Step 3 for each inequality of given LPP.
Step 5
Find the common shaded region (feasible region) of all inequalities given by constraints and non-negativity restrictions.
Step 6
Find the coordinates of each corner points of the feasible region. Find the values of the objective function ($z$) at each of the corner points of the feasible region.
Step 7
Find the maximum or minimum (as the case may be) value of the objective function $z$. The coordinate of corner point which gives maximum or minimum value of the objective function determine the optimal solution of the LPP.
The limitation of graphical method is that it can be used to solve LPP with two variables only. The graphical method of solving linear programming problem is of limited application in real life business problems because in real business problems the number of variables are large in numbers.
Graphical Method for LPP Example 1
Solve the following LPP graphically.
$$ \begin{eqnarray*} Max\; z= 2x +5y & & \\ \mbox{s.t. } x + 4y&\leq & 24 \\ 3x+y &\leq & 21 \\ x+y &\leq & 9 \\ \mbox{and }x , y & \geq & 0 \end{eqnarray*} $$
Solution
Step 1
Consider all inequality constraint as equality:
$x+4y = 24$.
$3x+y = 21$.
$x+y = 9$.
Step 2
In the first equation $x+4y = 24$, taking $x = 0$, we get $y = 6$. i.e., $A (0, 6)$ and taking $y = 0$, we get $x=24$. i.e., $B(24,0)$.
| Points | X coordinate | Y Coordinate |
|---|---|---|
| $A$ | 0 | 6 |
| $B$ | 24 | 0 |
In the second equation $3x+y = 21$, taking $x = 0$, we get $y=21$. i.e., $C(0,21)$ and taking $y = 0$, we get $x=7$. i.e. $D(7,0)$.
| Points | X coordinate | Y Coordinate |
|---|---|---|
| $C$ | 0 | 21 |
| $D$ | 7 | 0 |
In the third equation $x+y = 9$, taking $x = 0$, we get $y=9$. i.e., $E(0,9)$ and taking $y = 0$, we get $x=9$. i.e. $F(9,0)$.
| Points | X coordinate | Y Coordinate |
|---|---|---|
| $E$ | 0 | 9 |
| $F$ | 9 | 0 |
Step 3 to 5
Plot these points on the graph by taking suitable scale.
The feasible region for the given linear programming problem is shaded in the following graph. That is Region $OAPQD$.
Step 6
The coordinates of $P$ can be obtained by solving the two equations $x+4y=24$ and $x+y=9$. The coordinates of $P$ are $(4,5)$.
The coordinates of $Q$ can be obtained by solving the two equations $3x+y=21$ and $x+y=9$. The coordinates of $P$ are $(6,3)$.
The corner points of the feasible region are:
| Corner Points | Coordinates | $Z=2x + 5 y$ |
|---|---|---|
| $O$ | $(0,0)$ | $Z = 2 \times 0 + 5 \times 0=0$ |
| $A$ | $(0,6)$ | $Z = 2 \times 0 + 5 \times 6=30$ |
| $P$ | $(4,5)$ | $Z = 2 \times 4 + 5 \times 5=33$ |
| $Q$ | $(6,3)$ | $Z = 2 \times 6 + 5 \times 3=27$ |
| $D$ | $(7,0)$ | $Z = 2 \times 7 + 5 \times 0=14$ |
Step 7
The maximum value of the objective function $z$ is 33, which is at $P(4,5)$. Hence the problem has unique optimal solution. The optimal solution to the given linear programming problem is $x=4$ and $y=5$ with maximum value of the objective function is $z=33$.
Graphical Method for LPP Example 2
Solve the following LPP graphically.
$$ \begin{eqnarray*} Min\; z= 5x +6y & & \\ \mbox{s.t. } x+ y&\leq & 1000 \\ x &\geq & 300 \\ y &\geq & 150 \\ \mbox{and }x , y & \geq & 0 \end{eqnarray*} $$
Solution
Step 1
Consider all inequality constraint of LPP as equality:
$x +y = 1000$
$x = 300$
and
$y = 150$.
Step 2
In the first equality constraint $x +y = 1000$, taking $x = 0$, we get $y = 1000$. i.e., $A (0, 1000)$ and taking $y = 0$, we get $x=1000$. i.e., $B(1000,0)$.
| Points | X coordinate | Y Coordinate |
|---|---|---|
| $A$ | 0 | 1000 |
| $B$ | 1000 | 0 |
The second equality constraint $x= 300$, is the line parallel to $Y$-axis at $(300,0)$.
| Points | X coordinate | Y Coordinate |
|---|---|---|
| $C$ | 300 | 0 |
The third equality constraint $y= 150$, is the line parallel to $X$-axis at $(0,150)$.
| Points | X coordinate | Y Coordinate |
|---|---|---|
| $D$ | 0 | 150 |
Step 3 to 5
Plot these points on the graph by taking suitable scale.
The feasible region for the given linear programming problem is shaded in the following graph. That is Region $PQR$.
Step 6
The coordinates of $P$ can be obtained by solving the two equations $x=300$ and $y=150$. The coordinates of $P$ are $(300,150)$.
The coordinates of $Q$ can be obtained by solving the two equations $x+y=1000$ and $x=300$. The coordinates of $Q$ are $(300,700)$.
The coordinates of $R$ can be obtained by solving the two equations $x+y=1000$ and $y=150$. The coordinates of $R$ are $(850,150)$.
The corner points of the feasible region are:
| Corner Points | Coordinates | $Z=5x + 6 y$ |
|---|---|---|
| $P$ | $(300,150)$ | $Z = 5 \times 300 + 6 \times 150=2400$ |
| $Q$ | $(300,700)$ | $Z = 5\times 300 + 6\times 700=5700$ |
| $R$ | $(850,150)$ | $Z = 5\times 850 + 6\times 150=5150$ |
Step 7
The minimum value of the objective function $z$ is 2400, which is at $P(300,150)$. Hence the problem has unique optimal solution. The optimal solution to the given linear programming problem is $x=300$ and $y=150$ with minimum value of the objective function is $z=2400$.
Graphical Method for LPP Example 3
Solve the following LPP graphically.
$$ \begin{eqnarray*} Max\; z= 3x +4y & & \\ \mbox{s.t. } x - y&\leq & 1 \\ -x+y &\leq & 0 \\ \mbox{and }x , y & \geq & 0 \end{eqnarray*} $$
Solution
Step 1
Consider all inequality constraint of LPP as equality:
$x -y = 1$
$-x+y = 0$
Step 2
In the first equality constraint $x -y = 1$, taking $x = 0$, we get $y = -1$. i.e., $A (0, -1)$ and taking $y = 0$, we get $x=1$. i.e., $B(1,0)$.
| Points | X coordinate | Y Coordinate |
|---|---|---|
| $A$ | 0 | -1 |
| $B$ | 1 | 0 |
In the second equality constraint $-x+y = 0$ (i.e., $x=y$. The two points are $O(0,0)$ and $C(1,1)$.
| Points | X coordinate | Y Coordinate |
|---|---|---|
| $O$ | 0 | 0 |
| $C$ | 1 | 1 |
Step 3 to 5
Plot these points on the graph by taking suitable scale.
Step 6
As there is no points in common, which satisfies both the constraints simultaneously. Hence there is no feasible solution to the given linear programming problem.
Step 7
Thus given linear programming problem has no feasible solution.
Graphical Method for LPP Example 4
Solve the following LPP graphically.
$$ \begin{eqnarray*} Max\; z= 3x +5y & & \\ \mbox{s.t. } 2x + y&\geq & 7 \\ x+y&\geq & 6 \\ x+3y &\geq & 9 \\ \mbox{and }x , y & \geq & 0 \end{eqnarray*} $$
Solution
Step 1
Consider all inequality constraint as equality:
$2x+y = 7$.
$x+y = 6$.
$x+3y = 9$.
Step 2
In the first equation $2x+y = 7$, taking $x = 0$, we get $y = 7$. i.e., $A (0, 7)$ and taking $y = 0$, we get $x=7/2 = 3.5$. i.e., $B(3.5,0)$.
| Points | X coordinate | Y Coordinate |
|---|---|---|
| $A$ | 0 | 7 |
| $B$ | 3.5 | 0 |
In the second equation $x+y = 6$, taking $x = 0$, we get $y=6$. i.e., $C(0,6)$ and taking $y = 0$, we get $x=6$. i.e. $D(6,0)$.
| Points | X coordinate | Y Coordinate |
|---|---|---|
| $C$ | 0 | 6 |
| $D$ | 6 | 0 |
In the third equation $x+3y = 9$, taking $x = 0$, we get $y=3$. i.e., $E(0,3)$ and taking $y = 0$, we get $x=9$. i.e. $F(9,0)$.
| Points | X coordinate | Y Coordinate |
|---|---|---|
| $E$ | 0 | 3 |
| $F$ | 9 | 0 |
Sep 3 to 5
Plot these points on the graph by taking suitable scale.
The feasible region for the given linear programming problem is shaded in the following graph. The feasible region is an unbounded space.
Step 6
The coordinates of $P$ can be obtained by solving the two equations $2x+y=7$ and $x+y=6$. The coordinates of $P$ are $(1,5)$.
The coordinates of $Q$ can be obtained by solving the two equations $x+3y=9$ and $x+y=6$. The coordinates of $P$ are $(4.5,1.5)$.
The corner points of the feasible region are:
| Corner Points | Coordinates | $Z=3x + 5y$ |
|---|---|---|
| $A$ | $(0,7)$ | $Z = 3\times 0 + 5\times 7=35$ |
| $P$ | $(1,5)$ | $Z = 3\times 1 + 5\times 5=28$ |
| $Q$ | $(4.5,1.5)$ | $Z = 3\times 4.5 + 5\times 1.5=12$ |
| $F$ | $(9,0)$ | $Z = 3\times 9 + 5\times 0=27$ |
Since the feasible region is unbounded space, let us check the value of objective function for any point from from the feasible region, say $R(0,10)$. The value of $Z$ ate $R(0,10)$ is $Z= 30 + 510=50$.
Step 7
The value of $Z$ at $R(0,10)$ is $50$, which is larger than the value of $Z$ at corner points.
This shows that the value of objective function increases infinitely as you go through the feasible region.
Hence the problem has unbounded solution.
Graphical Method for LPP Example 5
Solve the following LPP graphically.
$$ \begin{eqnarray*} Min\; z= 200x +150y & & \\ \mbox{s.t. } 6x + 2y&\geq & 8 \\ 2x+4y &\geq & 12 \\ 4x+12y &\geq & 24 \\ \mbox{and }x , y & \geq & 0 \end{eqnarray*} $$
Solution
Step 1
Consider all inequality constraint as equality:
$6x+2y = 8$.
$2x+4y = 12$.
$4x+12y = 24$.
Step 2
In the first equation $6x+2y = 8$, taking $x = 0$, we get $y = 4$. i.e., $A (0, 4)$ and taking $y = 0$, we get $x=8/6 = 1.3$. i.e., $B(1.3,0)$.
| Points | X coordinate | Y Coordinate |
|---|---|---|
| $A$ | 0 | 4 |
| $B$ | 1.3 | 0 |
In the second equation $2x+4y = 12$, taking $x = 0$, we get $y=3$. i.e., $C(0,3)$ and taking $y = 0$, we get $x=6$. i.e. $D(6,0)$.
| Points | X coordinate | Y Coordinate |
|---|---|---|
| $C$ | 0 | 3 |
| $D$ | 6 | 0 |
In the third equation $4x+12y = 24$, taking $x = 0$, we get $y=2$. i.e., $E(0,2)$ and taking $y = 0$, we get $x=6$. i.e. $F(6,0)$.
| Points | X coordinate | Y Coordinate |
|---|---|---|
| $E$ | 0 | 2 |
| $F$ | 6 | 0 |
Step 3 to 5
Plot these points on the graph by taking suitable scale.
The feasible region for the given linear programming problem is shaded in the following graph.
Step 6
The coordinates of $G$ can be obtained by solving the two equations $6x+2y=8$ and $2x+4y=12$. The coordinates of $G$ are $(0.4,2.8)$.
The corner points of the feasible region are:
| Corner Points | Coordinates | $Z=200x + 150 y$ |
|---|---|---|
| $A$ | $(0,4)$ | $Z = 200\times 0 + 150\times 4=600$ |
| $G$ | $(0.4,2.8)$ | $Z = 200\times 0.4 + 150\times 2.8=500$ |
| $D$ | $(6,0)$ | $Z = 200\times 6 + 150\times 0=1200$ |
Step 7
The minimum value of the objective function $z$ is 500, which is at $G(0.4,2.8)$. Hence the problem has unique optimal solution. The optimal solution to the given linear programming problem is $x=0.4$ and $y=2.8$ with minimum value of the objective function is $z=500$.
Note that the feasible region is an open space (unbounded). But still the problem has a unique solution.
Graphical Method for LPP Example 6
Solve the following LPP graphically.
$$ \begin{eqnarray*} Max\; z= 4x +3y & & \\ \mbox{s.t. } 4x + 3y&\leq & 24 \\ x&\leq & 5 \\ y &\leq & 6 \\ \mbox{and }x , y & \geq & 0 \end{eqnarray*} $$
Solution
Step 1
Consider all inequality constraint as equality:
$4x+3y = 24$.
$x = 5$.
$y = 6$.
Step 2
In the first equation $4x+3y = 24$, taking $x = 0$, we get $y = 8$. i.e., $A (0, 8)$ and taking $y = 0$, we get $x=6$. i.e., $B(6,0)$.
| Points | X coordinate | Y Coordinate |
|---|---|---|
| $A$ | 0 | 8 |
| $B$ | 6 | 0 |
The second equation $x= 5$, is the line parallel to $Y$-axis at $(5,0)$.
| Point | X coordinate | Y Coordinate |
|---|---|---|
| $C$ | 5 | 0 |
The third equation $y= 6$, is the line parallel to $X$-axis at $(0,6)$.
| Point | X coordinate | Y Coordinate |
|---|---|---|
| $D$ | 0 | 6 |
Sep 3 to 5
Plot these points on the graph by taking suitable scale.
The feasible region for the given linear programming problem is shaded in the following graph.
Step 6
The coordinates of $P$ can be obtained by solving the two equations $4x+3y=24$ and $y=6$. The coordinates of $P$ are $(3/2,6)$.
The coordinates of $Q$ can be obtained by solving the two equations $4x+3y=24$ and $x=5$. The coordinates of $Q$ are $(5,4/3)$.
The corner points of the feasible region are:
| Corner Points | Coordinates | $Z=4x + 3y$ |
|---|---|---|
| $O$ | $(0,0)$ | $Z = 4\times 0 + 3\times 0=0$ |
| $D$ | $(0,6)$ | $Z = 4\times 0 + 3\times 6=18$ |
| $P$ | $(3/2,6)$ | $Z = 4\times 3/2 + 3\times 6=24$ |
| $Q$ | $(5,4/3)$ | $Z = 4\times 5 + 3\times 4/3=24$ |
| $C$ | $(5,0)$ | $Z = 4\times 5 + 3\times 0=20$ |
Step 7
The maximum value of the objective function $Z$ is 24 which is at $P(3/2,6)$ and $Q(5,4/3)$.
Since the maximum vale of $Z$ is at two points $P$ and $Q$, the given problem has an alternate optimum solution.
Note that, for any point on the segment $PQ$ the value of $Z$ will be 24 (maximum).
Alternate solution to the linear programming problem exists, when one of the constraint is parallel to the objective function.
Endnote
In this tutorial you learn about how to use graphical method to solve a linear programming problem involving two variables.
To learn more about linear programming problem, please refer to the following tutorials:
Let me know in the comments if you have any questions on Graphical method to solve linear programming problem and your thoughts on this article.
