SORTING FEASIBLE BASIC SOLUTIONS OF A LINEAR PROGRAM,

An algorithm for sorting feasible basic solutions of a linear program is proposed. The algorithm proceeds from one basic solution to the next in order of non-increasing values of the objective function. The use of the proposed procedure is demonstrated through numerical examples and geometrical interpretations. The algorithm solves problems where a basic feasible solution is sought, maximizing a linear objective function and satisfying some prescribed conditions. This category includes the fixed-charge problem, the travelling salesman-problem, the mixed 0,1 linear program, etc. Author