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

Format:

Book

Author/Creator:

Dharmadhikari, Vinay.

Contributor:

National Bureau of Economic Research.

Series:

Working Paper Series (National Bureau of Economic Research) no. w0100.

NBER working paper series no. w0100

Language:

English

Subjects (All):

Economics.

Economics--Periodicals.

Physical Description:

1 online resource: illustrations (black and white);

Other Title:

Finding a Dual Feasible Solution to an LP with M Equalities in

Place of Publication:

Cambridge, Mass. National Bureau of Economic Research 1975.

Cambridge, Massachusetts : National Bureau of Economic Research, 1975.

Summary:

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.

Notes:

Print version record

August 1975.