2. Example-1
Find solution using dual-simplex method
MAX Z = -2x1 - x2
subject to
-3x1 - x2 <= -3
-4x1 - 3x2 <= -6
-x1 - 2x2 <= -3
and x1,x2 >= 0
Solution:
Problem is
| Max `Z` | `=` | ` - ` | `2` | `x_1` | ` - ` | `` | `x_2` |
| | subject to | | ` - ` | `3` | `x_1` | ` - ` | `` | `x_2` | ≤ | `-3` | | ` - ` | `4` | `x_1` | ` - ` | `3` | `x_2` | ≤ | `-6` | | ` - ` | `` | `x_1` | ` - ` | `2` | `x_2` | ≤ | `-3` |
| | and `x_1,x_2 >= 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` | `=` | ` - ` | `2` | `x_1` | ` - ` | `` | `x_2` | ` + ` | `0` | `S_1` | ` + ` | `0` | `S_2` | ` + ` | `0` | `S_3` |
| | subject to | | ` - ` | `3` | `x_1` | ` - ` | `` | `x_2` | ` + ` | `` | `S_1` | | | | | | | = | `-3` | | ` - ` | `4` | `x_1` | ` - ` | `3` | `x_2` | | | | ` + ` | `` | `S_2` | | | | = | `-6` | | ` - ` | `` | `x_1` | ` - ` | `2` | `x_2` | | | | | | | ` + ` | `` | `S_3` | = | `-3` |
| | and `x_1,x_2,S_1,S_2,S_3 >= 0` |
| Iteration-1 | | `C_j` | `-2` | `-1` | `0` | `0` | `0` | | `B` | `C_B` | `X_B` | `x_1` | `x_2` | `S_1` | `S_2` | `S_3` | | `S_1` | `0` | `-3` | `-3` | `-1` | `1` | `0` | `0` | | `S_2` | `0` | `-6` | `-4` | `(-3)` | `0` | `1` | `0` | | `S_3` | `0` | `-3` | `-1` | `-2` | `0` | `0` | `1` | | `Z=0` | | `Z_j` | `0` | `0` | `0` | `0` | `0` | | | | `Z_j-C_j` | `2` | `1` | `0` | `0` | `0` | | | | `"Ratio"=(Z_j-C_j)/(S_2,j)`
and `S_2,j<0` | `-0.5` | `-0.3333``uarr` | --- | --- | --- |
Minimum negative `X_B` is `-6` and its row index is `2`. So, the leaving basis variable is `S_2`.
Maximum negative ratio is `-0.3333` and its column index is `2`. So, the entering variable is `x_2`.
`:.` The pivot element is `-3`.
Entering `=x_2`, Departing `=S_2`, Key Element `=-3`
`R_2`(new)`= R_2`(old) `-: (-3)`| `R_2`(old) = | `-6` | `-4` | `-3` | `0` | `1` | `0` | | `R_2`(new)`= R_2`(old) `-: (-3)` | `2` | `4/3` | `1` | `0` | `-1/3` | `0` |
`R_1`(new)`= R_1`(old) + `R_2`(new)| `R_1`(old) = | `-3` | `-3` | `-1` | `1` | `0` | `0` | | `R_2`(new) = | `2` | `4/3` | `1` | `0` | `-1/3` | `0` | | `R_1`(new)`= R_1`(old) + `R_2`(new) | `-1` | `-5/3` | `0` | `1` | `-1/3` | `0` |
`R_3`(new)`= R_3`(old) + `2 R_2`(new)| `R_3`(old) = | `-3` | `-1` | `-2` | `0` | `0` | `1` | | `R_2`(new) = | `2` | `4/3` | `1` | `0` | `-1/3` | `0` | | `2 xx R_2`(new) = | `4` | `8/3` | `2` | `0` | `-2/3` | `0` | | `R_3`(new)`= R_3`(old) + `2 R_2`(new) | `1` | `5/3` | `0` | `0` | `-2/3` | `1` |
| Iteration-2 | | `C_j` | `-2` | `-1` | `0` | `0` | `0` | | `B` | `C_B` | `X_B` | `x_1` | `x_2` | `S_1` | `S_2` | `S_3` | | `S_1` | `0` | `-1` | `(-5/3)` | `0` | `1` | `-1/3` | `0` | | `x_2` | `-1` | `2` | `4/3` | `1` | `0` | `-1/3` | `0` | | `S_3` | `0` | `1` | `5/3` | `0` | `0` | `-2/3` | `1` | | `Z=-2` | | `Z_j` | `-4/3` | `-1` | `0` | `1/3` | `0` | | | | `Z_j-C_j` | `2/3` | `0` | `0` | `1/3` | `0` | | | | `"Ratio"=(Z_j-C_j)/(S_1,j)`
and `S_1,j<0` | `-0.4``uarr` | --- | --- | `-1` | --- |
Minimum negative `X_B` is `-1` and its row index is `1`. So, the leaving basis variable is `S_1`.
Maximum negative ratio is `-0.4` and its column index is `1`. So, the entering variable is `x_1`.
`:.` The pivot element is `-5/3`.
Entering `=x_1`, Departing `=S_1`, Key Element `=-5/3`
`R_1`(new)`= R_1`(old) `xx(-3/5)`| `R_1`(old) = | `-1` | `-5/3` | `0` | `1` | `-1/3` | `0` | | `R_1`(new)`= R_1`(old) `xx(-3/5)` | `3/5` | `1` | `0` | `-3/5` | `1/5` | `0` |
`R_2`(new)`= R_2`(old) - `4/3 R_1`(new)| `R_2`(old) = | `2` | `4/3` | `1` | `0` | `-1/3` | `0` | | `R_1`(new) = | `3/5` | `1` | `0` | `-3/5` | `1/5` | `0` | | `4/3 xx R_1`(new) = | `4/5` | `4/3` | `0` | `-4/5` | `4/15` | `0` | | `R_2`(new)`= R_2`(old) - `4/3 R_1`(new) | `6/5` | `0` | `1` | `4/5` | `-3/5` | `0` |
`R_3`(new)`= R_3`(old) - `5/3 R_1`(new)| `R_3`(old) = | `1` | `5/3` | `0` | `0` | `-2/3` | `1` | | `R_1`(new) = | `3/5` | `1` | `0` | `-3/5` | `1/5` | `0` | | `5/3 xx R_1`(new) = | `1` | `5/3` | `0` | `-1` | `1/3` | `0` | | `R_3`(new)`= R_3`(old) - `5/3 R_1`(new) | `0` | `0` | `0` | `1` | `-1` | `1` |
| Iteration-3 | | `C_j` | `-2` | `-1` | `0` | `0` | `0` | | `B` | `C_B` | `X_B` | `x_1` | `x_2` | `S_1` | `S_2` | `S_3` | | `x_1` | `-2` | `3/5` | `1` | `0` | `-3/5` | `1/5` | `0` | | `x_2` | `-1` | `6/5` | `0` | `1` | `4/5` | `-3/5` | `0` | | `S_3` | `0` | `0` | `0` | `0` | `1` | `-1` | `1` | | `Z=-12/5` | | `Z_j` | `-2` | `-1` | `2/5` | `1/5` | `0` | | | | `Z_j-C_j` | `0` | `0` | `2/5` | `1/5` | `0` | | | | Ratio | --- | --- | --- | --- | --- |
Since all `Z_j-C_j >= 0` and all `X_(Bi) >= 0` thus the current solution is the optimal solution.
Hence, optimal solution is arrived with value of variables as :
`x_1=3/5,x_2=6/5`
Max `Z=-12/5`
This material is intended as a summary. Use your textbook for detail explanation.
Any bug, improvement, feedback then
|
