Finding a Dual Feasible Solution to an LP with M Equalities in (l&M) Dual Iterations / Vinay Dharmadhikari.

By: Contributor(s): Material type: TextSeries: Publication details: Cambridge, Mass. National Bureau of Economic Research 1975.Description: 1 online resource: illustrations (black and white)Online resources: Available additional physical forms:
  • Hardcopy version available to institutional subscribers
Abstract: 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.
No physical items for this record

August 1975.

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.

Hardcopy version available to institutional subscribers

System requirements: Adobe [Acrobat] Reader required for PDF files.

Mode of access: World Wide Web.

Print version record

Licensed e-book