Karmarkar-iç nokta algoritması ve bir üretim işletmesinde uygulama denemesi

Abstract

1980'Ii yıllarda Yöneylem Araştırması'nda önemli bir gelişme, Doğrusal Programlama (DP) problemlerinin çözümü için iç nokta algoritmalarının ortaya çıkmasıdır. Karmarkar-İç Nokta AIgoritması, 1984'te Narendra Karmarkar tarafından geliştirilmiş olan polinom zamanlı bir algoritmadır. Karmarkar Algoritması, tanımlanan bir uygun çözümden başlayıp; her bir adımda uygun bölgenin iç noktalarında var olan daha iyi bir çözüme giderek optimal çözüme ulaşmaya çalışır. Çalışmamızın amacı, doğrusal programlama probleminin kısa sürede çözülmesinde Karmarkar- İç Nokta AIgoritmasının etkinliğinin gösterilmesidir. Çalışma üç bölümden oluşmaktadır. Birinci bölümde, iç nokta algoritmalarının teorisi, tarihsel gelişimi ve sınıflandırılması konularına yer verilecek olup; bu konularda bilgi toplanmaya çalışılmıştır. ikinci bölümde, Karmarkar-İç Nokta Algoritmasına ilişkin temel kavramlar açıklanmaya çalışılmıştır. Daha sonra, Karmarkar-İç Nokta Algoritmasının adımları, üstünlüğü ve algoritmaya bağlı olarak geliştirilen bazı etkin algoritmalar hakkında bilgi verilmeye çalışılmıştır. Üçüncü bölümde ise, ETİ Gıda Grubunun üretim planlama bölümünde bir doğrusal programlama modeli kurularak, Karmarkar-İç Nokta Algoritması ve etkin bir iç nokta algoritması olan Mehrotra Tahminci-Düzeltici AIgoritması ile çözülmeye çalışılacaktır. Modelin çözümü için, MOSEK, PCx, XPRESS-MP/Barrier ve XPRESS-MP/Simplex yazılımlarından yararlanılmıştır. Çözüm sonucunda işletmede üretilen ürünlere ilişkin minimum maliyetli bir aylık üretim planı hazırlanmıştır.