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