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

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

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

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

उदाहरण के लिए, फ़ंक्शन को कम करने की समस्या पर विचार करें $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}.$ कई समस्याओं में, संभव सेट एक बाधा को दर्शाता है कि एक या अधिक चर गैर-नकारात्मक होना चाहिए। शुद्ध पूर्णांक प्रोग्रामिंग समस्याओं में, संभव सेट पूर्णांकों (या उसके कुछ सबसेट) का सेट है। रैखिक प्रोग्रामिंग समस्याओं में, व्यवहार्य सेट एक उत्तल सेट polytope है: आयाम (गणित और भौतिकी) में एक क्षेत्र जिसकी सीमाएं hyperplanes द्वारा बनाई गई हैं और जिनके कोने वर्टेक्स (ज्यामिति) हैं।

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

उत्तल संभव सेट

See also: Convex optimization

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

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

कोई व्यवहार्य सेट नहीं

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

सीमित और असीमित संभव सेट

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

व्यवहार्य सेट घिरा हुआ सेट हो सकते हैं। उदाहरण के लिए, बाधा सेट {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.$

लीनियर प्रोग्रामिंग

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

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