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

For the context of control theory, see Stochastic control.

गणितीय अनुकूलन के क्षेत्र में, स्टोकेस्टिक प्रोग्रामिंग गणितीय मॉडल अनुकूलन (गणित) समस्याओं के लिए एक ढांचा है जिसमें अनिश्चितता शामिल है। एक स्टोकेस्टिक प्रोग्राम एक अनुकूलन समस्या है जिसमें कुछ या सभी समस्या पैरामीटर अनिश्चित हैं, लेकिन ज्ञात संभाव्यता वितरण का पालन करते हैं। यह ढांचा नियतात्मक अनुकूलन के विपरीत है, जिसमें सभी समस्या मापदंडों को सटीक रूप से ज्ञात माना जाता है। स्टोकेस्टिक प्रोग्रामिंग का लक्ष्य एक निर्णय खोजना है जो निर्णय निर्माता द्वारा चुने गए कुछ मानदंडों का अनुकूलन करता है, और समस्या के मापदंडों की अनिश्चितता के लिए उचित रूप से खाता है। क्योंकि कई वास्तविक दुनिया के फैसलों में अनिश्चितता शामिल है, स्टोकेस्टिक प्रोग्रामिंग ने वित्त से लेकर परिवहन से लेकर ऊर्जा अनुकूलन तक के व्यापक क्षेत्रों में आवेदन पाया है।

दो चरण की समस्याएं

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

$$\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)$ दूसरे चरण की समस्या का डेटा शामिल है। इस सूत्रीकरण में, पहले चरण में हमें अभी और अभी निर्णय लेना है $x$ अनिश्चित डेटा की प्राप्ति से पहले $\xi$, एक यादृच्छिक वेक्टर के रूप में देखा जाता है। दूसरे चरण में, की प्राप्ति के बाद $\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})$$

और, इसके अलावा, दो-चरण की समस्या को एक बड़ी रैखिक प्रोग्रामिंग समस्या के रूप में तैयार किया जा सकता है (इसे मूल समस्या का नियतात्मक समतुल्य कहा जाता है, खंड देखें § Deterministic equivalent of a stochastic problem).

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

1. परिदृश्यों का निर्माण कैसे करें, देखें § Scenario construction;
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$ हालाँकि, हर परिदृश्य में समान हैं, क्योंकि हमें यह जानने से पहले पहली अवधि के लिए निर्णय लेना चाहिए कि कौन सा परिदृश्य साकार होगा। नतीजतन, बाधाओं को शामिल करना $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}})$.

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

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

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

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

अनिश्चितता के तहत निर्णय लेने को समझने में स्टोकेस्टिक डायनेमिक प्रोग्रामिंग एक उपयोगी उपकरण है। अनिश्चितता के तहत पूंजीगत स्टॉक का संचय एक उदाहरण है; अक्सर इसका उपयोग संसाधन अर्थशास्त्रियों द्वारा निकोलस जॉर्जस्कु-रोगेन#मैन27 के आर्थिक संघर्ष और मानव जाति के सामाजिक विकास का विश्लेषण करने के लिए किया जाता है।28जैव अर्थशास्त्र।29 जहां अनिश्चितता प्रवेश करती है जैसे कि मौसम आदि।

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

Main article: Intertemporal portfolio choice

See also: Merton's portfolio problem

निम्नलिखित मल्टी-स्टेज स्टोकेस्टिक प्रोग्रामिंग के वित्त से एक उदाहरण है। मान लीजिए कि समय पर $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 उदाहरण स्तर प्रारूप उत्पन्न कर सकते हैं, जो सॉल्वर को समस्या की संरचना को गैर-निरर्थक रूप में बताता है।

यह भी देखें

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

अग्रिम पठन

• 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