Stokastik Hedef Programlama — Belirsizlik Altında Çoklu Hedeflerin Optimizasyonu
- Ortaya koyan
- Contini, B. (building on Charnes & Cooper's chance-constrained programming)
- Yıl
- 1968
- Tür
- Stochastic multi-goal optimization
- Aile
- Simulation / optimization
Bu metin makine çevirisidir ve henüz incelenmedi. Asıl metni İngilizce oku
Ne işe yarar?
Stokastik Hedef Programlama (SGP), hedef çıktılarındaki, kısıt katsayılarındaki veya sağ taraf parametrelerindeki belirsizliği ele almak için klasik hedef programlamayı genişletir.
Olasılıksal kısıtları ve stokastik amaç fonksiyonu bileşenlerini dahil ederek, kabul edilebilir olasılık seviyelerinde birden çok hedefi karşılayan çözümler bulur; bu da onu verilerin doğası gereği belirsiz veya değişken olduğu karar problemleri için uygun kılar.
Yöntemin mantığı
Klasik hedef programlama şunu sorar: her hedefe aynı anda ne kadar yaklaşabiliriz? Stokastik Hedef Programlama da aynı soruyu sorar ancak dünyanın belirsiz olduğunu kabul eder — hedefler kayabilir, kaynaklar değişebilir ve veriler gürültülü olabilir. SGP, tek bir sabit senaryo için optimizasyon yapmak yerine, beklenen değerde iyi performans gösteren veya her hedefi belirtilen bir olasılıkla karşılayan çözümler arar. Bunu, bilmediğiniz şeyleri dürüstçe hesaba katarak mümkün olan en iyi planı yapmak gibi düşünebilirsiniz.
Tarih
Hedef programlama, Charnes ve Cooper tarafından 1950'lerin sonlarında tanıtıldı. Contini (1968), şans kısıtlı programlama fikirlerini kullanarak bunu stokastik ayarlara resmen genişletti. Sonraki on yıllarda finans, tarım ve kamu politikasında artan uygulamalar görüldü. Yöntem, 1990'lar ve 2000'lerde geliştirilen sağlam optimizasyonla bağlantılar yoluyla daha fazla teorik temel kazandı.
Ne zaman kullanılır?
Karar probleminin birden çok çelişkili hedefi olduğu, parametrelerin en azından bazılarının (talepler, maliyetler, verimler) belirsiz olduğu ve olasılık dağılımlarıyla karakterize edilebildiği ve politika yapıcıların en kötü durum sınırları yerine güven seviyeleri olarak ifade edilen garantilere ihtiyaç duyduğu durumlarda Stokastik Hedef Programlama kullanın. Tedarik zinciri planlaması, sağlık hizmetleri kaynak tahsisi, birden çok amaçlı finansal portföy yönetimi ve hava belirsizliği altındaki tarımsal planlama için uygundur. Hedeflerin gerçekten ölçülemez olduğu ve ağırlıklandırılamadığı durumlarda (sağlam optimizasyon kullanın), dağılımsal bilgi mevcut olmadığında (sağlam optimizasyon kullanın), problemde yalnızca bir amaç olduğunda (stokastik programlama kullanın) veya deterministik eşdeğer yeniden formülasyonların çözülemez hale geldiği senaryo sayısı çok fazlaysa KULLANMAYIN.
Sınırlar ve dikkat edilmesi gerekenler
- Ortalama, varyans gibi dağılım parametrelerinin bilgisi gerektirir ki bu parametrelerin doğru bir şekilde tahmin edilmesi zor olabilir.
- Normal olmayan dağılımlar veya ortak şans kısıtları, deterministik yeniden formülasyonu yönetilemez hale getirebilir ve senaryo tabanlı veya simülasyon yaklaşımları gerektirebilir.
- Güven seviyelerinin alpha_i ve hedef ağırlıklarının w_i seçimi doğası gereği özneldir ve sonuçları güçlü bir şekilde etkileyebilir.
- Özellikle büyük ölçekli veya doğrusal olmayan problemler için deterministik hedef programlamadan hesaplama açısından daha yoğundur.
- Olasılıksal hedefler arasındaki ödünleşmeleri teknik olmayan paydaşlar için yorumlamak zor olabilir.
Kaynak metnin koşulları, bağımsız bilimsel inceleme veya analiz motoru doğrulaması yerine geçmez.
Güçlü yönleri
- Tek bir optimizasyon çerçevesinde birden çok çelişkili hedefi eş zamanlı olarak ele alır.
- Her hedef veya kısıt için kabul edilebilir risk seviyelerinin (güven) açıkça belirtilmesine olanak tanır.
- Normal dağılım varsayımları altında, şans kısıtları standart çözücülerle çözülebilen yönetilebilir ikinci dereceden koni kısıtlarına indirgenir.
- Karar vericilere, tek senaryolu bir çözümden daha zengin bilgi sunan, hedefe ulaşma olasılığı sağlar.
- Deterministik hedef programlamayı özel bir durum olarak kapsar (sabit parametrelerle güven seviyesi = 1).
- Şans kısıtlı programlama ve sağlam optimizasyon literatürleriyle bağlantı kurarak teorik olarak sağlam bir temele sahiptir.
Uygulama alanları
- Tarımsal planlama: belirsiz yağış ve fiyat koşulları altında ürünler arasında arazi ve kaynak tahsisi.
- Sağlık hizmetleri kaynak tahsisi: belirsiz hasta talebi altında hizmet seviyesi hedeflerini karşılarken personel ve yatak planlaması.
- Tedarik zinciri yönetimi: belirsiz verimler, teslim süreleri ve talep ile üretim ve stok planlaması.
- Piyasa belirsizliği altında birden çok hedef (getiri, risk, likidite) ile finansal portföy optimizasyonu.
- Enerji sistemleri planlaması: belirsiz yenilenebilir üretim göz önüne alındığında maliyet, güvenilirlik ve emisyon hedeflerini dengeleme.
- Belediye bütçelemesi: belirsiz gelir ve giderler göz önüne alındığında kamu fonlarını departmanlar arasında tahsis etme.
Nasıl çalışır?
Nasıl çalışır?
Karar değişkenlerini, birden çok özlemsel hedefi (çıktıları) ve varsa sert kısıtları tanımlayın. Her hedef i şu şekilde ifade edilir: f_i(x) + d_i^- - d_i^+ = g_i, burada d_i^- ve d_i^+ hedef g_i'den sapma değişkenleridir (negatif ve pozitif). Her hedefe ulaşmanın göreceli önemini yansıtan öncelik ağırlıkları atayın.
Hangi parametrelerin belirsiz olduğunu belirleyin: hedef çıktılar g_i, kısıt katsayıları veya amaç fonksiyonu katsayıları bilinen veya tahmin edilen dağılımlara (örneğin, normal, üniform, ampirik) sahip rassal değişkenler olarak modellenebilir. Dağılımsal varsayımları geçmiş verilere veya uzman görüşüne dayanarak belirtin.
Belirsiz kısıtları şans (olasılıksal) kısıtlarına dönüştürün. Rassal parametre b_i ve F dağılımını içeren stokastik bir kısıt için, P(g_i(x) <= b_i) >= alpha_i gerekliliğini koyun; burada alpha_i kullanıcı tarafından belirtilen bir güven seviyesidir (örneğin, 0.90 veya 0.95). Normal dağılım varsayımları altında bunlar deterministik ikinci dereceden koni kısıtları olarak yeniden formüle edilebilir.
Formül
P(g_i(x) \leq b_i) \geq \alpha_i
Ortaya çıkan (muhtemelen yeniden formüle edilmiş) optimizasyon problemini çözün: sapmaların ağırlıklı toplamını minimize edin min sum_i (w_i^+ d_i^+ + w_i^- d_i^-), şans kısıtlarının deterministik eşdeğerlerine ve kalan sert kısıtlara tabi olarak. Problem yapısına bağlı olarak Doğrusal Programlama (LP), Karma Tamsayılı Doğrusal Programlama (MILP) veya doğrusal olmayan çözücüler kullanın.
Formül
\min \sum_{i} (w_i^+ d_i^+ + w_i^- d_i^-)Çözümü, hedef gerçekleştirme seviyelerini, kısıt tatmin olasılığını ve dağılımsal varsayımlara duyarlılığı kontrol ederek değerlendirin. Parametre gerçekleşmelerini örnekleyerek ve simüle edilmiş senaryolarda çözümün belirtilen güven seviyelerinde hedefleri karşıladığını doğrulayarak sonradan Monte Carlo geçerliliği gerçekleştirin.
Sık yapılan hatalar
- Belirsiz parametrelerin normal olduğunu ampirik doğrulama olmadan varsaymak yanıltıcı güven garantileri üretebilir.
- Aşırı yüksek güven seviyeleri (örneğin, 0.999) ayarlamak, modeli etkili bir şekilde muhafazakar bir deterministik formülasyona indirger ve stokastik modelleme amacını boşa çıkarır.
- Şans kısıtlı hedef programlamayı sağlam hedef programlama ile karıştırmak — ikisi belirsizliği farklı şekilde ele alır ve birbirinin yerine kullanılamaz.
- Stokastik çözümü Monte Carlo simülasyonu ile doğrulamamak, hedef ihlali riskinin gerçekte bilinmemesine neden olur.
- Belirsiz parametreler arasındaki korelasyonu göz ardı etmek, çözülemez veya aşırı iyimser çözümler üretebilir.
Sık sorulan sorular
Stokastik Hedef Programlama klasik Hedef Programlamadan nasıl farklıdır?
Klasik hedef programlama, tüm parametrelerin (hedefler, kısıtlar, maliyetler) kesin olarak bilindiğini varsayar. Stokastik Hedef Programlama, bazı parametrelerin rassal değişken olmasına izin verir ve hedeflerin tam olarak değil, belirli bir güven seviyesinde karşılanmasını gerektiren olasılıksal kısıtları içerir.
En yaygın kullanılan dağılım varsayımı hangisidir?
Normal dağılım en yaygın varsayımdır çünkü şans kısıtlarının deterministik ikinci dereceden koni kısıtları olarak tam olarak yeniden formüle edilmesine izin verir. Veriler normal olmayan dağılımları gösterdiğinde, bunun yerine senaryo tabanlı veya simülasyon yaklaşımları kullanılır.
Her şans kısıtı için güven seviyelerini alpha_i nasıl seçerim?
Güven seviyeleri, karar vericinin her hedef için risk toleransını yansıtır. Uygulamada 0.90–0.95 değerleri yaygındır. Daha yüksek değerler problemi daha muhafazakar hale getirir ve diğer hedeflerin gevşetilmesini gerektirebilir; daha düşük değerler daha fazla risk tanır ancak kabul edilemez sonuçlara yol açabilir.
Stokastik Hedef Programlama tamsayı karar değişkenlerini ele alabilir mi?
Evet. Tamsayı değişkenlerle birleştirildiğinde problem Stokastik Tamsayılı Hedef Programlama haline gelir; bu daha zordur ancak şans kısıtı yeniden formülasyonları ile tamsayılı dallanma ve sınırlandırma kullanılarak orta ölçekli örnekler için hala çözülebilir.
Belirsiz parametrelerim olduğunda Stokastik Hedef Programlama mı yoksa Sağlam Optimizasyon mu kullanmalıyım?
Güvenilir dağılım bilgileriniz varsa ve olasılıksal garantiler istiyorsanız, SGP uygundur. Yalnızca belirsizlik kümelerini (sınırları) biliyorsanız ve dağılım varsayımları olmadan en kötü durum garantileri istiyorsanız, sağlam optimizasyon daha iyidir. Her ikisi de uygulanabilir olduğunda, her iki yaklaşımdan elde edilen çözümleri karşılaştırmak iyi bir uygulamadır.
İlgili yöntemler
Kaynaklar
Contini, B. (1968). A stochastic approach to goal programming. Operations Research, 16(3), 576–586.
DOI kaynağını açKopyalandı.Charnes, A., Cooper, W. W. (1959). Chance-constrained programming. Management Science, 6(1), 73–79.
DOI kaynağını açKopyalandı.