Pemrograman Stokastik

Pemrograman stokastik (Ingg. stochastic programming) — cabang pemrograman matematis yang mengembangkan model dan metode penyelesaian masalah optimasi dalam kondisi ketidakpastian, ketika beberapa parameter model tidak diketahui secara pasti, melainkan direpresentasikan sebagai variabel acak dengan distribusi probabilitas yang diketahui atau diestimasi.

Berbeda dengan masalah deterministik, di mana semua data dianggap sebagai konstanta yang telah ditetapkan, pemrograman stokastik bertujuan menemukan solusi (atau kebijakan pengambilan keputusan) yang optimal dalam suatu pengertian statistik tertentu. Paling sering hal ini berarti meminimalkan atau memaksimalkan nilai ekspektasi matematis dari fungsi tujuan. Gagasan utamanya adalah menemukan kebijakan pengambilan keputusan yang akan menjadi yang terbaik "rata-rata" atas semua kemungkinan realisasi parameter acak, yang sangat relevan untuk masalah di mana keputusan diambil berulang kali dalam kondisi serupa (misalnya, dalam manajemen persediaan atau sistem energi).

Formulasi matematis masalah

Secara umum, masalah pemrograman stokastik dapat dirumuskan sebagai: $\underset{x\in X}{min}𝔼[f(x,\xi )]$ di mana:

• $x$ — vektor variabel kendali (keputusan) yang perlu ditentukan.
• $X$ — himpunan solusi yang layak untuk $x$, yang didefinisikan oleh batasan deterministik.
• $\xi$ — vektor acak yang merepresentasikan parameter tidak pasti dari masalah (misalnya, permintaan, harga, kondisi cuaca).
• $f(x,\xi )$ — fungsi tujuan yang nilainya bergantung pada keputusan yang diambil $x$ maupun realisasi vektor acak $\xi$.
• $𝔼[\cdot ]$ — operator ekspektasi matematis yang dihitung berdasarkan distribusi probabilitas vektor $\xi$.

Prinsip terpenting yang mendasari model stokastik multi-tahap adalah prinsip non-antisipasi (Ingg. non-anticipativity principle). Prinsip ini menyatakan bahwa keputusan yang diambil pada tahap mana pun hanya dapat bergantung pada informasi yang tersedia hingga saat itu, dan tidak dapat "melihat ke masa depan".

Masalah dua tahap dengan hak kompensasi

Model yang paling umum adalah masalah dua tahap dengan hak kompensasi (Ingg. two-stage stochastic program with recourse). Proses pengambilan keputusan dibagi menjadi dua tahap:

1. Tahap pertama: Keputusan "di sini dan sekarang" (here-and-now) diambil — vektor $x$ ditentukan. Keputusan ini harus diambil sebelum realisasi spesifik dari vektor acak $\xi$ diketahui.
2. Tahap kedua: Setelah peristiwa acak terjadi, keputusan korektif atau kompensasi (recourse decision) — vektor $y(\xi )$ — diambil, yang bertujuan meminimalkan dampak negatif atau memanfaatkan peluang yang muncul akibat kombinasi keputusan tahap pertama $x$ dan hasil $\xi$.

Secara matematis, masalah dua tahap pemrograman linier stokastik dirumuskan sebagai berikut: $\underset{x\in {ℝ}^{n_1}}{min}\{c^{T}x+{𝔼}_{\xi }[Q(x,\xi )]\}$ dengan batasan tahap pertama: $Ax=b,x\ge 0$. Di sini $Q(x,\xi )$ — fungsi kompensasi (recourse function), yang merupakan nilai optimal dari masalah tahap kedua: $Q(x,\xi )=\underset{y\in {ℝ}^{n_2}}{min}\{q(\xi {)}^{T}y\mid T(\xi )x+Wy=h(\xi ),y\ge 0\}$ di mana $\xi$ — vektor acak yang mencakup parameter $q(\xi ),T(\xi )$ dan $h(\xi )$; sementara $c,A,b$ dan $W$ — parameter deterministik.

Sifat dan teorema utama

• Konveksitas: Salah satu hasil fundamental dari teori ini adalah bahwa untuk masalah dua tahap pemrograman linier stokastik, fungsi kompensasi yang diharapkan $Q(x)={𝔼}_{\xi }[Q(x,\xi )]$ merupakan fungsi cembung. Sifat ini sangat penting karena menjamin bahwa masalah tahap pertama secara keseluruhan merupakan masalah pemrograman cembung, yang memiliki metode penyelesaian efisien dan di mana optimum global bertepatan dengan optimum lokal.
• Ekuivalen deterministik: Jika vektor acak $\xi$ memiliki sejumlah realisasi (skenario) yang terbatas ${\xi }_1,\dots ,{\xi }_K$ dengan probabilitas $p_1,\dots ,p_K$, maka masalah pemrograman stokastik dapat dirumuskan ulang sebagai satu masalah optimasi deterministik besar. Dalam hal ini, ekspektasi matematis digantikan oleh jumlah tertimbang atas semua skenario. Namun, ukuran masalah ini tumbuh secara linier seiring dengan jumlah skenario, yang menyebabkan "kutukan dimensi" dan membuat pendekatan ini tidak dapat diselesaikan secara komputasi untuk jumlah skenario yang besar.

Perbandingan dengan optimasi robust

Pemrograman stokastik adalah salah satu dari beberapa pendekatan untuk optimasi dalam kondisi ketidakpastian. Perbedaan utamanya dari optimasi robust terletak pada cara pemodelan ketidakpastian dan kriteria optimalitas.

Perbandingan pendekatan optimasi dalam kondisi ketidakpastian

Kriteria	Optimasi stokastik	Optimasi robust
Representasi ketidakpastian	Parameter adalah variabel acak dengan distribusi probabilitas yang diketahui	Parameter termasuk dalam himpunan ketidakpastian yang ditentukan, distribusi tidak diperlukan
Kriteria optimalitas	Optimasi ekspektasi matematis dari fungsi tujuan	Optimasi dalam skenario terburuk (minimax)
Karakter solusi	Kebijakan yang optimal "rata-rata", dapat tidak layak untuk skenario langka	Solusi yang dijamin layak untuk semua realisasi; dapat bersifat konservatif

Contoh

• Masalah penjual koran (Ingg. newsvendor problem): Masalah manajemen persediaan klasik, di mana penjual harus memutuskan berapa banyak barang yang akan dibeli tanpa mengetahui permintaan masa depan yang pasti. Solusinya menyeimbangkan antara risiko kerugian akibat kelebihan stok dan risiko kehilangan keuntungan akibat kekurangan stok.
• Masalah petani: Seorang petani memutuskan berapa hektar lahan yang akan dialokasikan untuk berbagai tanaman pada luas total tertentu, tanpa mengetahui cuaca masa depan yang mempengaruhi hasil panen. Setelah cuaca diketahui, petani dapat mengambil tindakan korektif (misalnya, menjual kelebihan panen atau membeli kekurangan panen di pasar).

Lihat pula

• Pemrograman matematis
• Riset operasi
• Optimasi robust
• Pemrograman dinamis
• Teori kendali

Catatan

</references>