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` |
| `Z` | | | | | | | | | | | | | ` - ` | `` | `A_1` | ` - ` | `` | `A_2` | = | `0` |
|
| `` | `2` | `x_1` | ` + ` | `` | `x_2` | ` - ` | `` | `S_1` | | | | ` + ` | `` | `A_1` | | | | = | `4` | | `` | `` | `x_1` | ` + ` | `7` | `x_2` | | | | ` - ` | `` | `S_2` | | | | ` + ` | `` | `A_2` | = | `7` |
|
Simplex tableau is
Tableau-0
| `"Basis"` | `x_1` | `x_2` | `S_1` | `S_2` | `A_1` | `A_2` | `RHS` | |
| `R_1` `Z` | `0` | `0` | `0` | `0` | `-1` | `-1` | `0` | |
| `R_2` `A_1` | `2` | `1` | `-1` | `0` | `1` | `0` | `4` | |
| `R_3` `A_2` | `1` | `7` | `0` | `-1` | `0` | `1` | `7` | |
Make the Z-row consistent with the rest of the table (set coefficient of basis variables to 0 in Z-row)
`R_1`(new)`= R_1`(old) + `R_2`(old)
| `x_1` | `x_2` | `S_1` | `S_2` | `A_1` | `A_2` | `RHS` |
| `R_1`(old) = | `0` | `0` | `0` | `0` | `-1` | `-1` | `0` |
| `R_2`(old) = | `2` | `1` | `-1` | `0` | `1` | `0` | `4` |
| `R_1`(new)`= R_1`(old) + `R_2`(old) | `2` | `1` | `-1` | `0` | `0` | `-1` | `4` |
`R_1`(new)`= R_1`(old) + `R_3`(old)
| `x_1` | `x_2` | `S_1` | `S_2` | `A_1` | `A_2` | `RHS` |
| `R_1`(old) = | `2` | `1` | `-1` | `0` | `0` | `-1` | `4` |
| `R_3`(old) = | `1` | `7` | `0` | `-1` | `0` | `1` | `7` |
| `R_1`(new)`= R_1`(old) + `R_3`(old) | `3` | `8` | `-1` | `-1` | `0` | `0` | `11` |
Tableau-1
| `"Basis"` | `x_1` | `x_2``darr` | `S_1` | `S_2` | `A_1` | `A_2` | `RHS` | `"Ratio"=(RHS)/(x_2)` |
| `R_1` `Z` | `3` | `8` | `-1` | `-1` | `0` | `0` | `11` | |
| `R_2` `A_1` | `2` | `1` | `-1` | `0` | `1` | `0` | `4` | `(4)/(1)=4` |
| `R_3` `A_2` | `1` | `(7)` | `0` | `-1` | `0` | `1` | `7` | `(7)/(7)=1``->` |
Most Positive `Z` is `8`. So,
the entering variable is `x_2`.
Minimum ratio is `1`. So,
the leaving basis variable is `A_2`.
`:.`
The pivot element is `7`.
Entering `=x_2`, Departing `=A_2`, Key Element `=7`
`R_3`(new)`= R_3`(old) `-: 7`
| `x_1` | `x_2` | `S_1` | `S_2` | `A_1` | `A_2` | `RHS` |
| `R_3`(old) = | `1` | `7` | `0` | `-1` | `0` | `1` | `7` |
| `R_3`(new)`= R_3`(old) `-: 7` | `0.1429` | `1` | `0` | `-0.1429` | `0` | `0.1429` | `1` |
`R_2`(new)`= R_2`(old) - `R_3`(new)
| `x_1` | `x_2` | `S_1` | `S_2` | `A_1` | `A_2` | `RHS` |
| `R_2`(old) = | `2` | `1` | `-1` | `0` | `1` | `0` | `4` |
| `R_3`(new) = | `0.1429` | `1` | `0` | `-0.1429` | `0` | `0.1429` | `1` |
| `R_2`(new)`= R_2`(old) - `R_3`(new) | `1.8571` | `0` | `-1` | `0.1429` | `1` | `-0.1429` | `3` |
`R_1`(new)`= R_1`(old) - `8 R_3`(new)
| `x_1` | `x_2` | `S_1` | `S_2` | `A_1` | `A_2` | `RHS` |
| `R_1`(old) = | `3` | `8` | `-1` | `-1` | `0` | `0` | `11` |
| `R_3`(new) = | `0.1429` | `1` | `0` | `-0.1429` | `0` | `0.1429` | `1` |
| `8 xx R_3`(new) = | `1.1429` | `8` | `0` | `-1.1429` | `0` | `1.1429` | `8` |
| `R_1`(new)`= R_1`(old) - `8 R_3`(new) | `1.8571` | `0` | `-1` | `0.1429` | `0` | `-1.1429` | `3` |
Tableau-2
| `"Basis"` | `x_1``darr` | `x_2` | `S_1` | `S_2` | `A_1` | `A_2` | `RHS` | `"Ratio"=(RHS)/(x_1)` |
| `R_1` `Z` | `1.8571` | `0` | `-1` | `0.1429` | `0` | `-1.1429` | `3` | |
| `R_2` `A_1` | `(1.8571)` | `0` | `-1` | `0.1429` | `1` | `-0.1429` | `3` | `(3)/(1.8571)=1.6154``->` |
| `R_3` `x_2` | `0.1429` | `1` | `0` | `-0.1429` | `0` | `0.1429` | `1` | `(1)/(0.1429)=7` |
Most Positive `Z` is `1.8571`. So,
the entering variable is `x_1`.
Minimum ratio is `1.6154`. So,
the leaving basis variable is `A_1`.
`:.`
The pivot element is `1.8571`.
Entering `=x_1`, Departing `=A_1`, Key Element `=1.8571`
`R_2`(new)`= R_2`(old) `-: 1.8571`
| `x_1` | `x_2` | `S_1` | `S_2` | `A_1` | `A_2` | `RHS` |
| `R_2`(old) = | `1.8571` | `0` | `-1` | `0.1429` | `1` | `-0.1429` | `3` |
| `R_2`(new)`= R_2`(old) `-: 1.8571` | `1` | `0` | `-0.5385` | `0.0769` | `0.5385` | `-0.0769` | `1.6154` |
`R_3`(new)`= R_3`(old) - `0.1429 R_2`(new)
| `x_1` | `x_2` | `S_1` | `S_2` | `A_1` | `A_2` | `RHS` |
| `R_3`(old) = | `0.1429` | `1` | `0` | `-0.1429` | `0` | `0.1429` | `1` |
| `R_2`(new) = | `1` | `0` | `-0.5385` | `0.0769` | `0.5385` | `-0.0769` | `1.6154` |
| `0.1429 xx R_2`(new) = | `0.1429` | `0` | `-0.0769` | `0.011` | `0.0769` | `-0.011` | `0.2308` |
| `R_3`(new)`= R_3`(old) - `0.1429 R_2`(new) | `0` | `1` | `0.0769` | `-0.1538` | `-0.0769` | `0.1538` | `0.7692` |
`R_1`(new)`= R_1`(old) - `1.8571 R_2`(new)
| `x_1` | `x_2` | `S_1` | `S_2` | `A_1` | `A_2` | `RHS` |
| `R_1`(old) = | `1.8571` | `0` | `-1` | `0.1429` | `0` | `-1.1429` | `3` |
| `R_2`(new) = | `1` | `0` | `-0.5385` | `0.0769` | `0.5385` | `-0.0769` | `1.6154` |
| `1.8571 xx R_2`(new) = | `1.8571` | `0` | `-1` | `0.1429` | `1` | `-0.1429` | `3` |
| `R_1`(new)`= R_1`(old) - `1.8571 R_2`(new) | `0` | `0` | `0` | `0` | `-1` | `-1` | `0` |
Tableau-3
| `"Basis"` | `x_1` | `x_2` | `S_1` | `S_2` | `A_1` | `A_2` | `RHS` | |
| `R_1` `Z` | `0` | `0` | `0` | `0` | `-1` | `-1` | `0` | |
| `R_2` `x_1` | `1` | `0` | `-0.5385` | `0.0769` | `0.5385` | `-0.0769` | `1.6154` | |
| `R_3` `x_2` | `0` | `1` | `0.0769` | `-0.1538` | `-0.0769` | `0.1538` | `0.7692` | |
Since all `Z_j <= 0`
Hence, optimal solution is arrived with value of variables as :
`x_1=1.6154,x_2=0.7692`
Min `Z=0`
-->Phase-2<--
we eliminate the artificial variables and change the objective function for the original,
`Z - x_1 - x_2=0`
Simplex tableau is
Tableau-0
| `"Basis"` | `x_1` | `x_2` | `S_1` | `S_2` | `RHS` | |
| `R_1` `Z` | `-1` | `-1` | `0` | `0` | `0` | |
| `R_2` `x_1` | `1` | `0` | `-0.5385` | `0.0769` | `1.6154` | |
| `R_3` `x_2` | `0` | `1` | `0.0769` | `-0.1538` | `0.7692` | |
Make the Z-row consistent with the rest of the table (set coefficient of basis variables to 0 in Z-row)
`R_1`(new)`= R_1`(old) + `R_2`(old)
| `x_1` | `x_2` | `S_1` | `S_2` | `RHS` |
| `R_1`(old) = | `-1` | `-1` | `0` | `0` | `0` |
| `R_2`(old) = | `1` | `0` | `-0.5385` | `0.0769` | `1.6154` |
| `R_1`(new)`= R_1`(old) + `R_2`(old) | `0` | `-1` | `-0.5385` | `0.0769` | `1.6154` |
`R_1`(new)`= R_1`(old) + `R_3`(old)
| `x_1` | `x_2` | `S_1` | `S_2` | `RHS` |
| `R_1`(old) = | `0` | `-1` | `-0.5385` | `0.0769` | `1.6154` |
| `R_3`(old) = | `0` | `1` | `0.0769` | `-0.1538` | `0.7692` |
| `R_1`(new)`= R_1`(old) + `R_3`(old) | `0` | `0` | `-0.4615` | `-0.0769` | `2.3846` |
Tableau-1
| `"Basis"` | `x_1` | `x_2` | `S_1` | `S_2` | `RHS` | |
| `R_1` `Z` | `0` | `0` | `-0.4615` | `-0.0769` | `2.3846` | |
| `R_2` `x_1` | `1` | `0` | `-0.5385` | `0.0769` | `1.6154` | |
| `R_3` `x_2` | `0` | `1` | `0.0769` | `-0.1538` | `0.7692` | |
Since all `Z_j <= 0`
Hence, optimal solution is arrived with value of variables as :
`x_1=1.6154,x_2=0.7692`
Min `Z=2.3846`