Algorithm
|
Graphical Method Steps (Rule)
|
|
Step-1:
|
Generate the mathematical model of the given LP problem.
|
|
Step-2:
|
a. Replace `<=` and `>=` sign to `=` in each constraint (inequality to equality).
b. Find the two points of each line and draw it on graph.
c. For inequality sign of each constraint, decide the area of feasible solution.
(For `<=` constraint it is left side of the line and for `>=` constraint it is right side of the line.
So for easy understanding, take any point of left side of line and if it satisfies the constraint then mark the left side area otherwise mark the right side area)
d. Shade the common portion of the graph.
|
|
Step-3:
|
a. Decide the extreme points (corner points) of the feasible region.
b. Calculate the objective function value at each extreme points.
c. Find out min or max value (optimal value) of the objective function.
|
Example-1
Find solution using graphical method
MAX z = 40x1 + 80x2
subject to
2x1 + 3x2 <= 48
x1 <= 15
x2 <= 10
and x1,x2 >= 0
Solution:
Problem is
| MAX `z_x` | `=` | `` | `40` | `x_1` | ` + ` | `80` | `x_2` |
|
| subject to |
| `` | `2` | `x_1` | ` + ` | `3` | `x_2` | ≤ | `48` | | `` | `` | `x_1` | | | | ≤ | `15` | | | | `` | `` | `x_2` | ≤ | `10` |
|
| and `x_1,x_2 >= 0; ` |
Hint to draw constraints
1. To draw constraint `color{red}{2x_1+3x_2<=48 ->(1)}`
Treat it as `color{red}{2x_1+3x_2=48}`
When `x_1=0` then `x_2=?`
`=>2(0)+3x_2=48`
`=>3x_2=48`
`=>x_2=(48)/(3)=16`
When `x_2=0` then `x_1=?`
`=>2x_1+3(0)=48`
`=>2x_1=48`
`=>x_1=(48)/(2)=24`
2. To draw constraint `color{green}{x_1<=15 ->(2)}`
Treat it as `color{green}{x_1=15}`
Here line is parallel to Y-axis
3. To draw constraint `color{blue}{x_2<=10 ->(3)}`
Treat it as `color{blue}{x_2=10}`
Here line is parallel to X-axis
The value of the objective function at each of these extreme points is as follows:
Extreme Point
Coordinates
(`x_1`,`x_2`) | Lines through Extreme Point | Objective function value
`z=40x_1 + 80x_2` |
| `color{red}{O(0,0)}` | `color{black}{4->x_1>=0}`
`color{black}{5->x_2>=0}` | `40(0)+80(0)=0` |
| `color{green}{A(15,0)}` | `color{green}{2->x_1<=15}`
`color{black}{5->x_2>=0}` | `40(15)+80(0)=600` |
| `color{blue}{B(15,6)}` | `color{red}{1->2x_1+3x_2<=48}`
`color{green}{2->x_1<=15}` | `40(15)+80(6)=1080` |
| `color{brown}{C(9,10)}` | `color{red}{1->2x_1+3x_2<=48}`
`color{blue}{3->x_2<=10}` | `40(9)+80(10)=1160` |
| `color{darkorange}{D(0,10)}` | `color{blue}{3->x_2<=10}`
`color{black}{4->x_1>=0}` | `40(0)+80(10)=800` |
The maximum value of the objective function `z=1160` occurs at the extreme point `(9,10)`.
Hence, the optimal solution to the given LP problem is : `x_1=9, x_2=10` and max `z=1160`.
This material is intended as a summary. Use your textbook for detail explanation.
Any bug, improvement, feedback then
