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

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}$ परिदृश्य को मानने के बराबर है। द्वितीय चरण में अनिश्चितताओं को समाविष्ट करने के लिए, भिन्न परिदृश्यों के लिए प्रायिकताओं को आवंटित करना चाहिए और संगत निर्धारणात्मक समतुल्य को हल करना चाहिए।

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

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

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

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

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

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

मोंटे कार्लो प्रतिचयन और प्रतिदर्श औसत सन्निकटन (एसएए) विधि

मोंटे कार्लो अनुकरण का उपयोग, एक प्रबंधनीय आकार के लिए निर्धारित परिदृश्य को कम करने के लिए एक सामान्य दृष्टिकोण है। माना परिदृश्यों की कुल संख्या अत्यधिक या अपरिमित है। आगे माना कि हम यादृच्छिक सदिश $\xi$ की $N$ प्रतिकृतियों का एक प्रतिदर्श $\xi ^{1},\xi ^{2},\dots ,\xi ^{N}$ उत्पन्न कर सकते हैं। सामान्यतः प्रतिदर्श को स्वतंत्र और समान रूप से वितरित (आई.आई.डी प्रतिदर्श) माना जाता है। दिए गए एक प्रतिदर्श के लिए, प्रत्याशा फलन $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}}$

इस सूत्रीकरण को प्रतिदर्श औसत सन्निकटन विधि के रूप में जाना जाता है। एसएए समस्या माने गए प्रतिदर्श का एक फलन है और इस अर्थ में यादृच्छिक है। दिए गए प्रतिदर्श $\xi ^{1},\xi ^{2},\dots ,\xi ^{N}$ के लिए, एसएए समस्या परिदृश्यों $\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$ के $N$ प्रतिफलनों का एक प्रतिदर्श $\xi ^{1},\dots ,\xi ^{N}$ है। इस यादृच्छिक प्रतिदर्श को $\xi$ के $N$ प्रेक्षणों को ऐतिहासिक आँकड़े के रूप में देखा जा सकता है, या इसे मोंटे कार्लो प्रतिरूपण तकनीकों द्वारा उत्पन्न किया जा सकता है। तब हम एक संगत प्रतिदर्श औसत सन्निकटन सूत्रित कर सकते हैं

$\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)$ का एक अनभिनत आंकलक है। इसलिए, यह आशा करना स्वाभाविक है कि एसएए समस्या का इष्टतम मान और इष्टतम हल वास्तविक समस्या के अपने समतुल्यों के साथ अभिसरण करते हैं क्योंकि $N\rightarrow \infty$।

एसएए आंकलकों की संगतता

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

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

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

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

कुछ स्थितियों में एसएए समस्या के सुसंगत समुच्चय $X$ का इष्टतमीकरण किया गया है, तो संगत एसएए समस्या निम्न रूप ग्रहण करती है

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

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

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

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

एसएए इष्टतम मान के उपगमन

माना प्रतिदर्श $\xi ^{1},\dots ,\xi ^{N}$ आई.आई.डी. है और एक बिंदु $x\in X$ को नियत करता है। फिर $g(x)$ का प्रतिदर्श औसत आंकलक ${\hat {g}}_{N}(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)$ वाला लगभग अभिलम्ब बंटन है। यह $f(x)$ के लिए निम्न (अनुमानित) $100(1-\alpha )$ % विश्वास्यता अंतराल की ओर जाता है:

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

प्रत्येक अवधि $t=1,\dots ,T$ के लिएक, ुल प्रतिफल $\xi _{t}=(\xi _{1t},\dots ,\xi _{nt})$ पर विचार करें। यह एक सदिश-मान यादृच्छिक प्रक्रिया $\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]})$, समय $t$ तक यादृच्छिक प्रक्रिया के इतिहास $\xi _{[t]}=(\xi _{1},\dots ,\xi _{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]}]$ दिये गये $\xi _{[T-1]}$ $U(W_{T})$ की सप्रतिबन्ध प्रत्याशा को दर्शाता है। उपरोक्त समस्या का इष्टतम मान $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}$, $t=2,\dots ,T$ के लिए $\xi _{1},\dots ,\xi _{t-1}$ से स्वतंत्र है। इस स्थिति में, संगत सप्रतिबन्ध प्रत्याशाएँ, अप्रतिबंध प्रत्याशाएँ बन जाती हैं, और फलन $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})$, $t=T-2,\dots ,1$ के लिए निम्न का इष्टतम मान है

${\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}}$

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

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

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

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

ये दोनों एसएमपीएस उदाहरण तत्क्षण स्तर प्रारूप उत्पन्न कर सकते हैं, जो गैर-निरर्थक रूप में समस्या की संरचना को हलकर्ताओं तक पहुँचाता है।

यह भी देखें

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

अग्रिम पठन

• 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