Find solution using Simplex method (BigM method)
MAX Z = 3x1 + 5x2 + 4x3
subject to
2x1 + 3x2 <= 8
2x2 + 5x3 <= 10
3x1 + 2x2 + 4x3 <= 15
and x1,x2,x3 >= 0; Solution:Problem is | Max `Z` | `=` | `` | `3` | `x_1` | ` + ` | `5` | `x_2` | ` + ` | `4` | `x_3` |
|
| subject to |
| `` | `2` | `x_1` | ` + ` | `3` | `x_2` | | | | ≤ | `8` | | | | `` | `2` | `x_2` | ` + ` | `5` | `x_3` | ≤ | `10` | | `` | `3` | `x_1` | ` + ` | `2` | `x_2` | ` + ` | `4` | `x_3` | ≤ | `15` |
|
| and `x_1,x_2,x_3 >= 0; ` |
The problem is converted to canonical form by adding slack, surplus and artificial variables as appropiate
1. As the constraint-1 is of type '`<=`' we should add slack variable `S_1`
2. As the constraint-2 is of type '`<=`' we should add slack variable `S_2`
3. As the constraint-3 is of type '`<=`' we should add slack variable `S_3`
After introducing slack variables| Max `Z` | `=` | `` | `3` | `x_1` | ` + ` | `5` | `x_2` | ` + ` | `4` | `x_3` | ` + ` | `0` | `S_1` | ` + ` | `0` | `S_2` | ` + ` | `0` | `S_3` |
|
| subject to |
| `` | `2` | `x_1` | ` + ` | `3` | `x_2` | | | | ` + ` | `` | `S_1` | | | | | | | = | `8` | | | | `` | `2` | `x_2` | ` + ` | `5` | `x_3` | | | | ` + ` | `` | `S_2` | | | | = | `10` | | `` | `3` | `x_1` | ` + ` | `2` | `x_2` | ` + ` | `4` | `x_3` | | | | | | | ` + ` | `` | `S_3` | = | `15` |
|
| and `x_1,x_2,x_3,S_1,S_2,S_3 >= 0` |
| `Z` | ` - ` | `3` | `x_1` | ` - ` | `5` | `x_2` | ` - ` | `4` | `x_3` | | | | | | | | | | = | `0` |
|
| `` | `2` | `x_1` | ` + ` | `3` | `x_2` | | | | ` + ` | `` | `S_1` | | | | | | | = | `8` | | | | `` | `2` | `x_2` | ` + ` | `5` | `x_3` | | | | ` + ` | `` | `S_2` | | | | = | `10` | | `` | `3` | `x_1` | ` + ` | `2` | `x_2` | ` + ` | `4` | `x_3` | | | | | | | ` + ` | `` | `S_3` | = | `15` |
|
Simplex tableau is
Tableau-0
| `"Basis"` | `x_1` | `x_2` | `x_3` | `S_1` | `S_2` | `S_3` | `RHS` | |
| `R_1` `Z` | `-3` | `-5` | `-4` | `0` | `0` | `0` | `0` | |
| `R_2` `S_1` | `2` | `3` | `0` | `1` | `0` | `0` | `8` | |
| `R_3` `S_2` | `0` | `2` | `5` | `0` | `1` | `0` | `10` | |
| `R_4` `S_3` | `3` | `2` | `4` | `0` | `0` | `1` | `15` | |
Tableau-1
| `"Basis"` | `x_1` | `x_2``darr` | `x_3` | `S_1` | `S_2` | `S_3` | `RHS` | `"Ratio"=(RHS)/(x_2)` |
| `R_1` `Z` | `-3` | `-5` | `-4` | `0` | `0` | `0` | `0` | |
| `R_2` `S_1` | `2` | `(3)` | `0` | `1` | `0` | `0` | `8` | `(8)/(3)=2.6667``->` |
| `R_3` `S_2` | `0` | `2` | `5` | `0` | `1` | `0` | `10` | `(10)/(2)=5` |
| `R_4` `S_3` | `3` | `2` | `4` | `0` | `0` | `1` | `15` | `(15)/(2)=7.5` |
Most Negative `Z` is `-5`. So,
the entering variable is `x_2`.
Minimum ratio is `2.6667`. So,
the leaving basis variable is `S_1`.
`:.`
The pivot element is `3`.
Entering `=x_2`, Departing `=S_1`, Key Element `=3`
`R_2`(new)`= R_2`(old) `-: 3`
| `x_1` | `x_2` | `x_3` | `S_1` | `S_2` | `S_3` | `RHS` |
| `R_2`(old) = | `2` | `3` | `0` | `1` | `0` | `0` | `8` |
| `R_2`(new)`= R_2`(old) `-: 3` | `0.6667` | `1` | `0` | `0.3333` | `0` | `0` | `2.6667` |
`R_3`(new)`= R_3`(old) - `2 R_2`(new)
| `x_1` | `x_2` | `x_3` | `S_1` | `S_2` | `S_3` | `RHS` |
| `R_3`(old) = | `0` | `2` | `5` | `0` | `1` | `0` | `10` |
| `R_2`(new) = | `0.6667` | `1` | `0` | `0.3333` | `0` | `0` | `2.6667` |
| `2 xx R_2`(new) = | `1.3333` | `2` | `0` | `0.6667` | `0` | `0` | `5.3333` |
| `R_3`(new)`= R_3`(old) - `2 R_2`(new) | `-1.3333` | `0` | `5` | `-0.6667` | `1` | `0` | `4.6667` |
`R_4`(new)`= R_4`(old) - `2 R_2`(new)
| `x_1` | `x_2` | `x_3` | `S_1` | `S_2` | `S_3` | `RHS` |
| `R_4`(old) = | `3` | `2` | `4` | `0` | `0` | `1` | `15` |
| `R_2`(new) = | `0.6667` | `1` | `0` | `0.3333` | `0` | `0` | `2.6667` |
| `2 xx R_2`(new) = | `1.3333` | `2` | `0` | `0.6667` | `0` | `0` | `5.3333` |
| `R_4`(new)`= R_4`(old) - `2 R_2`(new) | `1.6667` | `0` | `4` | `-0.6667` | `0` | `1` | `9.6667` |
`R_1`(new)`= R_1`(old) - `-5 R_2`(new)
| `x_1` | `x_2` | `x_3` | `S_1` | `S_2` | `S_3` | `RHS` |
| `R_1`(old) = | `-3` | `-5` | `-4` | `0` | `0` | `0` | `0` |
| `R_2`(new) = | `0.6667` | `1` | `0` | `0.3333` | `0` | `0` | `2.6667` |
| `-5 xx R_2`(new) = | `-3.3333` | `-5` | `0` | `-1.6667` | `0` | `0` | `-13.3333` |
| `R_1`(new)`= R_1`(old) - `-5 R_2`(new) | `0.3333` | `0` | `-4` | `1.6667` | `0` | `0` | `13.3333` |
Tableau-2
| `"Basis"` | `x_1` | `x_2` | `x_3``darr` | `S_1` | `S_2` | `S_3` | `RHS` | `"Ratio"=(RHS)/(x_3)` |
| `R_1` `Z` | `0.3333` | `0` | `-4` | `1.6667` | `0` | `0` | `13.3333` | |
| `R_2` `x_2` | `0.6667` | `1` | `0` | `0.3333` | `0` | `0` | `2.6667` | `(2.6667)/(0)` (ignore, denominator is 0) |
| `R_3` `S_2` | `-1.3333` | `0` | `(5)` | `-0.6667` | `1` | `0` | `4.6667` | `(4.6667)/(5)=0.9333``->` |
| `R_4` `S_3` | `1.6667` | `0` | `4` | `-0.6667` | `0` | `1` | `9.6667` | `(9.6667)/(4)=2.4167` |
Most Negative `Z` is `-4`. So,
the entering variable is `x_3`.
Minimum ratio is `0.9333`. So,
the leaving basis variable is `S_2`.
`:.`
The pivot element is `5`.
Entering `=x_3`, Departing `=S_2`, Key Element `=5`
`R_3`(new)`= R_3`(old) `-: 5`
| `x_1` | `x_2` | `x_3` | `S_1` | `S_2` | `S_3` | `RHS` |
| `R_3`(old) = | `-1.3333` | `0` | `5` | `-0.6667` | `1` | `0` | `4.6667` |
| `R_3`(new)`= R_3`(old) `-: 5` | `-0.2667` | `0` | `1` | `-0.1333` | `0.2` | `0` | `0.9333` |
`R_2`(new)`= R_2`(old)
| `x_1` | `x_2` | `x_3` | `S_1` | `S_2` | `S_3` | `RHS` |
| `R_2`(old) = | `0.6667` | `1` | `0` | `0.3333` | `0` | `0` | `2.6667` |
| `R_2`(new)`= R_2`(old) | `0.6667` | `1` | `0` | `0.3333` | `0` | `0` | `2.6667` |
`R_4`(new)`= R_4`(old) - `4 R_3`(new)
| `x_1` | `x_2` | `x_3` | `S_1` | `S_2` | `S_3` | `RHS` |
| `R_4`(old) = | `1.6667` | `0` | `4` | `-0.6667` | `0` | `1` | `9.6667` |
| `R_3`(new) = | `-0.2667` | `0` | `1` | `-0.1333` | `0.2` | `0` | `0.9333` |
| `4 xx R_3`(new) = | `-1.0667` | `0` | `4` | `-0.5333` | `0.8` | `0` | `3.7333` |
| `R_4`(new)`= R_4`(old) - `4 R_3`(new) | `2.7333` | `0` | `0` | `-0.1333` | `-0.8` | `1` | `5.9333` |
`R_1`(new)`= R_1`(old) - `-4 R_3`(new)
| `x_1` | `x_2` | `x_3` | `S_1` | `S_2` | `S_3` | `RHS` |
| `R_1`(old) = | `0.3333` | `0` | `-4` | `1.6667` | `0` | `0` | `13.3333` |
| `R_3`(new) = | `-0.2667` | `0` | `1` | `-0.1333` | `0.2` | `0` | `0.9333` |
| `-4 xx R_3`(new) = | `1.0667` | `0` | `-4` | `0.5333` | `-0.8` | `0` | `-3.7333` |
| `R_1`(new)`= R_1`(old) - `-4 R_3`(new) | `-0.7333` | `0` | `0` | `1.1333` | `0.8` | `0` | `17.0667` |
Tableau-3
| `"Basis"` | `x_1``darr` | `x_2` | `x_3` | `S_1` | `S_2` | `S_3` | `RHS` | `"Ratio"=(RHS)/(x_1)` |
| `R_1` `Z` | `-0.7333` | `0` | `0` | `1.1333` | `0.8` | `0` | `17.0667` | |
| `R_2` `x_2` | `0.6667` | `1` | `0` | `0.3333` | `0` | `0` | `2.6667` | `(2.6667)/(0.6667)=4` |
| `R_3` `x_3` | `-0.2667` | `0` | `1` | `-0.1333` | `0.2` | `0` | `0.9333` | `(0.9333)/(-0.2667)` (ignore, denominator is -ve) |
| `R_4` `S_3` | `(2.7333)` | `0` | `0` | `-0.1333` | `-0.8` | `1` | `5.9333` | `(5.9333)/(2.7333)=2.1707``->` |
Most Negative `Z` is `-0.7333`. So,
the entering variable is `x_1`.
Minimum ratio is `2.1707`. So,
the leaving basis variable is `S_3`.
`:.`
The pivot element is `2.7333`.
Entering `=x_1`, Departing `=S_3`, Key Element `=2.7333`
`R_4`(new)`= R_4`(old) `-: 2.7333`
| `x_1` | `x_2` | `x_3` | `S_1` | `S_2` | `S_3` | `RHS` |
| `R_4`(old) = | `2.7333` | `0` | `0` | `-0.1333` | `-0.8` | `1` | `5.9333` |
| `R_4`(new)`= R_4`(old) `-: 2.7333` | `1` | `0` | `0` | `-0.0488` | `-0.2927` | `0.3659` | `2.1707` |
`R_2`(new)`= R_2`(old) - `0.6667 R_4`(new)
| `x_1` | `x_2` | `x_3` | `S_1` | `S_2` | `S_3` | `RHS` |
| `R_2`(old) = | `0.6667` | `1` | `0` | `0.3333` | `0` | `0` | `2.6667` |
| `R_4`(new) = | `1` | `0` | `0` | `-0.0488` | `-0.2927` | `0.3659` | `2.1707` |
| `0.6667 xx R_4`(new) = | `0.6667` | `0` | `0` | `-0.0325` | `-0.1951` | `0.2439` | `1.4472` |
| `R_2`(new)`= R_2`(old) - `0.6667 R_4`(new) | `0` | `1` | `0` | `0.3659` | `0.1951` | `-0.2439` | `1.2195` |
`R_3`(new)`= R_3`(old) + `0.2667 R_4`(new)
| `x_1` | `x_2` | `x_3` | `S_1` | `S_2` | `S_3` | `RHS` |
| `R_3`(old) = | `-0.2667` | `0` | `1` | `-0.1333` | `0.2` | `0` | `0.9333` |
| `R_4`(new) = | `1` | `0` | `0` | `-0.0488` | `-0.2927` | `0.3659` | `2.1707` |
| `0.2667 xx R_4`(new) = | `0.2667` | `0` | `0` | `-0.013` | `-0.078` | `0.0976` | `0.5789` |
| `R_3`(new)`= R_3`(old) + `0.2667 R_4`(new) | `0` | `0` | `1` | `-0.1463` | `0.122` | `0.0976` | `1.5122` |
`R_1`(new)`= R_1`(old) - `-0.7333 R_4`(new)
| `x_1` | `x_2` | `x_3` | `S_1` | `S_2` | `S_3` | `RHS` |
| `R_1`(old) = | `-0.7333` | `0` | `0` | `1.1333` | `0.8` | `0` | `17.0667` |
| `R_4`(new) = | `1` | `0` | `0` | `-0.0488` | `-0.2927` | `0.3659` | `2.1707` |
| `-0.7333 xx R_4`(new) = | `-0.7333` | `0` | `0` | `0.0358` | `0.2146` | `-0.2683` | `-1.5919` |
| `R_1`(new)`= R_1`(old) - `-0.7333 R_4`(new) | `0` | `0` | `0` | `1.0976` | `0.5854` | `0.2683` | `18.6585` |
Tableau-4
| `"Basis"` | `x_1` | `x_2` | `x_3` | `S_1` | `S_2` | `S_3` | `RHS` | |
| `R_1` `Z` | `0` | `0` | `0` | `1.0976` | `0.5854` | `0.2683` | `18.6585` | |
| `R_2` `x_2` | `0` | `1` | `0` | `0.3659` | `0.1951` | `-0.2439` | `1.2195` | |
| `R_3` `x_3` | `0` | `0` | `1` | `-0.1463` | `0.122` | `0.0976` | `1.5122` | |
| `R_4` `x_1` | `1` | `0` | `0` | `-0.0488` | `-0.2927` | `0.3659` | `2.1707` | |
Since all `Z_j >= 0`
Hence, optimal solution is arrived with value of variables as :
`x_1=2.1707,x_2=1.2195,x_3=1.5122`
Max `Z=18.6585`