Yöneylem araştırmasında şebeke modellerine vekil kısıt uygulamaları

Optimizasyon probleminin kısıtlarının tek bir vekil kısıt haline getirildiği gevşetmeye vekil gevşetme adı verilir. Tamsayılı programlama için Lagrange dual arama yöntemlerine benzer olarak, geleneksel vekil dual arama yöntemi de çarpanları güncellemek için yardımcı lineer programlama problemlerini kullanır. Bu yöntem, minimizasyon amaçlı problemin optimal amaç değerine bir alt sınır sağlar ve uygun çözümler kümesini genişletir. Bu alt sınır Lagrange gevşetmesinin sağladığı alt sınırdan daha büyük veya eşittir, dolayısıyla vekil gevşetme daha iyi bir yaklaşım sağlayabilir. Dualite boşluğu olması durumlarında, geleneksel yöntem ile problemin optimal amaç değeri bulunamayabilir. Bu durumda, lineer olmayan vekil kısıt yöntemleri kullanılabilir. Bu çalışmada, kaynak düğümlerinden varış düğümlerine minimum maliyetli uygun akışların belirlendiği minimum maliyetli akış problemleri üzerinde gevşetme stratejileri ve uygun parametre seçimleri tartışılmıştır. Ayrıca, çoklu sırt çantası modelleri için problem boyutlarını azaltan, çoklu vekil kısıtları kullanan ve yarılama algoritmalarına dayalı bir sezgisel geliştirilmiştir.