3. Example-2
Find solution using dual-simplex method
MIN Z = 2x1 + 3x2 + 0x3
subject to
2x1 - x2 - x3 >= 3
x1 - x2 + x3 >= 2
and x1,x2,x3 >= 0
Solution:
Problem is
| Min `Z` | `=` | `` | `2` | `x_1` | ` + ` | `3` | `x_2` | | | |
| | subject to | | `` | `2` | `x_1` | ` - ` | `` | `x_2` | ` - ` | `` | `x_3` | ≥ | `3` | | `` | `` | `x_1` | ` - ` | `` | `x_2` | ` + ` | `` | `x_3` | ≥ | `2` |
| | and `x_1,x_2,x_3 >= 0; ` |
In order to apply the dual simplex method, convert Min Z to Max Z and all `>=` constraint to `<=` constraint by multiply -1.
Problem is
| Max `Z` | `=` | ` - ` | `2` | `x_1` | ` - ` | `3` | `x_2` | | | |
| | subject to | | ` - ` | `2` | `x_1` | ` + ` | `` | `x_2` | ` + ` | `` | `x_3` | ≤ | `-3` | | ` - ` | `` | `x_1` | ` + ` | `` | `x_2` | ` - ` | `` | `x_3` | ≤ | `-2` |
| | 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`
After introducing slack variables
| Max `Z` | `=` | ` - ` | `2` | `x_1` | ` - ` | `3` | `x_2` | ` + ` | `0` | `x_3` | ` + ` | `0` | `S_1` | ` + ` | `0` | `S_2` |
| | subject to | | ` - ` | `2` | `x_1` | ` + ` | `` | `x_2` | ` + ` | `` | `x_3` | ` + ` | `` | `S_1` | | | | = | `-3` | | ` - ` | `` | `x_1` | ` + ` | `` | `x_2` | ` - ` | `` | `x_3` | | | | ` + ` | `` | `S_2` | = | `-2` |
| | and `x_1,x_2,x_3,S_1,S_2 >= 0` |
| Iteration-1 | | `C_j` | `-2` | `-3` | `0` | `0` | `0` | | `B` | `C_B` | `X_B` | `x_1` | `x_2` | `x_3` | `S_1` | `S_2` | | `S_1` | `0` | `-3` | `(-2)` | `1` | `1` | `1` | `0` | | `S_2` | `0` | `-2` | `-1` | `1` | `-1` | `0` | `1` | | `Z=0` | | `Z_j` | `0` | `0` | `0` | `0` | `0` | | | | `Z_j-C_j` | `2` | `3` | `0` | `0` | `0` | | | | `"Ratio"=(Z_j-C_j)/(S_1,j)`
and `S_1,j<0` | `-1``uarr` | --- | --- | --- | --- |
Minimum negative `X_B` is `-3` and its row index is `1`. So, the leaving basis variable is `S_1`.
Maximum negative ratio is `-1` and its column index is `1`. So, the entering variable is `x_1`.
`:.` The pivot element is `-2`.
Entering `=x_1`, Departing `=S_1`, Key Element `=-2`
`R_1`(new)`= R_1`(old) `-: (-2)`| `R_1`(old) = | `-3` | `-2` | `1` | `1` | `1` | `0` | | `R_1`(new)`= R_1`(old) `-: (-2)` | `3/2` | `1` | `-1/2` | `-1/2` | `-1/2` | `0` |
`R_2`(new)`= R_2`(old) + `R_1`(new)| `R_2`(old) = | `-2` | `-1` | `1` | `-1` | `0` | `1` | | `R_1`(new) = | `3/2` | `1` | `-1/2` | `-1/2` | `-1/2` | `0` | | `R_2`(new)`= R_2`(old) + `R_1`(new) | `-1/2` | `0` | `1/2` | `-3/2` | `-1/2` | `1` |
| Iteration-2 | | `C_j` | `-2` | `-3` | `0` | `0` | `0` | | `B` | `C_B` | `X_B` | `x_1` | `x_2` | `x_3` | `S_1` | `S_2` | | `x_1` | `-2` | `3/2` | `1` | `-1/2` | `-1/2` | `-1/2` | `0` | | `S_2` | `0` | `-1/2` | `0` | `1/2` | `(-3/2)` | `-1/2` | `1` | | `Z=-3` | | `Z_j` | `-2` | `1` | `1` | `1` | `0` | | | | `Z_j-C_j` | `0` | `4` | `1` | `1` | `0` | | | | `"Ratio"=(Z_j-C_j)/(S_2,j)`
and `S_2,j<0` | --- | --- | `-0.6667``uarr` | `-2` | --- |
Minimum negative `X_B` is `-1/2` and its row index is `2`. So, the leaving basis variable is `S_2`.
Maximum negative ratio is `-0.6667` and its column index is `3`. So, the entering variable is `x_3`.
`:.` The pivot element is `-3/2`.
Entering `=x_3`, Departing `=S_2`, Key Element `=-3/2`
`R_2`(new)`= R_2`(old) `xx(-2/3)`| `R_2`(old) = | `-1/2` | `0` | `1/2` | `-3/2` | `-1/2` | `1` | | `R_2`(new)`= R_2`(old) `xx(-2/3)` | `1/3` | `0` | `-1/3` | `1` | `1/3` | `-2/3` |
`R_1`(new)`= R_1`(old) + `1/2 R_2`(new)| `R_1`(old) = | `3/2` | `1` | `-1/2` | `-1/2` | `-1/2` | `0` | | `R_2`(new) = | `1/3` | `0` | `-1/3` | `1` | `1/3` | `-2/3` | | `1/2 xx R_2`(new) = | `1/6` | `0` | `-1/6` | `1/2` | `1/6` | `-1/3` | | `R_1`(new)`= R_1`(old) + `1/2 R_2`(new) | `5/3` | `1` | `-2/3` | `0` | `-1/3` | `-1/3` |
| Iteration-3 | | `C_j` | `-2` | `-3` | `0` | `0` | `0` | | `B` | `C_B` | `X_B` | `x_1` | `x_2` | `x_3` | `S_1` | `S_2` | | `x_1` | `-2` | `5/3` | `1` | `-2/3` | `0` | `-1/3` | `-1/3` | | `x_3` | `0` | `1/3` | `0` | `-1/3` | `1` | `1/3` | `-2/3` | | `Z=-10/3` | | `Z_j` | `-2` | `4/3` | `0` | `2/3` | `2/3` | | | | `Z_j-C_j` | `0` | `13/3` | `0` | `2/3` | `2/3` | | | | 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=5/3,x_2=0,x_3=1/3`
Max `Z=-10/3`
`:.` Min `Z=10/3`
This material is intended as a summary. Use your textbook for detail explanation.
Any bug, improvement, feedback then
|
