Pemrograman Tujuan Kuat — Mencapai Berbagai Target di Bawah Ketidakpastian
- Diperkenalkan oleh
- Charnes, A. & Cooper, W. W. (goal programming); Mulvey, J. M. et al. (robust optimization framework)
- Tahun
- 1961 (GP); 1990s (robust extension)
- Jenis
- Mathematical programming under uncertainty
- Keluarga
- Simulation / optimization
Teks ini adalah terjemahan mesin dan belum ditinjau. Baca versi asli dalam bahasa Inggris
Apa fungsinya?
Pemrograman Tujuan Kuat (RGP) memperluas pemrograman tujuan klasik untuk menangani parameter model yang tidak pasti atau ambigu.
Alih-alih meminimalkan deviasi dari target yang pasti, RGP mencari solusi yang tetap layak dan mendekati optimal di berbagai skenario yang masuk akal atau realisasi data yang tidak pasti. RGP sangat berharga dalam masalah perencanaan di mana tujuan bersifat aspirasional dan data masukan membawa variabilitas inheren atau kesalahan estimasi.
Intuisi di balik metode
Pemrograman tujuan klasik bertanya: seberapa dekat kita bisa mencapai beberapa target secara bersamaan? Pemrograman tujuan kuat menambahkan pertanyaan kedua yang krusial: apakah solusi tersebut masih berkinerja dapat diterima ketika data kita salah atau kondisi berubah? Dengan secara eksplisit memodelkan ketidakpastian dalam biaya, ketersediaan sumber daya, atau tingkat target, RGP menemukan rencana yang mengorbankan sedikit optimalitas dalam kondisi ideal sebagai ganti stabilitas di berbagai skenario realistis. RGP memperlakukan deviasi kasus terburuk atau skenario rata-rata sebagai tujuan sebenarnya, bukan hanya deviasi data nominal.
Sejarah
Pemrograman tujuan diperkenalkan oleh Charnes dan Cooper pada tahun 1961 sebagai cara untuk menangani berbagai tujuan dengan meminimalkan deviasi berbobot dari target. Kerangka kerja optimasi kuat, diformalkan oleh Mulvey, Vanderbei, dan Zenios pada tahun 1995, memberikan cara yang berprinsip untuk menyematkan ketidakpastian berbasis skenario ke dalam program matematika. Integrasi mereka ke dalam pemrograman tujuan kuat mengikuti secara alami melalui tahun 1990-an dan 2000-an ketika para peneliti menerapkan ide-ide optimasi kuat ke masalah perencanaan multi-tujuan dalam riset operasi.
Kapan digunakan
Gunakan pemrograman tujuan kuat ketika Anda menghadapi perencanaan multi-tujuan dengan parameter yang tidak pasti dan membutuhkan solusi yang andal di berbagai skenario, bukan hanya optimal dalam kondisi yang diasumsikan. Ideal untuk perencanaan rantai pasokan, manajemen portofolio, kebijakan publik, dan alokasi sumber daya dengan anggaran atau permintaan yang tidak pasti. JANGAN gunakan ketika semua parameter diketahui dengan pasti (GP standar sudah cukup), ketika jumlah skenario sangat besar tanpa reformulasi yang dapat ditangani, atau ketika tujuan benar-benar tidak dapat dibandingkan dan tidak ada agregasi berbasis deviasi yang bermakna.
Batasan dan pertimbangan
- Memformulasikan model ketidakpastian (himpunan skenario atau politop ketidakpastian) membutuhkan pengetahuan domain dan seringkali merupakan bagian tersulit.
- Formulasi kuat dapat secara signifikan meningkatkan ukuran masalah dan biaya komputasi dibandingkan dengan GP deterministik.
- Pilihan kriteria ketahanan (minimax, nilai harapan, penalti varians) tidak standar dan secara substansial memengaruhi hasil.
- Prioritas leksikografis dalam pengaturan kuat bisa rumit untuk diimplementasikan dengan benar di seluruh skenario.
Syarat dari sumber tidak menggantikan tinjauan ilmiah independen atau validasi oleh mesin analisis.
Kelebihan
- Menangani berbagai tujuan yang saling bertentangan secara bersamaan sambil secara eksplisit memperhitungkan ketidakpastian parameter.
- Menghasilkan solusi yang lebih dapat diimplementasikan dalam praktik karena kinerjanya menurun secara bertahap di bawah gangguan data.
- Fleksibel: mengakomodasi formulasi stokastik berbasis skenario dan himpunan ketidakpastian interval/polihedral.
- Struktur prioritas (leksikografis atau berbobot) memberikan kontrol intuitif atas pentingnya tujuan.
- Trade-off ketahanan-optimalitas eksplisit dan dapat dikontrol melalui parameter penalti lambda.
Penerapan
- Desain jaringan rantai pasokan dengan permintaan dan biaya yang tidak pasti
- Alokasi sumber daya layanan kesehatan yang memenuhi berbagai target layanan di bawah variabilitas anggaran
- Optimasi portofolio yang menyeimbangkan tujuan pengembalian, risiko, dan likuiditas di bawah ketidakpastian pasar
- Perencanaan kebijakan publik dengan pendapatan masa depan yang tidak pasti dan target pengeluaran multi-sektor
- Perencanaan sistem energi dengan output terbarukan yang tidak pasti dan berbagai tujuan lingkungan dan biaya
Cara kerjanya
Cara kerjanya
Identifikasi variabel keputusan, tingkat target aspirasional untuk setiap tujuan (misalnya, laba >= T1, limbah <= T2), dan struktur prioritas (leksikografis atau berbobot). Definisikan variabel deviasi positif dan negatif d+ dan d- yang mengukur pencapaian berlebih dan kurang dari setiap tujuan.
Tentukan sumber ketidakpastian: target sisi kanan yang tidak pasti, koefisien kendala, atau bobot tujuan. Representasikan ketidakpastian sebagai himpunan skenario terbatas S = {s1, ..., sK} dengan probabilitas ps, atau sebagai himpunan ketidakpastian interval/polihedral untuk formulasi optimasi kuat.
Konstruksi model kuat dengan menggabungkan variabel deviasi yang diindeks skenario dan menambahkan suku penalti ketahanan. Formulasi umum meminimalkan deviasi yang diharapkan ditambah penalti lambda dikalikan varians (atau deviasi kasus terburuk) di seluruh skenario, menyeimbangkan kualitas solusi dan stabilitas.
Selesaikan model ekuivalen deterministik yang dihasilkan — biasanya program kuadratik atau linier tergantung pada kriteria ketahanan yang dipilih. Prioritas leksikografis dapat ditangani dengan optimasi berurutan pada tingkat tujuan.
Evaluasi solusi di semua skenario: laporkan pencapaian tujuan rata-rata, kasus terburuk, dan kasus terbaik. Lakukan analisis sensitivitas pada parameter trade-off ketahanan lambda untuk mengungkapkan kurva efisiensi antara optimalitas dan stabilitas.
Kesalahan umum
- Membingungkan GP kuat dengan GP stokastik: GP kuat sering menargetkan kinerja kasus terburuk atau yang dihukum varians, sedangkan GP stokastik meminimalkan deviasi yang diharapkan — pilihan tersebut mengubah model dan interpretasi.
- Terlalu konservatif: menggunakan ketahanan kasus terburuk tanpa mengkalibrasi himpunan ketidakpastian dapat menghasilkan solusi yang terlalu hati-hati yang jauh dari optimal dalam skenario tipikal.
- Mengabaikan validasi probabilitas skenario atau batas ketidakpastian terhadap data nyata, membuat analisis ketahanan menyesatkan.
- Memperlakukan penalti lambda sebagai konstanta tetap daripada mengeksplorasi kurva trade-off-nya, yang menyembunyikan biaya sebenarnya dari ketahanan.
Pertanyaan yang sering diajukan
Bagaimana pemrograman tujuan kuat berbeda dari pemrograman tujuan stokastik?
GP Stokastik meminimalkan deviasi rata-rata (rata-rata) yang diharapkan di seluruh skenario yang dibobot oleh probabilitas. GP Kuat biasanya juga menghukum variabilitas atau hasil kasus terburuk — lebih konservatif tetapi menghasilkan solusi yang berkinerja lebih konsisten di semua skenario, bahkan yang berprobabilitas rendah.
Bisakah saya menggunakan ketidakpastian interval alih-alih skenario?
Ya. Ketika parameter berada dalam interval atau polihedra, formulasi rekanan kuat (mengikuti pendekatan Ben-Tal dan Nemirovski) dapat diturunkan, mengubah GP yang tidak pasti menjadi program deterministik yang dapat diselesaikan oleh solver LP atau SOCP standar.
Apa yang dikontrol oleh parameter lambda?
Lambda mengatur trade-off antara kinerja nominal dan ketahanan. Lambda nol mengembalikan GP nilai harapan; meningkatkan lambda menghukum varians atau deviasi kasus terburuk lebih berat, menghasilkan solusi yang lebih kuat tetapi berpotensi kurang optimal (dalam harapan).
Apakah ada perangkat lunak yang tersedia untuk pemrograman tujuan kuat?
Formulasi standar dapat diselesaikan dengan solver LP/QP apa pun (CPLEX, Gurobi, GLPK). Ekstensi stokastik dapat menggunakan GAMS, SPInE, atau pustaka Python seperti PuLP dan Pyomo dengan enumerasi skenario.
Kapan saya harus memilih GP kuat daripada analisis sensitivitas sederhana pada GP biasa?
Pilih GP kuat ketika Anda membutuhkan satu rencana yang dapat diimplementasikan yang secara eksplisit mengoptimalkan stabilitas, bukan hanya ketika Anda ingin memahami seberapa sensitif solusi GP yang sudah dipilih terhadap perubahan parameter.
Metode terkait
Sumber
Charnes, A., Cooper, W. W. (1961). Management Models and Industrial Applications of Linear Programming. Wiley, New York.
ISBN: 9780471155041Disalin.Mulvey, J. M., Vanderbei, R. J., Zenios, S. A. (1995). Robust optimization of large-scale systems. Operations Research, 43(2), 264-281.
Buka referensi DOIDisalin.