Published

2003-07-01

A “feasible direction” search for Lineal Programming problem solving

Una búsqueda de "Direcciones factibles” para la solución de problemas de programación lineal

DOI:

https://doi.org/10.15446/ing.investig.v23n3.14703

Keywords:

linear programming, simplex method, polyhedral characteristics, primal and dual linear programs relations, karush-kuhn-tucker optimality criteria (en)
programación lineal, método simplex, características poliédricas, relaciones de los programas lineales principal y dual, criterios de optimalidad Karush-Kuhn-Tucker (es)

Authors

  • Jaime U Malpica Angarita Universidad Nacional de Colombia

The study presents an approach to solve linear programming problems with no artificial variables. A primal linear minimization problem in standard form and its associated dual linear maximization problem are used. Initially, the dual (or a partial dual) program is solved by a "feasible direction" search, where the Karush-Kuhn-Tucker conditions help to verify its optimality and then its feasibility. The "feasible direction" search exploits the characteristics of the convex polyhedron (or polytope) formed by the dual program constraints to find a starting point and then follows line segments, whose directions are found in affine subspaces defined by boundary hyperplanes of polyhedral faces, to find next points up to the (an) optimal one. Then, the remaining dual constraints not satisfied at that optimal dual point, if there are any, are handled as nonbasic variables of the primal program, which is to be solved by such "feasible direction" search.

El estudio presenta un enfoque para resolver problemas de programa con lineal sin el uso de variables artificiales. Se emplea la pareja dual: un problema lineal de minimización (principal) en la forma estándar y un problema lineal de maximización asociado (dual). Inicialmente, el programa dual (o un programa dual parcial) se resuelve por medio de una búsqueda de "direcciones factibles", donde las condiciones de Karush-Kuhn Tucker ayudan, primero, a verificar su optimalidad y después, su factibilidad. La búsqueda de "direcciones factibles" explota las características del poliedro (o politopo) convexo formado por las restricciones del programa dual para hallar un punto inicial y luego sigue segmentos de rectas cuyas direcciones se encuentran en subespacios afines definidos por los hiperplanos de frontera de las caras poliédricas, para hallar los puntos siguientes hasta el (o un) punto óptimo. Luego, las restricciones duales restantes no satisfechas en aquel punto dual óptimo, si hay alguna, se manejan como variables no básicas del programa principal, que se resuelve por la misma búsqueda de "direcciones factibles".

References

Alevras, D.; Padberg, M.W. (2001). Linear Optimization and Extensions, Problems and Solutions. New York: Springer-Verlag. DOI: https://doi.org/10.1007/978-3-642-56628-8

Banchoff, T,; Werner, J. (1992). Linear Algebra Through Geometry. Second Ed. New York; Springer-Verlag. DOI: https://doi.org/10.1007/978-1-4612-4390-8

Bazaraa, M.; Jarvis, J., y Sherali, H. (1990). Linear Programming and Network Rows, Second Ed. New York: John Wiley.

Dantzig, G.B. (1963). Linear Programming and Extensions. New Jersey: Princeton University Press, Princeton. DOI: https://doi.org/10.7249/R366

Gale, D. (1960). The Theory of Linear Economic Models, New York: McGraw-Hill.

Mangasarian, O. L. (1969). Nonlinear Programming. New York: McGraw-Hill.

Papadimitriou, C.H. (1998). Combinatorial Optimization: Algorithms and Complexity. New York Dover Publications, Mineola.

Rockafellar, R.T. (1970), Convex Analysis. New Jersey: Princeton University Press, Princeton,

Simonnard, M. (1966). Linear Programming. New Jersey: Prentice-Hall, Englewood Cliffs,

Stoer, J.; Witzgall, C. (1970), Convexity and Optimization in Finite Dimensions I. New York: Springer-Verlag. DOI: https://doi.org/10.1007/978-3-642-46216-0

Zoutendijk, G. (1976). Mathematical Programming Methods. Amsterdam: North-Holland Publishing.

How to Cite

APA

Malpica Angarita, J. U. (2003). A “feasible direction” search for Lineal Programming problem solving. Ingeniería e Investigación, 23(3), 39–43. https://doi.org/10.15446/ing.investig.v23n3.14703

ACM

[1]
Malpica Angarita, J.U. 2003. A “feasible direction” search for Lineal Programming problem solving. Ingeniería e Investigación. 23, 3 (Jul. 2003), 39–43. DOI:https://doi.org/10.15446/ing.investig.v23n3.14703.

ACS

(1)
Malpica Angarita, J. U. A “feasible direction” search for Lineal Programming problem solving. Ing. Inv. 2003, 23, 39-43.

ABNT

MALPICA ANGARITA, J. U. A “feasible direction” search for Lineal Programming problem solving. Ingeniería e Investigación, [S. l.], v. 23, n. 3, p. 39–43, 2003. DOI: 10.15446/ing.investig.v23n3.14703. Disponível em: https://revistas.unal.edu.co/index.php/ingeinv/article/view/14703. Acesso em: 29 mar. 2024.

Chicago

Malpica Angarita, Jaime U. 2003. “A ‘feasible direction’ search for Lineal Programming problem solving”. Ingeniería E Investigación 23 (3):39-43. https://doi.org/10.15446/ing.investig.v23n3.14703.

Harvard

Malpica Angarita, J. U. (2003) “A ‘feasible direction’ search for Lineal Programming problem solving”, Ingeniería e Investigación, 23(3), pp. 39–43. doi: 10.15446/ing.investig.v23n3.14703.

IEEE

[1]
J. U. Malpica Angarita, “A ‘feasible direction’ search for Lineal Programming problem solving”, Ing. Inv., vol. 23, no. 3, pp. 39–43, Jul. 2003.

MLA

Malpica Angarita, J. U. “A ‘feasible direction’ search for Lineal Programming problem solving”. Ingeniería e Investigación, vol. 23, no. 3, July 2003, pp. 39-43, doi:10.15446/ing.investig.v23n3.14703.

Turabian

Malpica Angarita, Jaime U. “A ‘feasible direction’ search for Lineal Programming problem solving”. Ingeniería e Investigación 23, no. 3 (July 1, 2003): 39–43. Accessed March 29, 2024. https://revistas.unal.edu.co/index.php/ingeinv/article/view/14703.

Vancouver

1.
Malpica Angarita JU. A “feasible direction” search for Lineal Programming problem solving. Ing. Inv. [Internet]. 2003 Jul. 1 [cited 2024 Mar. 29];23(3):39-43. Available from: https://revistas.unal.edu.co/index.php/ingeinv/article/view/14703

Download Citation

CrossRef Cited-by

CrossRef citations0

Dimensions

PlumX

Article abstract page views

384

Downloads

Download data is not yet available.