×

Un algorithme pour la résolution du programme linéaire général. (An algorithm for the solution of the general linear program). (French) Zbl 0726.90060

Summary: We propose an algorithm, called SGGP, for solving a general linear programming problem. The proposed algorithm works directly in the primal variables space and comprises two phases. Phase I (initialization of the algorithm of determination of an extreme point of a convex polyhedron, which uses phase II as in the simplex algorithm) has been constructed in two forms (primal and dual procedures). Designed as a natural extension of the simplex algorithm, the algorithm SGGP contains its usual variants (dual simplex, case of bounded variables,...).
We show that SGGP is a projected gradient method with an extreme point of the convex polyhedron as the starting point.

MSC:

90C05 Linear programming
90-08 Computational methods for problems pertaining to operations research and mathematical programming