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

Olasılıklı Doğrusal Programlama — Rastgele Parametrelerle Belirsizlik Altında Optimizasyon

Ortaya koyan
George B. Dantzig
Yıl
1955
Tür
Stochastic optimization model
Aile
Simulation / optimization

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

Yazı boyutu

Ne işe yarar?

Olasılıklı Doğrusal Programlama (ODP) (İng: Stochastic Linear Programming - SLP), klasik doğrusal programlamayı, maliyetler, talepler, kaynak mevcudiyeti gibi bazı model parametrelerinin belirsiz olduğu ve rassal değişkenler olarak modellendiği ayarlara genişletir.

Olasılık dağılımları üzerinden beklenen maliyetleri optimize ederek, ODP, tek bir varsayılan dünya durumu için değil, bir dizi olası gelecek için uygun ve optimuma yakın kalan kararlar üretir.

Yöntemin mantığı

Klasik doğrusal programlama, her katsayının kesin olarak bilindiğini varsayar. Pratikte, gelecekteki talep, fiyatlar ve verimler belirsizdir. ODP bu belirsizliği doğrudan modele dahil eder: tek bir sabit senaryo için optimizasyon yapmak yerine, planlamacı önce birinci aşama eylemleri şimdi belirler, hangi senaryonun gerçekleştiğini gözlemler, ardından herhangi bir eksikliği veya fazlalığı gidermek için tedbir eylemleri alır. Amaç fonksiyonu, taahhüt maliyetleri ile beklenen tedbir maliyetlerini dengeleyerek tüm senaryolar üzerinden toplam beklenen maliyeti en aza indirir. Bu, gerçek yönetsel mantığı yansıtır — bugün ne kadar ön sipariş vereceğinize karar verirsiniz ve yarın daha pahalıya daha fazla alabilir veya fazlalığı indirimli satabilirsiniz.

Tarih

Olasılıklı programlama, simplex yöntemini geliştirmesinden kısa bir süre sonra 1955'te iki aşamalı modeli tanıtan George Dantzig tarafından öncülük edildi. Beale (1955) bağımsız olarak benzer fikirler önerdi. Alan, Birge ve Louveaux'nun etkili 1997 ders kitabı ve 1960'lar-1980'lerde L-şekilli (Benders) ayrıştırma algoritmasının geliştirilmesiyle sistematik hale getirildi. ODP, dünya çapında enerji, lojistik ve finansta operasyonel kararların temelini oluşturmaktadır.

Ne zaman kullanılır?

ODP'yi şu durumlarda kullanın: (1) anahtar girdi parametreleri gerçekten belirsizse ve bir olasılık dağılımı veya ampirik senaryo kümesi ile karakterize edilebiliyorsa; (2) belirsizlik çözülmeden önce kararlar alınmalı, ancak sonrasında maliyetle düzeltici eylemler mümkünse; (3) amaç fonksiyonu ve kısıtlar karar değişkenlerinde doğrusalsa. Tipik uygulamalar arasında üretim planlaması, tedarik zinciri tasarımı, enerji sevkiyatı ve portföy optimizasyonu yer alır. ODP'yi şu durumlarda KULLANMAYIN: belirsizlik olasılıksal olarak ölçülemiyorsa (bunun yerine sağlam optimizasyon kullanın); kararlar ve sonuçlar arasındaki ilişki doğrusal olmayan veya tamsayı ise (olasılıklı MIP veya olasılıklı dinamik programlama kullanın); senaryo kümesi listelenecek kadar büyükse ve ayrıştırma hesaplama açısından imkansızsa; veya basit bir deterministik hassasiyet analizi belirsizlik etkisini anlamak için yeterliyse.

Sınırlar ve dikkat edilmesi gerekenler

  • Belirsiz parametreler için bir olasılık dağılımı veya senaryo kümesi belirtilmesini gerektirir — bu dağılımsal varsayımın doğrulanması genellikle zordur.
  • Hesaplama yükü, senaryo ve birinci aşama değişkenlerinin sayısıyla hızla artar; büyük problemler ayrıştırma ve önemli çözücü kaynakları gerektirir.
  • Doğrusal amaç fonksiyonu ve kısıtlarla sınırlıdır; doğrusal olmayan veya tamsayı yapıları, daha fazla karmaşıklık ekleyen uzantılar gerektirir.
  • Beklenen değer amaç fonksiyonu kuyruk risklerini göz ardı edebilir; riskten kaçınan varyantlar (CVaR, şans kısıtları) modelleme ve hesaplama ek yükü getirir.

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

Güçlü yönleri

  • Olasılıksal belirsizliği doğrudan optimizasyona dahil ederek, tek bir varsayılan gelecek yerine senaryolar boyunca sağlam kararlar üretir.
  • İki aşamalı çerçeve, gerçek karar süreçlerini yakından yansıtır: şimdi taahhüt et, sonra tedbirle uyum sağla.
  • Olasılıklı Çözümün Değeri (VSS) ve EVPI, belirsizliği modellemenin faydasını iletmek için ilkeli metrikler sağlar.
  • Olgun algoritmalar (L-şekilli / Benders ayrıştırması) ve ticari çözücüler (CPLEX, Gurobi) tarafından iyi desteklenir.
  • Ayrıştırma yoluyla büyük pratik problemlere ölçeklenir; senaryolar arasında paralelleştirilebilir.

Uygulama alanları

  • Belirsiz yenilenebilir üretim ve talep altında elektrik güç sistemi planlaması ve birim taahhüdü.
  • Belirsiz müşteri talebi, teslim süreleri veya nakliye maliyetleri ile tedarik zinciri ağı tasarımı.
  • Belirsiz yağış ve emtia fiyatları altında ürün ve sulama planlaması.
  • Bütçe ve düzenleyici kısıtlar altında belirsiz varlık getirileri ile finansal portföy optimizasyonu.
  • Belirsiz yolcu talebi altında havayolu gelir yönetimi ve mürettebat çizelgeleme.
  • Belirsiz afet senaryoları öncesinde insani yardım lojistiği için yardım malzemelerinin önceden konumlandırılması.

Nasıl çalışır?

Nasıl çalışır?

1

İki aşamalı modeli formüle edin: birinci aşama değişkenleri x, belirsizlik çözülmeden önce alınan şimdiki kararları temsil eder; amaç fonksiyonu, birinci aşama maliyeti c^T x artı rassal vektör xi üzerinden beklenen tedbir maliyeti E[Q(x,xi)]'yi en aza indirir. Kısıtlar Ax = b, senaryodan bağımsız olarak birinci aşama kararları için geçerli olmalıdır.

Formül
\min_{x} c^T x + \mathbb{E}_\xi[Q(x, \xi)] \quad \text{s.t. } Ax = b,\; x \geq 0
2

Rassal vektör xi'yi, toplamı 1 olan her biri p_s olasılığa sahip ayrık bir senaryo kümesi {xi_1, ..., xi_S} aracılığıyla temsil edin. Senaryolar, geçmiş verilerden, uzman görüşlerinden veya Monte Carlo örneklemesinden çekilebilir. Senaryo kümesinin kalitesi, çözüm kalitesini kritik olarak belirler; problem boyutunu yönetilebilir tutmak için yaygın olarak senaryo azaltma teknikleri (örneğin, Wasserstein mesafesi kümelemesi) uygulanır.

3

Her xi_s senaryosu için, tedbir alt problemi şu şekilde çözülür: birinci aşama kararı x verildiğinde, W y_s = h(xi_s) - T(xi_s) x, y_s >= 0 koşulunu sağlayan en ucuz düzeltici eylemi y_s bulun. Eğer uygun bir tedbir yoksa, büyük bir ceza (veya uygunsuzluk) uygulanır, bu da birinci aşama kararının çok agresif olduğunu gösterir.

Formül
Q(x, \xi) = \min_{y} q(\xi)^T y \quad \text{s.t. } W y = h(\xi) - T(\xi) x,\; y \geq 0
4

Küçük ila orta ölçekli senaryo kümeleri için tam genişletilmiş formu (tüm senaryolar tek bir büyük LP olarak istiflenmiş) çözün veya büyük kümeler için Benders ayrıştırmasını (L-şekilli yöntem) uygulayın. L-şekilli yöntem, senaryo alt problemlerinin blok-diyagonal yapısından yararlanarak yakınsama sağlanana kadar bir ana probleme uygunluk ve fizibilite kesmeleri ekler.

5

Olasılıklı Çözümün Değeri (VSS) — deterministik ortalama-değer çözümüne göre elde edilen kazanç — ve Mükemmel Bilgi Beklenen Değeri (EVPI) — mükemmel öngörünün ne kadar değerli olacağının üst sınırı — aracılığıyla çözüm kalitesini değerlendirin. Birinci aşama kararını x*, beklenen toplam maliyeti ve senaryo başına tedbir maliyetlerini karar vericilere risk profilini iletmek için raporlayın.

Sık yapılan hatalar

  • Çok az senaryo kullanmak, örnek dışı olarak kötü performans gösteren yanlı bir çözüme yol açar; her zaman örnek dışı senaryo testi ile doğrulayın.
  • Ortalama-değer deterministik çözümünü (ortalama değerleri kullanarak) olasılıklı çözümle karıştırmak — parametreler kararlı görünse bile VSS büyük olabilir.
  • Tedbirin fizibilitesini göz ardı etmek: ikinci aşama alt problemi bazı senaryolar için uygunsuz olabiliyorsa, modelin tam tedbir kısıtlarına veya açık cezalara ihtiyacı vardır.
  • Tarihsel senaryo dağılımına, özellikle tedarik zinciri veya finansal uygulamalarda, kuyruk veya düşmanca senaryolara karşı stres testi yapmadan aşırı uyum sağlamak.
  • Olasılıklı LP'yi, karar vericinin aslında beklenen değer-nötr olmaktan çok belirsizlikten kaçındığı durumlarda sağlam optimizasyonun yerine doğrudan bir ikame olarak ele almak.

Sık sorulan sorular

Olasılıklı doğrusal programlama ile sağlam optimizasyon arasındaki fark nedir?

ODP, bir olasılık dağılımı üzerindeki senaryoların beklenen maliyetini en aza indirir ve belirsizlik çözüldükten sonra tedbir eylemlerine izin verir. Sağlam optimizasyon ise olasılık dağılımı varsaymadan bir belirsizlik kümesi üzerindeki en kötü durumu optimize eder ve tipik olarak tüm senaryolar için geçerli olan tek bir sabit çözüm üretir. ODP, olasılıklar tahmin edilebildiğinde tercih edilir; sağlam optimizasyon, yalnızca belirsizlik kümesi bilindiğinde veya kuyruk riski koruması en önemli olduğunda tercih edilir.

Tipik olarak kaç senaryo gereklidir?

Bu, problemin boyutuna ve dağılımsal karmaşıklığa bağlıdır. Akıllıca üretilirse (örneğin, moment eşleştirme veya senaryo azaltma yoluyla) planlama problemleri için genellikle on ila birkaç yüz senaryo yeterlidir. Monte Carlo tabanlı örnek ortalama yaklaşımı (SAA), yüksek doğruluklu çözümler için binlerce senaryo gerektirebilir ve güven aralıkları yakınsamayı yönlendirir.

ODP tamsayı veya ikili kararları işleyebilir mi?

Doğrudan değil — tamsayı değişkenler, hesaplama açısından önemli ölçüde daha zor olan Olasılıklı Tamsayı Programlama (OTP) veya Olasılıklı Karma Tamsayı Programlama (OKTP) gerektirir. ODP yalnızca tüm karar değişkenleri sürekli olduğunda geçerlidir.

Olasılıklı Çözümün Değeri (VSS) neyi ölçer?

VSS = EEV - RP, burada EEV, tüm senaryolar üzerinden değerlendirilen deterministik ortalama-değer çözümünün beklenen maliyetidir ve RP gerçek olasılıklı optimumdur (tedbir problemi). Yüksek bir VSS, belirsizliği göz ardı etmenin ve ortalama parametreleri kullanmanın önemli ölçüde daha kötü sonuçlara yol açtığını gösterir.

Hangi çözücüler ve yazılımlar olasılıklı doğrusal programlamayı destekler?

CPLEX ve Gurobi gibi ticari çözücüler, genişletilmiş formu doğrudan çözebilir. Açık kaynaklı çerçeveler arasında SMPS format okuyucuları, PySP (Pyomo'nun bir parçası) ve Julia paketi StochasticPrograms.jl bulunur. Büyük ölçekli problemler için, özel L-şekilli ayrıştırma uygulamaları araştırma ve endüstride yaygındır.

İlgili yöntemler

Kaynaklar

  1. Dantzig, G. B., & Madansky, A. (1961). On the solution of two-stage linear programs under uncertainty. Proceedings of the Fourth Berkeley Symposium on Mathematical Statistics and Probability, 1, 165–176.

    Yayın kaynağını aç
    Kopyalandı.
  2. Birge, J. R., & Louveaux, F. (1997). Introduction to Stochastic Programming. Springer, New York.

    ISBN: 9780387982175
    Kopyalandı.