Production
https://prod.org.br/doi/10.1590/S0103-65131996000200001?lang=en
Production
Article

Programação linear por partes: revisão teórica e aplicações

Programação linear por partes: revisão teórica e aplicações

Marins, Fernando Augusto S.; Perin Filho, Clóvis

Downloads: 1
Views: 833

Resumo

Procura-se resgatar a importância de uma subárea da Programação Matemática conhecida como Programação Linear Por Partes - PLP. De fato a PLP tem inúmeras aplicações tanto na área teórica como em situações reais. Este trabalho apresenta os resultados de uma pesquisa bibliográfica, efetuada nas principais revistas técnicas e livros disponíveis relacionados com Pesquisa Operacional, que visou situar o estado da'arte da Programação Linear por Partes, bem como a abrangência de sua aplicabilidade. Particularmente, no contexto da PLP, este texto deslaca a Programação em Redes Lineares por Partes devido a sua relevância em muitas situações práticas.

Palavras-chave

Programação linear por partes, programação em redes lineares por partes, programação linear e programação não-linear

Abstract

The importance of a subárea of Mathematical Programming known as Piecewise-Linear Programming - PLP is emphasized. In fact PLP has many both theoretical and real life applications. This paper presents the results of an extensive bibliographical research, including the most relevant Operations Research journals and books available, which had as goal to find out Piecewise-Linear Programming state-of-art, as well as its range of applicability. Particularly, inside PLP context, this paper details Network Piecewise-Linear Programming due to its relevance to several real life situations.

Keywords

Piecewise-Linear Programming, Network Piecewise-Linear Programming

References



[1] Ahlfeld, D. P., R. S. Dembo, J. M. Mulvey. e S. A. Zenios. 1987. Nonlinear Programming on Generalized Networks. Association for Computing Machinery Transactions on Mathematical Software 13, No. 4, 350-367.

[2] Ahuja. R. K.. J. L. Batra, e S. K. Gupta. 1984. A Parametric Algorithm for the Convex Cost Network Flow and Related Problems. European Journal of Operational Research 16, No. 2, 222-235.

[3] Ahuja, R. K... T. L. Magnanti, e J. B. Orlin. 1993. Network Flows: Theory, Algorithms and Applications. Englewood Cliffs. NJ. Prentice-Hall.

[4] Anthonisse. J. M, K. M. Van Hee, e J. K. Lenstra. 1988. Resource-Constrained Project Scheduling: An International Exercise in DSS. Decision Support Systems 3, 249-257.

[5] Barras, J., S. Alec, C. Pasche, P. A. Chamorel. A. J. Germond, e D. De Werra. 1987. Network Simplex Method Applied to AC Load-Flow Calculation. Institute of Electrical and Electronics Engineers Transactions on Power Systems Vol PWRS-2.No. 1, 197-203.

[6] Barrodale. I., e F. D. K. Roberts. 1973. An Improved Algorithm for Discrete L1 Linear Approximation. SIAM Journal on Numerical Analysis 10, 839-848.

[7] Bartels, R. H. 1980. A Penalty Linear Programming Method Using Reduced-Gradient Basis-Exchange Techniques. Linear Algebra and Its Applications 29. 17-32.

[8] Beale. E. M. L. 1959. An Algorithm for Solving the Transportation Problem when Shipping Cost over each Route is Convex. Naval Research Logistics Quarterly 6, 43-56.

[9] Charnes, A, e C. E. Lemke. 1954. Minimization of Non-Linear Separable Convex Functionals. Naval Research Logistics Quarterly 1, 301-312.

[10] Chames, A, e W. W. Cooper. 1957. Nonlinear Power of Adjacent Extreme Point Methods in Linear Programming. Econométrica 25. 132-153.

[11] Charret, D. E. 1970. Plastic Analysis and Optimum Design of Slabs and Frames. Special Report S2/1970. Civil Engineering, Monash University. Clayton - Victoria. Australia.

[12] Collins, M.. L. Cooper. R Helgason. J. Kennington. eL. LeBlanc. 1978. Solving the Pipe Network Analysis Problem Using Optimization Techniques. Management Science 24. No. 7. 747-760.

[13] Conn, A. R. 1976. Linear Programming via a Nondifferentiable Penalty Function. SIAM Journal on Numerical Analysis 13, No. 1, 145-154.

[14] Cooper, L., e L. J. LeBlanc. 1977. Stochastic Transportation Problems and Other Networks Related Convex Problems. Naval Research Logistics Quarterly 24, No. 2, 327-337.

[15] Dantzig, G. 1956. Recent Advances in Linear Programming. Management Science 2, No. 2, 131-144.

[16] Dantzig, G. B. 1955. Linear Programming under Uncertainty. Management Science 1, No. 3, 197-206.

[17) Dantzig, G., S. Johnson, e W. White. 1958. A Linear Programming Approach to the Chemical Equilibrium Problem. Management Science 5, No. 1, 38-43.

[18] Davies, M.. 1967. Linear Approximation Using the Criterion of Least Total Deviations. Journal of the Royal Statistical Society B 29, 101-109.

[19] Dembo, R. S., A. Chiarri, J. G. Martin, e L. Paradinas. 1990. Managing Hidroeléctrica Española's Hydroelectric Power System. Interfaces 20, No. 1, 115-135.

[20] De Wolf, D., O. J. De Bisthoven, e Y. Smeers. 1991. The Simplex Algorithm Extended to Piecewise Linearly Constrained Problems I: the Method and an Implementation. Discussion Paper No. 9119, Center for Operations Research & Econometrics, Universite Catholique de Louvain, Belgium.

[21] Edmonds, J., e R. M. Karp. 1972. Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems. Journal of the Association for Computing Machinery 19, No. 2, 248-264.

[22] Ferguson, A. R., e G. B. Dantzig. 1957. The Allocation of Aircrafts to Routes: An Example of Linear Programming under Uncertain Demand. Management Science 3, No. 1, 45-73.

[23] Fernandes, J. F. R. 1979. Programação Linear por Partes: Urn Problema de Grande Porte Resolvido por Técnicas de Decomposição. Tese de Doutoramento, Faculdade de Engenharia Elétrica, Universidade Estadual de Campinas, Campinas - SP, Brasil.

[24] Ferreira, E. P. 1979. Programação Linear por Partes: Um Método Dual-Primal. Dissertação de Mestrado, Faculdade de Engenharia Elétrica, Universidade Estadual de Campinas, Campinas - SP, Brasil.

[25] Fourer, R. 1992. A Simplex Algorithm for Piecewise-Linear Programming III: Computational Analysis and Applications. Mathematical Programming 53, No. 2, 213-235.

[26] Fourer, R. 1988. A Simplex Algorithm for Piecewise-Linear Programming II: Finiteness, Feasibility mid Degeneracy. Mathematical Programming 41, No. 3, 281-315.

[27] Fourer, R. 1985. A Simplex Algorithm for Piecewise-Linear Programming I: Derivation and Proof. Mathematical Programming 33, No. 2, 204-233.

[28] Fourer. R., e R. E. Marslen. 1992. Solving Piecewise-Linear Programs: Experiments with a Simplex Approach. ORSA Journal on Computing 4, No. 1, 15-31.

[29] França, P. M., J. F. R. Fernandes, e H. M. F. Tavares. 1987. Telephonic Network Expansion. Controle & Automação I, No. 3.

[30] Garcia, A. S. 1978. Um Método Dual-Simplex para Programação Linear por Partes. Dissertação de Mestrado, Instituto de Matemática, Estatística e Ciências da Computação, Universidade Estadual de Campinas, Campinas - SP, Brasil.

[31] Geoffrion, A. M. 1977. Objective Function Approximations in Mathematical Programming. Mathematical Programming 13, No. 1, 23-37.

[32] Glover. F., D. Klingman, e D. T. Phillips. 1992. Networks Models in Optimization and Their Applicalions in Practice. NY, John Wiley & Sons.

[33] Glover, F., D. Klingman, e N. Phillips. 1990. Netform Modeling and Applications. Interfaces 20, No. 4, 7-27.

[34] Golstein, E. G. 1960. A Certain Class of Nonlinear Extremum Problems. Soviet Mathematics 4, 863-866.

[35] Golstein, E. G., e D. Youdine. 1973. Problèmes Particuliers de la Programmation Lineaire. Moscow. Editions Mir.

[36] Güder, F.. e J. G. Morris. 1994. Optimal Objective Function Approximation for Separable Convex Quadratic Programming. Mathematical Programming 67. No. 1. 133-142.

[37] Gunn, E. A. .1981. An Unconstrained Dual for Linear Programming and its Solution by Piecewise Linear Optimization. Utilitas Mathematica 20, 5-19.

[38] Ho, J.K. 1985. Relationship Among Linear Formulation of Separable Convex Piecewise-Linear Programs. In: Mathematical Programming Study 24. 126-140, edited by R. W. Cottle, Amsterdam - The Netherlands, North-Holland Publishing Company.

[39] Hochbaum, D. S., e J. G. Shanthikumar. 1990. Convex Separable Optimization Is Not Much Harder than Linear Optimization. Journal of the Association for Computing Machinery 37. No. 4, 843-862.

[40] Kamesam, P. V.. e R. R. Meyer. 1984. Multipoint Methods for Separable Nonlinear Networks. In: Mathematical Programming Study 22, 185-205.

[41] Kao, C. Y, e R. R. Meyer. 1981. Secant Approximation Methods for Convex Optimization. In: Mathematical Programming Study 14, 143-162, edited by H. Hönig, B. Korte, e K. Ritter, Amsterdam - The Netherlands, North-Holland Publishing Company.

[42] Kennington, J. L., e R. V. Helgason. 1980. Algorithms for Network Programming. NY., John Wiley & Sons;

[43] Klein, M. 1983. A Transportation Model for Production Planning with Convex Costs. IIE Transactions 15, No. 3, 272-274.

[44] Klingman, D., A. Napier, e J. Stutz. 1974. NETGEN: A Program for Generating Large Scale Capacitated Assignment, Transportation, and Minimum Cost Flow Network Problems. Management Science 20, No. 5,814-821.

[45] Leblanc, L. J. 1976. The Use of Large Scale Mathematical Programming Models in Transportation Systems. Transportation Research 10, No. 6, 419-421.

[46] Levner. E. V, e A. S. Nemirosvsky. 1994. A Network Flow Algorithm for Just-in-Time Project Scheduling. European Journal of Operational Research 79, 167-175.

[47] Marins, F. A. S., e C. Perin Filho 1996. Algoritmos para a Programação em Redes Lineares por Partes. Submetido para publicação na revista Pesquisa Operacional da SOBRAPO.

[48] Marins, F. A. S., K. Darby-Dowman, E. F. Senne, A.F. Machado, e C. Perin Filho. 1996. Algorithms for Network Piecewise-Linear Programs: A Statistically Designed Study. Aceito para publicação no European Journal Of Operational Research.

[49] Marins. F. A. S., K. Darby-Dowman. E. F. Senne, A.F. Machado, e C. Perin Filho. 1995. Algorithms for Network Piecewise-Linear Programs: A Comparative Study Anais do XXVII Simpósio Brasileiro de Pesquisa Operacional, Vitória - ES, Brasil.

[50] Marins, F. A. S., e C. Perin Filho. 1994. Algorithms for Network Piecewise-Linear Prograins. Anais de Resumos do EURO XII/OR 36, Glasgow - Escócia.

[51] Marins, F. A. S.. C. Perin Filho, e A. F. Machado. 1993. An O(n.m'.log n.min(log nC, m'logn)) Algorithm for Network Piecewise-Linear Programs. Anais do XXV Simpósio Brasileiro de Pesquisa Operacional, Campinas - SP, Brasil.

[52] Marins, F. A. S., C. Perin Filho, e A. F. Machado. 1992. A Strongly Polynomial Algorithm for Network Piecewise-Linear Programs. Apresentado no XXIV Simpósio Brasileiro de Pesquisa Operacional, Salvador - BA. Brasil.

[53] Marins, F. A. S.. e C. Perin Filho. 1991. Computational Experience with a Dual Algorithm for Network Piecewise-Linear Programs. Anais do XIII World Congress on Computational and Applied Mathematics, 197-198, Dublin, Irlanda.

[54] Marins, F. A. S., e C. Perin 1990. A Dual Algorithm for Network Piecewise-Linear Programs. Apresentado no V Congresso Latino-Ibero-Americano de Pesquisa Operacional e Engenharia de Sistemas, Buenos Aires, Argentina.

[55] Marins, F. A. S., e C. Perin Filho 1989. An Out-of-Kilter Algorithm for Network Piecewise-Linear Programs. Anais do XII Congresso Nacional de Matemática Aplicada e Computacional, 126-130, São José do Rio Preto - SP, Brasil.

[56] Marins, F. A. S., e C. Perin Filho 1988. Strong Feasibility in Network Piecewise-Linear Programs. Anais do IV Congresso Latino-Ibero-Americano de Pesquisa Operacional e Engenharia de Sistemas, 364-383, Rio de Janeiro - RJ, Brasil.

[57] Marins, F. A. S. 1987. Estudos de Programas Lineares por Partes. Tese de Doutoramento, Faculdade de Engenharia Elétrica, Universidade Estadual de Campinas, Campinas - SP, Brasil.

[58] Markowitz, H. M., e A. F. Perold. 1981. Sparsity and Piecewise Linearity in Large Portfolio Optimization Problems. In: Sparse Matrices and Their Uses, 89-108, edited by I. S. Duff, Academic Press, NY.

[59] Meyer, R. R. 1982. Recursive Piecewise-Linear Approximation Methods for Nonlinear Networks. In: Evaluating Mathematical Programming Techniques, Lecture Notes in Economics and Mathematical Systems Vol 199, 315-322, edited by J. M. Mulvey, Springer-Verlag, NY

[60] Meyer, R. R. 1979. Two-Segment Separable Programming. 1979. Management Science 25, No. 4, 385-395.

[61] Monma, C. L., e M. Segal. 1982. A Primal Algorithm for Finding Minimum-Cost Flows in Capacitated Networks with Applications. The Bell System Technical Journal 61, No. 6, 949-968.

[62] Mulvey, J. M. 1989. Advances in Nonlinear Network Models and Algorithms. In: Algorithms and Model Formulations in Mathematical Programming - NATO ASI Series Vol F51, edited by Stein W. Wallace, Springer-Verlag, Berlin.

[63] Nakagawa, J. M. 1984. Planejamento de Sistemas Telefônicos: Alocação de Centros de Linhas. Dissertação de Mestrado, Faculdade de Engenharia Elétrica, Universidade Estadual de Campinas, Campinas - SP, Brasil.

[64] Orchard-Hays, W. 1968. Achanced Linear-Programming Computing Techniques. McGraw-Hill, New York, NY.

[65] Orden, A., e V. Nalbandian. 1968. A Bidirectional Simplex Algorithm. Journal of the Association for Computing Machinery 15, No. 2, 221-235.

[66] Perold, A. F. 1984. Large-Scale Portfolio Optimization. Management Science 30, No. 10, 1143-1160.

[67] Premoli, A. 1986. Piecewise-Linear Programming: The Compact (CPLP) Algorithm. Mathematical Programming 36. No. 2, 210-227.

[68] Rivindran. A., D. T. Phillips, e J. J. Solberg. 1987. Operations Research - Principles and Practice. New York, NY, John Wiley & Sons.

[69] Ribeiro, R. V. 1980. Estudos em Programação Linear. Tese de Doutoramento, Faculdade de Engenharia Elétrica, Universidade Estadual de Campinas, Campinas - SP, Brasil.

[70] Robers, P. D., e A. Ben-lsrael. 1969. An Interval Programming Algorithm for Discrete Linear L1 Approximation Problems. Journal of Approximation Theory 2, 323-336.

[71] Rockafellar, R. T. 1984. Network Flows and Monotropic Optimization. Wiley-Interscience, New York.

[72] Rockafellar, R T. 1981. Monotropic Programming: Descent Algorithms and Duality. In: Nonlinear Programming 4, 327-366. edited by O. L. Mangasarian, R. R. Meyer, e S. M. Robinson. NY, Academic Press.

[73] Rosenthal, R. E. 1981. A Nonlinear Network Flow Algorithm for Maximization of Benefits in a Hydroelectric Power System. Operations Research 29, No. 4, 763-786.

[74] Rosvany. G. I. N. 1971. Concave Programming and Piecewise-Linear Programming. International Journal for Numerical Methods in Engineering 3, No. 1, 131-144.

[75] Rosvany. G. I. N. 1970. Concave Programming in Structural Optimization. International Journal of Mechanical Sciences 12, No. 2, 131-142.

[76] Sasson, A. M., e H. D. Merrill. 1974. Some Applications of Optimization Techniques to Power Systems Problems. Proceedings of the Institute of Electrical and Electronics Engineers 62, No. 7, 959-972.

[77] Snyder, R. D. 1984. Linear Programming with Special Ordered Sets. Journal of the Operational Research Society 35, No. 1, 69-74.

[78] Snyder, R. D, 1981. Programming with Piecewise-Linear Objective Functions. Working Paper 9/81, Department of Econometrics and Operations Research. Monash University, Clayton, Victoria, Australia.

[79] Soares Filho, S., B. P. F. Braga Jr., e J. G. L. Caneja. 1989. Mid Term Multiobjeclive Operation Planning of a Multireservoir System: The Piracicaba River Basin Case. Apresentado no International Symposium on Water Resource Systems Application, Canada.

[80] Souza, C. R. 1977. Uma Aplicação de Programação Linear por Partes a Sistemas de Potência. Dissertação de Mestrado. Faculdade de Engenharia Elétrica, Universidade Estadual de Campinas, Campinas - SP, Brazil.

[81] Spyropoulos, K., E. Kiountouzis, e A. Young. 1973. Discrete Approximation in the L1 Norm. The Computer Journal 16, 180-186.

[82] Sun, J., e K. Tsai. 1989. An Implementation of the Network Simplex Method for Piecewise-Linear Programs. Technical Report 89-07, Department of Industrial Engineering and Management Sciences, Northwestern University, Evanston, IL, USA.

[83] Sun, J., L. Qi, e K.-H. Tsai. 1989. Solving Stochastic Transshipment Problems as Network Piecewise Linear Programs. Technical Report, Department of Industrial Engineering and Management Sciences. Northwestern University, Evanston, IL, USA.

[84] Thakur, L. S. 1986. Successive Approximation in Separable Programming: An Improved Procedure for Convex Separable Programs. Naval Research Logistics Quarterly 33, No. 2, 325-358.

[85] Thakur, L. S. 1978. Error Analysis for Convex Separable Programs: the Piecewise-Linear Approximation and the Bounds on the Optimal Objective Value. SIAM Journal on Applied Mathematics 34, No. 4, 704-714.

[86] Veldhorst, M.. 1990. A Bibliography on Network Flow Problems. Algorithms Review I, No.2, 97-117.

[87] Williams, A. C. 1962. A Treatment of Transportation Problems by Decomposition. SIAM Journal 10. No. 1. 35-48.

[88] Wolfe, P. 1965. The Composite Simplex Algorithm. SIAM Review 7, 42-54.

5883a4237f8c9da00c8b47d4 1574685864 Articles
Links & Downloads

Production

Share this page
Page Sections