Stokastik Karma Tamsayılı Programlama — Ayrık ve Sürekli Kararlarla Belirsizlik Altında Optimizasyon
Stochastic Mixed-Integer Programming (SMIP) · Ayrıca şöyle bilinir: SMIP, Stochastic MIP, Mixed-Integer Stochastic Programming, SMILP
Stokastik Karma Tamsayılı Programlama (SMIP), maliyetler, talepler, kapasiteler gibi temel parametrelerin belirsiz olduğu ve bir senaryo kümesi üzerinde olasılık dağılımları olarak modellendiği durumlarda ikili, tamsayılı ve sürekli kararların en iyi karışımını bulan bir optimizasyon çerçevesidir. Kombinatoryal kısıtlamalara uyarken belirsizliğe karşı koruma sağlayan senaryo ağaçlarını veya beklenen değer hedeflerini gömerek klasik Karma Tamsayılı Programlamayı (MIP) genişletir.
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
Kararlar ayrık veya ikili seçimler içerdiğinde (yatırım yap/yapma, açılacak birim sayısı) ve temel girdi parametreleri ölçülebilir olasılık dağılımlarıyla gerçekten belirsiz olduğunda SMIP kullanın. Talep belirsizliği altında tedarik zinciri ağı tasarımı, enerji kapasitesi genişletme, sağlık tesisi planlaması ve afet müdahale ön konumlandırması için idealdir. Tüm kararlar sürekli olduğunda (bunun yerine stokastik LP kullanın), belirsizlik anlamlı bir şekilde dağılımlar olarak nicelendirilemediğinde, belirsizliği temsil etmek için gereken senaryo sayısı çözülemez model boyutlarına yol açtığında ve ayrıştırma mevcut olmadığında veya gerekli karar kalitesi için simülasyon tabanlı bir sezgisel yeterli olduğunda kullanmayın.
Güçlü yönler & sınırlılıklar
- Belirsizlik altında kombinatoryal ayrık kararları tek bir tutarlı optimizasyon modelinde ele alır.
- Tüm senaryolarda beklenen performansı dengeleyen korumalı ilk aşama planları üretir.
- VSS ve EVPI metrikleri, stokastik modellemenin değeri için şeffaf gerekçe sağlar.
- Ayrıştırma algoritmaları (L-şekilli, aşamalı koruma) büyük senaryo kümelerine ölçeklenebilir.
- Ticari çözücülerde (CPLEX, Gurobi) ve modelleme dillerinde (AMPL, Pyomo) geniş çapta desteklenir.
- Hesaplama karmaşıklığı, senaryo sayısı ve tamsayı değişkenleriyle kombinatoryal olarak artar; büyük örnekler, etkili ayrıştırma olmadan çözülemez olabilir.
- Açık olasılık dağılımları veya senaryo kümeleri gerektirir — yanlış belirtilmiş belirsizlik modelleri, örnek dışı performansı kötü olan çözümlere yol açar.
- İki aşamalı formülasyonlar, çok dönemli kararları aşırı basitleştirebilir; çok aşamalı SMIP önemli ölçüde daha zordur.
- Tamsayı ikinci aşama başvuru, standart Benders kesmelerinin kullandığı dışbükeyliği bozar ve özel tamsayı L-şekilli kesmeler gerektirir.
SSS
SMIP, normal Karma Tamsayılı Programlamadan nasıl farklıdır?
Normal MIP, sabit, bilinen parametreler altında optimize eder. SMIP, belirsiz parametreleri olasılıklarla bir senaryo kümesi olarak açıkça modeller, tüm senaryolarda beklenen performansı optimize ederken, ilk aşama kararlarının belirsizlik ortaya çıkmadan önce alınmasını sağlar.
Kaç senaryoya ihtiyacım var?
Evrensel bir kural yoktur. Bazı problemlerde 10-50 kadar az senaryo, kararlı ilk aşama kararları için yeterli olabilir; diğerleri binlerce gerektirebilir. Senaryo azaltma teknikleri ve kararlılık testleri (daha fazla senaryo ekledikçe optimal çözümün değişmediğini kontrol etmek) yeterliliği belirlemeye yardımcı olur.
L-şekilli yöntem nedir?
L-şekilli yöntem, stokastik programlar için uyarlanmış bir Benders ayrıştırmasıdır. İlk aşama değişkenleri ve senaryo alt problemleri üzerinde bir ana MIP'yi yinelemeli olarak çözer, yakınsayana kadar ana probleme optimallik ve fizibilite kesmeleri ekler. Tamsayı başvuru için, standart Benders kesmelerinin yerini tamsayı L-şekilli kesmeler alır.
L-şekilli yerine ne zaman aşamalı koruma kullanmalıyım?
Aşamalı koruma, alt problem yapısına göre değil, senaryoya göre ayrışır, bu da onu paralel hesaplama için çok uygun hale getirir. Senaryoların çok olduğu ve alt problemlerin büyük olduğu durumlarda ve algoritmanın bir küme üzerinde çalıştırılabildiği durumlarda tercih edilir. L-şekilli genellikle daha az, iyi yapılandırılmış senaryolar için tercih edilir.
SMIP iki aşamadan fazlasını ele alabilir mi?
Evet, ancak çok aşamalı SMIP, aşama sayısıyla üstel olarak büyüyen bir senaryo ağacı gerektirir ve ayrıştırma önemli ölçüde daha karmaşık hale gelir. Pratikte, çoğu uygulamalı SMIP modeli, çok dönemli dinamikleri yuvarlanan ufuk veya toplama yoluyla yaklaşık olarak temsil eden iki aşama kullanır.
Kaynaklar
- Birge, J. R., & Louveaux, F. (1997). Introduction to Stochastic Programming. Springer Series in Operations Research. New York: Springer. ISBN: 9780387982175
- Sen, S., & Higle, J. L. (2005). The C3 theorem and a D2 algorithm for large scale stochastic mixed-integer programming: Set convexification. Mathematical Programming, 104(1), 1–20. DOI: 10.1007/s10107-004-0566-z ↗
Bu sayfayı kaynak gösterin
ScholarGate. (2026, June 3). Stochastic Mixed-Integer Programming (SMIP). ScholarGate. https://scholargate.app/tr/simulation/stochastic-mixed-integer-programming
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.
- Karmaşık-Tamsayı ProgramlamaSimülasyon↔ karşılaştır
- Monte Carlo SimülasyonuKarar verme↔ karşılaştır
- Stokastik Dinamik ProgramlamaSimülasyon↔ karşılaştır
- Olasılıklı Doğrusal ProgramlamaSimülasyon↔ karşılaştır
- Belirsizlik Altında Stokastik Çok Amaçlı OptimizasyonSimülasyon↔ karşılaştır