İç nokta ve simpleks algoritmalarının çözüm zamanı bakımından karşılaştırılması

Yöneylem araştırması uygulamalarında simpleks algoritması güçlü bir konuma sahiptir. Ne var ki simpleks algoritması üstel işlemli bir algoritma olduğundan değişken ve kısıt sayısı arttıkça işlem zamanı aşırı büyümektedir. Bu ve benzeri nedenlerle, alternatif olarak geliştirilen diğer algoritmalar ilgi odağı olmaktadır. Bu çalışmada, büyük-ölçekli sistemler için önerilen iç nokta algoritmalarının simpleks yöntemi ile çözüm zamanı bakımından karşılaştırması simulasyon yoluyla yapılacaktır.

Comparison of the interior point and simplex algorithms with respect to solution time

Simplex algorithm has the powerful position in the operational research applications. But the simplex is an exponentially processing algorithm and hence processing time increases extremely as the number of variables and constraints increases. By the case and-other similar reasons, the other algorithms developed as an alternative to simplex arouse interest time to time. In this study, a comparison of an interior point algorithm proposed for the large-scale systems and the simplex algorithm is given via the simulation in respect of their solution times.

___

1.Bal, H., Optimizasyon Teknikleri, Gazi Üniversitesi, Ankara (1995).
2.Gill, E. P., On Projected Newton Barrier Methods for Linear Programming and an Equivalance to Karmarkar's Projective Method, Mathematical Programming, Vol. 36, 183-209, (1986).
3.Nesterov, Y., Interior-point Methods: An old and new approach to nonlinear Programming, Mathematical Programming, Vol. 79, 285-297, (1997)
4.Alp, 1, Çok Amaçlı Karar Vermede Karmarkar Algoritmasının Kullanımı, Yöneylem Araştırması/ Endüstri Müh. Ulusal Kongresi, Bilkent, Ankara, (1994).
5.Lustig, I.J., Marsten, R.E. and Shanno, D.F., Interior Point Methods for Linear Programming Computational State of the Art, ORSA J. on Comput. (1994),6(1): 1-15.
6.Arbel A., Exploring Interior Point Linear Programming: Algorithms and Software, Cambridge, The MIT Press, (1993).
7.Kalai, G., Linear Ppogramming, the Simplex Algorithm and Simple Polytopes Mathematical Programming,,(1997) Vol. 79, 217-233.
8.Boris T. P., Introduction to Optimization, Optimization Software, Inc., Publications Division, New York,( 1987).