Finding a Dual Feasible Solution to an LP with M Equalities in (L&M) Dual Iterations

Lemke's dual-simplex method of linear programming is usually considered inferior to the primal simplex method for any general linear programming problems. One reason given is the difficulty of finding a starting dual-feasible basis. In this paper, a new starting technique is presented, which finds a dual-feasible basis in a single dual-simplex pivot for LP's with no equality constraints, and in (l+m3 ) pivots for LP'S with m3 equality constraints irrespective of the number of inequality constraints. The technique is illustrated on a small example problem. The performance, in terms of the number of pivots to optimality, of the dual-simplex with the new starting technique on 100 medium sized problems is reported and compared with that of the primal simplex. Finally, how the dual-simplex with the new starting technique can be efficiently implemented is briefly discussed