Sütun Üretimi (Dantzig-Wolfe)
Column Generation (Dantzig-Wolfe Decomposition) · Ayrıca şöyle bilinir: Dantzig-Wolfe decomposition, column generation method
George B. Dantzig ve Philip Wolfe tarafından 1960 yılında geliştirilen Sütun Üretimi, özel yapıya sahip büyük ölçekli lineer programlama problemlerini çözmek için güçlü bir optimizasyon tekniğidir. Dantzig-Wolfe Ayrıştırması olarak da bilinen bu yöntem, problemi bir ana probleme (değişkenlerin/sütunların alt kümesiyle sınırlı) ve bir fiyatlandırma alt problemine (yeni değişkenleri belirleyen) ayrıştırır, yalnızca ilgili sütunları tanıtarak çözümü iteratif olarak iyileştirir.
Tam yöntemi oku
Bu bölümü okumak için ücretsiz hesapla giriş yapın.
Yöntem haritası
İlişkili yöntemlerin komşuluğu — keşfetmek için bir düğüm seçin.
Ne zaman kullanılır
Özellikle değişken sayısı çok büyük ancak optimal çözüme küçük bir alt kümenin hakim olduğu özel yapıya sahip büyük ölçekli lineer programları çözerken sütun üretimini uygulayın. Kesme stoğu problemleri, araç rotalama, mürettebat çizelgeleme ve kutu paketleme için idealdir. Fiyatlandırma problemi çözümünü verimli bir şekilde sağlayan problem yapısı olduğunda kullanın. Yapısal olarak faydalanılamayan veya orta büyüklükteki problemler için standart LP çözücüler daha pratiktir.
Güçlü yönler & sınırlılıklar
- Sütun patlaması nedeniyle standart yöntemlerle çözülemeyen büyük ölçekli problemleri çözer
- Yalnızca ilgili sütunları üretmek için problem yapısından yararlanır
- İterasyon sırasında çözüm kalitesi hakkında sınırlar sağlar
- Özel alt yapıya sahip problemler için doğal olarak uygundur (özdeş alt problemler, simetri)
- Tamsayı programları için dallanma-ve-sınır ile entegre edilebilir (dallanma-ve-fiyat)
- Fiyatlandırma alt problemi çözümünü etkinleştiren problem yapısı gerektirir
- Yakınsama yavaş olabilir, özellikle optimalliğe yakın (kuyruk etkisi)
- Fiyatlandırma alt problemi çözümü güvenilir ve verimli olmalıdır, aksi takdirde verimlilik kazançları kaybolur
- Standart LP yöntemlerinden daha fazla uygulama karmaşıklığı
- Büyük ikili değerler ve azaltılmış maliyetlerle sayısal kararlılık sorunları
SSS
Sütun üretiminde fiyatlandırma problemi nedir ve azaltılmış maliyetlerle nasıl ilişkilidir?
Fiyatlandırma problemi, ana çözümü iyileştiren negatif azaltılmış maliyete sahip yeni değişkenleri (sütunları) belirler. Azaltılmış maliyet değerleri, sınırlı ana problemin dualinden gelir ve fiyatlandırma alt problemindeki aramayı yönlendirir.
Sütun üretimi neden tüm sütunlarla tam problemi çözmekten daha iyidir?
Birçok problemde, potansiyel sütun sayısı üstel veya sonsuzdur, bu da hepsini listelemeyi imkansız hale getirir. Sütun üretimi, yalnızca gerekli sütunları isteğe bağlı olarak üretir, bu da hesaplama yükünü önemli ölçüde azaltır.
Kuyruk etkisi nedir ve nasıl azaltılabilir?
Kuyruk etkisi, sütun üretimi optimalliğe yakın yavaş ilerleme kaydettiğinde, minimum iyileştirme ile birçok sütun ürettiğinde meydana gelir. Stabilizasyon teknikleri (ikili yumuşatma, güven bölgesi yöntemleri, kesme stratejileri) etkisini azaltır.
Dallanma-ve-fiyat, sütun üretimini tamsayı programlamaya nasıl genişletir?
Dallanma-ve-fiyat, sütun üretimini dallanma-ve-sınır ile birleştirir: her düğümde, sütun üretimi LP gevşemesini çözer ve dallanma kararları LP çözümleri kesirli olduğunda problemi daha fazla kısıtlar.
Kaynaklar
- Dantzig, G. B., & Wolfe, P. (1960). Decomposition principle for linear programs. Operations Research, 8(1), 101-111. DOI: 10.1287/opre.8.1.101 ↗
- Gilmore, P. C., & Gomory, R. E. (1961). A linear programming approach to the cutting-stock problem. Operations Research, 9(6), 849-859. DOI: 10.1287/opre.9.6.849 ↗
Bu sayfayı kaynak gösterin
ScholarGate. (2026, June 3). Column Generation (Dantzig-Wolfe Decomposition). ScholarGate. https://scholargate.app/tr/operations-research/column-generation
Hangi yöntem?
Bu yöntemi en yakın akrabalarının yanına koyup yan yana okuyun — kütüphane kitapları masaya serer; seçim sizindir.
- Benders AyrıştırmasıYöneylem araştırması↔ karşılaştır
- Simpleks YöntemiYöneylem araştırması↔ karşılaştır