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

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

1. Kitaplar
2. Arbel, A.(1993). Exploring Interior – Point Linear Programming
3. (Algorithms and Software ). Hong Kong: Times Roman by Asco
4. Trade Typesetting Ltd. Bazaraa, M. S., Jarvis, J.J., Sherali, H.D.(1990).Linear Programming and
5. Network Flows. USA: Second Edition, John Wiley&Sons, Inc. Chong, E. K. P., Zak, S. H.(1996).An Introduction to Optimization, USA:
6. John Wiley & Sons, Inc. Fang, S., Puthenpura, S.(1993).Linear Optimization and Extensions, Theory
7. and Algorithms. USA: Prentice –Hall,Inc. Hertog, D.den(1994). Interior Point Approach to Linear, Quadratic and
8. Convex Programming. Netherlands: Kluwer Academic Publishers. Hillier, F.S., Lieberman, G.J.(1995). Introduction to Operations Research. ,

9. Singapore: Mc Graw-Hill,Inc., Sixth Edition.
10. Knowles, T. W.(1989).Management Science Building and Using Models.,
11. USA:Richard D.Irwin, Inc. Kojima, M., Megiddo, N., Noma, T., Yoshise, A.(1991).A Unified Approach
12. To Interior Point Algoirthms for Linear Complementarity Problems.
13. Germany: Springer Verlag. Moon, T.K., Stirling, W.C.(2000).Mathematical Methods and Algorithms for
14. Signal Processing. USA: Prentice-Hall,Inc. Nash, G., Sofer, A.(1996).Linear and Nonlinear Programmming.Singapore:
15. McGraw-Hill Companies,Inc.,. Nocedal, J., Wright, S.(1999).Numerical Optimization. Springer Series in
16. Operations Research, New York : Springer. Rardin, R.L.(1998).Optimization in Operations Research. New Jersey:
17. Prentice Hall,Inc. Render, B., Stair, R.M.(1997).Quantitative Analysis for Management. New
18. Jersey : Prentice-Hall,Inc., Sixth Edition. Roos, C., Terlaky, T., Vial, J. Ph.(1997).Theory and Algorithms for Linear
19. Optimization. An Interior Point Approach, England: John Wiley & Sons Ltd. Schrijver, A.(1998).Linear and Integer Programming. England:John
20. Wiley&Sons Ltd. Taha, H.(2000).Yöneylem Araştırması. 6. Basımdan Çeviri, Çev:Ş.Alp
21. Baray, Şakir Esnaf, İstanbul: Literatür Yayıncılık. Winston, W. L.(1994). Operations Research Applications and Algorithms. –
22. Belmont, Calif. : Duxbury Press. Wright, S. J.( 1997).Primal - Dual Interior Points Methods. The Society for
23. Industrial and Applied Mathematics, USA:Siam. Makaleler Andersen, E. D., Gondzio, J., Meszaros, C., Xu, X.(1996).
24. “Implementation of Interior Point Methods For Large Scale
25. Linear Programs”, Interior Point Methods of Mathematical
26. Programming, Netherlands: Kluwer Academic Publishers. Andersen, E. D., Ye, Y.(1996). “Combining Interior-point and Pivoting
27. Algorithms for Linear Programming”, Management Science, Vol.
28. ,No.12, Institute for Operations Research and Management Sciences. Arbel, A.(1994).“A Multiobjective Interior Primal – Dual Linear
29. Programming Algorithm” Computers Operations Research, Vol. 21,
30. No. 4, Great Britain: Elsevier Science Ltd., s. 433 – 445. Bal, H.(1995). “Using of Karmarkar Algorithm in Linear Goal Programming
31. 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
32. Survey”, Operations Research, Vol. 29, No.6, Operations Research
33. Society of America. Cavalier, T. M., C. Schall, K.(1987). “Implementing An Affine Scaling
34. Algorithm For Linear Programming”, Comput. Operations Research,
35. Vol.14, No.5, Great Britain :Pergamon Journals Ltd. Dodani, M. H., Babu, A. J. G.(1989).“Karmarkar”s Projective Method For
36. Linear Programming : A Computational Appraisal”, Computers
37. Industrial Engineering, Vol. 16, No.1, ., Great Britain: Pergamon Press plc. Gay, D. M.(1987).”A Variant of Karmarkar”s Linear Programming
38. Algorithm For Problems In Standart Form”, Mathematical
39. Programming 37,North Holland. Goldfarb, D., Todd, M.J.(1989). “Linear Programming”, Handbooks in
40. Operations Research and Management Science, Volume 1, Elsevier
41. Science Publishers B.V., Netherlands. Gonzaga, C. C.(1991). “ Large Step Path – Following Methods For Linear
42. Programming, Part I : Barrier Function Method ”, SIAM Journal on
43. Optinization, Vol.1, No.2, Society for Industrial and Applied Mathematics. Gonzaga, C. C.(1991). “ Large Step Path – Following Methods For Linear
44. Programming, Part II : Potential Reduction Method ”, SIAM Journal
45. on Optinization, Vol.1, No.2, SIAM. Güler, O., Ye, Y.(1993). “Convergence Behavior of Interior-point
46. Algorithms”, Mathematical Programming 60, North-Holland. Hertog, D.Den, Roos, C.(1991). “A Survey of search directions in interior
47. point methods for linear programming”, Mathematical Programming
48. 52, North-Holland. Karmarkar, N.(1984). “ A New Polynomial Time Algorithm For Linear
49. Programming”, Combinatorica, Vol.4. Murray, Walter(1989).“Methods For Large – Scale Linear Programming”,
50. Algorithms and Model Formulations in Mathematical Programming
51. Ed: Stein W. Wallace, Berlin : Springer – Verlag. Powell, M.J.D.(1993).“On The Number of Karmarkar”s Algorithm for
52. Linear Programming”, Mathematical Programming 62, North-Holland.
53. Rockett, A. M., Stevenson J.C.(1987). “Karmarkar Algorithm”, Byte, September.
54. Tardos, E.(1986).“A Strongly Polynomial Algorithm To Solve
55. Combinatorial Linear Programs”, Operations Research, Vol.34,
56. No.2, Operations Research Society of America. Tepecik, A.( 1998).”Geliştirilmiş Karmarkar Algoritması”,Gazi Ünv. Fen
57. Bil.Ens.Der., Cilt.11, No.4,Ankara. Ye, Y., Kojıma, M.(1987).“Recovering Optimal Dual Solutions in
58. Karmarkar”s Polynomial Algorithm For Linear Programming”,
59. Mathematical Programming 39, North-Holland.