Karmarkar algoritması ve çok amaçlı programlamaya uygulanması

Abstract

Özet Bu çalışma, üç ana bölümden oluşmuştur. İlk bölümde son yılların oldukça popüler konusu olan, mucidi (N. Karmarkar) tarafından Simplex metodundan 50-100 misli daha hızlı olduğu söylenen Karmarkar Algoritması bütün detayları ile incelenmiştir. İkinci bölümde, çözümü bilinmeyen standard formdaki LP problemlerini göz önüne alarak, gerçek Primal ve Dual çözümlere yakınsayan yaklaşık primal ve dual çözümler oluşturan, `Değiştirilmiş Karmarkar Algoritması` hesaplanmış örneklerle açıklanmıştır. Üçüncü ve son ana bölümde ise Affine-Scaling Primal Algoritması olarak ta bilinen değiştirilmiş karmarkar algoritmasına dayanan bir çok amaçlı LP algoritması sunulmuştur. Herbir amaca ait projekte edilmiş gradientlerin konvex kombinezonunun kullanımı ve bu birleştirilmiş tek doğrultu boyunca yeni iterasyonlann nasıl elde edileceği açıklanmıştır. iv

ABSTRACT This study consists of three main parts. In the first part, Karmarkar's Algorithm, which was devised by Karmakar, is studied in details. This algorithm is 50-100 times faster than that of simplex method. In the second part considering LP problem in the standard form of which solution in not known Modified Karmarkar Algorithm which approximates primal and dual solutions as well as finding them is explained giving computational examples. In the last part, Multiobjective Linear Programming algorithm that is based on modified Karmarkar's algorithm known as the Affine Scaling Primal Algorithm is given. The use of convex combination of the projected gradients is shown for every objective. It was explained that how we can step toward the next iterate along combined direction.