Multiple optimal solution
The optimal value of the objective function occurs at more than 1 extreme points, then the problem has multiple optimal solution.
Example
Find solution using graphical method
MAX z = 10x1 + 6x2
subject to
5x1 + 3x2 <= 30
x1 + 2x2 <= 18
and x1,x2 >= 0
Solution:
Problem is
| MAX `z_x` | `=` | `` | `10` | `x_1` | ` + ` | `6` | `x_2` |
|
| subject to |
| `` | `5` | `x_1` | ` + ` | `3` | `x_2` | ≤ | `30` | | `` | `` | `x_1` | ` + ` | `2` | `x_2` | ≤ | `18` |
|
| and `x_1,x_2 >= 0; ` |
Hint to draw constraints
1. To draw constraint `color{red}{5x_1+3x_2<=30 ->(1)}`
Treat it as `color{red}{5x_1+3x_2=30}`
When `x_1=0` then `x_2=?`
`=>5(0)+3x_2=30`
`=>3x_2=30`
`=>x_2=(30)/(3)=10`
When `x_2=0` then `x_1=?`
`=>5x_1+3(0)=30`
`=>5x_1=30`
`=>x_1=(30)/(5)=6`
2. To draw constraint `color{green}{x_1+2x_2<=18 ->(2)}`
Treat it as `color{green}{x_1+2x_2=18}`
When `x_1=0` then `x_2=?`
`=>(0)+2x_2=18`
`=>2x_2=18`
`=>x_2=(18)/(2)=9`
When `x_2=0` then `x_1=?`
`=>x_1+2(0)=18`
`=>x_1=18`
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=10x_1 + 6x_2` |
| `color{red}{O(0,0)}` | `color{black}{3->x_1>=0}`
`color{black}{4->x_2>=0}` | `10(0)+6(0)=0` |
| `color{green}{A(6,0)}` | `color{red}{1->5x_1+3x_2<=30}`
`color{black}{4->x_2>=0}` | `10(6)+6(0)=60` |
| `color{blue}{B(0.86,8.57)}` | `color{red}{1->5x_1+3x_2<=30}`
`color{green}{2->x_1+2x_2<=18}` | `10(0.86)+6(8.57)=60` |
| `color{brown}{C(0,9)}` | `color{green}{2->x_1+2x_2<=18}`
`color{black}{3->x_1>=0}` | `10(0)+6(9)=54` |
The maximum value of the objective function `z=60` occurs at 2 extreme points.
Hence, problem has multiple optimal solutions and max `z=60`.
This material is intended as a summary. Use your textbook for detail explanation.
Any bug, improvement, feedback then
