बाधा (गणित)

For constraints in Hamiltonian mechanics, see constraint (classical mechanics), first class constraint, primary constraint, and holonomic constraint.

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

उदाहरण

निम्नलिखित एक साधारण अनुकूलन समस्या है:

$\min f(\mathbf {x} )=x_{1}^{2}+x_{2}^{4}$

का विषय है

$x_{1}\geq 1$

और

$x_{2}=1,$

कहाँ $\mathbf {x}$ वेक्टर को दर्शाता है (x₁,x₂).

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

बाधाओं के बिना, समाधान (0,0) होगा, जहां $f(\mathbf {x} )$ सबसे कम मूल्य है। लेकिन यह समाधान बाधाओं को पूरा नहीं करता। ऊपर बताई गई विवश अनुकूलन समस्या का समाधान है $\mathbf {x} =(1,1)$, जो कि के सबसे छोटे मान वाला बिंदु है $f(\mathbf {x} )$ जो दो बाधाओं को संतुष्ट करता है।

शब्दावली

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

हार्ड और सॉफ्ट कंस्ट्रेंट

यदि समस्या अनिवार्य करती है कि बाधाएँ संतुष्ट हों, जैसा कि ऊपर की चर्चा में है, बाधाओं को कभी-कभी कठिन बाधाओं के रूप में संदर्भित किया जाता है। हालाँकि, कुछ समस्याओं में, जिन्हें कंस्ट्रेंट संतुष्टि समस्या#Flexible CSPs कहा जाता है, इसे प्राथमिकता दी जाती है लेकिन यह आवश्यक नहीं है कि कुछ बाधाओं को संतुष्ट किया जाए; ऐसी गैर-अनिवार्य बाधाओं को बाधा अनुकूलन#सामान्य रूप के रूप में जाना जाता है। उदाहरण के लिए, वरीयता-आधारित नियोजन में नरम बाधाएँ उत्पन्न होती हैं। मैक्स-सीएसपी समस्या में, कई बाधाओं का उल्लंघन करने की अनुमति है, और समाधान की गुणवत्ता को संतुष्ट बाधाओं की संख्या से मापा जाता है।

वैश्विक बाधाएं

वैश्विक बाधाएं एक साथ लिए गए कई चरों पर एक विशिष्ट संबंध का प्रतिनिधित्व करने वाली बाधाएँ हैं। उनमें से कुछ, जैसे कि alldifferent बाधा, एक सरल भाषा में परमाणु बाधाओं के संयोजन के रूप में फिर से लिखी जा सकती है: द alldifferent बाधा एन चर पर रखती है $x_{1}...x_{n}$, और संतुष्ट है अगर चर जोड़े में अलग-अलग मान लेते हैं। यह शब्दार्थ की दृष्टि से असमानताओं के संयोजन के समतुल्य है $x_{1}\neq x_{2},x_{1}\neq x_{3}...,x_{2}\neq x_{3},x_{2}\neq x_{4}...x_{n-1}\neq x_{n}$. अन्य वैश्विक बाधाएं बाधा ढांचे की अभिव्यक्तता का विस्तार करती हैं। इस मामले में, वे आमतौर पर मिश्रित समस्याओं की एक विशिष्ट संरचना पर कब्जा कर लेते हैं। उदाहरण के लिए, regular बाधा व्यक्त करती है कि चर के अनुक्रम को नियतात्मक परिमित automaton द्वारा स्वीकार किया जाता है।

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

यह भी देखें

• बाधा बीजगणित
• करुश-कुह्न-टकर की स्थिति
• लैग्रेंज गुणक
• लेवल सेट
• रैखिक प्रोग्रामिंग
• नॉनलाइनियर प्रोग्रामिंग
• प्रतिबंध (गणित)
• संतुष्टि मॉड्यूलो सिद्धांत

अग्रिम पठन

• Beveridge, Gordon S. G.; Schechter, Robert S. (1970). "Essential Features in Optimization". Optimization: Theory and Practice. New York: McGraw-Hill. pp. 5–8. ISBN 0-07-005128-3.

बाहरी संबंध

• Nonlinear programming FAQ
• Mathematical Programming Glossary