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

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}$ है। इस यादृच्छिक प्रतिदर्श को ऐतिहासिक डेटा के रूप में देखा जा सकता है $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