8. Standard form-2 using Big M method : Example-2
Find solution using Revised Simplex (BigM) method
MIN Z = x1 + x2
subject to
x1 + 2x2 >= 7
4x1 + x2 >= 6
and x1,x2 >= 0
Solution:
Problem is
| Min `Z` | `=` | `` | `` | `x_1` | ` + ` | `` | `x_2` |
| | subject to | | `` | `` | `x_1` | ` + ` | `2` | `x_2` | ≥ | `7` | | `` | `4` | `x_1` | ` + ` | `` | `x_2` | ≥ | `6` |
| | and `x_1,x_2 >= 0; ` |
| `:.` Max `Z` | `=` | ` - ` | `` | `x_1` | ` - ` | `` | `x_2` |
Step-1 :
The problem is converted to canonical form by adding slack, surplus and artificial variables as appropiate
After introducing surplus,artificial variables
| `` | `` | `x_1` | ` + ` | `2` | `x_2` | ` - ` | `` | `S_1` | | | | ` + ` | `` | `A_1` | | | | = | `7` | | `` | `4` | `x_1` | ` + ` | `` | `x_2` | | | | ` - ` | `` | `S_2` | | | | ` + ` | `` | `A_2` | = | `6` |
|
The problem is converted to canonical form by adding slack, surplus and artificial variables as appropiate
After introducing surplus,artificial variables
| `` | `` | `Z'` | ` + ` | `` | `x_1` | ` + ` | `` | `x_2` | | | | | | | ` - ` | `M` | `A_1` | ` - ` | `M` | `A_2` | = | `0` | | | | `` | `` | `x_1` | ` + ` | `2` | `x_2` | ` - ` | `` | `S_1` | | | | ` + ` | `` | `A_1` | | | | = | `7` | | | | `` | `4` | `x_1` | ` + ` | `` | `x_2` | | | | ` - ` | `` | `S_2` | | | | ` + ` | `` | `A_2` | = | `6` |
|
Now represent the new system of constraint equations in the matrix form
`[[1,1,1,0,0,-M,-M],[0,1,2,-1,0,1,0],[0,4,1,0,-1,0,1]][[Z'],[x_1],[x_2],[S_1],[S_2],[A_1],[A_2]]=[[0],[7],[6]]`
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,-M,-M],[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`
`A_1` | `beta_2`
`A_2` | `y_1`
| Min Ratio
`(X_B)/(y_1)` | `x_1` | `x_2` | `S_1` | `S_2` | | `Z'` | `0` | `1` | `-M` | `-M` | | --- | `1` | `1` | `0` | `0` | | `A_1` | `7` | `0` | `1` | `0` | | --- | `1` | `2` | `-1` | `0` | | `A_2` | `6` | `0` | `0` | `1` | | --- | `4` | `1` | `0` | `-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,-M,-M]] [[1,1,0,0],[1,2,-1,0],[4,1,0,-1]]}`
`="Min"{[[-5M+1,-3M+1,M,M]]}`
`=-5M+1` (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,-M,-M],[0,1,0],[0,0,1]] [[1],[1],[4]]=[[-5M+1],[1],[4]]`
and `X_B = [[0],[7],[6]]`
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"{(7)/(1),(6)/(4)}`
`="Min"{7,3/2}`
`=3/2 ("correspnds to " x_(B2)/y_(21))`
Thus, vector `A_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`
`A_1` | `beta_2`
`A_2` | `y_1`
| Min Ratio
`(X_B)/(y_1)` | `x_1` | `x_2` | `S_1` | `S_2` | | `Z'` | `0` | `1` | `-M` | `-M` | `-5M+1` | --- | `1` | `1` | `0` | `0` | | `A_1` | `7` | `0` | `1` | `0` | `1` | `7` | `1` | `2` | `-1` | `0` | | `A_2` | `6` | `0` | `0` | `1` | `4` | `3/2` | `4` | `1` | `0` | `-1` |
The table solution is now updated by replacing variable `A_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` | `-M` | `-M` | `-5M+1` | | `R_2` | `7` | `1` | `0` | `1` | | `R_3` | `6` | `0` | `1` | `4` |
`R_3`(new)`= R_3`(old)` -: 4`| `R_3`(old) = | `6` | | `0` | `1` | | `R_3`(new)`= R_3`(old)` -: 4` | `3/2` | | `0` | `1/4` |
`R_1`(new)`= R_1`(old) + `(5M-1) R_3`(new)| `R_1`(old) = | `0` | | `-M` | `-M` | | `R_3`(new) = | `3/2` | | `0` | `1/4` | | `5M-1 xx R_3`(new) = | `(15M-3)/2` | | `0` | `(5M-1)/4` | | `R_1`(new)`= R_1`(old) + `(5M-1) R_3`(new) | `(15M-3)/2` | | `-M` | `(M-1)/4` |
`R_2`(new)`= R_2`(old) - `R_3`(new)| `R_2`(old) = | `7` | | `1` | `0` | | `R_3`(new) = | `3/2` | | `0` | `1/4` | | `R_2`(new)`= R_2`(old) - `R_3`(new) | `11/2` | | `1` | `-1/4` |
The improved solution is
| | Basis Inverse `B_1^(-1)` | | | Additional table | | `B` | `X_B` | `beta_0`
`Z'` | `beta_1`
`A_1` | `beta_2`
`x_1` | `y_1`
| Min Ratio
`(X_B)/(y_1)` | `A_2` | `x_2` | `S_1` | `S_2` | | `Z'` | `(15M-3)/2` | `1` | `-M` | `(M-1)/4` | | --- | `M` | `1` | `0` | `0` | | `A_1` | `11/2` | `0` | `1` | `-1/4` | | --- | `0` | `2` | `-1` | `0` | | `x_1` | `3/2` | `0` | `0` | `1/4` | | --- | `1` | `1` | `0` | `-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,-M,(M-1)/4]] [[M,1,0,0],[0,2,-1,0],[1,1,0,-1]]}`
`="Min"{[[(5M-1)/4,(-7M+3)/4,M,(-M+1)/4]]}`
`=(-7M+3)/4` (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,-M,(M-1)/4],[0,1,-1/4],[0,0,1/4]] [[1],[2],[1]]=[[(-7M+3)/4],[7/4],[1/4]]`
and `X_B = [[(15M-3)/2],[11/2],[3/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"{(11/2)/(7/4),(3/2)/(1/4)}`
`="Min"{22/7,6}`
`=22/7 ("correspnds to " x_(B1)/y_(12))`
Thus, vector `A_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`
`A_1` | `beta_2`
`x_1` | `y_2`
| Min Ratio
`(X_B)/(y_2)` | `A_2` | `x_2` | `S_1` | `S_2` | | `Z'` | `(15M-3)/2` | `1` | `-M` | `(M-1)/4` | `(-7M+3)/4` | --- | `M` | `1` | `0` | `0` | | `A_1` | `11/2` | `0` | `1` | `-1/4` | `7/4` | `22/7` | `0` | `2` | `-1` | `0` | | `x_1` | `3/2` | `0` | `0` | `1/4` | `1/4` | `6` | `1` | `1` | `0` | `-1` |
The table solution is now updated by replacing variable `A_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` | `(15M-3)/2` | `-M` | `(M-1)/4` | `(-7M+3)/4` | | `R_2` | `11/2` | `1` | `-1/4` | `7/4` | | `R_3` | `3/2` | `0` | `1/4` | `1/4` |
`R_2`(new)`= R_2`(old) `xx4/7`| `R_2`(old) = | `11/2` | | `1` | `-1/4` | | `R_2`(new)`= R_2`(old) `xx4/7` | `22/7` | | `4/7` | `-1/7` |
`R_1`(new)`= R_1`(old) + `((7M-3)/4) R_2`(new)| `R_1`(old) = | `(15M-3)/2` | | `-M` | `(M-1)/4` | | `R_2`(new) = | `22/7` | | `4/7` | `-1/7` | | `(7M-3)/4 xx R_2`(new) = | `(11M)/(2)-33/14` | | `M-3/7` | `-(M)/(4)+3/28` | | `R_1`(new)`= R_1`(old) + `((7M-3)/4) R_2`(new) | `13M-27/7` | | `-3/7` | `-1/7` |
`R_3`(new)`= R_3`(old) - `1/4 R_2`(new)| `R_3`(old) = | `3/2` | | `0` | `1/4` | | `R_2`(new) = | `22/7` | | `4/7` | `-1/7` | | `1/4 xx R_2`(new) = | `11/14` | | `1/7` | `-1/28` | | `R_3`(new)`= R_3`(old) - `1/4 R_2`(new) | `5/7` | | `-1/7` | `2/7` |
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)` | `A_2` | `A_1` | `S_1` | `S_2` | | `Z'` | `13M-27/7` | `1` | `-3/7` | `-1/7` | | --- | `M` | `M` | `0` | `0` | | `x_2` | `22/7` | `0` | `4/7` | `-1/7` | | --- | `0` | `1` | `-1` | `0` | | `x_1` | `5/7` | `0` | `-1/7` | `2/7` | | --- | `1` | `0` | `0` | `-1` |
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,-3/7,-1/7]] [[M,M,0,0],[0,1,-1,0],[1,0,0,-1]]}`
`="Min"{[[M-1/7,M-3/7,3/7,1/7]]}`
Since all `Z_j-C_j >= 0`
Hence, optimal solution is arrived with value of variables as :
`x_1=5/7,x_2=22/7`
Max `Z=-27/7`
`:.` Min `Z=27/7`
This material is intended as a summary. Use your textbook for detail explanation.
Any bug, improvement, feedback then
|
