1. Algorithm & Example-1
Algorithm
|
Two-Phase Method Steps (Rule)
|
|
Step-1:
|
Phase-1
a. Form a new objective function by assigning zero to every original variable (including slack and surplus variables) and -1 to each of the artificial variables.
eg. Max Z = - A1 - A2
b. Using simplex method, try to eliminate the artificial varibles from the basis.
c. The solution at the end of Phase-1 is the initial basic feasible solution for Phase-2.
|
|
Step-2:
|
Phase-2
a. The original objective function is used and coefficient of artificial variable is 0 (so artificial variable is removed from the calculation process).
b. Then simplex algorithm is used to find optimal solution.
|
Example
Find solution using Two-Phase method
MIN Z = x1 + x2
subject to
2x1 + x2 >= 4
x1 + 7x2 >= 7
and x1,x2 >= 0
Solution:
Problem is
| Min `Z` | `=` | `` | `` | `x_1` | ` + ` | `` | `x_2` |
| | subject to | | `` | `2` | `x_1` | ` + ` | `` | `x_2` | ≥ | `4` | | `` | `` | `x_1` | ` + ` | `7` | `x_2` | ≥ | `7` |
| | and `x_1,x_2 >= 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 subtract surplus variable `S_1` and add artificial variable `A_1`
2. As the constraint-2 is of type '`>=`' we should subtract surplus variable `S_2` and add artificial variable `A_2`
After introducing surplus,artificial variables
| Min `Z` | `=` | | | | | | | | | | | | | `` | `` | `A_1` | ` + ` | `` | `A_2` |
| | subject to | | `` | `2` | `x_1` | ` + ` | `` | `x_2` | ` - ` | `` | `S_1` | | | | ` + ` | `` | `A_1` | | | | = | `4` | | `` | `` | `x_1` | ` + ` | `7` | `x_2` | | | | ` - ` | `` | `S_2` | | | | ` + ` | `` | `A_2` | = | `7` |
| | and `x_1,x_2,S_1,S_2,A_1,A_2 >= 0` |
| Iteration-1 | | `C_j` | `0` | `0` | `0` | `0` | `1` | `1` | | | `B` | `C_B` | `X_B` | `x_1` | `x_2` Entering variable
| `S_1` | `S_2` | `A_1` | `A_2` | MinRatio
`(X_B)/(x_2)` | | `A_1` | `1` | `4` | `2` | `1` | `-1` | `0` | `1` | `0` | `(4)/(1)=4` | | `A_2` Leaving variable
| `1` | `7` | `1` | `(7)` (pivot element)
| `0` | `-1` | `0` | `1` | `(7)/(7)=1``->` | `Z=0` `0=`
`Z_j=sum C_B X_B`
| | `Z_j` `Z_j=sum C_B x_j`
| `3` `3=1xx2+1xx1`
`Z_j=sum C_B x_1`
| `8` `8=1xx1+1xx7`
`Z_j=sum C_B x_2`
| `-1` `-1=1xx(-1)+1xx0`
`Z_j=sum C_B S_1`
| `-1` `-1=1xx0+1xx(-1)`
`Z_j=sum C_B S_2`
| `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` | `-3` `-3=0-3`
| `-8` `-8=0-8`
`uarr` | `1` `1=0-(-1)`
| `1` `1=0-(-1)`
| `0` `0=1-1`
| `0` `0=1-1`
| |
Negative minimum `C_j-Z_j` is `-8` and its column index is `2`. So, the entering variable is `x_2`.
Minimum ratio is `1` and its row index is `2`. So, the leaving basis variable is `A_2`.
`:.` The pivot element is `7`.
Entering `=x_2`, Departing `=A_2`, Key Element `=7`
`R_2`(new)`= R_2`(old)`-: 7`
`R_1`(new)`= R_1`(old)`- R_2`(new)
| Iteration-2 | | `C_j` | `0` | `0` | `0` | `0` | `1` | | | `B` | `C_B` | `X_B` | `x_1` Entering variable
| `x_2` | `S_1` | `S_2` | `A_1` | MinRatio
`(X_B)/(x_1)` | | `A_1` Leaving variable
| `1` | `3` `3=4-1`
`R_1`(new)`= R_1`(old)`- R_2`(new)
| `(13/7)` `13/7=2-1/7` (pivot element)
`R_1`(new)`= R_1`(old)`- R_2`(new)
| `0` `0=1-1`
`R_1`(new)`= R_1`(old)`- R_2`(new)
| `-1` `-1=(-1)-0`
`R_1`(new)`= R_1`(old)`- R_2`(new)
| `1/7` `1/7=0-(-1/7)`
`R_1`(new)`= R_1`(old)`- R_2`(new)
| `1` `1=1-0`
`R_1`(new)`= R_1`(old)`- R_2`(new)
| `(3)/(13/7)=1.62``->` | | `x_2` | `0` | `1` `1=7-:7`
`R_2`(new)`= R_2`(old)`-: 7`
| `1/7` `1/7=1-:7`
`R_2`(new)`= R_2`(old)`-: 7`
| `1` `1=7-:7`
`R_2`(new)`= R_2`(old)`-: 7`
| `0` `0=0-:7`
`R_2`(new)`= R_2`(old)`-: 7`
| `-1/7` `-1/7=(-1)-:7`
`R_2`(new)`= R_2`(old)`-: 7`
| `0` `0=0-:7`
`R_2`(new)`= R_2`(old)`-: 7`
| `(1)/(1/7)=7` | `Z=0` `0=0xx1`
`Z_j=sum C_B X_B`
| | `Z_j` `Z_j=sum C_B x_j`
| `13/7` `13/7=1xx13/7+0xx1/7`
`Z_j=sum C_B x_1`
| `0` `0=1xx0+0xx1`
`Z_j=sum C_B x_2`
| `-1` `-1=1xx(-1)+0xx0`
`Z_j=sum C_B S_1`
| `1/7` `1/7=1xx1/7+0xx(-1/7)`
`Z_j=sum C_B S_2`
| `1` `1=1xx1+0xx0`
`Z_j=sum C_B A_1`
| | | | | `C_j-Z_j` | `-13/7` `-13/7=0-13/7`
`uarr` | `0` `0=0-0`
| `1` `1=0-(-1)`
| `-1/7` `-1/7=0-1/7`
| `0` `0=1-1`
| |
Negative minimum `C_j-Z_j` is `-13/7` and its column index is `1`. So, the entering variable is `x_1`.
Minimum ratio is `1.62` and its row index is `1`. So, the leaving basis variable is `A_1`.
`:.` The pivot element is `13/7`.
Entering `=x_1`, Departing `=A_1`, Key Element `=13/7`
`R_1`(new)`= R_1`(old)`xx7/13`
`R_2`(new)`= R_2`(old)`- 1/7 R_1`(new)
| Iteration-3 | | `C_j` | `0` | `0` | `0` | `0` | | | `B` | `C_B` | `X_B` | `x_1` | `x_2` | `S_1` | `S_2` | MinRatio | | `x_1` | `0` | `21/13` `21/13=3xx7/13`
`R_1`(new)`= R_1`(old)`xx7/13`
| `1` `1=13/7xx7/13`
`R_1`(new)`= R_1`(old)`xx7/13`
| `0` `0=0xx7/13`
`R_1`(new)`= R_1`(old)`xx7/13`
| `-7/13` `-7/13=(-1)xx7/13`
`R_1`(new)`= R_1`(old)`xx7/13`
| `1/13` `1/13=1/7xx7/13`
`R_1`(new)`= R_1`(old)`xx7/13`
| | | `x_2` | `0` | `10/13` `10/13=1-1/7xx21/13`
`R_2`(new)`= R_2`(old)`- 1/7 R_1`(new)
| `0` `0=1/7-1/7xx1`
`R_2`(new)`= R_2`(old)`- 1/7 R_1`(new)
| `1` `1=1-1/7xx0`
`R_2`(new)`= R_2`(old)`- 1/7 R_1`(new)
| `1/13` `1/13=0-1/7xx(-7/13)`
`R_2`(new)`= R_2`(old)`- 1/7 R_1`(new)
| `-2/13` `-2/13=(-1/7)-1/7xx1/13`
`R_2`(new)`= R_2`(old)`- 1/7 R_1`(new)
| | `Z=0` `0=0xx21/13+0xx10/13`
`Z_j=sum C_B X_B`
| | `Z_j` `Z_j=sum C_B x_j`
| `0` `0=0xx1+0xx0`
`Z_j=sum C_B x_1`
| `0` `0=0xx0+0xx1`
`Z_j=sum C_B x_2`
| `0` `0=0xx(-7/13)+0xx1/13`
`Z_j=sum C_B S_1`
| `0` `0=0xx1/13+0xx(-2/13)`
`Z_j=sum C_B S_2`
| | | | | `C_j-Z_j` | `0` `0=0-0`
| `0` `0=0-0`
| `0` `0=0-0`
| `0` `0=0-0`
| |
Since all `C_j-Z_j >= 0`
Hence, optimal solution is arrived with value of variables as :
`x_1=21/13,x_2=10/13`
Min `Z = 0`
-->Phase-2<--
we eliminate the artificial variables and change the objective function for the original,
| Iteration-1 | | `C_j` | `1` | `1` | `0` | `0` | | | `B` | `C_B` | `X_B` | `x_1` | `x_2` | `S_1` | `S_2` | MinRatio | | `x_1` | `1` | `21/13` | `1` | `0` | `-7/13` | `1/13` | | | `x_2` | `1` | `10/13` | `0` | `1` | `1/13` | `-2/13` | | `Z=31/13` `31/13=1xx21/13+1xx10/13`
`Z_j=sum C_B X_B`
| | `Z_j` `Z_j=sum C_B x_j`
| `1` `1=1xx1+1xx0`
`Z_j=sum C_B x_1`
| `1` `1=1xx0+1xx1`
`Z_j=sum C_B x_2`
| `-6/13` `-6/13=1xx(-7/13)+1xx1/13`
`Z_j=sum C_B S_1`
| `-1/13` `-1/13=1xx1/13+1xx(-2/13)`
`Z_j=sum C_B S_2`
| | | | | `C_j-Z_j` | `0` `0=1-1`
| `0` `0=1-1`
| `6/13` `6/13=0-(-6/13)`
| `1/13` `1/13=0-(-1/13)`
| |
Since all `C_j-Z_j >= 0`
Hence, optimal solution is arrived with value of variables as :
`x_1=21/13,x_2=10/13`
Min `Z = 31/13`
This material is intended as a summary. Use your textbook for detail explanation.
Any bug, improvement, feedback then
|
