İçeriğe atla
Arama sonuçlarına dön

Sütun Üretimi (Dantzig-Wolfe)

Ortaya koyan
George B. Dantzig and Philip Wolfe
Yıl
1960
Tür
algorithm
Aile
Optimization

Bu metin makine çevirisidir ve henüz incelenmedi. Asıl metni İngilizce oku

Yazı boyutu

Ne işe yarar?

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.

Yöntemin mantığı

Bu yöntem, birçok büyük optimizasyon probleminin özel bir yapıya sahip olduğunu fark eder: çok sayıda değişken ancak az sayıda gerçekten önemli kısıt veya doğal olarak ayrıştırılabilir alt problemler. Tüm olası değişkenlerle tam problemi çözmek yerine, sütun üretimi yalnızca umut vadeden az sayıda sütunu (değişkeni) korur. Azaltılmış maliyetler ve problem yapısı kullanılarak çözülen fiyatlandırma problemi, ana çözümü iyileştiren yeni sütunları belirler. En umut vadeden sütunları iteratif olarak ekleyerek, algoritma tüm sütunları aynı anda işleme hesaplama yükünden kaçınarak verimli bir şekilde bir çözüm oluşturur.

Tarih

Dantzig ve Wolfe, 1960 yılında lineer programlar için ayrıştırma ilkesini tanıttı ve teorik temeli oluşturdu. Gilmore ve Gomory (1961) bunu kesme stoğu problemine uygulayarak pratik gücünü gösterdi. Yöntem, 1980'ler-90'larda araç rotalama ve çizelgeleme problemleri için önem kazandı. Dallanma-ve-sınır ile entegrasyonu, dallanma-ve-fiyat algoritmaları oluşturarak tamsayı programlamaya uygulanabilirliğini genişletti. Modern uygulamalar arasında havayolu mürettebatı çizelgeleme, gemi rotalama ve büyük ölçekli lojistik optimizasyonu yer almaktadır.

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.

Sınırlar ve dikkat edilmesi gerekenler

  • 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ı

Kaynak metnin koşulları, bağımsız bilimsel inceleme veya analiz motoru doğrulaması yerine geçmez.

Güçlü yönleri

  • 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)

Uygulama alanları

  • Kesme stoğu problemi: malzemeyi gerekli boyutlarda keserken israfı en aza indirme
  • Araç rotalama: zaman pencereleri ve kapasite kısıtlamaları ile teslimat ve nakliye için rotaları optimize etme
  • Mürettebat çizelgeleme: toplam maliyeti en aza indirerek mürettebat üyelerini uçuşlara veya vardiyalara atama
  • Kutu paketleme: israfı ve kutu sayısını en aza indirmek için eşyaları konteynerlere verimli bir şekilde paketleme
  • Vardiya çizelgeleme: uygunluk ve tercih kısıtlamalarına saygı duyarak işçileri vardiyalar boyunca çizelgeleme
  • Havayolu planlaması: uçuş çizelgeleme, mürettebat atamaları ve uçak bakım koordinasyonu

Nasıl çalışır?

Nasıl çalışır?

1

Başlangıçta, ilk uygun çözüm için gerekli sütunların bir alt kümesini içeren sınırlı bir ana problemle başlayın.

2

Mevcut sınırlı ana problemin dualini simpleks tablosunu kullanarak çözün. Azaltılmış maliyetleri belirleyin ve negatif azaltılmış maliyete sahip değişkenleri bulmak için fiyatlandırma alt problemini kurun (minimize etmek için).

3

Fiyatlandırma alt problemini özel yapısını kullanarak çözün. Negatif azaltılmış maliyete sahip yeni bir sütun bulunursa, onu ana probleme ekleyin ve tekrarlayın. İyileştirici bir sütun yoksa, mevcut çözüm optimaldir.

Sık yapılan hatalar

  • Sütun üretiminden elde edilen verimlilik kazançlarını geçersiz kılan verimsiz bir fiyatlandırma alt problemi algoritması seçmek
  • Ayrıştırmaya uygun problem yapısını tanımamak, bu da kötü performansa yol açar
  • Yetersiz yakınsama tespiti veya çok katı tolerans, iterasyonları boşa harcar
  • Kuyruk etkisini gidermek için stabilizasyon teknikleri uygulamamak

Sık sorulan sorular

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.

İlgili yöntemler

Kaynaklar

  1. Dantzig, G. B., & Wolfe, P. (1960). Decomposition principle for linear programs. Operations Research, 8(1), 101-111.

    DOI kaynağını aç
    Kopyalandı.
  2. Gilmore, P. C., & Gomory, R. E. (1961). A linear programming approach to the cutting-stock problem. Operations Research, 9(6), 849-859.

    DOI kaynağını aç
    Kopyalandı.