स्टोकेस्टिक प्रोग्रामिंग

For नियंत्रण सिद्धांत का संदर्भ, see प्रसंभाव्य नियंत्रण.

गणितीय अनुकूलन के क्षेत्र में, प्रसंभाव्य प्रोग्रामिंग या प्रसंभाव्य प्रोग्रामिंग प्रतिरूपण अनुकूलन समस्याओं के लिए एक ऐसी संरचना है जिसमें अनिश्चितता सम्मिलित है। प्रसंभाव्य प्रोग्राम एक ऐसी अनुकूलन समस्या है जिसमें कुछ या सभी समस्या प्राचल अनिश्चित हैं, लेकिन ज्ञात प्रायिकता वितरणों का अनुसरण करते हैं। यह संरचना निर्धारणात्मक अनुकूलन के विपरीत है, जिसमें सभी समस्या प्राचलों को यथार्थ रूप से ज्ञात माना जाता है। प्रसंभाव्य प्रोग्रामिंग का लक्ष्य एक ऐसा निर्णय प्राप्त करना है जो निर्णायक द्वारा चयनित कुछ प्राचलों का अनुकूलन करता है, और समस्या के प्राचलों की अनिश्चितता के लिए उचित रूप से ध्यान देने योग्य है। क्योंकि कई वास्तविक जगत के निर्णयों में अनिश्चितता सम्मिलित है, अतः प्रसंभाव्य प्रोग्रामिंग का अनुप्रयोग वित्त से लेकर परिवहन तक ऊर्जा अनुकूलन के क्षेत्रों की एक विस्तृत श्रृंखला में देखा जाता है।

द्वि-चरणीय समस्याएँ

द्वि-चरणीय प्रसंभाव्य प्रोग्रामिंग का मूल विचार यह है कि (इष्टतम) निर्णय, निर्णय लिए जाने के समय उपलब्ध आंकड़ों पर आधारित होने चाहिए और ये निर्णय भविष्य के प्रेक्षणों पर निर्भर नहीं हो सकते हैं। प्रसंभाव्य प्रोग्रामिंग में द्वि-चरणीय सूत्रीकरण का उपयोग व्यापक रूप से किया जाता है। द्वि-चरणीय प्रसंभाव्य प्रोग्रामिंग समस्या का सामान्य सूत्रीकरण निम्न द्वारा दिया जाता है:

$$\min _{x\in X}\{g(x)=f(x)+E_{\xi }[Q(x,\xi )]\}$$

जहाँ $Q(x,\xi )$ द्वितीय-चरण की समस्या का इष्टतम मान है

$$\min _{y}\{q(y,\xi )\,|\,T(\xi )x+W(\xi )y=h(\xi )\}.$$

चिरसम्मत द्वि-चरणीय रैखिक प्रसंभाव्य प्रोग्रामिंग समस्याओं को निम्न रूप में सूत्रित किया जा सकता है

$${\begin{array}{llr}\min \limits _{x\in \mathbb {R} ^{n}}&g(x)=c^{T}x+E_{\xi }[Q(x,\xi )]&\\{\text{subject to}}&Ax=b&\\&x\geq 0&\end{array}}$$

जहाँ $Q(x,\xi )$ द्वितीय-चरण की समस्या का इष्टतम मान है

$${\begin{array}{llr}\min \limits _{y\in \mathbb {R} ^{m}}&q(\xi )^{T}y&\\{\text{subject to}}&T(\xi )x+W(\xi )y=h(\xi )&\\&y\geq 0&\end{array}}$$

ऐसे सूत्रीकरण में, $x\in \mathbb {R} ^{n}$ प्रथम-चरण निर्णय चर सदिश है, $y\in \mathbb {R} ^{m}$ द्वितीय-चरण निर्णय चर सदिश है, और $\xi (q,T,W,h)$ द्वितीय चरण की समस्या के आँकड़े को समाहित करता है। इस सूत्रीकरण में, प्रथम चरण में हमें अनिश्चित आँकड़े $\xi$ (इसे एक यादृच्छिक सदिश के रूप में देखा जाता है) की प्राप्ति से पहले "यहीं और अभी (तत्काल)" निर्णय $x$ लेना होता है। द्वितीय चरण में, $\xi$ की प्राप्ति के उपलब्ध होने के बाद, हम उपयुक्त अनुकूलन समस्या को हल करके अपने व्यवहार को अनुकूलित करते हैं।

प्रथम चरण में हम प्रथम चरण के निर्णय की लागत $c^{T}x$ के साथ-साथ (इष्टतम) द्वितीय चरण के निर्णय की अपेक्षित लागत का अनुकूलन (उपर्युक्त सूत्रीकरण में न्यूनीकृत) करते हैं। हम द्वितीय चरण की समस्या को केवल एक ऐसी अनुकूलन समस्या के रूप में देख सकते हैं जो अनिश्चित आंकड़ों के प्रकट होने पर हमारे अनुमानित इष्टतम व्यवहार का वर्णन करती है, या हम इसके हल को एक ऐसी आश्रय क्रिया के रूप में मान सकते हैं जहाँ शब्द $Wy$ निकाय $Tx\leq h$ की संभावित असंगति की क्षतिपूर्ति करता है और $q^{T}y$ इस आश्रय क्रिया की लागत है।

विचार की गयी द्वि-चरणीय समस्या रैखिक है क्योंकि उद्देश्य फलन और व्यवरोध रैखिक हैं। संकल्पनात्मक रूप से यह आवश्यक नहीं है और अधिक सामान्य द्वि-चरणीय प्रसंभाव्य प्रोग्रामों पर विचार किया जा सकता है। उदाहरण के लिए, यदि प्रथम-चरण की समस्या पूर्णांक है, तो प्रथम-चरण की समस्या में समाकलनीय व्यवरोधों को इस प्रकार जोड़ा जा सकता है कि सुसंगत समुच्चय असतत हो जाये। आवश्यकतानुसार अरैखिक उद्देश्यों और व्यवरोधों को भी सम्मिलित किया जा सकता है।

बंटनात्मक कल्पना

उपरोक्त द्वि-चरणीय समस्या का सूत्रीकरण यह मानता है कि द्वितीय-चरण के डेटा $\xi$ को ज्ञात प्रायिकता वितरण वाले एक यादृच्छिक सदिश के रूप में प्रतिरूपित किया गया है। यह कई स्थितियों में उचित होता है। उदाहरण के लिए, $\xi$ के बंटन को ऐतिहासिक आँकड़े से अनुमानित किया जा सकता है यदि मान जाता है कि वितरण किसी समयावधि में प्रभावशाली रूप से परिवर्तित नहीं होता है। इसके अतिरिक्त, प्रतिदर्श के प्रयोगसिद्ध बंटन का उपयोग $\xi$ के अग्रिम मानों के बंटन के सन्निकटन के रूप में किया जा सकता है। यदि $\xi$ का पूर्व मॉडल उपलब्ध है, तो बेज़ के अपडेट द्वारा पश्चवर्ती बंटन प्राप्त किया जा सकता है।

असततीकरण

द्वि-चरणीय की प्रसंभाव्य समस्या को संख्यात्मक रूप से हल करने के लिए, प्रायः यह मानने की आवश्यकता होती है कि यादृच्छिक सदिश $\xi$ में परिदृश्य नामक संभावित प्राप्तियों की संख्या सीमित है, माना ये $\xi _{1},\dots ,\xi _{K}$ हैं, जिनके संगत प्रायिकता द्रव्यमान $p_{1},\dots ,p_{K}$ हैं। तब प्रथम चरण की समस्या के उद्देश्य फलन में प्रत्याशा को निम्न योग के रूप में लिखा जा सकता है:

$$E[Q(x,\xi )]=\sum \limits _{k=1}^{K}p_{k}Q(x,\xi _{k})$$

और इसके अतिरिक्त, द्वि-चरणीय समस्या को एक बड़ी रैखिक प्रोग्रामन समस्या के रूप में सूत्रित किया जा सकता है (इसे मूल समस्या का निर्धारणात्मक समतुल्य कहा जाता है, § § यादृच्छिक समस्या का निर्धारक समतुल्य अनुभाग देखें)।

जब $\xi$ में संभावित प्राप्तियों की संख्या अपरिमित (या बहुत बड़ी) है, तो इस बंटन का निरूपण परिदृश्यों द्वारा करने के लिए मानक दृष्टिकोण है। यह दृष्टिकोण तीन प्रश्न उठाता है, अर्थात्:

1. परिदृश्यों का निर्माण कैसे करें, देखें § परिदृश्य निर्माण;
2. निर्धारणात्मक समतुल्य को कैसे हल करें। सीपीएलईएक्स, और जीएनयू रैखिक प्रोग्रामिंग किट (जीएलपीके) जैसे अनुकूलक बड़ी रैखिक/अरैखिक समस्याओं को हल कर सकते हैं। विस्कॉन्सिन विश्वविद्यालय, मैडिसन में आयोजित एनईओएस सर्वर कई आधुनिक हलकर्ताओं तक मुफ्त पहुँच की अनुमति प्रदान करता है। निर्धारणात्मक समतुल्य की संरचना बेंडर्स अपघटन या परिदृश्य अपघटन जैसी अपघटन विधियों को लागू करने के लिए विशेष रूप से उत्तरदायी है,
3. "सही" इष्टतम के सापेक्ष प्राप्त हल की गुणवत्ता को कैसे मापें।

ये प्रश्न स्वतंत्र नहीं हैं। उदाहरण के लिए, निर्मित परिदृश्यों की संख्या निर्धारणात्मक समतुल्य की वश्यता और प्राप्त हलों की गुणवत्ता दोनों को प्रभावित करती है।

प्रसंभाव्य रैखिक प्रोग्राम

एक प्रसंभाव्य रैखिक प्रोग्राम क्लासिकल टू-स्टेज प्रसंभाव्य प्रोग्राम का एक विशिष्ट उदाहरण है। एक प्रसंभाव्य एलपी मल्टी-पीरियड लीनियर प्रोग्राम (एलपी) के संग्रह से बनाया गया है, जिनमें से प्रत्येक की संरचना समान है लेकिन कुछ अलग डेटा है। $k^{th}$ एच> दो-अवधि एलपी, प्रतिनिधित्व करते हैं $k^{th}$ परिदृश्य, निम्नलिखित रूप होने के रूप में माना जा सकता है:

${\begin{array}{lccccccc}{\text{Minimize}}&f^{T}x&+&g^{T}y&+&h_{k}^{T}z_{k}&&\\{\text{subject to}}&Tx&+&Uy&&&=&r\\&&&V_{k}y&+&W_{k}z_{k}&=&s_{k}\\&x&,&y&,&z_{k}&\geq &0\end{array}}$

वैक्टर $x$ और $y$ में प्रथम-अवधि चर होते हैं, जिनके मान तुरंत चुने जाने चाहिए। सदिश $z_{k}$ में बाद की अवधि के लिए सभी चर शामिल हैं। विवशताएँ $Tx+Uy=r$ में केवल प्रथम-अवधि चर शामिल होते हैं और प्रत्येक परिदृश्य में समान होते हैं। अन्य बाधाओं में बाद की अवधि के चर शामिल हैं और भविष्य के बारे में अनिश्चितता को दर्शाते हुए परिदृश्य से परिदृश्य में कुछ मामलों में भिन्न हैं।

ध्यान दें कि हल करना $k^{th}$ दो-अवधि एलपी मानने के बराबर है $k^{th}$ बिना किसी अनिश्चितता के दूसरी अवधि में परिदृश्य। दूसरे चरण में अनिश्चितताओं को शामिल करने के लिए, किसी को अलग-अलग परिदृश्यों के लिए संभावनाओं को आवंटित करना चाहिए और संबंधित निर्धारणात्मक समतुल्य को हल करना चाहिए।

एक प्रसंभाव्य समस्या के निर्धारणात्मक समकक्ष

परिमित संख्या में परिदृश्यों के साथ, द्वि-चरणीय प्रसंभाव्य रैखिक कार्यक्रमों को बड़ी रैखिक प्रोग्रामिंग समस्याओं के रूप में तैयार किया जा सकता है। इस सूत्रीकरण को अक्सर निर्धारणात्मक समतुल्य रैखिक कार्यक्रम कहा जाता है, या निर्धारणात्मक समतुल्य के लिए संक्षिप्त किया जाता है। (सख्ती से एक निर्धारणात्मक समतुल्य बोलना कोई भी गणितीय कार्यक्रम है जिसका उपयोग इष्टतम प्रथम-चरण के निर्णय की गणना करने के लिए किया जा सकता है, इसलिए ये निरंतर संभाव्यता वितरण के लिए भी मौजूद रहेंगे, जब कोई किसी बंद रूप में दूसरे चरण की लागत का प्रतिनिधित्व कर सकता है।) के लिए उदाहरण के लिए, उपरोक्त प्रसंभाव्य रैखिक कार्यक्रम के समतुल्य समतुल्य बनाने के लिए, हम एक प्रायिकता प्रदान करते हैं $p_{k}$ प्रत्येक परिदृश्य के लिए $k=1,\dots ,K$।

फिर हम सभी परिदृश्यों से बाधाओं के अधीन उद्देश्य के अपेक्षित मान को कम कर सकते हैं:

${\begin{array}{lccccccccccccc}{\text{Minimize}}&f^{\top }x&+&g^{\top }y&+&p_{1}h_{1}^{\top }z_{1}&+&p_{2}h_{2}^{T}z_{2}&+&\cdots &+&p_{K}h_{K}^{\top }z_{K}&&\\{\text{subject to}}&Tx&+&Uy&&&&&&&&&=&r\\&&&V_{1}y&+&W_{1}z_{1}&&&&&&&=&s_{1}\\&&&V_{2}y&&&+&W_{2}z_{2}&&&&&=&s_{2}\\&&&\vdots &&&&&&\ddots &&&&\vdots \\&&&V_{K}y&&&&&&&+&W_{K}z_{K}&=&s_{K}\\&x&,&y&,&z_{1}&,&z_{2}&,&\ldots &,&z_{K}&\geq &0\\\end{array}}$ हमारे पास एक अलग सदिश है $z_{k}$ प्रत्येक परिदृश्य के लिए बाद की

हमारे पास एक अलग सदिश है प्रत्येक परिदृश्य के लिए बाद की अवधि के चर $k$। पहली अवधि के चर $x$ और $y$ हालाँकि, हर परिदृश्य में y समान होते हैं, क्योंकि हमें यह जानने से पहले पहली अवधि के लिए निर्णय लेना चाहिए कि कौन सा परिदृश्य साकार होगा। नतीजतन, बाधाओं को शामिल करना $x$ और $y$ को केवल एक बार निर्दिष्ट करने की आवश्यकता है, जबकि शेष बाधाओं को प्रत्येक परिदृश्य के लिए अलग से दिया जाना चाहिए।

परिदृश्य निर्माण

व्यवहार में भविष्य पर विशेषज्ञों की राय जानने के द्वारा परिदृश्यों का निर्माण करना संभव हो सकता है। निर्मित परिदृश्यों की संख्या अपेक्षाकृत मामूली होनी चाहिए ताकि प्राप्त निर्धारणात्मक समतुल्य को उचित कम्प्यूटेशनल प्रयास से हल किया जा सके। अक्सर यह दावा किया जाता है कि केवल कुछ परिदृश्यों का उपयोग करने वाला एक समाधान केवल एक परिदृश्य को मानने वाले समाधान की तुलना में अधिक अनुकूलनीय योजनाएं प्रदान करता है। कुछ मामलों में ऐसे दावे को अनुकरण द्वारा सत्यापित किया जा सकता है। सिद्धांत रूप में गारंटी के कुछ उपाय कि एक प्राप्त समाधान मूल समस्या को उचित सटीकता के साथ हल करता है। आम तौर पर अनुप्रयोगों में केवल प्रथम चरण इष्टतम समाधान $x^{*}$ का एक व्यावहारिक मान है क्योंकि लगभग हमेशा यादृच्छिक डेटा का "सत्य" अहसास निर्मित (उत्पन्न) परिदृश्यों के सेट से अलग होगा।

कल्पना करना $\xi$ में शामिल है $d$ स्वतंत्र यादृच्छिक घटक, जिनमें से प्रत्येक में तीन संभावित अहसास हैं (उदाहरण के लिए, प्रत्येक यादृच्छिक मापदंडों की भविष्य की प्राप्ति को निम्न, मध्यम और उच्च के रूप में वर्गीकृत किया गया है), तो परिदृश्यों की कुल संख्या है $K=3^{d}$। परिदृश्यों की संख्या में इस तरह की घातीय वृद्धि उचित आकार के लिए भी विशेषज्ञ की राय का उपयोग करके मॉडल विकास को बहुत कठिन बना देती है $d$। स्थिति और भी खराब हो जाती है अगर कुछ यादृच्छिक घटक $\xi$ का निरंतर वितरण है।

मोंटे कार्लो नमूनाकरण और नमूना औसत सन्निकटन (SAA) विधि

एक प्रबंधनीय आकार के लिए निर्धारित परिदृश्य को कम करने के लिए एक सामान्य दृष्टिकोण मोंटे कार्लो सिमुलेशन का उपयोग करना है। मान लीजिए परिदृश्यों की कुल संख्या बहुत बड़ी या अनंत है। आगे मान लीजिए कि हम एक नमूना उत्पन्न कर सकते हैं $\xi ^{1},\xi ^{2},\dots ,\xi ^{N}$ का $N$ यादृच्छिक सदिश की प्रतिकृति $\xi$. आमतौर पर नमूने को स्वतंत्र और समान रूप से वितरित (i.i.d नमूना) माना जाता है। एक नमूना दिया गया है, अपेक्षा फलन $q(x)=E[Q(x,\xi )]$ नमूना औसत द्वारा अनुमानित है

${\hat {q}}_{N}(x)={\frac {1}{N}}\sum _{j=1}^{N}Q(x,\xi ^{j})$ और फलस्वरूप प्रथम चरण की समस्या द्वारा दी गई है

${\begin{array}{rlrrr}{\hat {g}}_{N}(x)=&\min \limits _{x\in \mathbb {R} ^{n}}&c^{T}x+{\frac {1}{N}}\sum _{j=1}^{N}Q(x,\xi ^{j})&\\&{\text{subject to}}&Ax&=&b\\&&x&\geq &0\end{array}}$ इस सूत्रीकरण को नमूना औसत सन्निकटन विधि के रूप में जाना जाता है। SAA समस्या माने गए नमूने का एक कार्य है और इस अर्थ में यादृच्छिक है। दिए गए नमूने के लिए $\xi ^{1},\xi ^{2},\dots ,\xi ^{N}$ SAA समस्या परिदृश्यों के साथ द्वि-चरणीय प्रसंभाव्य रैखिक प्रोग्रामिंग समस्या के समान रूप की है $\xi ^{j}$., $j=1,\dots ,N$, प्रत्येक को समान संभावना के साथ लिया गया $p_{j}={\frac {1}{N}}$.

सांख्यिकीय निष्कर्ष

निम्नलिखित प्रसंभाव्य प्रोग्रामिंग समस्या पर विचार करें

$\min \limits _{x\in X}\{g(x)=f(x)+E[Q(x,\xi )]\}$

यहाँ $X$ का एक गैर-रिक्त बंद उपसमुच्चय है $\mathbb {R} ^{n}$, $\xi$ एक यादृच्छिक सदिश है जिसका संभाव्यता वितरण $P$ एक सेट पर समर्थित है $\Xi \subset \mathbb {R} ^{d}$, और $Q:X\times \Xi \rightarrow \mathbb {R}$. टू-स्टेज प्रसंभाव्य प्रोग्रामिंग के ढांचे में, $Q(x,\xi )$ संबंधित दूसरे चरण की समस्या के इष्टतम मान द्वारा दिया गया है।

ये मान लीजिए $g(x)$ सभी के लिए अच्छी तरह से परिभाषित और परिमित मानवान है $x\in X$. इसका तात्पर्य है कि प्रत्येक के लिए $x\in X$ मान $Q(x,\xi )$ लगभग निश्चित है।

मान लीजिए कि हमारे पास एक नमूना है $\xi ^{1},\dots ,\xi ^{N}$ का $N$यादृच्छिक सदिश की प्राप्ति $\xi$. इस यादृच्छिक नमूने को ऐतिहासिक डेटा के रूप में देखा जा सकता है $N$ के अवलोकन $\xi$, या इसे मोंटे कार्लो सैंपलिंग तकनीकों द्वारा उत्पन्न किया जा सकता है। तब हम एक संगत नमूना औसत सन्निकटन तैयार कर सकते हैं

$\min \limits _{x\in X}\{{\hat {g}}_{N}(x)=f(x)+{\frac {1}{N}}\sum _{j=1}^{N}Q(x,\xi ^{j})\}$

बड़ी संख्या के कानून के अनुसार हमारे पास कुछ नियमितता शर्तों के तहत है ${\frac {1}{N}}\sum _{j=1}^{N}Q(x,\xi ^{j})$ प्रायिकता 1 से बिंदुवार अभिसरित होता है $E[Q(x,\xi )]$ जैसा $N\rightarrow \infty$. इसके अलावा, हल्के अतिरिक्त परिस्थितियों में अभिसरण एक समान है। हमारे पास भी है $E[{\hat {g}}_{N}(x)]=g(x)$, अर्थात।, ${\hat {g}}_{N}(x)$ का निष्पक्ष आकलनकर्ता है $g(x)$. इसलिए, यह उम्मीद करना स्वाभाविक है कि SAA समस्या का इष्टतम मान और इष्टतम समाधान वास्तविक समस्या के अपने समकक्षों के साथ अभिसरण करते हैं क्योंकि $N\rightarrow \infty$.

एसएए अनुमानकों की संगति

संभव सेट मान लीजिए $X$ SAA समस्या का समाधान निश्चित है, अर्थात यह नमूने से स्वतंत्र है। होने देना $\vartheta ^{*}$ और $S^{*}$ वास्तविक समस्या का क्रमशः इष्टतम मान और इष्टतम समाधान का सेट हो और चलो ${\hat {\vartheta }}_{N}$ और ${\hat {S}}_{N}$ SAA समस्या का क्रमशः इष्टतम मान और इष्टतम समाधान का सेट हो।

1. होने देना $g:X\rightarrow \mathbb {R}$ और ${\hat {g}}_{N}:X\rightarrow \mathbb {R}$ (निर्धारणात्मक) वास्तविक मानवान कार्यों का एक क्रम हो। निम्नलिखित दो गुण समतुल्य हैं:
   • किसी के लिए ${\overline {x}}\in X$ और कोई अनुक्रम $\{x_{N}\}\subset X$ में अभिसरण ${\overline {x}}$ यह इस प्रकार है कि ${\hat {g}}_{N}(x_{N})$ में विलीन हो जाता है $g({\overline {x}})$
   • कार्यक्रम $g(\cdot )$ निरंतर चालू है $X$ और ${\hat {g}}_{N}(\cdot )$ में विलीन हो जाता है $g(\cdot )$ के किसी भी कॉम्पैक्ट सबसेट पर समान रूप से $X$
2. यदि SAA समस्या का उद्देश्य ${\hat {g}}_{N}(x)$ वास्तविक समस्या के उद्देश्य में परिवर्तित हो जाता है $g(x)$ संभाव्यता 1 के साथ, जैसा $N\rightarrow \infty$, समान रूप से व्यवहार्य सेट पर $X$. तब ${\hat {\vartheta }}_{N}$ में विलीन हो जाता है $\vartheta ^{*}$ प्रायिकता 1 के रूप में $N\rightarrow \infty$.
3. मान लीजिए कि एक कॉम्पैक्ट सेट मौजूद है $C\subset \mathbb {R} ^{n}$ ऐसा है कि
   • सेट $S$ वास्तविक समस्या का इष्टतम समाधान रिक्त नहीं है और इसमें निहित है $C$
   • कार्यक्रम $g(x)$ परिमित मानवान और निरंतर है $C$
   • कार्यों का क्रम ${\hat {g}}_{N}(x)$ में विलीन हो जाता है $g(x)$ संभाव्यता 1 के साथ, जैसा $N\rightarrow \infty$, समान रूप से $x\in C$
   • के लिए $N$ काफी बड़ा सेट ${\hat {S}}_{N}$ खाली नहीं है और ${\hat {S}}_{N}\subset C$ संभाव्यता 1 के साथ

तब ${\hat {\vartheta }}_{N}\rightarrow \vartheta ^{*}$ और $\mathbb {D} (S^{*},{\hat {S}}_{N})\rightarrow 0$ प्रायिकता 1 के रूप में $N\rightarrow \infty$. ध्यान दें कि $\mathbb {D} (A,B)$ सेट के विचलन को दर्शाता है $A$ सेट से $B$, के रूप में परिभाषित

$\mathbb {D} (A,B):=\sup _{x\in A}\{\inf _{x'\in B}\|x-x'\|\}$

कुछ स्थितियों में व्यवहार्य सेट $X$ SAA समस्या का अनुमान लगाया जाता है, तो संबंधित SAA समस्या का रूप ले लेती है

$\min _{x\in X_{N}}{\hat {g}}_{N}(x)$

जहाँ $X_{N}$ का उपसमुच्चय है $\mathbb {R} ^{n}$ नमूने के आधार पर और इसलिए यादृच्छिक है। फिर भी, SAA आकलनकर्ताओं के लिए निरंतरता परिणाम अभी भी कुछ अतिरिक्त धारणाओं के तहत प्राप्त किए जा सकते हैं:

1. मान लीजिए कि एक कॉम्पैक्ट सेट मौजूद है $C\subset \mathbb {R} ^{n}$ ऐसा है कि
   • सेट $S$ वास्तविक समस्या का इष्टतम समाधान रिक्त नहीं है और इसमें निहित है $C$
   • कार्यक्रम $g(x)$ परिमित मानवान और निरंतर है $C$
   • कार्यों का क्रम ${\hat {g}}_{N}(x)$ में विलीन हो जाता है $g(x)$ संभाव्यता 1 के साथ, जैसा $N\rightarrow \infty$, समान रूप से $x\in C$
   • के लिए $N$ काफी बड़ा सेट ${\hat {S}}_{N}$ खाली नहीं है और ${\hat {S}}_{N}\subset C$ संभाव्यता 1 के साथ
   • अगर $x_{N}\in X_{N}$ और $x_{N}$ प्रायिकता 1 के साथ एक बिंदु पर अभिसरित होता है $x$, तब $x\in X$
   • कुछ बिंदु के लिए $x\in S^{*}$ एक क्रम होता है $x_{N}\in X_{N}$ ऐसा है कि $x_{N}\rightarrow x$ संभाव्यता 1 के साथ।

तब ${\hat {\vartheta }}_{N}\rightarrow \vartheta ^{*}$ और $\mathbb {D} (S^{*},{\hat {S}}_{N})\rightarrow 0$ प्रायिकता 1 के रूप में $N\rightarrow \infty$.

एसएए इष्टतम मान के स्पर्शोन्मुख

मान लीजिए नमूना $\xi ^{1},\dots ,\xi ^{N}$ आई.आई.डी. और एक बिंदु तय करें $x\in X$. फिर नमूना औसत अनुमानक ${\hat {g}}_{N}(x)$, का $g(x)$, निष्पक्ष है और इसमें विचरण है ${\frac {1}{N}}\sigma ^{2}(x)$, जहाँ $\sigma ^{2}(x):=Var[Q(x,\xi )]$ परिमित माना जाता है। इसके अलावा, केंद्रीय सीमा प्रमेय द्वारा हमारे पास वह है

${\sqrt {N}}[{\hat {g}}_{N}-g(x)]\xrightarrow {\mathcal {D}} Y_{x}$

जहाँ $\xrightarrow {\mathcal {D}}$ वितरण में अभिसरण को दर्शाता है और $Y_{x}$ माध्य के साथ एक सामान्य वितरण है $0$ और विचरण $\sigma ^{2}(x)$, के रूप में लिखा गया है ${\mathcal {N}}(0,\sigma ^{2}(x))$.

दूसरे शब्दों में, ${\hat {g}}_{N}(x)$ विषम रूप से सामान्य वितरण है, यानी, बड़े के लिए $N$, ${\hat {g}}_{N}(x)$ माध्य के साथ लगभग सामान्य वितरण है $g(x)$ और विचरण ${\frac {1}{N}}\sigma ^{2}(x)$. यह निम्नलिखित (अनुमानित) की ओर जाता है $100(1-\alpha )$के लिए % विश्वास अंतराल $f(x)$:

$\left[{\hat {g}}_{N}(x)-z_{\alpha /2}{\frac {{\hat {\sigma }}(x)}{\sqrt {N}}},{\hat {g}}_{N}(x)+z_{\alpha /2}{\frac {{\hat {\sigma }}(x)}{\sqrt {N}}}\right]$

जहाँ $z_{\alpha /2}:=\Phi ^{-1}(1-\alpha /2)$ (यहाँ $\Phi (\cdot )$ मानक सामान्य वितरण के सीडीएफ को दर्शाता है) और

${\hat {\sigma }}^{2}(x):={\frac {1}{N-1}}\sum _{j=1}^{N}\left[Q(x,\xi ^{j})-{\frac {1}{N}}\sum _{j=1}^{N}Q(x,\xi ^{j})\right]^{2}$

का नमूना प्रसरण अनुमान है $\sigma ^{2}(x)$. यानी के आकलन में त्रुटि $g(x)$ आदेश का (संकीर्ण रूप से) है $O({\sqrt {N}})$.

अनुप्रयोग और उदाहरण

जैविक अनुप्रयोग

व्यावहारिक पारिस्थितिकी जैसे क्षेत्रों में जानवरों के व्यवहार को मॉडल करने के लिए अक्सर प्रसंभाव्य गतिशील प्रोग्रामिंग का उपयोग किया जाता है। इष्टतम फोर्जिंग के मॉडल के अनुभवजन्य परीक्षण, जैविक जीवन चक्र संक्रमण जैसे कि पक्षियों में भागना और परजीवी ततैया में अंडे देना व्यवहारिक निर्णय लेने के विकास की व्याख्या करने में इस मॉडलिंग तकनीक के मान को दर्शाता है। ये मॉडल आम तौर पर दो चरणों के बजाय कई चरणों वाले होते हैं।

आर्थिक अनुप्रयोग

अनिश्चितता के तहत निर्णय लेने को समझने में प्रसंभाव्य डायनेमिक प्रोग्रामिंग एक उपयोगी उपकरण है। अनिश्चितता के तहत पूंजीगत स्टॉक का संचय एक उदाहरण है; अक्सर इसका उपयोग संसाधन अर्थशास्त्रियों द्वारा जैव आर्थिक समस्याओं का विश्लेषण करने के लिए किया जाता है जहां मौसम, आदि में अनिश्चितता प्रवेश करती है।

उदाहरण: मल्टीस्टेज पोर्टफोलियो अनुकूलन

Main article: अंतर्कालिक पोर्टफोलियो चयन

See also: मर्टन की पोर्टफोलियो समस्या

निम्नलिखित मल्टी-स्टेज प्रसंभाव्य प्रोग्रामिंग के वित्त से एक उदाहरण है। मान लीजिए कि समय पर $t=0$ हमारे पास प्रारंभिक पूंजी है $W_{0}$ में निवेश करना $n$ संपत्तियां। आगे मान लीजिए कि हमें समय-समय पर अपने पोर्टफोलियो को पुनर्संतुलित करने की अनुमति है $t=1,\dots ,T-1$ लेकिन इसमें अतिरिक्त नकदी डाले बिना। प्रत्येक अवधि में $t$ हम वर्तमान धन के पुनर्वितरण के बारे में निर्णय लेते हैं $W_{t}$ बिच में $n$ संपत्तियां। होने देना $x_{0}=(x_{10},\dots ,x_{n0})$ एन संपत्ति में निवेश की गई प्रारंभिक राशि हो। हम चाहते हैं कि प्रत्येक $x_{i0}$ अऋणात्मक है और वह संतुलन समीकरण है $\sum _{i=1}^{n}x_{i0}=W_{0}$ धारण करना चाहिए।

कुल रिटर्न पर विचार करें $\xi _{t}=(\xi _{1t},\dots ,\xi _{nt})$ प्रत्येक अवधि के लिए $t=1,\dots ,T$. यह एक सदिश-मानवान यादृच्छिक प्रक्रिया बनाता है $\xi _{1},\dots ,\xi _{T}$. समय अवधि में $t=1$, हम राशियों को निर्दिष्ट करके पोर्टफोलियो को पुनर्संतुलित कर सकते हैं $x_{1}=(x_{11},\dots ,x_{n1})$ संबंधित संपत्तियों में निवेश किया। उस समय पहली अवधि में रिटर्न का एहसास हो गया है, इसलिए इस जानकारी का उपयोग पुनर्संतुलन निर्णय में करना उचित है। इस प्रकार, दूसरे चरण के फैसले, समय पर $t=1$, वास्तव में यादृच्छिक सदिश की प्राप्ति के कार्य हैं $\xi _{1}$, अर्थात।, $x_{1}=x_{1}(\xi _{1})$. इसी तरह, समय पर $t$ निर्णय $x_{t}=(x_{1t},\dots ,x_{nt})$ एक कार्य है $x_{t}=x_{t}(\xi _{[t]})$ द्वारा उपलब्ध कराई गई जानकारी के अनुसार $\xi _{[t]}=(\xi _{1},\dots ,\xi _{t})$ समय-समय पर यादृच्छिक प्रक्रिया का इतिहास $t$. कार्यों का एक क्रम $x_{t}=x_{t}(\xi _{[t]})$, $t=0,\dots ,T-1$, साथ $x_{0}$ स्थिर होने के नाते, निर्णय प्रक्रिया की कार्यान्वयन योग्य नीति को परिभाषित करता है। ऐसा कहा जाता है कि ऐसी नीति संभव है यदि यह संभावना 1 के साथ मॉडल की कमी को पूरा करती है, यानी गैर-नकारात्मकता की कमी $x_{it}(\xi _{[t]})\geq 0$, $i=1,\dots ,n$, $t=0,\dots ,T-1$, और धन की कमी का संतुलन,

$\sum _{i=1}^{n}x_{it}(\xi _{[t]})=W_{t},$

जहां अवधि में $t=1,\dots ,T$ धन $W_{t}$ द्वारा दिया गया है

$W_{t}=\sum _{i=1}^{n}\xi _{it}x_{i,t-1}(\xi _{[t-1]}),$

जो यादृच्छिक प्रक्रिया की प्राप्ति और समय तक के निर्णयों पर निर्भर करता है $t$.

मान लीजिए कि उद्देश्य अंतिम अवधि में इस धन की अपेक्षित उपयोगिता को अधिकतम करना है, अर्थात समस्या पर विचार करना

$\max E[U(W_{T})].$

यह एक मल्टीस्टेज प्रसंभाव्य प्रोग्रामिंग समस्या है, जहाँ से चरणों को क्रमांकित किया जाता है $t=0$ से $t=T-1$। अनुकूलन सभी कार्यान्वयन योग्य और व्यवहार्य नीतियों पर किया जाता है। समस्या के विवरण को पूरा करने के लिए किसी को भी यादृच्छिक प्रक्रिया के संभाव्यता वितरण को परिभाषित करने की आवश्यकता होती है $\xi _{1},\dots ,\xi _{T}$। यह विभिन्न तरीकों से किया जा सकता है। उदाहरण के लिए, प्रक्रिया के समय के विकास को परिभाषित करने वाला एक विशेष परिदृश्य वृक्ष का निर्माण कर सकता है। यदि प्रत्येक स्तर पर प्रत्येक परिसंपत्ति के यादृच्छिक रिटर्न को दो निरंतरताओं की अनुमति दी जाती है, अन्य संपत्तियों से स्वतंत्र, तो परिदृश्यों की कुल संख्या है $2^{nT}.$।}

गतिशील प्रोग्रामिंग समीकरण लिखने के लिए, उपरोक्त मल्टीस्टेज समस्या को समय में पिछड़ने पर विचार करें। अंतिम चरण में $t=T-1$, एक अहसास $\xi _{[T-1]}=(\xi _{1},\dots ,\xi _{T-1})$ यादृच्छिक प्रक्रिया ज्ञात है और $x_{T-2}$ चुना गया है। इसलिए, निम्नलिखित समस्या को हल करने की आवश्यकता है

${\begin{array}{lrclr}\max \limits _{x_{T-1}}&E[U(W_{T})|\xi _{[T-1]}]&\\{\text{subject to}}&W_{T}&=&\sum _{i=1}^{n}\xi _{iT}x_{i,T-1}\\&\sum _{i=1}^{n}x_{i,T-1}&=&W_{T-1}\\&x_{T-1}&\geq &0\end{array}}$

जहाँ $E[U(W_{T})|\xi _{[T-1]}]$ की सशर्त अपेक्षा को दर्शाता है $U(W_{T})$ दिया गया $\xi _{[T-1]}$. उपरोक्त समस्या का इष्टतम मान इस पर निर्भर करता है $W_{T-1}$ और $\xi _{[T-1]}$ और निरूपित किया जाता है $Q_{T-1}(W_{T-1},\xi _{[T-1]})$.

इसी तरह, चरणों में $t=T-2,\dots ,1$, समस्या का समाधान करना चाहिए

${\begin{array}{lrclr}\max \limits _{x_{t}}&E[Q_{t+1}(W_{t+1},\xi _{[t+1]})|\xi _{[t]}]&\\{\text{subject to}}&W_{t+1}&=&\sum _{i=1}^{n}\xi _{i,t+1}x_{i,t}\\&\sum _{i=1}^{n}x_{i,t}&=&W_{t}\\&x_{t}&\geq &0\end{array}}$

जिसका इष्टतम मान द्वारा निरूपित किया जाता है $Q_{t}(W_{t},\xi _{[t]})$. अंत में, मंच पर $t=0$, एक समस्या हल करता है

${\begin{array}{lrclr}\max \limits _{x_{0}}&E[Q_{1}(W_{1},\xi _{[1]})]&\\{\text{subject to}}&W_{1}&=&\sum _{i=1}^{n}\xi _{i,1}x_{i0}\\&\sum _{i=1}^{n}x_{i0}&=&W_{0}\\&x_{0}&\geq &0\end{array}}$

चरणवार स्वतंत्र यादृच्छिक प्रक्रिया

प्रक्रिया के सामान्य वितरण के लिए $\xi _{t}$, इन गतिशील प्रोग्रामिंग समीकरणों को हल करना कठिन हो सकता है। यदि प्रक्रिया नाटकीय रूप से सरल हो जाती है $\xi _{t}$ चरणवार स्वतंत्र है, अर्थात, $\xi _{t}$ से स्वतंत्र है $\xi _{1},\dots ,\xi _{t-1}$ के लिए $t=2,\dots ,T$. इस मामले में, संबंधित सशर्त अपेक्षाएं बिना शर्त अपेक्षाएं और कार्य बन जाती हैं $Q_{t}(W_{t})$, $t=1,\dots ,T-1$ पर निर्भर नहीं है $\xi _{[t]}$. वह है, $Q_{T-1}(W_{T-1})$ समस्या का इष्टतम मान है

${\begin{array}{lrclr}\max \limits _{x_{T-1}}&E[U(W_{T})]&\\{\text{subject to}}&W_{T}&=&\sum _{i=1}^{n}\xi _{iT}x_{i,T-1}\\&\sum _{i=1}^{n}x_{i,T-1}&=&W_{T-1}\\&x_{T-1}&\geq &0\end{array}}$

और $Q_{t}(W_{t})$ का इष्टतम मान है

${\begin{array}{lrclr}\max \limits _{x_{t}}&E[Q_{t+1}(W_{t+1})]&\\{\text{subject to}}&W_{t+1}&=&\sum _{i=1}^{n}\xi _{i,t+1}x_{i,t}\\&\sum _{i=1}^{n}x_{i,t}&=&W_{t}\\&x_{t}&\geq &0\end{array}}$

के लिए $t=T-2,\dots ,1$.

सॉफ्टवेयर उपकरण

मॉडलिंग भाषाएं

सभी असतत प्रसंभाव्य प्रोग्रामिंग समस्याओं को किसी भी बीजगणितीय मॉडलिंग भाषा के साथ प्रदर्शित किया जा सकता है, मैन्युअल रूप से स्पष्ट या निहित गैर-प्रत्याशाकता को लागू करने के लिए यह सुनिश्चित करने के लिए कि परिणामी मॉडल प्रत्येक चरण में उपलब्ध कराई गई जानकारी की संरचना का सम्मान करता है। एक सामान्य मॉडलिंग भाषा द्वारा उत्पन्न एक SP समस्या का एक उदाहरण काफी बड़ा हो जाता है (रैखिक रूप से परिदृश्यों की संख्या में), और इसका मैट्रिक्स उस संरचना को खो देता है जो समस्याओं के इस वर्ग के लिए आंतरिक है, जिसका समाधान समय पर अन्यथा शोषण किया जा सकता है विशिष्ट अपघटन एल्गोरिदम। विशेष रूप से SP के लिए डिज़ाइन की गई मॉडलिंग भाषाओं के एक्सटेंशन दिखाई देने लगे हैं, देखें:

• एआईएमएमएस - एसपी समस्याओं की परिभाषा का समर्थन करता है
• ईएमपी एसपी (प्रसंभाव्य प्रोग्रामिंग के लिए विस्तारित गणितीय प्रोग्रामिंग) - प्रसंभाव्य प्रोग्रामिंग को सुविधाजनक बनाने के लिए जीएएमएस का एक मॉड्यूल बनाया गया है (इसमें पैरामीट्रिक वितरण के लिए कीवर्ड, मौका की कमी और जोखिम के उपाय जैसे जोखिम पर मान और अपेक्षित कमी शामिल है)।
• एसएएमपीएल - एएमपीएल के एक्सटेंशन का एक सेट विशेष रूप से प्रसंभाव्य प्रोग्राम व्यक्त करने के लिए डिज़ाइन किया गया है (मौका बाधाओं के लिए सिंटैक्स शामिल है, एकीकृत मौके की कमी और मजबूत अनुकूलन समस्याएं)

वे दोनों SMPS उदाहरण स्तर प्रारूप उत्पन्न कर सकते हैं, जो सॉल्वर को समस्या की संरचना को गैर-निरर्थक रूप में बताता है।

यह भी देखें

• सहसंबंध अंतराल
• प्रसंभाव्य प्रोग्रामिंग के लिए विस्तारित गणितीय प्रोग्रामिंग (ईएमपी)
• जोखिम में एंट्रोपिक मान
• फोर्टएसपी
• एसएएमपीएल बीजगणितीय मॉडलिंग भाषा
• परिदृश्य अनुकूलन
• प्रसंभाव्य अनुकूलन
• अवसर-व्यवरोधित पोर्टफोलियो चयन

अग्रिम पठन

• John R. Birge and François V. Louveaux. Introduction to Stochastic Programming. Springer Verlag, New York, 1997.
• Kall, Peter; Wallace, Stein W. (1994). Stochastic programming. Wiley-Interscience Series in Systems and Optimization. Chichester: John Wiley & Sons, Ltd. pp. xii+307. ISBN 0-471-95158-7. MR 1315300.
• G. Ch. Pflug: Optimization of Stochastic Models. The Interface between Simulation and Optimization. Kluwer, Dordrecht, 1996.
• András Prékopa. Stochastic Programming. Kluwer Academic Publishers, Dordrecht, 1995.
• Andrzej Ruszczynski and Alexander Shapiro (eds.) (2003) Stochastic Programming. Handbooks in Operations Research and Management Science, Vol. 10, Elsevier.
• Shapiro, Alexander; Dentcheva, Darinka; Ruszczyński, Andrzej (2009). Lectures on stochastic programming: Modeling and theory (PDF). MPS/SIAM Series on Optimization. Vol. 9. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM). Mathematical Programming Society (MPS). pp. xvi+436. ISBN 978-0-89871-687-0. MR 2562798.
• Stein W. Wallace and William T. Ziemba (eds.) (2005) Applications of Stochastic Programming. MPS-SIAM Book Series on Optimization 5
• King, Alan J.; Wallace, Stein W. (2012). Modeling with Stochastic Programming. Springer Series in Operations Research and Financial Engineering. New York: Springer. ISBN 978-0-387-87816-4.

बाहरी संबंध

• Stochastic Programming Community Home Page