Pemrograman Sasaran Stokastik — Mengoptimalkan Banyak Sasaran di Bawah Ketidakpastian
- Diperkenalkan oleh
- Contini, B. (building on Charnes & Cooper's chance-constrained programming)
- Tahun
- 1968
- Jenis
- Stochastic multi-goal optimization
- Keluarga
- Simulation / optimization
Teks ini adalah terjemahan mesin dan belum ditinjau. Baca versi asli dalam bahasa Inggris
Apa fungsinya?
Pemrograman Sasaran Stokastik (SGP) memperluas pemrograman sasaran klasik untuk menangani ketidakpastian dalam target sasaran, koefisien kendala, atau parameter sisi kanan.
Dengan menggabungkan kendala probabilistik dan komponen objektif stokastik, ia menemukan solusi yang memenuhi banyak sasaran pada tingkat probabilitas yang dapat diterima, membuatnya cocok untuk masalah keputusan di mana data secara inheren tidak pasti atau bervariasi.
Intuisi di balik metode
Pemrograman sasaran klasik bertanya: bisakah kita mendekati setiap sasaran secara bersamaan? Pemrograman Sasaran Stokastik menanyakan pertanyaan yang sama tetapi mengakui bahwa dunia tidak pasti — sasaran dapat bergeser, sumber daya dapat bervariasi, dan data bisa berisik. Alih-alih mengoptimalkan untuk satu skenario tetap, SGP mencari solusi yang berkinerja baik dalam ekspektasi atau yang memenuhi setiap sasaran dengan probabilitas yang ditentukan. Anggap saja sebagai membuat rencana terbaik yang mungkin sambil secara jujur memperhitungkan apa yang tidak Anda ketahui.
Sejarah
Pemrograman sasaran diperkenalkan oleh Charnes dan Cooper pada akhir 1950-an. Contini (1968) secara formal memperluasnya ke pengaturan stokastik menggunakan ide pemrograman kendala peluang. Dekade berikutnya melihat aplikasi yang berkembang di bidang keuangan, pertanian, dan kebijakan publik. Metode ini mendapatkan pijakan teoretis lebih lanjut melalui koneksi ke optimasi kuat yang dikembangkan pada tahun 1990-an dan 2000-an.
Kapan digunakan
Gunakan Pemrograman Sasaran Stokastik ketika masalah keputusan memiliki banyak sasaran yang saling bertentangan, setidaknya beberapa parameter (permintaan, biaya, hasil) tidak pasti dan dapat dikarakterisasi oleh distribusi probabilitas, dan pembuat kebijakan memerlukan jaminan yang dinyatakan sebagai tingkat kepercayaan daripada batas kasus terburuk. Sangat cocok untuk perencanaan rantai pasokan, alokasi sumber daya perawatan kesehatan, manajemen portofolio keuangan dengan banyak tujuan, dan perencanaan pertanian di bawah ketidakpastian cuaca. JANGAN gunakan ketika sasaran benar-benar tidak dapat dibandingkan dan tidak dapat dibobot, ketika tidak ada informasi distribusi yang tersedia (gunakan optimasi kuat sebagai gantinya), ketika masalah hanya memiliki satu tujuan (gunakan pemrograman stokastik), atau ketika jumlah skenario sangat besar sehingga formulasi ulang ekuivalen deterministik menjadi tidak dapat dipecahkan.
Batasan dan pertimbangan
- Memerlukan pengetahuan tentang parameter distribusi (rata-rata, varians) yang mungkin sulit diperkirakan secara akurat.
- Distribusi non-normal atau kendala peluang gabungan dapat membuat formulasi ulang deterministik menjadi tidak dapat dipecahkan, memerlukan pendekatan berbasis skenario atau simulasi.
- Pilihan tingkat kepercayaan alpha_i dan bobot sasaran w_i secara inheren bersifat subjektif dan dapat sangat memengaruhi hasil.
- Secara komputasi lebih menuntut daripada pemrograman sasaran deterministik, terutama untuk masalah skala besar atau nonlinier.
- Menginterpretasikan trade-off di antara sasaran probabilistik bisa sulit bagi pemangku kepentingan non-teknis.
Syarat dari sumber tidak menggantikan tinjauan ilmiah independen atau validasi oleh mesin analisis.
Kelebihan
- Menangani banyak sasaran yang saling bertentangan secara bersamaan dalam satu kerangka kerja optimasi.
- Memungkinkan spesifikasi eksplisit tingkat risiko yang dapat diterima (kepercayaan) untuk setiap sasaran atau kendala.
- Di bawah asumsi normalitas, kendala peluang berkurang menjadi kendala kerucut orde kedua yang dapat dipecahkan yang dapat dipecahkan dengan pemecah standar.
- Memberikan pengambil keputusan probabilitas pencapaian sasaran, menawarkan informasi yang lebih kaya daripada solusi skenario tunggal.
- Mencakup pemrograman sasaran deterministik sebagai kasus khusus (tingkat kepercayaan = 1 dengan parameter tetap).
- Secara teoritis kokoh, terhubung ke literatur pemrograman kendala peluang dan optimasi kuat.
Penerapan
- Perencanaan pertanian: mengalokasikan lahan dan sumber daya di berbagai tanaman di bawah kondisi curah hujan dan harga yang tidak pasti.
- Alokasi sumber daya perawatan kesehatan: menjadwalkan staf dan tempat tidur sambil memenuhi tujuan tingkat layanan di bawah permintaan pasien yang tidak pasti.
- Manajemen rantai pasokan: perencanaan produksi dan inventaris dengan hasil, waktu tunggu, dan permintaan yang tidak pasti.
- Optimasi portofolio keuangan dengan banyak tujuan (pengembalian, risiko, likuiditas) di bawah ketidakpastian pasar.
- Perencanaan sistem energi: menyeimbangkan tujuan biaya, keandalan, dan emisi mengingat generasi terbarukan yang tidak pasti.
- Penganggaran kota: mengalokasikan dana publik antar departemen dengan pendapatan dan pengeluaran yang tidak pasti.
Cara kerjanya
Cara kerjanya
Definisikan variabel keputusan, banyak sasaran aspirasional (target), dan kendala keras apa pun. Setiap sasaran i dinyatakan sebagai: f_i(x) + d_i^- - d_i^+ = g_i, di mana d_i^- dan d_i^+ adalah variabel deviasi negatif dan positif dari target g_i. Tetapkan bobot prioritas yang mencerminkan kepentingan relatif pencapaian setiap sasaran.
Identifikasi parameter mana yang tidak pasti: target sasaran g_i, koefisien kendala, atau koefisien fungsi tujuan dapat dimodelkan sebagai variabel acak dengan distribusi yang diketahui atau diperkirakan (misalnya, normal, seragam, empiris). Tentukan asumsi distribusi berdasarkan data historis atau penilaian ahli.
Ubah kendala yang tidak pasti menjadi kendala peluang (probabilistik). Untuk kendala stokastik yang melibatkan parameter acak b_i dengan distribusi F, persyaratkan P(g_i(x) <= b_i) >= alpha_i, di mana alpha_i adalah tingkat kepercayaan yang ditentukan pengguna (misalnya, 0,90 atau 0,95). Di bawah asumsi normalitas, ini dapat diformulasikan ulang sebagai kendala kerucut orde kedua deterministik.
Rumus
P(g_i(x) \leq b_i) \geq \alpha_i
Selesaikan masalah optimasi yang dihasilkan (kemungkinan diformulasikan ulang): minimalkan jumlah tertimbang deviasi min sum_i (w_i^+ d_i^+ + w_i^- d_i^-) tunduk pada ekuivalen deterministik dari kendala peluang dan kendala keras yang tersisa. Gunakan pemecah LP, MILP, atau nonlinier tergantung pada struktur masalah.
Rumus
\min \sum_{i} (w_i^+ d_i^+ + w_i^- d_i^-)Evaluasi solusi dengan memeriksa tingkat pencapaian sasaran, probabilitas kepatuhan kendala, dan sensitivitas terhadap asumsi distribusi. Lakukan validasi Monte Carlo pasca-hoc dengan mengambil sampel realisasi parameter dan memverifikasi bahwa solusi memenuhi sasaran pada tingkat kepercayaan yang dinyatakan dalam skenario simulasi.
Kesalahan umum
- Mengasumsikan normalitas parameter yang tidak pasti tanpa validasi empiris dapat menghasilkan jaminan kepercayaan yang menyesatkan.
- Menetapkan tingkat kepercayaan yang terlalu tinggi (misalnya, 0,999) secara efektif meruntuhkan model menjadi formulasi deterministik yang konservatif, mengalahkan tujuan pemodelan stokastik.
- Mencampuradukkan pemrograman sasaran kendala peluang dengan pemrograman sasaran kuat — keduanya menangani ketidakpastian secara berbeda dan tidak dapat dipertukarkan.
- Kegagalan memvalidasi solusi stokastik melalui simulasi Monte Carlo membuat risiko pelanggaran sasaran yang sebenarnya tidak diketahui.
- Mengabaikan korelasi di antara parameter yang tidak pasti dapat menghasilkan solusi yang tidak layak atau terlalu optimis.
Pertanyaan yang sering diajukan
Bagaimana Pemrograman Sasaran Stokastik berbeda dari Pemrograman Sasaran Klasik?
Pemrograman sasaran klasik mengasumsikan semua parameter (sasaran, kendala, biaya) diketahui dengan pasti. Pemrograman Sasaran Stokastik memungkinkan beberapa parameter menjadi variabel acak, menggabungkan kendala probabilistik yang mengharuskan sasaran dipenuhi dengan tingkat kepercayaan yang ditentukan daripada secara tepat.
Asumsi distribusi apa yang paling umum digunakan?
Normalitas adalah asumsi yang paling umum karena memungkinkan kendala peluang diformulasikan ulang secara tepat sebagai kendala kerucut orde kedua deterministik. Ketika data menunjukkan distribusi non-normal, pendekatan berbasis skenario atau simulasi digunakan sebagai gantinya.
Bagaimana cara memilih tingkat kepercayaan alpha_i untuk setiap kendala peluang?
Tingkat kepercayaan mencerminkan toleransi risiko pengambil keputusan untuk setiap sasaran. Nilai 0,90–0,95 umum dalam praktik. Nilai yang lebih tinggi membuat masalah lebih konservatif dan mungkin memerlukan relaksasi sasaran lain; nilai yang lebih rendah memungkinkan lebih banyak risiko tetapi dapat menyebabkan hasil yang tidak dapat diterima.
Bisakah Pemrograman Sasaran Stokastik menangani variabel keputusan integer?
Ya. Ketika dikombinasikan dengan variabel integer, masalahnya menjadi Pemrograman Sasaran Integer Stokastik, yang lebih sulit dipecahkan tetapi masih dapat dipecahkan untuk contoh berukuran sedang menggunakan branch-and-bound dengan formulasi ulang kendala peluang.
Haruskah saya menggunakan Pemrograman Sasaran Stokastik atau Optimasi Kuat ketika saya memiliki parameter yang tidak pasti?
Jika Anda memiliki informasi distribusi yang andal dan menginginkan jaminan probabilistik, SGP sesuai. Jika Anda hanya mengetahui himpunan ketidakpastian (batas) dan menginginkan jaminan kasus terburuk tanpa asumsi distribusi, optimasi kuat lebih baik. Ketika keduanya layak, membandingkan solusi dari kedua pendekatan adalah praktik yang baik.
Metode terkait
Sumber
Contini, B. (1968). A stochastic approach to goal programming. Operations Research, 16(3), 576–586.
Buka referensi DOIDisalin.Charnes, A., Cooper, W. W. (1959). Chance-constrained programming. Management Science, 6(1), 73–79.
Buka referensi DOIDisalin.