You are here

Home » Content

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

Journal Name:

  • Dumlupınar Üniversitesi Sosyal Bilimler Dergisi

Publication Year:

  • 2003

Key Words:

Keywords (Original Language):

Author NameUniversity of AuthorFaculty of Author
Abstract (2. Language): 
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.
Bookmark/Search this post with
Abstract (Original Language): 
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.
FULL TEXT (PDF): 
PDF icon arastirmax-ic-nokta-algoritmalari-dogrusal-programlamaya-uygulanmasi.pdf
  • 9
109-128
  • Turkish

REFERENCES

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.
42.,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.
18
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.
19
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.

Thank you for copying data from http://www.arastirmax.com