4. Infeasible solution example
Infeasible solution
If there is no any solution that satifies all the constraints, then it is called Infeasible solution
In the final simplex table when all `c_j - z_j` imply optimal solution but at least one artificial variable present in the basis with positive value. Then the problem has no feasible solution.
Example
Find solution using Two-Phase method
MIN Z = X1 - 2X2 - 3X3
subject to
-2X1 + X2 + 3X3 = 2
2X1 + 3X2 + 4X3 = 1
and X1,X2,X3 >= 0
Solution:
Problem is
| Min `Z` | `=` | `` | `` | `X_1` | ` - ` | `2` | `X_2` | ` - ` | `3` | `X_3` |
| | subject to | | ` - ` | `2` | `X_1` | ` + ` | `` | `X_2` | ` + ` | `3` | `X_3` | = | `2` | | `` | `2` | `X_1` | ` + ` | `3` | `X_2` | ` + ` | `4` | `X_3` | = | `1` |
| | and `X_1,X_2,X_3 >= 0; ` |
-->Phase-1<--
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 artificial variable `A_1`
2. As the constraint-2 is of type '`=`' we should add artificial variable `A_2`
After introducing artificial variables
| Min `Z` | `=` | | | | | | | | | | `` | `` | `A_1` | ` + ` | `` | `A_2` |
| | subject to | | ` - ` | `2` | `X_1` | ` + ` | `` | `X_2` | ` + ` | `3` | `X_3` | ` + ` | `` | `A_1` | | | | = | `2` | | `` | `2` | `X_1` | ` + ` | `3` | `X_2` | ` + ` | `4` | `X_3` | | | | ` + ` | `` | `A_2` | = | `1` |
| | and `X_1,X_2,X_3,A_1,A_2 >= 0` |
| Iteration-1 | | `C_j` | `0` | `0` | `0` | `1` | `1` | | | `B` | `C_B` | `X_B` | `X_1` | `X_2` | `X_3` Entering variable | `A_1` | `A_2` | MinRatio
`(X_B)/(X_3)` | | `A_1` | `1` | `2` | `-2` | `1` | `3` | `1` | `0` | `(2)/(3)=0.6667` | | `A_2` Leaving variable | `1` | `1` | `2` | `3` | `(4)` (pivot element) | `0` | `1` | `(1)/(4)=0.25``->` | `Z=0` `0=`
`Z_j=sum C_B X_B` | | `Z_j` `Z_j=sum C_B x_j` | `0` `0=1xx(-2)+1xx2`
`Z_j=sum C_B X_1` | `4` `4=1xx1+1xx3`
`Z_j=sum C_B X_2` | `7` `7=1xx3+1xx4`
`Z_j=sum C_B X_3` | `1` `1=1xx1+1xx0`
`Z_j=sum C_B A_1` | `1` `1=1xx0+1xx1`
`Z_j=sum C_B A_2` | | | | | `C_j-Z_j` | `0` `0=0-0` | `-4` `-4=0-4` | `-7` `-7=0-7``uarr` | `0` `0=1-1` | `0` `0=1-1` | |
Negative minimum `C_j-Z_j` is `-7` and its column index is `3`. So, the entering variable is `X_3`.
Minimum ratio is `0.25` and its row index is `2`. So, the leaving basis variable is `A_2`.
`:.` The pivot element is `4`.
Entering `=X_3`, Departing `=A_2`, Key Element `=4`
`R_2`(new)`= R_2`(old)`-: 4`
`R_1`(new)`= R_1`(old)`- 3 R_2`(new)
| Iteration-2 | | `C_j` | `0` | `0` | `0` | `1` | | | `B` | `C_B` | `X_B` | `X_1` | `X_2` | `X_3` | `A_1` | MinRatio | | `A_1` | `1` | `5/4` `5/4=2-3xx1/4`
`R_1`(new)`= R_1`(old)`- 3 R_2`(new) | `-7/2` `-7/2=(-2)-3xx1/2`
`R_1`(new)`= R_1`(old)`- 3 R_2`(new) | `-5/4` `-5/4=1-3xx3/4`
`R_1`(new)`= R_1`(old)`- 3 R_2`(new) | `0` `0=3-3xx1`
`R_1`(new)`= R_1`(old)`- 3 R_2`(new) | `1` `1=1-3xx0`
`R_1`(new)`= R_1`(old)`- 3 R_2`(new) | | | `X_3` | `0` | `1/4` `1/4=1-:4`
`R_2`(new)`= R_2`(old)`-: 4` | `1/2` `1/2=2-:4`
`R_2`(new)`= R_2`(old)`-: 4` | `3/4` `3/4=3-:4`
`R_2`(new)`= R_2`(old)`-: 4` | `1` `1=4-:4`
`R_2`(new)`= R_2`(old)`-: 4` | `0` `0=0-:4`
`R_2`(new)`= R_2`(old)`-: 4` | | `Z=0` `0=0xx1/4`
`Z_j=sum C_B X_B` | | `Z_j` `Z_j=sum C_B x_j` | `-7/2` `-7/2=1xx(-7/2)+0xx1/2`
`Z_j=sum C_B X_1` | `-5/4` `-5/4=1xx(-5/4)+0xx3/4`
`Z_j=sum C_B X_2` | `0` `0=1xx0+0xx1`
`Z_j=sum C_B X_3` | `1` `1=1xx1+0xx0`
`Z_j=sum C_B A_1` | | | | | `C_j-Z_j` | `7/2` `7/2=0-(-7/2)` | `5/4` `5/4=0-(-5/4)` | `0` `0=0-0` | `0` `0=1-1` | |
Since all `C_j-Z_j >= 0`
Hence, optimal solution is arrived with value of variables as :
`X_1=0,X_2=0,X_3=1/4`
Min `Z = 0`
But this solution is not feasible
because the final solution violates the `1^(st)` constraint ` - ` `2` `X_1` ` + ` `` `X_2` ` + ` `3` `X_3` = `2`.
and the artificial variable `A_1` appears in the basis with positive value `5/4`
This material is intended as a summary. Use your textbook for detail explanation.
Any bug, improvement, feedback then
|
