बाधा (गणित): Difference between revisions
No edit summary |
No edit summary |
||
(7 intermediate revisions by 4 users not shown) | |||
Line 1: | Line 1: | ||
{{short description|Condition of an optimization problem which the solution must satisfy}} | {{short description|Condition of an optimization problem which the solution must satisfy}} | ||
गणित में, '''बाधा''' अनुकूलन (गणित) समस्या ऐसा प्रतिबन्ध है जिसे समाधान को संतुष्ट करना चाहिए। कई प्रकार की बाधाएँ हैं- मुख्य रूप से [[समानता (गणित)]] बाधाएँ, [[असमानता (गणित)]] बाधाएँ, और पूर्णांक प्रोग्रामिंग है। सभी बाधाओं को संतुष्ट करने वाले प्रत्याशी समाधान के समूह को व्यवहार्य समूह कहा जाता है।<ref>{{cite book |first=Akira |last=Takayama |title=Mathematical Economics |location=New York |publisher=Cambridge University Press |edition=2nd |year=1985 |isbn=0-521-31498-4 |page=[https://archive.org/details/mathematicalecon00taka/page/61 61] |url=https://archive.org/details/mathematicalecon00taka |url-access=registration }}</ref> | |||
गणित में, बाधा | |||
== उदाहरण == | == उदाहरण == | ||
निम्नलिखित | निम्नलिखित साधारण अनुकूलन समस्या है: | ||
:<math>\min f(\mathbf x) = x_1^2+x_2^4</math> | :<math>\min f(\mathbf x) = x_1^2+x_2^4</math> | ||
का विषय है | का विषय है | ||
Line 13: | Line 10: | ||
:<math>x_2 = 1,</math> | :<math>x_2 = 1,</math> | ||
जहाँ <math>\mathbf x</math> वेक्टर को दर्शाता है (x<sub>1</sub>,x<sub>2</sub>). | |||
इस उदाहरण में, | इस उदाहरण में, प्रथम पंक्ति फ़ंक्शन को न्यूनतम करने के लिए परिभाषित करती है (उद्देश्य फ़ंक्शन, हानि फ़ंक्शन या व्यय फ़ंक्शन कहा जाता है)। द्वितीय और तृतीय पंक्तियाँ दो बाधाओं को परिभाषित करती हैं, जिनमें से प्रथम असमानता बाधा है और द्वितीय समानता बाधा है। ये दो बाधाएँ कठिन बाधाएँ हैं, जिसका अर्थ है कि वे संतुष्ट हों; वे प्रत्याशी समाधानों के व्यवहार्य समूह को परिभाषित करते हैं। | ||
बाधाओं के बिना, समाधान (0,0) होगा, जहां <math>f(\mathbf x)</math> सबसे | बाधाओं के बिना, समाधान (0,0) होगा, जहां <math>f(\mathbf x)</math> का सबसे अल्प मूल्य है। लेकिन यह समाधान बाधाओं को पूर्ण नहीं करता। ऊपर बताई गई [[विवश अनुकूलन]] समस्या का समाधान है <math>\mathbf x = (1,1)</math>, जो कि सबसे छोटे मान वाला बिंदु है <math>f(\mathbf x)</math> जो दो बाधाओं को संतुष्ट करता है। | ||
== शब्दावली == | == शब्दावली == | ||
* यदि असमानता बाधा इष्टतम बिंदु पर समानता के साथ रखती है, तो बाधा को'' बाध्यकारी'' कहा जाता है क्योंकि बिंदु को बाधा की दिशा में परिवर्तित नहीं किया जा सकता है, | * यदि असमानता बाधा इष्टतम बिंदु पर समानता के साथ रखती है, तो बाधा को'' बाध्यकारी'' कहा जाता है क्योंकि बिंदु को बाधा की दिशा में परिवर्तित नहीं किया जा सकता है, ऐसा करने से उद्देश्य फलन के मूल्य में सुधार होगा। | ||
* यदि | * यदि असमानता बाधा इष्टतम बिंदु पर कठोर असमानता के रूप में होती है (अर्थात, समानता के साथ नहीं है), तो {{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> | वैश्विक बाधाएं<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>बाधा व्यक्त करती है कि चर के अनुक्रम को नियतात्मक परिमित द्वारा स्वीकार किया जाता है। | ||
वैश्विक बाधाओं का उपयोग <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> बाधा संतुष्टि समस्याओं के मॉडलिंग को सरल बनाने के लिए, बाधा भाषाओं की अभिव्यक्तता का विस्तार करने के लिए, और | वैश्विक बाधाओं का उपयोग <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/ ऑनलाइन कैटलॉग] में संदर्भित किया गया है। | ||
== यह भी देखें == | == यह भी देखें == | ||
Line 44: | Line 41: | ||
* संतुष्टि मॉड्यूलो सिद्धांत | * संतुष्टि मॉड्यूलो सिद्धांत | ||
{{Div col end}} | {{Div col end}} | ||
== संदर्भ == | == संदर्भ == | ||
{{Reflist}} | {{Reflist}} | ||
== अग्रिम पठन == | == अग्रिम पठन == | ||
* {{cite book |first=Gordon S. G. |last=Beveridge |first2=Robert S. |last2=Schechter |chapter=Essential Features in Optimization |title=Optimization: Theory and Practice |location=New York |publisher=McGraw-Hill |year=1970 |pages=5–8 |isbn=0-07-005128-3 |chapter-url=https://books.google.com/books?id=TfhVXlWtOPQC&pg=PA5 }} | * {{cite book |first=Gordon S. G. |last=Beveridge |first2=Robert S. |last2=Schechter |chapter=Essential Features in Optimization |title=Optimization: Theory and Practice |location=New York |publisher=McGraw-Hill |year=1970 |pages=5–8 |isbn=0-07-005128-3 |chapter-url=https://books.google.com/books?id=TfhVXlWtOPQC&pg=PA5 }} | ||
== बाहरी संबंध == | == बाहरी संबंध == | ||
*[http://www.neos-guide.org/non-lp-faq Nonlinear programming FAQ] | *[http://www.neos-guide.org/non-lp-faq Nonlinear programming FAQ] | ||
*[http://glossary.computing.society.informs.org/ Mathematical Programming Glossary] | *[http://glossary.computing.society.informs.org/ Mathematical Programming Glossary] | ||
[[ca:Restricció]] | [[ca:Restricció]] | ||
[[es:Restricción (matemáticas)]] | [[es:Restricción (matemáticas)]] | ||
[[Category:Articles with hatnote templates targeting a nonexistent page]] | |||
[[Category: | |||
[[Category:Created On 13/02/2023]] | [[Category:Created On 13/02/2023]] | ||
[[Category:Lua-based templates]] | |||
[[Category:Machine Translated Page]] | |||
[[Category:Multi-column templates]] | |||
[[Category:Pages using div col with small parameter]] | |||
[[Category:Pages with script errors]] | |||
[[Category:Short description with empty Wikidata description]] | |||
[[Category:Templates Vigyan Ready]] | |||
[[Category:Templates that add a tracking category]] | |||
[[Category:Templates that generate short descriptions]] | |||
[[Category:Templates using TemplateData]] | |||
[[Category:Templates using under-protected Lua modules]] | |||
[[Category:Wikipedia fully protected templates|Div col]] | |||
[[Category:गणितीय अनुकूलन]] | |||
[[Category:बाधा प्रोग्रामिंग]] |
Latest revision as of 14:48, 27 October 2023
गणित में, बाधा अनुकूलन (गणित) समस्या ऐसा प्रतिबन्ध है जिसे समाधान को संतुष्ट करना चाहिए। कई प्रकार की बाधाएँ हैं- मुख्य रूप से समानता (गणित) बाधाएँ, असमानता (गणित) बाधाएँ, और पूर्णांक प्रोग्रामिंग है। सभी बाधाओं को संतुष्ट करने वाले प्रत्याशी समाधान के समूह को व्यवहार्य समूह कहा जाता है।[1]
उदाहरण
निम्नलिखित साधारण अनुकूलन समस्या है:
का विषय है
और
जहाँ वेक्टर को दर्शाता है (x1,x2).
इस उदाहरण में, प्रथम पंक्ति फ़ंक्शन को न्यूनतम करने के लिए परिभाषित करती है (उद्देश्य फ़ंक्शन, हानि फ़ंक्शन या व्यय फ़ंक्शन कहा जाता है)। द्वितीय और तृतीय पंक्तियाँ दो बाधाओं को परिभाषित करती हैं, जिनमें से प्रथम असमानता बाधा है और द्वितीय समानता बाधा है। ये दो बाधाएँ कठिन बाधाएँ हैं, जिसका अर्थ है कि वे संतुष्ट हों; वे प्रत्याशी समाधानों के व्यवहार्य समूह को परिभाषित करते हैं।
बाधाओं के बिना, समाधान (0,0) होगा, जहां का सबसे अल्प मूल्य है। लेकिन यह समाधान बाधाओं को पूर्ण नहीं करता। ऊपर बताई गई विवश अनुकूलन समस्या का समाधान है , जो कि सबसे छोटे मान वाला बिंदु है जो दो बाधाओं को संतुष्ट करता है।
शब्दावली
- यदि असमानता बाधा इष्टतम बिंदु पर समानता के साथ रखती है, तो बाधा को बाध्यकारी कहा जाता है क्योंकि बिंदु को बाधा की दिशा में परिवर्तित नहीं किया जा सकता है, ऐसा करने से उद्देश्य फलन के मूल्य में सुधार होगा।
- यदि असमानता बाधा इष्टतम बिंदु पर कठोर असमानता के रूप में होती है (अर्थात, समानता के साथ नहीं है), तो गैर बाध्यकारी को बाधा कहा जाता है, क्योंकि बिंदु बाधा की दिशा में भिन्न हो सकता है, चूंकि ऐसा करना इष्टतम नहीं होगा। कुछ प्रतिबन्ध के अनुसार, उदाहरण के लिए उत्तल अनुकूलन में, यदि कोई बाधा गैर बाध्यकारी है, तो उस बाधा के अभाव में भी अनुकूलन समस्या का ही समाधान होगा।
- यदि किसी दिए गए बिंदु पर बाधा संतुष्ट नहीं होती है, तो उस बिंदु को अक्षम्य क्षेत्र कहा जाता है।
कठिन और नरम बाधाएं
यदि समस्या अनिवार्य होती है कि बाधाएँ संतुष्ट हों, जैसा कि ऊपर की वर्णन में है, बाधाओं को कभी-कभी कठिन बाधाओं के रूप में संदर्भित किया जाता है।चूंकि, कुछ समस्याओं में, जिन्हें कंस्ट्रेंट संतुष्टि समस्या (फ्लेक्सिबल CSPs) कहा जाता है, इसे प्राथमिकता दी जाती है लेकिन यह आवश्यक नहीं है कि कुछ बाधाओं को संतुष्ट किया जाए; ऐसी गैर-अनिवार्य बाधाओं को नरम बाधाओं के रूप में जाना जाता है। उदाहरण के लिए, वरीयता-आधारित नियोजन में नरम बाधाएँ उत्पन्न होती हैं। मैक्स-सीएसपी समस्या में, कई बाधाओं का उल्लंघन करने की अनुमति है, और समाधान की गुणवत्ता को संतुष्ट बाधाओं की संख्या से मापा जाता है।
वैश्विक बाधाएं
वैश्विक बाधाएं[2] साथ लिए गए कई चरों पर विशिष्ट संबंध का प्रतिनिधित्व करने वाली बाधाएँ हैं। उनमें से कुछ, जैसे कि alldifferent
बाधा, सरल भाषा में परमाणु बाधाओं के संयोजन के रूप में फिर से लिखी जा सकती है: alldifferent
बाधा एन चर पर होती है , संतुष्ट है किन्तु चर जोड़े में भिन्न-भिन्न मान होते हैं। यह शब्दार्थ की दृष्टि से असमानताओं के संयोजन के समतुल्य है। अन्य वैश्विक बाधाएं बाधा के रूप में अभिव्यक्तता का विस्तार करती हैं। इस विषय में, वे सामान्यतः मिश्रित समस्याओं की विशिष्ट संरचना पर प्रभुत्व कर लेते हैं। उदाहरण के लिए, regular
बाधा व्यक्त करती है कि चर के अनुक्रम को नियतात्मक परिमित द्वारा स्वीकार किया जाता है।
वैश्विक बाधाओं का उपयोग [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.