SOLUCIÓN DEL PROBLEMA DE LOCALIZACIÓN DE PLANTAS CAPACITADAS DE FUENTE ÚNICA EN DOS ETAPAS MEDIANTE PLANOS DE CORTE FENCHEL.

  • Jenny Margarita Rojas Jerónimo Universidad César Vallejo
  • Billy Santos Toribio Aranda Universidad César Vallejo
Palabras clave: Envolvente convexa, Localización de plantas, Programación lineal Heurística

Resumen

En el presente trabajo, aplicamos la metodología de los planos de corte Fenchel para resolver el problema de Localización de Plantas Capacitadas de fuente única en dos etapas (TSCFL). Las desigualdades Fenchel describen la envolvente convexa de un conjunto X⊂R^n sin conocer explícitamente la estructura. La relajación Fenchel es una relajación lineal, se obtiene al agregar las desigualdades Fenchel más violadas obtenidas como solución del problema de separación asociado al problema primal. El valor de la relajación Fenchel constituye una cota inferior fuerte para el problema de localización. Simultáneamente se aplica una heurística basada en la relajación Fenchel para obtener una solución factible la cual constituye una cota superior. Ambas cotas se integran al algoritmo de Ramificación y Acotación basado en programación lineal para obtener el óptimo global. Asimismo, los cortes Fenchel presentan eficientes propiedades computacionales.

Citas

Aardal, K., Y. Pochet, L.A. Wolsey. (1995). Capacitated facility location: valid inequalities and facts Math. Oper. Res. 20, 562-582.
Aardal, K., S. Hoesel. (1995). Polyhedral Techniques in combinatorial optimization II: Computations, Report UU-CS-1995-42, Utrecht University.
Aardal, k., M. Labbé, J. Leung, M. Queyranne. (1996). On the Two-level Uncapacitated Facility Loction Problem Informs J. Computing. 8, 289-301.
Aardal, K., S. Hoesel. (1996) Polyhedral techniques in combinatorial optimization I: Theory, Statist. Neerlandica, 50, 3-26.
Boyd A. (1992). Fenchel cutting planes for integer program J.Oper. Res. 42 (1), 53-63.
Boyd A. (1993). Generating Fenchel cutting planes for Knapsack Poliyhedra, Siam J. Optimization. vol-3, pp 734-750.
Boyd A. (1995). On the convergence of Fenchel cutting planes in Mixed-integer programming, SIAM J. Optimization, vol 5, nº 2, 421-435.
Cornuéjols, G., R. Sridharam, J.M.Thizy. (1991). A comparasion of heuristics and relaxations for the capacitates plant location problem, European J. oper. 50, 28-297.
Geoffrion, A.M. (1974). Lagrangean relaxation and its uses in integer programming, Math. Pro.Stu. 2, 82-114.

Geoffrion, A.M., G.W. Graves. (1974). Multicommodity distribution system design by Benders decomposition, Mgmt Sci. 20, 822-844.
Hindi, K.S., T. Basta. (1991). Computationally Efficcient solution of a multiproduct, two-stage distribution-location problem, Op. Res. Soc. vol.45 nº 11, 1316-1323.
Kaufman, L., M. Van Eede, P. Hansen. (1977). A plant and warehouse location problem, Opl. Res. Q 28, 547-554.
Klose, A. (1995). A lagrangean heuristic to solve the two-stage capacitated facility location problem, Proceedings of the second International Workshop on Distribution Logistics, The Netherlands.
Klose, A. (1999). An LP-based heuristic for two-stage capacitated facility location problems, J. Oper. Res. Soc. 50, 157-166.
Klose, A. (2000). A lagrangean relax-and-cut approach for the two-stage capacitated facility location problem, European J. of Op.res. 126, 408-421.
Marín A., B. Pelegrín. (1999). Applying Lagrangian relaxation to the resolution of two-stage location problems, Annals of Operation Research 86, 179-198.
Sáez, J. (2000). Solving linear programmnig relaxations associated with Lagrange relaxations by Fenchel cutting planes, Eur.J.Oper. 121, 609-626.
Tcha, D., B. Lee. (1984). A branch and bound algorithm for the multi-lavel uncapacitated facility location problem, Eur. J. Opl.Res. 18, 35-43.
Tragantalerngsak, S., J. Holt, M. Rönnqvist. (1997). Lagrangian heuristics for the two-echelon, sigle-source, capacitated facility location problem, European Journal of Operational Research 102, 611-625.
Publicado
2019-08-16
Sección
Artículos de Investigación