> And I now see what you mean about multiple pivots. I must be > missing/forgetting something rather fundamental. If I introduce a new > column that can improve the objective, why is it there are potentially > multiple pivots? I would just expect the new column to enter and some > other column to exit. Any brief (or detailed) explanation would be > appreciated.
This is because every pivot changes not only primal values of variables but also dual ones (reduced costs). If you have optimal basis, all reduced costs have correct signs, and the dual basic solution is therefore feasible. Then you generate a column, i.e. add a new non-negative variables to the formulation. If its reduced cost has wrong sign, i.e. the basic solution becomes dual infeasible, the primal simplex chooses this new variable to made it basic; note that it is the only non-basic variable that can be chosen so far. However, once the simplex has changed the basis to the adjacent one, reduced costs of other non-basic variables have also changed, and there may appear non-basic variables whose reduced costs have wrong sign indicating dual infeasibility, though before such variables were "optimal". Thus, in general case the simplex methods may need more than one iteration to find the new optimum. _______________________________________________ Help-glpk mailing list [email protected] http://lists.gnu.org/mailman/listinfo/help-glpk
