Row generation techniques for approximate solution of linear programming problems

Bu tez çalışmasında, kısıt sayısı problem boyutuna göre çok fazla olan doğrusal programlama problemleri üzerinde kısıt türetme teknikleri uygulandı. Eklenen bir kısıtın amaç fonksiyon değerinde ortaya çıkardığı değişim için bir alt sınır değeri hesaplanabileceği ortaya kondu. Her kısıt türetme adımında, problemin olurlu bölgesinde büyük bir daralma ve amaç fonksiyon değerinde büyük bir değişim sağlayabilmek için bu alt sınır hesabı kısıt türetme adaylarının karşılaştırılması için kullanıldı. Problem çözümüne hızlı bir başlangıç yapabilmek için, ilk doğrusal programlama alt probleminin kısıtlarının etkin bir biçimde seçimini sağlayacak yöntemler araştırıldı. İlk alt problem çözümünün asıl doğrusal programlama probleminin olurlu bölgesine yakın olmasını sağlayacak, mümkün olduğunca küçük bir başlangıç kısıt alt kümesinin elde edilmesinde kullanılabilecek yöntemler değerlendirildi. Asıl problemin en iyi çözümüne yeterince yakın bir çözüm noktasında kısıt türetimine son verebilmek için yaklaşım tasarımları ele alındı ve karşılaştırıldı. Bu çalışmada sunulan kısıt türetme algoritması bir hızlı başlangıç tekniği ve yaklaşım tasarısıyla geliştirilerek bilgisayar üzerinde uygulandı. Bu uygulama algoritmanın hesaplama süresinin ve türettiği kısıt sayısının sınanmasında kullanıldı. Hesaplama zamanları iki verimli temel simpleks yöntemi ile karşılaştırıldı. Karşılaştırmalara göre, kısıt türetme algoritmasının bu iki yöntemden en az birinden, özellikle kısıt sayısı büyük olduğunda, daha hızlı çalıştığı ortaya çıktı.