बाधा (गणित): Difference between revisions
No edit summary |
No edit summary |
||
| Line 21: | Line 21: | ||
== शब्दावली == | == शब्दावली == | ||
* यदि असमानता बाधा इष्टतम बिंदु पर समानता के साथ रखती है, तो बाधा को'' बाध्यकारी'' कहा जाता है क्योंकि बिंदु को बाधा की दिशा में परिवर्तित नहीं किया जा सकता है, भले ही ऐसा करने से उद्देश्य फलन के मूल्य में सुधार होगा। | * यदि असमानता बाधा इष्टतम बिंदु पर समानता के साथ रखती है, तो बाधा को'' बाध्यकारी'' कहा जाता है क्योंकि बिंदु को बाधा की दिशा में परिवर्तित नहीं किया जा सकता है, भले ही ऐसा करने से उद्देश्य फलन के मूल्य में सुधार होगा। | ||
* यदि एक असमानता बाधा इष्टतम बिंदु पर सख्त असमानता'' के रूप में रखती है (अर्थात, समानता के साथ नहीं है), तो बाधा को कहा जाता है {{visible anchor|गैर बाध्यकारी}}, क्योंकि बिंदु बाधा की दिशा में भिन्न हो सकता है, | * यदि एक असमानता बाधा इष्टतम बिंदु पर सख्त असमानता'' के रूप में रखती है (अर्थात, समानता के साथ नहीं है), तो बाधा को कहा जाता है {{visible anchor|गैर बाध्यकारी}}, क्योंकि बिंदु बाधा की दिशा में भिन्न हो सकता है, चूंकि ऐसा करना इष्टतम नहीं होगा। कुछ शर्तों के तहत, उदाहरण के लिए उत्तल अनुकूलन में, यदि कोई बाधा गैर बाध्यकारी है, तो उस बाधा के अभाव में भी अनुकूलन समस्या का एक ही समाधान होगा।'' | ||
* यदि किसी दिए गए बिंदु पर एक बाधा संतुष्ट नहीं होती है, तो उस बिंदु को अक्षम्य क्षेत्र कहा जाता है। | * यदि किसी दिए गए बिंदु पर एक बाधा संतुष्ट नहीं होती है, तो उस बिंदु को अक्षम्य क्षेत्र कहा जाता है। | ||
== हार्ड और नरम बाधाएं == | == हार्ड और नरम बाधाएं == | ||
यदि समस्या अनिवार्य करती है कि बाधाएँ संतुष्ट हों, जैसा कि ऊपर की चर्चा में है, बाधाओं को कभी-कभी कठिन बाधाओं के रूप में संदर्भित किया जाता है। | यदि समस्या अनिवार्य करती है कि बाधाएँ संतुष्ट हों, जैसा कि ऊपर की चर्चा में है, बाधाओं को कभी-कभी कठिन बाधाओं के रूप में संदर्भित किया जाता है।''चूंकि'' , कुछ समस्याओं में, जिन्हें कंस्ट्रेंट संतुष्टि समस्या फ्लेक्सिबल CSPs कहा जाता है, इसे प्राथमिकता दी जाती है लेकिन यह आवश्यक नहीं है कि कुछ बाधाओं को संतुष्ट किया जाए; ऐसी गैर-अनिवार्य बाधाओं को नरम बाधाओं के रूप में जाना जाता है। उदाहरण के लिए, वरीयता-आधारित नियोजन में नरम बाधाएँ उत्पन्न होती हैं। [[मैक्स-सीएसपी]] समस्या में, कई बाधाओं का उल्लंघन करने की अनुमति है, और समाधान की गुणवत्ता को संतुष्ट बाधाओं की संख्या से मापा जाता है। | ||
== वैश्विक बाधाएं == | == वैश्विक बाधाएं == | ||
वैश्विक बाधाएं<ref>{{Cite book|title=Handbook of constraint programming|last1=Rossi|first1=Francesca|last2=Van Beek|first2=Peter|last3=Walsh|first3=Toby|date=2006|publisher=Elsevier|isbn=9780080463643|edition=1st|location=Amsterdam|chapter=7|oclc=162587579}}</ref> एक साथ लिए गए कई चरों पर एक विशिष्ट संबंध का प्रतिनिधित्व करने वाली बाधाएँ हैं। उनमें से कुछ, जैसे कि [https://sofdem.github.io/gccat/gccat/Callअलग.html <code>alldifferent</code>] बाधा, एक सरल भाषा में परमाणु बाधाओं के संयोजन के रूप में फिर से लिखी जा सकती है: <code>alldifferent</code> बाधा एन चर पर रखती है <math>x_1... x_n</math>, और संतुष्ट है अगर चर जोड़े में अलग-अलग मान लेते हैं। यह शब्दार्थ की दृष्टि से असमानताओं के संयोजन के समतुल्य है <math>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</math>. अन्य वैश्विक बाधाएं बाधा ढांचे की अभिव्यक्तता का विस्तार करती हैं। इस मामले में, वे | वैश्विक बाधाएं<ref>{{Cite book|title=Handbook of constraint programming|last1=Rossi|first1=Francesca|last2=Van Beek|first2=Peter|last3=Walsh|first3=Toby|date=2006|publisher=Elsevier|isbn=9780080463643|edition=1st|location=Amsterdam|chapter=7|oclc=162587579}}</ref> एक साथ लिए गए कई चरों पर एक विशिष्ट संबंध का प्रतिनिधित्व करने वाली बाधाएँ हैं। उनमें से कुछ, जैसे कि [https://sofdem.github.io/gccat/gccat/Callअलग.html <code>alldifferent</code>] बाधा, एक सरल भाषा में परमाणु बाधाओं के संयोजन के रूप में फिर से लिखी जा सकती है: <code>alldifferent</code> बाधा एन चर पर रखती है <math>x_1... x_n</math>, और संतुष्ट है अगर चर जोड़े में अलग-अलग मान लेते हैं। यह शब्दार्थ की दृष्टि से असमानताओं के संयोजन के समतुल्य है <math>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</math>. अन्य वैश्विक बाधाएं बाधा ढांचे की अभिव्यक्तता का विस्तार करती हैं। इस मामले में, वे सामान्यतः मिश्रित समस्याओं की एक विशिष्ट संरचना पर कब्जा कर लेते हैं। उदाहरण के लिए, <code>[[Regular constraint|regular]]</code> बाधा व्यक्त करती है कि चर के अनुक्रम को [[स्वचालन|नियतात्मक परिमित automaton]] द्वारा स्वीकार किया जाता है। | ||
वैश्विक बाधाओं का उपयोग <ref>{{Cite book|title=Principles and Practice of Constraint Programming CP 2003 00 : 9th International Conference, CP 2003, Kinsale, Ireland, September 29 October 3, 2003. Proceedings|date=2003|publisher=Springer-Verlag Berlin Heidelberg|last=Rossi|first=Francesca|isbn=9783540451938|location=Berlin|oclc=771185146}}</ref> बाधा संतुष्टि समस्याओं के मॉडलिंग को सरल बनाने के लिए, बाधा भाषाओं की अभिव्यक्तता का विस्तार करने के लिए, और [[बाधा प्रोग्रामिंग]] में भी सुधार करने के लिए किया जाता है: वास्तव में, चरों पर पूरी तरह से विचार करके, हल करने की प्रक्रिया में अव्यवहार्य स्थितियों को पहले देखा जा सकता है। कई वैश्विक बाधाओं को [https://sofdem.github.io/gccat/ ऑनलाइन कैटलॉग] में संदर्भित किया गया है। | वैश्विक बाधाओं का उपयोग <ref>{{Cite book|title=Principles and Practice of Constraint Programming CP 2003 00 : 9th International Conference, CP 2003, Kinsale, Ireland, September 29 October 3, 2003. Proceedings|date=2003|publisher=Springer-Verlag Berlin Heidelberg|last=Rossi|first=Francesca|isbn=9783540451938|location=Berlin|oclc=771185146}}</ref> बाधा संतुष्टि समस्याओं के मॉडलिंग को सरल बनाने के लिए, बाधा भाषाओं की अभिव्यक्तता का विस्तार करने के लिए, और [[बाधा प्रोग्रामिंग]] में भी सुधार करने के लिए किया जाता है: वास्तव में, चरों पर पूरी तरह से विचार करके, हल करने की प्रक्रिया में अव्यवहार्य स्थितियों को पहले देखा जा सकता है। कई वैश्विक बाधाओं को [https://sofdem.github.io/gccat/ ऑनलाइन कैटलॉग] में संदर्भित किया गया है। | ||
Revision as of 16:56, 18 February 2023
गणित में, बाधा एक अनुकूलन (गणित) समस्या की एक शर्त है जिसे समाधान को संतुष्ट करना चाहिए। कई प्रकार की बाधाएँ हैं- मुख्य रूप से समानता (गणित) बाधाएँ, असमानता (गणित) बाधाएँ, और पूर्णांक प्रोग्रामिंग। सभी बाधाओं को संतुष्ट करने वाले उम्मीदवार समाधान के सेट को व्यवहार्य सेट कहा जाता है।[1]
उदाहरण
निम्नलिखित एक साधारण अनुकूलन समस्या है:
का विषय है
और
कहाँ वेक्टर को दर्शाता है (x1,x2).
इस उदाहरण में, पहली पंक्ति फ़ंक्शन को न्यूनतम करने के लिए परिभाषित करती है (उद्देश्य फ़ंक्शन, हानि फ़ंक्शन या लागत फ़ंक्शन कहा जाता है)। दूसरी और तीसरी पंक्तियाँ दो बाधाओं को परिभाषित करती हैं, जिनमें से पहली एक असमानता बाधा है और दूसरी एक समानता बाधा है। ये दो बाधाएँ कठिन बाधाएँ हैं, जिसका अर्थ है कि यह आवश्यक है कि वे संतुष्ट हों; वे उम्मीदवार समाधानों के व्यवहार्य सेट को परिभाषित करते हैं।
बाधाओं के बिना, समाधान (0,0) होगा, जहां सबसे कम मूल्य है। लेकिन यह समाधान बाधाओं को पूरा नहीं करता। ऊपर बताई गई विवश अनुकूलन समस्या का समाधान है , जो कि के सबसे छोटे मान वाला बिंदु है जो दो बाधाओं को संतुष्ट करता है।
शब्दावली
- यदि असमानता बाधा इष्टतम बिंदु पर समानता के साथ रखती है, तो बाधा को बाध्यकारी कहा जाता है क्योंकि बिंदु को बाधा की दिशा में परिवर्तित नहीं किया जा सकता है, भले ही ऐसा करने से उद्देश्य फलन के मूल्य में सुधार होगा।
- यदि एक असमानता बाधा इष्टतम बिंदु पर सख्त असमानता के रूप में रखती है (अर्थात, समानता के साथ नहीं है), तो बाधा को कहा जाता है गैर बाध्यकारी, क्योंकि बिंदु बाधा की दिशा में भिन्न हो सकता है, चूंकि ऐसा करना इष्टतम नहीं होगा। कुछ शर्तों के तहत, उदाहरण के लिए उत्तल अनुकूलन में, यदि कोई बाधा गैर बाध्यकारी है, तो उस बाधा के अभाव में भी अनुकूलन समस्या का एक ही समाधान होगा।
- यदि किसी दिए गए बिंदु पर एक बाधा संतुष्ट नहीं होती है, तो उस बिंदु को अक्षम्य क्षेत्र कहा जाता है।
हार्ड और नरम बाधाएं
यदि समस्या अनिवार्य करती है कि बाधाएँ संतुष्ट हों, जैसा कि ऊपर की चर्चा में है, बाधाओं को कभी-कभी कठिन बाधाओं के रूप में संदर्भित किया जाता है।चूंकि , कुछ समस्याओं में, जिन्हें कंस्ट्रेंट संतुष्टि समस्या फ्लेक्सिबल CSPs कहा जाता है, इसे प्राथमिकता दी जाती है लेकिन यह आवश्यक नहीं है कि कुछ बाधाओं को संतुष्ट किया जाए; ऐसी गैर-अनिवार्य बाधाओं को नरम बाधाओं के रूप में जाना जाता है। उदाहरण के लिए, वरीयता-आधारित नियोजन में नरम बाधाएँ उत्पन्न होती हैं। मैक्स-सीएसपी समस्या में, कई बाधाओं का उल्लंघन करने की अनुमति है, और समाधान की गुणवत्ता को संतुष्ट बाधाओं की संख्या से मापा जाता है।
वैश्विक बाधाएं
वैश्विक बाधाएं[2] एक साथ लिए गए कई चरों पर एक विशिष्ट संबंध का प्रतिनिधित्व करने वाली बाधाएँ हैं। उनमें से कुछ, जैसे कि alldifferent बाधा, एक सरल भाषा में परमाणु बाधाओं के संयोजन के रूप में फिर से लिखी जा सकती है: alldifferent बाधा एन चर पर रखती है , और संतुष्ट है अगर चर जोड़े में अलग-अलग मान लेते हैं। यह शब्दार्थ की दृष्टि से असमानताओं के संयोजन के समतुल्य है . अन्य वैश्विक बाधाएं बाधा ढांचे की अभिव्यक्तता का विस्तार करती हैं। इस मामले में, वे सामान्यतः मिश्रित समस्याओं की एक विशिष्ट संरचना पर कब्जा कर लेते हैं। उदाहरण के लिए, regular बाधा व्यक्त करती है कि चर के अनुक्रम को नियतात्मक परिमित automaton द्वारा स्वीकार किया जाता है।
वैश्विक बाधाओं का उपयोग [3] बाधा संतुष्टि समस्याओं के मॉडलिंग को सरल बनाने के लिए, बाधा भाषाओं की अभिव्यक्तता का विस्तार करने के लिए, और बाधा प्रोग्रामिंग में भी सुधार करने के लिए किया जाता है: वास्तव में, चरों पर पूरी तरह से विचार करके, हल करने की प्रक्रिया में अव्यवहार्य स्थितियों को पहले देखा जा सकता है। कई वैश्विक बाधाओं को ऑनलाइन कैटलॉग में संदर्भित किया गया है।
यह भी देखें
- बाधा बीजगणित
- करुश-कुह्न-टकर की स्थिति
- लैग्रेंज गुणक
- लेवल सेट
- रैखिक प्रोग्रामिंग
- नॉनलाइनियर प्रोग्रामिंग
- प्रतिबंध (गणित)
- संतुष्टि मॉड्यूलो सिद्धांत
संदर्भ
- ↑ Takayama, Akira (1985). Mathematical Economics (2nd ed.). New York: Cambridge University Press. p. 61. ISBN 0-521-31498-4.
- ↑ Rossi, Francesca; Van Beek, Peter; Walsh, Toby (2006). "7". Handbook of constraint programming (1st ed.). Amsterdam: Elsevier. ISBN 9780080463643. OCLC 162587579.
- ↑ Rossi, Francesca (2003). Principles and Practice of Constraint Programming CP 2003 00 : 9th International Conference, CP 2003, Kinsale, Ireland, September 29 October 3, 2003. Proceedings. Berlin: Springer-Verlag Berlin Heidelberg. ISBN 9783540451938. OCLC 771185146.
अग्रिम पठन
- 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.
