In simplex algorithm, I applied the ratio test to find the leaving variable but it gave the same result for two variables. Should I choose one of them and calculate the objective function or calculate for both of them, then take the better one?
Asked
Active
Viewed 5,736 times
1 Answers
1
1) the variation in the objective function can be expressed as $ \Delta Z =|\hat{c}_k|\delta$, where $\hat{c}_k$ is the reduced cost of the entering variable and $\delta$ is it's maximum allowed increasing obtained by the ratio test. Therefore the test you propose is useless.
2) if the minimum ratio occurs for two different leaving variables, when you perform the pivot operation these two variables become both zero. One leaves the basis, the other remains a basic variable with a null value, that is the solution degenerate.
3) the simplex algorithm has some computational issues with degenerate solutions (cycling). To overcome these issues some rules can be adopted (anti-cycling rules). The most wide used is the Bland's rule: when there is an indetermination in selecting the leaving variable, choose the variable related to the constraint with the minimum index.
