1. Standard form-1 : Example-1
Find solution using Revised Simplex (BigM) method
MAX Z = 2x1 + x2
subject to
3x1 + 4x2 <= 6
6x1 + x2 <= 3
and x1,x2 >= 0
Solution:
Problem is
| Max `Z` | `=` | `` | `2` | `x_1` | ` + ` | `` | `x_2` |
| | subject to | | `` | `3` | `x_1` | ` + ` | `4` | `x_2` | ≤ | `6` | | `` | `6` | `x_1` | ` + ` | `` | `x_2` | ≤ | `3` |
| | and `x_1,x_2 >= 0; ` |
Step-1 :
The problem is converted to canonical form by adding slack, surplus and artificial variables as appropiate
After introducing slack variables
| `` | `3` | `x_1` | ` + ` | `4` | `x_2` | ` + ` | `` | `S_1` | | | | = | `6` | | `` | `6` | `x_1` | ` + ` | `` | `x_2` | | | | ` + ` | `` | `S_2` | = | `3` |
|
The problem is converted to canonical form by adding slack, surplus and artificial variables as appropiate
After introducing slack variables
| `` | `` | `Z'` | ` - ` | `2` | `x_1` | ` - ` | `` | `x_2` | | | | | | | = | `0` | | | | `` | `3` | `x_1` | ` + ` | `4` | `x_2` | ` + ` | `` | `S_1` | | | | = | `6` | | | | `` | `6` | `x_1` | ` + ` | `` | `x_2` | | | | ` + ` | `` | `S_2` | = | `3` |
|
Now represent the new system of constraint equations in the matrix form
`[[1,-2,-1,0,0],[0,3,4,1,0],[0,6,1,0,1]][[Z'],[x_1],[x_2],[S_1],[S_2]]=[[0],[6],[3]]`
or
`[[1,-c],[0,A]][[Z],[x]]=[[0,b]]; x>=0`
where `e=beta_0,a_3=beta_1,a_4=beta_2`
Step-2 : The basis matrix `B_1` of order `(2+1)=3` can be expressed as
`B_1=[beta_0,beta_1,beta_2]=[[1,0,0],[0,1,0],[0,0,1]]`
Then, `B_1^(-1)=[[1,C_B B^(-1)],[0,B^(-1)]]=1; B=[[1,0],[0,1]]=[beta_1,beta_2]; C_B=[0,0]`
| | Basis Inverse `B_1^(-1)` | | | Additional table | | `B` | `X_B` | `beta_0`
`Z'` | `beta_1`
`S_1` | `beta_2`
`S_2` | `y_1`
| Min Ratio
`(X_B)/(y_1)` | `x_1` | `x_2` | | `Z'` | `0` | `1` | `0` | `0` | | --- | `-2` | `-1` | | `S_1` | `6` | `0` | `1` | `0` | | --- | `3` | `4` | | `S_2` | `3` | `0` | `0` | `1` | | --- | `6` | `1` |
Iteration=1 : Repeat steps 3 to 5 to get new solution
Step-3: To select the vector corresponding to a non-basic variable to enter into the basis, we compute
`z_k-c_k="Min" {(z_j-c_j)<0;}`
`="Min"{(1^(st)" row of " B_1^(-1)) ("Columns " a_j " not in basis")}`
`="Min"{[[1,0,0]] [[-2,-1],[3,4],[6,1]]}`
`="Min"{[[-2,-1]]}`
`=-2` (correspnds to `z_1-c_1`)
Thus, vector `x_1` is selected to enter into the basis, for `k=1`
Step-4: To select a basic variable to leave the basis, we compute `y_k` for k=1, as follows
`y_1= B_1^(-1) a_1=[[1,0,0],[0,1,0],[0,0,1]] [[-2],[3],[6]]=[[-2],[3],[6]]`
and `X_B = [[0],[6],[3]]`
Now, calculate the minimum ratio to select the basic variable to leave the basis
`x_(Br)/y_(rk)= "Min" {x_(Bi)/y_(ik), y_(ik)>0}`
`="Min"{(6)/(3),(3)/(6)}`
`="Min"{2,1/2}`
`=1/2 ("correspnds to " x_(B2)/y_(21))`
Thus, vector `S_2` is selected to leave the basis, for `r=2`
The table with new entries in column `y_1` and the minimum ratio
| | Basis Inverse `B_1^(-1)` | | | Additional table | | `B` | `X_B` | `beta_0`
`Z'` | `beta_1`
`S_1` | `beta_2`
`S_2` | `y_1`
| Min Ratio
`(X_B)/(y_1)` | `x_1` | `x_2` | | `Z'` | `0` | `1` | `0` | `0` | `-2` | --- | `-2` | `-1` | | `S_1` | `6` | `0` | `1` | `0` | `3` | `2` | `3` | `4` | | `S_2` | `3` | `0` | `0` | `1` | `6` | `1/2` | `6` | `1` |
The table solution is now updated by replacing variable `S_2` with the variable `x_1` into the basis.
For this we apply the following row operations in the same way as in the simplex method
| `X_B` | `beta_1` | `beta_2` | `y_1` | | `R_1` | `0` | `0` | `0` | `-2` | | `R_2` | `6` | `1` | `0` | `3` | | `R_3` | `3` | `0` | `1` | `6` |
`R_3`(new)`= R_3`(old)` -: 6`| `R_3`(old) = | `3` | | `0` | `1` | | `R_3`(new)`= R_3`(old)` -: 6` | `1/2` | | `0` | `1/6` |
`R_1`(new)`= R_1`(old) + `2 R_3`(new)| `R_1`(old) = | `0` | | `0` | `0` | | `R_3`(new) = | `1/2` | | `0` | `1/6` | | `2 xx R_3`(new) = | `1` | | `0` | `1/3` | | `R_1`(new)`= R_1`(old) + `2 R_3`(new) | `1` | | `0` | `1/3` |
`R_2`(new)`= R_2`(old) - `3 R_3`(new)| `R_2`(old) = | `6` | | `1` | `0` | | `R_3`(new) = | `1/2` | | `0` | `1/6` | | `3 xx R_3`(new) = | `3/2` | | `0` | `1/2` | | `R_2`(new)`= R_2`(old) - `3 R_3`(new) | `9/2` | | `1` | `-1/2` |
The improved solution is
| | Basis Inverse `B_1^(-1)` | | | Additional table | | `B` | `X_B` | `beta_0`
`Z'` | `beta_1`
`S_1` | `beta_2`
`x_1` | `y_1`
| Min Ratio
`(X_B)/(y_1)` | `S_2` | `x_2` | | `Z'` | `1` | `1` | `0` | `1/3` | | --- | `0` | `-1` | | `S_1` | `9/2` | `0` | `1` | `-1/2` | | --- | `0` | `4` | | `x_1` | `1/2` | `0` | `0` | `1/6` | | --- | `1` | `1` |
Iteration=2 : Repeat steps 3 to 5 to get new solution
Step-3: To select the vector corresponding to a non-basic variable to enter into the basis, we compute
`z_k-c_k="Min" {(z_j-c_j)<0;}`
`="Min"{(1^(st)" row of " B_1^(-1)) ("Columns " a_j " not in basis")}`
`="Min"{[[1,0,1/3]] [[0,-1],[0,4],[1,1]]}`
`="Min"{[[1/3,-2/3]]}`
`=-2/3` (correspnds to `z_2-c_2`)
Thus, vector `x_2` is selected to enter into the basis, for `k=2`
Step-4: To select a basic variable to leave the basis, we compute `y_k` for k=2, as follows
`y_2= B_1^(-1) a_2=[[1,0,1/3],[0,1,-1/2],[0,0,1/6]] [[-1],[4],[1]]=[[-2/3],[7/2],[1/6]]`
and `X_B = [[1],[9/2],[1/2]]`
Now, calculate the minimum ratio to select the basic variable to leave the basis
`x_(Br)/y_(rk)= "Min" {x_(Bi)/y_(ik), y_(ik)>0}`
`="Min"{(9/2)/(7/2),(1/2)/(1/6)}`
`="Min"{9/7,3}`
`=9/7 ("correspnds to " x_(B1)/y_(12))`
Thus, vector `S_1` is selected to leave the basis, for `r=1`
The table with new entries in column `y_2` and the minimum ratio
| | Basis Inverse `B_1^(-1)` | | | Additional table | | `B` | `X_B` | `beta_0`
`Z'` | `beta_1`
`S_1` | `beta_2`
`x_1` | `y_2`
| Min Ratio
`(X_B)/(y_2)` | `S_2` | `x_2` | | `Z'` | `1` | `1` | `0` | `1/3` | `-2/3` | --- | `0` | `-1` | | `S_1` | `9/2` | `0` | `1` | `-1/2` | `7/2` | `9/7` | `0` | `4` | | `x_1` | `1/2` | `0` | `0` | `1/6` | `1/6` | `3` | `1` | `1` |
The table solution is now updated by replacing variable `S_1` with the variable `x_2` into the basis.
For this we apply the following row operations in the same way as in the simplex method
| `X_B` | `beta_1` | `beta_2` | `y_2` | | `R_1` | `1` | `0` | `1/3` | `-2/3` | | `R_2` | `9/2` | `1` | `-1/2` | `7/2` | | `R_3` | `1/2` | `0` | `1/6` | `1/6` |
`R_2`(new)`= R_2`(old) `xx2/7`| `R_2`(old) = | `9/2` | | `1` | `-1/2` | | `R_2`(new)`= R_2`(old) `xx2/7` | `9/7` | | `2/7` | `-1/7` |
`R_1`(new)`= R_1`(old) + `2/3 R_2`(new)| `R_1`(old) = | `1` | | `0` | `1/3` | | `R_2`(new) = | `9/7` | | `2/7` | `-1/7` | | `2/3 xx R_2`(new) = | `6/7` | | `4/21` | `-2/21` | | `R_1`(new)`= R_1`(old) + `2/3 R_2`(new) | `13/7` | | `4/21` | `5/21` |
`R_3`(new)`= R_3`(old) - `1/6 R_2`(new)| `R_3`(old) = | `1/2` | | `0` | `1/6` | | `R_2`(new) = | `9/7` | | `2/7` | `-1/7` | | `1/6 xx R_2`(new) = | `3/14` | | `1/21` | `-1/42` | | `R_3`(new)`= R_3`(old) - `1/6 R_2`(new) | `2/7` | | `-1/21` | `4/21` |
The improved solution is
| | Basis Inverse `B_1^(-1)` | | | Additional table | | `B` | `X_B` | `beta_0`
`Z'` | `beta_1`
`x_2` | `beta_2`
`x_1` | `y_2`
| Min Ratio
`(X_B)/(y_2)` | `S_2` | `S_1` | | `Z'` | `13/7` | `1` | `4/21` | `5/21` | | --- | `0` | `0` | | `x_2` | `9/7` | `0` | `2/7` | `-1/7` | | --- | `0` | `1` | | `x_1` | `2/7` | `0` | `-1/21` | `4/21` | | --- | `1` | `0` |
Iteration=3 : Repeat steps 3 to 5 to get new solution
Step-3: To select the vector corresponding to a non-basic variable to enter into the basis, we compute
`z_k-c_k="Min" {(z_j-c_j)<0;}`
`="Min"{(1^(st)" row of " B_1^(-1)) ("Columns " a_j " not in basis")}`
`="Min"{[[1,4/21,5/21]] [[0,0],[0,1],[1,0]]}`
`="Min"{[[5/21,4/21]]}`
Since all `Z_j-C_j >= 0`
Hence, optimal solution is arrived with value of variables as :
`x_1=2/7,x_2=9/7`
Max `Z=13/7`
This material is intended as a summary. Use your textbook for detail explanation.
Any bug, improvement, feedback then
|
