How can you prove that the min ratio test in phase II in the simplex algorithm ensures that a feasible tableau remains feasible on pivot in linear programming?
Asked
Active
Viewed 1,949 times
1 Answers
0
As leaving basic variable, you're considering only those which reduce (indicated by positive coefficient in the chosen pivot column) as the entering variable increases from zero. The min ratio identifies the one (or ones, in the event of a tie) which reaches zero first. Afterwards, assuming there were no ties, there are the same number of basic (greater than zero) and non-basic (zero) variables as before. No negative variables mean that no constraints have been violated, i.e. the new tableau is feasible. Ties and zero basic variables don't change this. It can be helpful considering a two- or three-variable problem, drawing the constraints and resulting feasible region, and marking the route taken by the basis as it moves from vertex to vertex.
This isn't specifically to do with phase II of a problem where the origin is infeasible (hence the use of artificial variables which must be driven non-basic by a penalty in the objective function), it applies to any problem where the curent solution is feasible but not optimal.
GarryB
- 94