Stokastik Tam Sayılı Programlama — Belirsizlik Altında Ayrık Kararların Optimizasyonu
- Ortaya koyan
- Dantzig, G. B.; Beale, E. M. L.
- Yıl
- 1955
- Tür
- Optimization under uncertainty with discrete decisions
- Aile
- Simulation / optimization
Bu metin makine çevirisidir ve henüz incelenmedi. Asıl metni İngilizce oku
Ne işe yarar?
Stokastik Tam Sayılı Programlama (STSP), tam sayılı (ayrık) karar değişkenlerini açık olasılıksal belirsizlik modellemesiyle birleştiren bir optimizasyon çerçevesidir.
Belirsizlik çözülmeden önce bazı kararların verilmesi gerektiği gerçeğini hesaba katarak, gelecekteki senaryo dağılımları üzerinden beklenen maliyeti minimize eden (veya beklenen faydayı maksimize eden) en iyi şimdiki (here-and-now) kararı arar.
Yöntemin mantığı
Birçok gerçek karar hem ayrık (bir tesis inşa et veya etme; bir işçi ata veya atama) hem de belirsizdir (talep, maliyetler ve kısıtlar karar anında bilinmez). STSP her iki zorluğu eş zamanlı olarak ele alır. Belirsiz geleceği, ilişkili olasılıklara sahip senaryolar kümesi olarak modeller, ardından ortalama olarak en iyi performansı gösteren — veya en kötü durum sonuçlarına karşı korunma sağlayan — tam sayılı çözümü bulur. Stokastik doğrusal programlamanın aksine, ayrık yapı problemi kombinatoryal olarak daha zor hale getirir, ancak üretilen kararlar yuvarlama veya yaklaştırma olmaksızın doğrudan uygulanabilir.
Tarih
Stokastik programlama, belirsizlik altındaki doğrusal programlar için iki aşamalı geri kazanım modellerini bağımsız olarak öneren Dantzig (1955) ve Beale (1955)'e dayanır. Tam sayılı uzantı, tam sayılı programlamanın 1960'lar-1980'ler boyunca olgunlaşmasıyla ortaya çıktı. Birge ve Louveaux'nun 1997 tarihli ders kitabı alanı kodlaştırdı ve Kleywegt vd. (2002), büyük ölçekli stokastik ayrık optimizasyon için standart hesaplama yaklaşımı olarak Örnek Ortalama Yaklaşımı'nı oluşturdu.
Ne zaman kullanılır?
Kararların doğası gereği ayrık olduğu (ikili seçimler, tam birim tahsisleri, rota atamaları) ve karar anında temel parametrelerin belirsiz olduğu durumlarda Stokastik Tam Sayılı Programlama kullanın. Kapasite planlama, tedarik zinciri ağ tasarımı, talep belirsizliği altında çizelgeleme, enerji sevkiyatı ve rastgele verimlerle kaynak tahsisi için uygundur. Tüm değişkenlerin sürekli olduğu (stokastik doğrusal programlama yeterlidir), belirsizliğin ihmal edilebilir olduğu veya karar vermeden önce tamamen gözlemlenebildiği, problem ölçeğinin ayrıştırma altyapısı olmadan senaryo numaralandırmasını hesaplama açısından olanaksız kıldığı veya yalnızca tek bir deterministik senaryonun ilgili olduğu durumlarda KULLANMAYIN.
Sınırlar ve dikkat edilmesi gerekenler
- Hesaplama karmaşıklığı, senaryo ve tam sayılı değişken sayısı ile hızla artar; büyük örnekler NP-zorludur.
- Senaryo üretimi, güvenilir olasılık dağılımları gerektirir; bunlar sınırlı veriden elde edilmesi veya tahmin edilmesi zor olabilir.
- Çok aşamalı uzantılar (ikiden fazla aşama), senaryo ağaçlarında üssel büyüme ile karşı karşıya kalır ve nadiren üç aşamadan fazlası için çözülebilirdir.
- Geri kazanım fizibilitesini, öngörülememe kısıtlarını ve ceza yapılarını doğru bir şekilde belirtmek için modelleme becerisi gereklidir.
Kaynak metnin koşulları, bağımsız bilimsel inceleme veya analiz motoru doğrulaması yerine geçmez.
Güçlü yönleri
- Nokta tahminleri yerine belirsizliği açıkça modeller, gerçekleşen senaryolara karşı dayanıklı çözümler üretir.
- Ayrık ve ikili kararları doğal olarak ele alır, bu nedenle çözümler sonradan yuvarlama olmaksızın doğrudan uygulanabilir.
- İki aşamalı çerçeve, stratejik birinci aşama kararlarını operasyonel ikinci aşama geri kazanım eylemlerinden temiz bir şekilde ayırır.
- Kaynak tedariki, ceza maliyetleri ve düzeltici çizelgeleme dahil olmak üzere zengin geri kazanım yapılarını destekler.
- İstatistiksel kalite sınırları (SAA aracılığıyla), uygulayıcıların nicelendirilmiş güvenle optimumluğa yakınlığı belgelendirmesine olanak tanır.
Uygulama alanları
- Stokastik talep ve teslim süreleri altında tedarik zinciri ağ tasarımı
- Belirsiz yenilenebilir çıktı ile güç üretim genişletme planlaması
- Değişken prosedür süreleri altında hastane ameliyathane çizelgelemesi
- Stokastik uçuş gecikmeleriyle havayolu mürettebat çizelgelemesi
- Afetlerden önce yardım malzemelerinin önceden konumlandırılmasına yönelik insani lojistik
- Ayrık varlık seçimi ve senaryo bazlı getirilerle finansal portföy optimizasyonu
Nasıl çalışır?
Nasıl çalışır?
Birinci aşama problemini formüle edin: belirsizlik ortaya çıkmadan önce x tam sayılı (veya karma tam sayılı) karar değişkenlerini seçin. Hem anlık maliyeti hem de tüm senaryolar üzerindeki beklenen geri kazanım maliyetini içeren bir amaç fonksiyonu tanımlayın. x'i fizibilite koşullarına bağlayan kısıtlar burada belirtilir.
Formül
\min_{x \in \mathbb{Z}^n} c^T x + \mathbb{E}_\xi[Q(x, \xi)]Belirsizliği sonlu sayıda senaryo aracılığıyla temsil edin. Her senaryo, rastgele parametrelere (talep seviyeleri, maliyetler, kaynak kullanılabilirliği) belirli değerler atar. Senaryolar, tarihsel örnekleme, uyarlanmış dağılımlardan Monte Carlo çekimleri veya uzman tarafından tanımlanmış temsili vakalar aracılığıyla üretilebilir. Her senaryo, toplamı bire eşit olan bir olasılık ağırlığı taşır.
Standart iki aşamalı formülasyonda, x sabitlendikten ve xi senaryosu gerçekleştikten sonra, bir geri kazanım (ikinci aşama) problemi y düzeltici eylemlerini belirler. Geri kazanım problemi genellikle bir doğrusal veya tam sayılı programdır. Tam model, c^T x artı beklenen geri kazanım maliyeti E[Q(x, xi)]'yi minimize eder.
Formül
Q(x, \xi) = \min_{y \geq 0} q(\xi)^T y \;\text{ s.t. } W(\xi)y = h(\xi) - T(\xi)xHer x için geri kazanım maliyetini değerlendirmek üzere senaryo alt problemlerini çözün. Teknikler arasında dallanma ve sınırlandırma (branch-and-bound), Benders ayrıştırması, Lagrange gevşetmesi ve Örnek Ortalama Yaklaşımı (Sample Average Approximation - SAA) yöntemi bulunur. Büyük senaryo ağaçları için ayrıştırma algoritmaları senaryolar arasındaki blok yapısından yararlanır.
Beklenen geri kazanım maliyetini tahmin etmek için alt problem sonuçlarını toplayın. SAA'da bu, S örneklenmiş senaryo üzerinden ortalamadır. Elde edilen yaklaşım, S büyüdükçe gerçek beklentiye yakınsar. Çözüm kalitesi üzerindeki istatistiksel sınırlar, örnek varyansından hesaplanabilir.
Formül
\mathbb{E}_\xi[Q(x,\xi)] \approx \frac{1}{S} \sum_{s=1}^{S} Q(x, \xi_s)Optimumluk veya optimumluğa yakınlık durumunu, optimumluk boşlukları, yakınsama kriterleri veya SAA'dan elde edilen istatistiksel güven aralıkları aracılığıyla doğrulayın. Boşluk kabul edilebilir değilse, senaryo kümesini iyileştirin, örneklem boyutunu artırın veya gevşetmeleri sıkılaştırın. Birinci aşama çözümü x* ve beklenen toplam maliyetini raporlayın.
Sık yapılan hatalar
- Çok az senaryo kullanmak aşırı güvenli çözümler üretir; çok fazla senaryo kullanmak problemi hesaplama açısından çözülemez hale getirir — SAA yakınsama tanılarıyla dengeleyin.
- İkinci aşamada gereklilik varken bütünlüğü göz ardı etmek, iyimser maliyet tahminlerine ve uygulanamaz geri kazanım eylemlerine yol açar.
- Parametrelerin (örneğin, ilişkili talep ve fiyat) korelasyonlu olduğu durumlarda senaryo bağımsızlığını varsaymak, beklenen maliyet tahminine sistematik yanlılık katar.
- Çok aşamalı problemlerde öngörülememe kısıtlarını unutmak, modelin pratikte mevcut olmayacak gelecekteki bilgiden yararlanmasına izin verir.
Sık sorulan sorular
Stokastik Tam Sayılı Programlama, sağlam optimizasyondan nasıl farklıdır?
STSP, olasılık ağırlıklı bir senaryo kümesi üzerinden beklenen maliyeti minimize eder, bazı senaryoların olasılık dışı olmaları durumunda yüksek maliyetle sonuçlanabileceğini kabul eder. Sağlam optimizasyon, bir belirsizlik kümesi üzerinden en kötü durum maliyetini minimize eder ve olasılıksal varsayımlarda bulunmaz. STSP bir olasılık dağılımı gerektirir; sağlam optimizasyon yalnızca bir belirsizlik kümesi gerektirir. STSP genellikle daha az muhafazakardır ancak daha fazla veri gerektirir.
Pratikte kaç senaryo gereklidir?
Bu, problemin boyutuna ve istenen doğruluğa bağlıdır. Örnek Ortalama Yaklaşımı (SAA) yaklaşımı, optimumluk boşluğu üzerinde istatistiksel güven aralıkları sağlar. Tipik uygulamalı çalışmalar onlarca ila binlerce senaryo kullanır; yakınsama tanıları (sınır tahmin edicisinin varyansı) seçimi yönlendirir. Yapılandırılmış problemler için senaryo azaltma teknikleri (örneğin, Heitsch-Romisch), senaryo sayılarını önemli ölçüde azaltabilir.
Stokastik Tam Sayılı Programlama iki aşamadan fazlasını ele alabilir mi?
Evet, ancak çok aşamalı STSP önemli ölçüde daha zordur. Senaryo ağacı aşamalarla üssel olarak büyür ve her düğümde öngörülememe kısıtlarının uygulanması gerekir. Pratikte, çözülebilir uygulamalar için üç aşamalı modeller normdur; bunun ötesinde, genellikle yuvarlanan ufuk veya senaryo ağacı azaltma gibi yaklaşımlar gereklidir.
Stokastik Tam Sayılı Programlama modellerini hangi yazılımlar çözebilir?
Yaygın çözücüler arasında CPLEX ve Gurobi (AMPL, Julia'da JuMP veya Python'da PuLP/Pyomo gibi cebirsel modelleme dilleri aracılığıyla), senaryo ayrıştırmasını destekleyenler bulunur. Özel stokastik programlama çerçeveleri arasında PySP (Python), SMPS format çözücüleri ve SAA ile ilerici gizlemeyi uygulayan Julia paketi StochasticPrograms.jl bulunur.
Stokastik Tam Sayılı Programlama ile Stokastik Karma Tam Sayılı Programlama aynı mıdır?
Stokastik Tam Sayılı Programlama daha geniş sınıftır; Stokastik Karma Tam Sayılı Programlama (SKTSP), özellikle bir veya her iki aşamada bazı değişkenlerin sürekli, diğerlerinin ise tam sayılı olduğu modelleri ifade eder. SKTSP pratikte en genel ve en sık karşılaşılan formdur.
İlgili yöntemler
Kaynaklar
Birge, J. R., & Louveaux, F. (1997). Introduction to Stochastic Programming. Springer, New York.
ISBN: 978-1-4614-0237-4Kopyalandı.Kleywegt, A. J., Shapiro, A., & Homem-de-Mello, T. (2002). The sample average approximation method for stochastic discrete optimization. SIAM Journal on Optimization, 12(2), 479-502.
DOI kaynağını açKopyalandı.