संभाव्य क्षेत्र

पाँच रेखीय व्यवरोधों के साथ एक समस्या (नीले रंग में, गैर-नकारात्मकता व्यवरोधों सहित)। पूर्णांक बाधाओं की अनुपस्थिति में संभाव्य समुच्चय पूरे क्षेत्र को नीले रंग से घिरा हुआ है, लेकिन पूर्णांक बाधाओं के साथ यह लाल बिंदुओं का समुच्चय है।

तीन चर के साथ रैखिक प्रोग्रामिंग समस्या का बंद संभाव्य क्षेत्र अवमुख बहुतल है।

गणितीय अनुकूलन में, संभाव्य क्षेत्र, संभाव्य समुच्चय, खोज स्थान, या समाधान स्थान अनुकूलन समस्या के सभी संभावित बिंदुओं (चयन चर के मूल्यों के समुच्चय) का समुच्चय है जो समस्या की बाधा (गणित) को संतुष्ट करता है, संभावित रूप से असमानता सहित ( गणित), समानता (गणित), और पूर्णांक प्रतिबंध। उम्मीदवारों के समुच्चय को कम करने से पहले, यह समस्या के कैंडिडेट सलूशन का प्रारंभिक समुच्चय है।

उदाहरण के लिए, फलन को कम करने की समस्या पर विचार करें $x^{2}+y^{4}$ चर के संबंध में $x$ और $y,$ का विषय है $1\leq x\leq 10$ और $5\leq y\leq 12.\,$ यहाँ साध्य समुच्चय युग्मों (x, y) का समुच्चय है जिसमें x का मान कम से कम 1 और अधिक से अधिक 10 तथा y का मान कम से कम 5 और अधिक से अधिक 12 है। समस्या का साध्य समुच्चय अलग है। उद्देश्य फलन से, जो मानदंड को अनुकूलित करने के लिए कहता है और जो उपरोक्त उदाहरण में है $x^{2}+y^{4}.$

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

बाधा संतुष्टि संभाव्य क्षेत्र में एक बिंदु खोजने की प्रक्रिया है।

अवमुख संभाव्य समुच्चय

See also: उत्तल अनुकूलन

रैखिक प्रोग्रामिंग समस्या में, रैखिक बाधाओं की एक श्रृंखला उन चरों के लिए संभावित मानों का अवमुख संभाव्य क्षेत्र उत्पन्न करती है। द्वि-चर स्थितियों में यह क्षेत्र अवमुख सरल बहुभुज के आकार में है।

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

संभाव्य समुच्चय की अनुपस्थिति

यदि अनुकूलन समस्या की बाधाएँ परस्पर विरोधाभासी हैं, तो ऐसे कोई बिंदु नहीं हैं जो सभी बाधाओं को पूरा करते हैं और इस प्रकार संभाव्य क्षेत्र खाली समुच्चय है। इस स्थितियों में समस्या का कोई हल नहीं है और इसे अक्षम्य कहा जाता है।

सीमित और असीमित संभाव्य समुच्चय

परिबद्ध सुसंगत समुच्चय (शीर्ष) और एक अपरिबद्ध साध्य समुच्चय (नीचे)। नीचे का समुच्चय दाहिनी ओर सदैव के लिए जारी रहता है।

संभाव्य समुच्चय घिरा हुआ समुच्चय हो सकता हैं। उदाहरण के लिए, बाधा समुच्चय {x ≥ 0, y ≥ 0} द्वारा परिभाषित संभाव्य समुच्चय अबाधित है क्योंकि कुछ दिशाओं में कोई सीमा नहीं है कि कोई कितनी दूर तक जा सकता है और अभी भी संभाव्य क्षेत्र में हो सकता है। इसके विपरीत, व्यवरोध समुच्चय {x ≥ 0, y ≥ 0, x + 2y ≤ 4} द्वारा गठित संभाव्य समुच्चय परिबद्ध है क्योंकि किसी भी दिशा में संचलन की सीमा व्यवरोधों द्वारा सीमित है।

n चरों वाली रैखिक प्रोग्रामिंग समस्याओं में, संभाव्य समुच्चय को परिबद्ध करने के लिए आवश्यक नियम यह है कि व्यवरोधों की संख्या कम से कम n + 1 हो (जैसा कि ऊपर दिए गए उदाहरण में दिखाया गया है)।

यदि संभाव्य समुच्चय असीमित है, तो उद्देश्य फलन के विनिर्देशों के आधार पर इष्टतम हो सकता है या नहीं भी हो सकता है। उदाहरण के लिए, यदि संभाव्य क्षेत्र को बाधा समुच्चय {x ≥ 0, y ≥ 0} द्वारा परिभाषित किया गया है, तो x + y को अधिकतम करने की समस्या का कोई इष्टतम नहीं है क्योंकि x या y को बढ़ाकर किसी भी कैंडिडेट सलूशन में सुधार किया जा सकता है; फिर भी यदि समस्या x + y को कम करने की है, तो इष्टतम (विशेष रूप से (x, y) = (0, 0) पर) है।

कैंडिडेट सलूशन

गणितीय अनुकूलन और गणित की अन्य शाखाओं में, और खोज एल्गोरिदम (कंप्यूटर विज्ञान में एक विषय) में, एक कैंडिडेट सलूशन किसी समस्या के संभाव्य क्षेत्र में संभावित समाधानों के समुच्चय (गणित) का एक तत्व (गणित) है। एक कैंडिडेट सलूशन को समस्या का एक संभावित या उचित समाधान नहीं होना चाहिए - यह केवल उस समुच्चय में है जो सभी बाधाओं (गणित) को संतुष्ट करता है; किंतु यह संभाव्य समाधानों के समुच्चय में है। विभिन्न प्रकार की अनुकूलन समस्याओं को हल करने के लिए एल्गोरिदम अधिकांशतः कैंडिडेट सलूशनों के समुच्चय को संभाव्य समाधानों के सबसमुच्चय तक सीमित कर देते हैं, जिनके अंक कैंडिडेट सलूशन के रूप में बने रहते हैं जबकि अन्य संभाव्य समाधान उम्मीदवारों के रूप में बाहर कर दिए जाते हैं।

किसी भी संभावित बिंदु को बाहर करने से पहले, सभी उम्मीदवार समाधानों का स्थान, संभाव्य क्षेत्र, संभाव्य समुच्चय, खोज स्थान या समाधान स्थान कहा जाता है। यह उन सभी संभावित समाधानों का समूह है जो समस्या की बाधाओं को पूरा करते हैं। बाधा संतुष्टि संभाव्य समुच्चय में बिंदु खोजने की प्रक्रिया है।

जेनेटिक एल्गोरिद्म

आनुवंशिक एल्गोरिथम के स्थितियों में, कैंडिडेट सलूशन एल्गोरिथम द्वारा विकसित की जा रही जनसंख्या में व्यक्ति हैं।

कलन

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

फार्म के एकपदियों के प्रतिअवकलज लेने में $x^{n},$ कैवलियरी के चतुर्भुज सूत्र का उपयोग करने वाला कैंडिडेट सलूशन होगा ${\tfrac {1}{n+1}}x^{n+1}+C.$ यह कैंडिडेट सलूशन वास्तव में कब को छोड़कर सही है $n=-1.$

रैखिक प्रोग्रामिंग

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

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