Stokastik Programlama

Stokastik programlama (İng. stochastic programming) — matematiksel programlamanın bir alt dalı olup, modelin bazı parametrelerinin kesin olarak bilinmediği, bunun yerine bilinen veya tahmin edilen olasılık dağılımlarına sahip rastgele değişkenler olarak temsil edildiği belirsizlik koşullarında optimizasyon problemlerini çözmek için modeller ve yöntemler geliştiren bir disiplindir.

Tüm verilerin sabit ve bilinen sabitler olarak kabul edildiği deterministik problemlerin aksine, stokastik programlama; belirli bir istatistiksel anlamda optimal olan bir çözüm (veya karar politikası) bulmayı hedefler. Bu, çoğunlukla amaç fonksiyonunun beklenen değerinin minimize edilmesi veya maksimize edilmesi anlamına gelir. Temel fikir, rastgele parametrelerin tüm olası gerçekleşmeleri üzerinden "ortalamada" en iyi olacak bir karar politikası bulmaktır; bu yaklaşım, özellikle kararların benzer koşullarda defalarca alındığı problemler (örneğin stok yönetimi veya enerji sistemleri) için büyük önem taşır.

Matematiksel Problem Formülasyonu

Stokastik programlama problemi genel formda şu şekilde ifade edilebilir: $\underset{x\in X}{min}𝔼[f(x,\xi )]$ burada:

• $x$ — belirlenmesi gereken karar değişkenlerinin (kararların) vektörü.
• $X$ — deterministik kısıtlar tarafından tanımlanan $x$ için uygun çözümler kümesi.
• $\xi$ — problemin belirsiz parametrelerini (örneğin talep, fiyatlar, hava koşulları) temsil eden rastgele vektör.
• $f(x,\xi )$ — değeri hem alınan karar $x$'ye hem de rastgele vektörün gerçekleşmesi $\xi$'e bağlı olan amaç fonksiyonu.
• $𝔼[\cdot ]$ — $\xi$ vektörünün olasılık dağılımına göre hesaplanan beklenen değer operatörü.

Çok aşamalı stokastik modellerin temelinde yatan en önemli ilke öngörüsüzlük ilkesidir (İng. non-anticipativity principle). Bu ilke, herhangi bir aşamada alınan kararların yalnızca o ana kadar mevcut olan bilgiye bağlı olabileceğini ve "geleceğe bakamayacağını" belirtir.

İki Aşamalı Telafi Hakkına Sahip Problem

En yaygın model, telafi hakkına sahip iki aşamalı stokastik programdır (İng. two-stage stochastic program with recourse). Karar alma süreci iki aşamaya ayrılır:

1. Birinci aşama: "Burada ve şimdi" (here-and-now) kararı alınır — $x$ vektörü belirlenir. Bu karar, rastgele vektörün $\xi$ belirli bir gerçekleşmesi bilinmeden önce verilmek zorundadır.
2. İkinci aşama: Rastgele olay gerçekleştikten sonra, birinci aşama kararı $x$ ile $\xi$ sonucunun birleşiminden doğan olumsuz etkileri en aza indirmeye veya ortaya çıkan elverişli fırsatlardan yararlanmaya yönelik bir düzeltici ya da telafi kararı (recourse decision) — $y(\xi )$ vektörü — alınır.

Matematiksel olarak iki aşamalı stokastik doğrusal programlama problemi şu şekilde formüle edilir: $\underset{x\in {ℝ}^{n_1}}{min}\{c^{T}x+{𝔼}_{\xi }[Q(x,\xi )]\}$ birinci aşama kısıtları altında: $Ax=b,x\ge 0$. Burada $Q(x,\xi )$ — telafi fonksiyonu (recourse function) olup ikinci aşama probleminin optimal değerini temsil eder: $Q(x,\xi )=\underset{y\in {ℝ}^{n_2}}{min}\{q(\xi {)}^{T}y\mid T(\xi )x+Wy=h(\xi ),y\ge 0\}$ burada $\xi$ — $q(\xi ),T(\xi )$ ve $h(\xi )$ parametrelerini içeren rastgele vektör; $c,A,b$ ve $W$ ise deterministik parametrelerdir.

Temel Özellikler ve Teoremler

• Dışbükeylik: Teorinin temel sonuçlarından biri, iki aşamalı stokastik doğrusal programlama problemi için beklenen telafi fonksiyonu $Q(x)={𝔼}_{\xi }[Q(x,\xi )]$'nin dışbükey bir fonksiyon olduğudur. Bu özellik son derece önemlidir; zira birinci aşamanın genel probleminin bir dışbükey programlama problemi olduğunu garanti eder. Bunun için etkili çözüm yöntemleri mevcuttur ve global optimum yerel optimumla çakışır.
• Deterministik eşdeğer: Rastgele vektörün $\xi$ sonlu sayıda olası gerçekleşmesi (senaryosu) ${\xi }_1,\dots ,{\xi }_K$ ve bunlara karşılık gelen olasılıkları $p_1,\dots ,p_K$ varsa, stokastik programlama problemi tek bir büyük deterministik optimizasyon problemi olarak yeniden formüle edilebilir. Bu durumda beklenen değer, tüm senaryolar üzerinden ağırlıklı bir toplamla değiştirilir. Ancak bu problemin boyutu senaryo sayısıyla doğrusal olarak büyümekte; bu durum "boyutların lanetine" yol açmakta ve büyük senaryo sayıları için bu yaklaşımı hesaplamalı olarak çözümsüz kılmaktadır.

Robust Optimizasyon ile Karşılaştırma

Stokastik programlama, belirsizlik koşullarında optimizasyona yönelik çeşitli yaklaşımlardan biridir. Robust optimizasyondan temel farkı, belirsizliğin modelleme biçimi ve optimallik kriteridir.

Belirsizlik koşullarında optimizasyon yaklaşımlarının karşılaştırması

Kriter	Stokastik optimizasyon	Robust optimizasyon
Belirsizliğin temsili	Parametreler, bilinen olasılık dağılımına sahip rastgele değişkenlerdir	Parametreler belirli bir belirsizlik kümesine aittir; dağılım gerekmez
Optimallik kriteri	Amaç fonksiyonunun beklenen değerinin optimizasyonu	En kötü senaryoda optimizasyon (minimax)
Çözümün niteliği	"Ortalamada" optimal politika, nadir senaryolar için uygun olmayabilir	Tüm gerçekleşmeler için uygunluğu garanti edilen çözüm; muhafazakâr olabilir

Örnekler

• Gazete bayii problemi (İng. newsvendor problem): Bir satıcının gelecekteki kesin talebi bilmeden ne kadar stok satın alacağına karar vermesi gereken klasik bir stok yönetimi problemidir. Çözüm, fazla stoktan kaynaklanan kayıp riski ile kıtlıktan kaynaklanan kaçırılan kâr riski arasında denge kurar.
• Çiftçi problemi: Bir çiftçi, verimi etkileyen gelecekteki hava koşullarını bilmeden toplam arazisini farklı ürünler arasında nasıl böleceğine karar verir. Hava koşulları belli olduğunda çiftçi düzeltici adımlar atabilir (örneğin fazla ürünü satmak veya eksik ürünü piyasadan satın almak).

Ayrıca bakınız

• Matematiksel programlama
• Yöneylem araştırması
• Robust optimizasyon
• Dinamik programlama
• Kontrol teorisi

Notlar

</references>