İÇ NOKTA ALGORİTMALARI VE DOĞRUSAL PROGRAMLAMAYA UYGULANAMASI

Year 2003, Issue: 9, - , 20.06.2015

Gülnur Keçek

Abstract

Karmarkar’s Interior Point Algorithm is an algorithm developed by Narendra Karmarkar in 1984 and known the major algorithm of interior point algorithms. In Interior point algorithms, it is tried to reach for the optimum solution by starting from an available one and gradually continuing for better ones which lie in the interior points of the available area. The purpose of our study is to present the efficiency of Karmarkar’s Interior Point Algorithm and Mehrotra Predictor-Corrector Algorithm, which is an other effective interior point algorithm in solving the linear programming problem in a very short time. A linear programming model has been formulated that has 4500 decision variables and 180 constraints. This model has been solved by interior point algorithms and Simplex Algorithm and they have been compared. MOSEK, PCx, XPRESS-MP/Barrier and XPRESS-MP/Simplex softwares are used for the solution of the model

Keywords

Interior point algorithms, unit simplex

İÇ NOKTA ALGORİTMALARI VE DOĞRUSAL PROGRAMLAMAYA UYGULANAMASI

Abstract

Karmarkar-İç Nokta Algoritması, 1984’te Narendra Karmarkar tarafından geliştirilmiş olup; iç nokta algoritmalarının ana algoritması olarak bilinen bir algoritmadır. İç nokta algoritmalarında, uygun bölge içerisindeki bir noktadan başlayıp; her bir adımda uygun bölgenin iç noktalarında var olan daha iyi bir çözüme gidilerek optimal çözüme ulaşılmaya çalışılır. Çalışmamızın amacı, doğrusal programlama probleminin kısa sürede çözülmesinde Karmarkar- İç Nokta Algoritmasının ve etkin bir iç nokta algoritması olan Mehrotra tahminci-düzeltici Algoritması’nın etkinliğinin gösterilmesidir. Bir üretim işletmesine ilişkin 4500 karar değişkeni ve 180 kısıtlayıcı içeren bir Doğrusal programlama modeli oluşturulmuştur. Model, iç nokta algoritmaları ve Simpleks algoritması ile çözülerek, çözüm sonuçları karşılaştırılmıştır. Modelin çözümü için MOSEK, PCx, XPRESS-MP/Barrier ve XPRESS-MP/Simplex yazılımlarından yararlanılmıştır

Keywords

İç nokta algoritmaları, Birim Simpleks

References

• Kitaplar
• Arbel, A.(1993). Exploring Interior – Point Linear Programming
• (Algorithms and Software ). Hong Kong: Times Roman by Asco
• Trade Typesetting Ltd. Bazaraa, M. S., Jarvis, J.J., Sherali, H.D.(1990).Linear Programming and
• Network Flows. USA: Second Edition, John Wiley&Sons, Inc. Chong, E. K. P., Zak, S. H.(1996).An Introduction to Optimization, USA:
• John Wiley & Sons, Inc. Fang, S., Puthenpura, S.(1993).Linear Optimization and Extensions, Theory
• and Algorithms. USA: Prentice –Hall,Inc. Hertog, D.den(1994). Interior Point Approach to Linear, Quadratic and
• Convex Programming. Netherlands: Kluwer Academic Publishers. Hillier, F.S., Lieberman, G.J.(1995). Introduction to Operations Research. ,
• Singapore: Mc Graw-Hill,Inc., Sixth Edition.
• Knowles, T. W.(1989).Management Science Building and Using Models.,
• USA:Richard D.Irwin, Inc. Kojima, M., Megiddo, N., Noma, T., Yoshise, A.(1991).A Unified Approach
• To Interior Point Algoirthms for Linear Complementarity Problems.
• Germany: Springer Verlag. Moon, T.K., Stirling, W.C.(2000).Mathematical Methods and Algorithms for
• Signal Processing. USA: Prentice-Hall,Inc. Nash, G., Sofer, A.(1996).Linear and Nonlinear Programmming.Singapore:
• McGraw-Hill Companies,Inc.,. Nocedal, J., Wright, S.(1999).Numerical Optimization. Springer Series in
• Operations Research, New York : Springer. Rardin, R.L.(1998).Optimization in Operations Research. New Jersey:
• Prentice Hall,Inc. Render, B., Stair, R.M.(1997).Quantitative Analysis for Management. New
• Jersey : Prentice-Hall,Inc., Sixth Edition. Roos, C., Terlaky, T., Vial, J. Ph.(1997).Theory and Algorithms for Linear
• Optimization. An Interior Point Approach, England: John Wiley & Sons Ltd. Schrijver, A.(1998).Linear and Integer Programming. England:John
• Wiley&Sons Ltd. Taha, H.(2000).Yöneylem Araştırması. 6. Basımdan Çeviri, Çev:Ş.Alp
• Baray, Şakir Esnaf, İstanbul: Literatür Yayıncılık. Winston, W. L.(1994). Operations Research Applications and Algorithms. –
• Belmont, Calif. : Duxbury Press. Wright, S. J.( 1997).Primal - Dual Interior Points Methods. The Society for
• Industrial and Applied Mathematics, USA:Siam. Makaleler Andersen, E. D., Gondzio, J., Meszaros, C., Xu, X.(1996).
• “Implementation of Interior Point Methods For Large Scale
• Linear Programs”, Interior Point Methods of Mathematical
• Programming, Netherlands: Kluwer Academic Publishers. Andersen, E. D., Ye, Y.(1996). “Combining Interior-point and Pivoting
• Algorithms for Linear Programming”, Management Science, Vol.
• ,No.12, Institute for Operations Research and Management Sciences. Arbel, A.(1994).“A Multiobjective Interior Primal – Dual Linear
• Programming Algorithm” Computers Operations Research, Vol. 21,
• No. 4, Great Britain: Elsevier Science Ltd., s. 433 – 445. Bal, H.(1995). “Using of Karmarkar Algorithm in Linear Goal Programming
• and an application”, Gazi Üniversitesi Fen Bilimleri Ens. Der. C.8., S.1. Bland, R.G., Goldfarb, D., Todd M.( 1981).“The Ellipsoid Method : A
• Survey”, Operations Research, Vol. 29, No.6, Operations Research
• Society of America. Cavalier, T. M., C. Schall, K.(1987). “Implementing An Affine Scaling
• Algorithm For Linear Programming”, Comput. Operations Research,
• Vol.14, No.5, Great Britain :Pergamon Journals Ltd. Dodani, M. H., Babu, A. J. G.(1989).“Karmarkar”s Projective Method For
• Linear Programming : A Computational Appraisal”, Computers
• Industrial Engineering, Vol. 16, No.1, ., Great Britain: Pergamon Press plc. Gay, D. M.(1987).”A Variant of Karmarkar”s Linear Programming
• Algorithm For Problems In Standart Form”, Mathematical
• Programming 37,North Holland. Goldfarb, D., Todd, M.J.(1989). “Linear Programming”, Handbooks in
• Operations Research and Management Science, Volume 1, Elsevier
• Science Publishers B.V., Netherlands. Gonzaga, C. C.(1991). “ Large Step Path – Following Methods For Linear
• Programming, Part I : Barrier Function Method ”, SIAM Journal on
• Optinization, Vol.1, No.2, Society for Industrial and Applied Mathematics. Gonzaga, C. C.(1991). “ Large Step Path – Following Methods For Linear
• Programming, Part II : Potential Reduction Method ”, SIAM Journal
• on Optinization, Vol.1, No.2, SIAM. Güler, O., Ye, Y.(1993). “Convergence Behavior of Interior-point
• Algorithms”, Mathematical Programming 60, North-Holland. Hertog, D.Den, Roos, C.(1991). “A Survey of search directions in interior
• point methods for linear programming”, Mathematical Programming
• 52, North-Holland. Karmarkar, N.(1984). “ A New Polynomial Time Algorithm For Linear
• Programming”, Combinatorica, Vol.4. Murray, Walter(1989).“Methods For Large – Scale Linear Programming”,
• Algorithms and Model Formulations in Mathematical Programming
• Ed: Stein W. Wallace, Berlin : Springer – Verlag. Powell, M.J.D.(1993).“On The Number of Karmarkar”s Algorithm for
• Linear Programming”, Mathematical Programming 62, North-Holland.
• Rockett, A. M., Stevenson J.C.(1987). “Karmarkar Algorithm”, Byte, September.
• Tardos, E.(1986).“A Strongly Polynomial Algorithm To Solve
• Combinatorial Linear Programs”, Operations Research, Vol.34,
• No.2, Operations Research Society of America. Tepecik, A.( 1998).”Geliştirilmiş Karmarkar Algoritması”,Gazi Ünv. Fen
• Bil.Ens.Der., Cilt.11, No.4,Ankara. Ye, Y., Kojıma, M.(1987).“Recovering Optimal Dual Solutions in
• Karmarkar”s Polynomial Algorithm For Linear Programming”,
• Mathematical Programming 39, North-Holland.