बाधा (गणित)

For हैमिल्टनियन यांत्रिकी में बाधाओं के लिए, see बाधा (शास्त्रीय यांत्रिकी),; प्रथम श्रेणी बाधा; प्राथमिक बाधा; and होलोनोमिक बाधा.

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

उदाहरण

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

$\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} )$ जो दो बाधाओं को संतुष्ट करता है।

शब्दावली

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

कठिन और नरम बाधाएं

यदि समस्या अनिवार्य होती है कि बाधाएँ संतुष्ट हों, जैसा कि ऊपर की वर्णन में है, बाधाओं को कभी-कभी कठिन बाधाओं के रूप में संदर्भित किया जाता है।चूंकि, कुछ समस्याओं में, जिन्हें कंस्ट्रेंट संतुष्टि समस्या (फ्लेक्सिबल 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बाधा व्यक्त करती है कि चर के अनुक्रम को नियतात्मक परिमित द्वारा स्वीकार किया जाता है।

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

यह भी देखें

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

अग्रिम पठन

• 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