प्रतिबंधित अनुकूलन: Difference between revisions

Latest revision as of 16:01, 22 August 2023

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

बाधा-संतुष्टि का समस्याओं से संबंध

विवश-अनुकूलन समस्या (सीओपी) मौलिक रूप से बाधा-संतुष्टि समस्या (सीएसपी) के प्रारूप के लिए महत्वपूर्ण सामान्यीकरण है।^[1] सीओपी सीएसपी है, जिसमें अनुकूलित किया जाने वाला आब्जेक्टिव फंक्शन सम्मिलित होते है। इस प्रकार अनुकूलन भाग को संभालने के लिए कई एल्गोरिदम का उपयोग किया जाता है।

सामान्य प्रपत्र

एक सामान्य विवश न्यूनतमकरण समस्या इस प्रकार लिखी जा सकती है:^[2]

{\begin{array}{rcll}\min &~&f(\mathbf {x} )&\\\mathrm {subject~to} &~&g_{i}(\mathbf {x} )=c_{i}&{\text{for }}i=1,\ldots ,n\quad {\text{Equality constraints}}\\&~&h_{j}(\mathbf {x} )\geq d_{j}&{\text{for }}j=1,\ldots ,m\quad {\text{Inequality constraints}}\end{array}}

जहाँ $g_{i}(\mathbf {x} )=c_{i}~\mathrm {for~} i=1,\ldots ,n$ और $h_{j}(\mathbf {x} )\geq d_{j}~\mathrm {for~} j=1,\ldots ,m$ ऐसी बाधाएं हैं, जिन्हें संतुष्ट करना आवश्यक होता है, इन्हें बाधा (गणित) के लिए कठोर और सरल बाधाएं कहा जाता है, और $f(\mathbf {x} )$ वस्तुनिष्ठ फंक्शन है, जिससे बाधाओं के अधीन अनुकूलित करने की आवश्यकता होती है।

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

हल करने की विधि

कई प्रतिबंधित अनुकूलन एल्गोरिदम को अधिकांशतः पेनैल्टी पद्धति के उपयोग के माध्यम से, अप्रतिबंधित स्थिति में अनुकूलित किया जा सकता है। चूंकि, अप्रतिबंधित विधि द्वारा उठाए गए खोज के लिए बढ़ाये गए इस चरण के लिए बाधित समस्या के लिए अस्वीकार्य हो सकते हैं, जिससे अभिसरण की कमी हो सकती है। इसे मराटोस प्रभाव कहा जाता है।^[3]

समानता की बाधाएं

प्रतिस्थापन विधि

बहुत ही सरल समस्याओं के लिए, मान लें कि एकल समानता बाधा के अधीन दो वैरियेबल के बीच के इस फंक्शन को प्रतिस्थापन विधि के द्वारा लागू करने पर सबसे व्यावहारिक माना जाता है।^[4] इस प्रकार को किसी विचार फंक्शन संरचना बनाने के लिए आब्जेक्टिव फंक्शन में बाधा को प्रतिस्थापित करने का है, जो इस बाधा के प्रभाव को सम्मिलित करता है। उदाहरण के लिए यदि मान लें कि उद्देश्य अधिकतम करना है, जिसके लिए $f(x,y)=x\cdot y$ मुख्य रूप से $x+y=10$ का विषय है, यहाँ पर बाधा का तात्पर्य $y=10-x$ से है, जिसे बनाने के आब्जेक्टिव फंक्शन $p(x)=x(10-x)=10x-x^{2}$ में प्रतिस्थापित किया जा सकता है, इसका प्रथम-क्रम ${\frac {\partial p}{\partial x}}=10-2x=0$ के लिए आवश्यक शर्त देता है, जिसका हल $x=5$ और इसके परिणामस्वरूप, $y=10-5=5$ द्वारा किया जा सकता है।

लैग्रेंज गुणक

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

असमानता बाधाएं

असमान बाधाओं के साथ, समस्या को ज्यामितीय इष्टतमता स्थितियों, फ्रिट्ज़ जॉन स्थितियों और करुश-कुह्न-टकर स्थितियों के संदर्भ में वर्णित किया जा सकता है, जिसके अनुसार सरल समस्याएं हल हो सकती हैं।

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

यदि आब्जेक्टिव फंक्शन और सभी कठिन बाधाएं लीनियर हैं और कुछ कठिन बाधाएं असमानताएं हैं, तो समस्या लीनियर प्रोग्रामिंग समस्या है। इस प्रकार इसे सिंप्लेक्स विधि द्वारा हल किया जा सकता है, जो सामान्यतः इसकी समस्या के आकार में बहुपद समय में कार्य करता है, अपितु इसकी गारंटी नहीं है, या आंतरिक बिंदु विधियों द्वारा जो बहुपद समय में कार्य करने की गारंटी देता है।

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

यदि आब्जेक्टिव फंक्शन या कुछ बाधाएँ नाॅन लीनियर हैं, और कुछ बाधाएँ असमानताएँ हैं, तो समस्या नाॅन लीनियर प्रोग्रामिंग समस्या है।

क्वाडरैटिक प्रोग्रामिंग

यदि सभी कठिन बाधाएं लीनियर हैं और कुछ असमानताएं हैं, अपितु यह आब्जेक्टिव फंक्शन क्वाडरैटिक है, जो समस्या क्वाडरैटिक प्रोग्रामिंग समस्या के रूप से जाना जाता है। यह इस प्रकार की नॉनलाइनियर प्रोग्रामिंग है। यदि आब्जेक्टिव फंक्शन उत्तल फंक्शन है तो इसे अभी भी दीर्घवृत्त विधि द्वारा बहुपद समय में हल किया जा सकता है, अन्यथा इस समस्या एनपी कठिन हो सकती है।

केकेटी की शर्तें

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

शाखा और सीमा

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

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

दूसरी ओर, यह अनुमानित लागत उस प्रभावी लागत से कम नहीं हो सकती है जो हल का विस्तार करके प्राप्त की जा सकती है, अन्यथा एल्गोरिदम पीछे हट सकता है जबकि अब तक पाए गए सर्वोत्तम हल से उत्तम हल उपस्थित है। इसके परिणामस्वरूप एल्गोरिदम की लागत पर ऊपरी सीमा की आवश्यकता होती है, जो इस प्रकार आंशिक हल का विस्तार करके प्राप्त की जा सकती है, और यह ऊपरी सीमा यथासंभव छोटी होनी चाहिए।

इस दृष्टिकोण का रूपांतर जिसे हेन्सन विधि कहा जाता है, इसके अतिरिक्त यहाँ पर अंतराल अंकगणित इतिहास का उपयोग करता है।^[5] यह स्वाभाविक रूप से आयताकार बाधाओं को लागू करता है।

बाउंडिंग फंक्शन

आंशिक हल के लिए इस ऊपरी सीमा का मूल्यांकन करने का तरीका प्रत्येक सरल बाधा पर अलग से विचार करना है। प्रत्येक सरल बाधा के लिए, अनअसाइन्ड वेरिएबल्स के किसी भी असाइनमेंट के लिए अधिकतम संभव मान माना जाता है। इन मूल्यों का योग ऊपरी सीमा है क्योंकि सरल बाधाएं उच्च मूल्य नहीं मान सकती हैं। यह सटीक है क्योंकि सरल बाधाओं के अधिकतम मूल्य विभिन्न मूल्यांकनों से प्राप्त हो सकते हैं: सरल बाधा अधिकतम $x=a$ तक हो सकती है, जबकि अन्य बाधा अधिकतम $x=b$ तक हो सकती है।

रूसी डाॅल की खोज

यह विधि^[6] ब्रांच-एंड-बाउंड एल्गोरिदम $n$ समस्याएं चलाता है, जहाँ $n$ वैरियेबल्स की संख्या है, ऐसी प्रत्येक समस्या वैरियेबल्स के अनुक्रम को छोड़ने से प्राप्त उपसमस्या $x_{1},\ldots ,x_{i}$ है, यहाँ पर इस प्रकार की मूल समस्या से, साथ ही उनमें उपस्थित बाधाओं से किया जाता हैं। इस प्रकार वैरियेबल पर समस्या के पश्चात $x_{i+1},\ldots ,x_{n}$ के हल हो जाने पर, इसकी इष्टतम लागत को अन्य समस्याओं को हल करते समय ऊपरी सीमा के रूप में उपयोग किया जा सकता है,

विशेष रूप से, किसी हल की लागत का अनुमान $x_{i+1},\ldots ,x_{n}$ हैं, चूंकि असाइन किए गए वैरियेबल को उस लागत में जोड़ा जाता है जो मूल्यांकन किए गए वैरियेबल से प्राप्त होती है। वस्तुतः यह मूल्यांकन किए गए वैरियेबल्स को अनदेखा करने और असाइन न किए गए वैरियेबल्स पर समस्या को हल करने के अनुरूप है, इसके अतिरिक्त बाद वाली समस्याएं पहले ही हल हो चुकी है। इसका अधिक सटीक रूप से, असाइन किए गए और अनअसाइन किए गए दोनों वैरियेबल वाले सरल बाधाओं की लागत का अनुमान या मनमाने ढंग से अन्य विधि का उपयोग करके ऊपर दिया गया है, इसके अतिरिक्त केवल अनिर्धारित वैरियेबल वाले सरल बाधाओं की लागत का अनुमान संबंधित समस्या के इष्टतम हल का उपयोग करके लगाया जाता है, जो इस बिंदु पर पहले से ही ज्ञात है।

रूसी डाॅल की खोज पद्धति और डायनेमिक प्रोग्रामिंग के बीच समानता है। डायनेमिक प्रोग्रामिंग के समान रूसी डाॅल की खोज पूरी समस्या को हल करने के लिए उप-समस्याओं को हल करती है। अपितु, जबकि डायनामिक प्रोग्रामिंग मुख्यतः इस प्रकार की संपूर्ण समस्याओं का परिणाम प्राप्त करने के लिए उप-समस्याओं पर प्राप्त परिणामों को सीधे संयोजित करता है, इस प्रकार रूसी डाॅल की खोज केवल अपनी खोज के समय उन्हें सीमा के रूप में उपयोग करती है।

बकेट उन्मूलन

बकेट एलिमिनेशन एल्गोरिदम को बाधा अनुकूलन के लिए अनुकूलित किया जा सकता है। किसी दिए गए वेरिएबल को वास्तव में सभी सरल बाधाओं को नए सरल बाधा के साथ प्रतिस्थापित करके समस्या से हटाया जा सकता है। इस नई बाधा की लागत की गणना हटाए गए वैरियेबल के प्रत्येक मान के लिए अधिकतम मान मानकर की जाती है। इस प्रकार औपचारिक रूप से, यदि $x$ क्या वेरिएबल को हटाया जाना है, यहाँ पर $C_{1},\ldots ,C_{n}$ में सम्मिलित सरल बाधाएं हैं, और $y_{1},\ldots ,y_{m}$ के अतिरिक्त उनके वैरियेबल $x$ हैं, इस प्रकार की नई सरल बाधाओं द्वारा इन्हें परिभाषित किया गया है:

C(y_{1}=a_{1},\ldots ,y_{n}=a_{n})=\max _{a}\sum _{i}C_{i}(x=a,y_{1}=a_{1},\ldots ,y_{n}=a_{n}).

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

यह भी देखें

संदर्भ

↑ Rossi, Francesca; van Beek, Peter; Walsh, Toby (2006-01-01), Rossi, Francesca; van Beek, Peter; Walsh, Toby (eds.), "Chapter 1 – Introduction", Foundations of Artificial Intelligence, Handbook of Constraint Programming, Elsevier, vol. 2, pp. 3–12, doi:10.1016/s1574-6526(06)80005-2, retrieved 2019-10-04
↑ Martins, J. R. R. A.; Ning, A. (2021). इंजीनियरिंग डिज़ाइन अनुकूलन (in English). Cambridge University Press. ISBN 978-1108833417.
↑ Wenyu Sun; Ya-Xiang Yuan (2010). Optimization Theory and Methods: Nonlinear Programming, Springer, ISBN 978-1441937650. p. 541
↑ Prosser, Mike (1993). "Constrained Optimization by Substitution". अर्थशास्त्रियों के लिए बुनियादी गणित. New York: Routledge. pp. 338–346. ISBN 0-415-08424-5.
↑ Leader, Jeffery J. (2004). संख्यात्मक विश्लेषण और वैज्ञानिक संगणना. Addison Wesley. ISBN 0-201-73499-0.
↑ Verfaillie, Gérard, Michel Lemaître, and Thomas Schiex. "Russian doll search for solving constraint optimization problems." AAAI/IAAI, Vol. 1. 1996.

अग्रिम पठन

Bertsekas, Dimitri P. (1982). Constrained Optimization and Lagrange Multiplier Methods. New York: Academic Press. ISBN 0-12-093480-9.
Dechter, Rina (2003). Constraint Processing. Morgan Kaufmann. ISBN 1-55860-890-7.

| group5 = Metaheuristics | abbr5 = heuristic | list5 =

| below =

Software

}} | group5 =Metaheuuristic |abbr5 = heuristic | list5 =*विकासवादी एल्गोरिथ्म

| below =* सॉफ्टवेयर

}}

[1] Rossi, Francesca; van Beek, Peter; Walsh, Toby (2006-01-01), Rossi, Francesca; van Beek, Peter; Walsh, Toby (eds.), "Chapter 1 – Introduction", Foundations of Artificial Intelligence, Handbook of Constraint Programming, Elsevier, vol. 2, pp. 3–12, doi:10.1016/s1574-6526(06)80005-2, retrieved 2019-10-04

[edo2021-2] Martins, J. R. R. A.; Ning, A. (2021). इंजीनियरिंग डिज़ाइन अनुकूलन (in English). Cambridge University Press. ISBN 978-1108833417.

[3] Wenyu Sun; Ya-Xiang Yuan (2010). Optimization Theory and Methods: Nonlinear Programming, Springer, ISBN 978-1441937650. p. 541

[4] Prosser, Mike (1993). "Constrained Optimization by Substitution". अर्थशास्त्रियों के लिए बुनियादी गणित. New York: Routledge. pp. 338–346. ISBN 0-415-08424-5.

[5] Leader, Jeffery J. (2004). संख्यात्मक विश्लेषण और वैज्ञानिक संगणना. Addison Wesley. ISBN 0-201-73499-0.

[6] Verfaillie, Gérard, Michel Lemaître, and Thomas Schiex. "Russian doll search for solving constraint optimization problems." AAAI/IAAI, Vol. 1. 1996.

[1]

[2]

[3]

[4]

[5]

[6]

@@ Line 1: / Line 1: @@
 {{Short description|Optimizing objective functions that have constrained variables}}
-[[गणितीय अनुकूलन]] में, प्रतिबंधित अनुकूलन (कुछ संदर्भों में बाधा अनुकूलन कहा जाता है) उन चर पर [[बाधा (गणित)]] की उपस्थिति में कुछ [[चर (गणित)]] के संबंध में एक उद्देश्य फ़ंक्शन को अनुकूलित करने की प्रक्रिया है। उद्देश्य फ़ंक्शन या तो एक हानि फ़ंक्शन या [[ऊर्जा समारोह]] है, जिसे [[मैक्सिमा और मिनिमा]] होना है, या एक इनाम फ़ंक्शन या उपयोगिता फ़ंक्शन है, जिसे [[अधिकतम]] किया जाना है। बाधाएं या तो कठोर बाधाएं हो सकती हैं, जो संतुष्ट होने के लिए आवश्यक चर के लिए शर्तें निर्धारित करती हैं, या नरम बाधाएं, जिनमें कुछ परिवर्तनीय मान होते हैं जिन्हें उद्देश्य फ़ंक्शन में दंडित किया जाता है, और उस सीमा के आधार पर, चर पर स्थितियां संतुष्ट नहीं होती हैं।
+[[गणितीय अनुकूलन]] में, प्रतिबंधित अनुकूलन को कुछ संदर्भों में बाधा अनुकूलन कहा जाता है, इस प्रकार किसी वैरियेबल पर [[बाधा (गणित)]] की उपस्थिति में कुछ [[चर (गणित)|वैरियेबल (गणित)]] के संबंध में इस प्रकार के उद्देश्यों के लिए उपयोग किये जाने वाले फंक्शन को अनुकूलित करने की प्रक्रिया है। इस उद्देश्य के लिए उपयुक्त फंक्शन या तो हानि फंक्शन या [[ऊर्जा समारोह|ऊर्जा फंक्शन]] है, जिसे [[मैक्सिमा और मिनिमा]] कहा जाता है या फंक्शन या उपयोगिता फंक्शन भी कहा जाता है, जिसके मान को [[अधिकतम]] किया जाना आवश्यक होता है। इस प्रकार की बाधाएं या तो कठोर बाधाएं हो सकती हैं, जो संतुष्ट होने के लिए आवश्यक वैरियेबल के लिए शर्तें निर्धारित करती हैं, या सरल बाधाएं, जिनमें कुछ परिवर्तनीय मान होते हैं, जिन्हें इन उद्देश्यों के आधार पर फंक्शन में पेनैल्टी दी जाती है, और उस सीमा के आधार पर वैरियेबल पर इन स्थितियों के लिए संतुष्ट नहीं होते हैं।
-== [[बाधा-संतुष्टि समस्या]]ओं से संबंध ==
+== [[बाधा-संतुष्टि समस्या|बाधा-संतुष्टि का समस्याओं]] से संबंध ==
-विवश-अनुकूलन समस्या (सीओपी) क्लासिक बाधा-संतुष्टि समस्या (सीएसपी) मॉडल का एक महत्वपूर्ण सामान्यीकरण है।<ref>{{Citation|last1=Rossi|first1=Francesca|title=Chapter 1 – Introduction|date=2006-01-01|url=http://www.sciencedirect.com/science/article/pii/S1574652606800052|work=Foundations of Artificial Intelligence|volume=2|pages=3–12|editor-last=Rossi|editor-first=Francesca|series=Handbook of Constraint Programming|publisher=Elsevier|doi=10.1016/s1574-6526(06)80005-2|access-date=2019-10-04|last2=van Beek|first2=Peter|last3=Walsh|first3=Toby|editor2-last=van Beek|editor2-first=Peter|editor3-last=Walsh|editor3-first=Toby}}</ref> सीओपी एक सीएसपी है जिसमें अनुकूलित किया जाने वाला एक उद्देश्य फ़ंक्शन शामिल है। अनुकूलन भाग को संभालने के लिए कई एल्गोरिदम का उपयोग किया जाता है।
+विवश-अनुकूलन समस्या (सीओपी) मौलिक रूप से बाधा-संतुष्टि समस्या (सीएसपी) के प्रारूप के लिए महत्वपूर्ण सामान्यीकरण है।<ref>{{Citation|last1=Rossi|first1=Francesca|title=Chapter 1 – Introduction|date=2006-01-01|url=http://www.sciencedirect.com/science/article/pii/S1574652606800052|work=Foundations of Artificial Intelligence|volume=2|pages=3–12|editor-last=Rossi|editor-first=Francesca|series=Handbook of Constraint Programming|publisher=Elsevier|doi=10.1016/s1574-6526(06)80005-2|access-date=2019-10-04|last2=van Beek|first2=Peter|last3=Walsh|first3=Toby|editor2-last=van Beek|editor2-first=Peter|editor3-last=Walsh|editor3-first=Toby}}</ref> सीओपी सीएसपी है, जिसमें अनुकूलित किया जाने वाला आब्जेक्टिव फंक्शन सम्मिलित होते है। इस प्रकार अनुकूलन भाग को संभालने के लिए कई एल्गोरिदम का उपयोग किया जाता है।
 ==सामान्य प्रपत्र==
@@ Line 16: / Line 16: @@
 \end{array}
 </math>
-कहाँ <math> g_i(\mathbf{x}) = c_i ~\mathrm{for~} i=1,\ldots,n </math> और <math> h_j(\mathbf{x}) \ge d_j ~\mathrm{for~} j=1,\ldots,m  </math> वे बाधाएं हैं जिन्हें संतुष्ट करना आवश्यक है (इन्हें बाधा (गणित)#कठोर और नरम बाधाएं कहा जाता है), और <math>f(\mathbf{x})</math> वस्तुनिष्ठ कार्य है जिसे बाधाओं के अधीन अनुकूलित करने की आवश्यकता है।
+जहाँ <math> g_i(\mathbf{x}) = c_i ~\mathrm{for~} i=1,\ldots,n </math> और <math> h_j(\mathbf{x}) \ge d_j ~\mathrm{for~} j=1,\ldots,m  </math> ऐसी बाधाएं हैं, जिन्हें संतुष्ट करना आवश्यक होता है, इन्हें बाधा (गणित) के लिए कठोर और सरल बाधाएं कहा जाता है, और <math>f(\mathbf{x})</math> वस्तुनिष्ठ फंक्शन है, जिससे बाधाओं के अधीन अनुकूलित करने की आवश्यकता होती है।
-कुछ समस्याओं में, जिन्हें अक्सर बाधा अनुकूलन समस्याएं कहा जाता है, उद्देश्य फ़ंक्शन वास्तव में लागत कार्यों का योग होता है, जिनमें से प्रत्येक उस सीमा (यदि कोई हो) को दंडित करता है, जिसके लिए एक बाधा (गणित) # हार्ड और सॉफ्ट बाधाएं (एक बाधा जिसे प्राथमिकता दी जाती है लेकिन संतुष्ट होने की आवश्यकता नहीं होती है) का उल्लंघन किया जाता है।
+कुछ समस्याओं में, जिन्हें अधिकांशतः बाधा अनुकूलन समस्याएं कहा जाता है, इस प्रकार उद्देश्यों के आधार पर फंक्शन वास्तव में लागत कार्यों का योग होता है, जिनमें से प्रत्येक उस सीमा यदि कोई हो जिसको पेनैल्टी करता है, जिसके लिए बाधा (गणित) हार्ड और सॉफ्ट बाधाएं मुख्य रूप से ऐसी बाधाएँ हैं, जिसे प्राथमिकता दी जाती है, अपितु संतुष्ट होने की आवश्यकता नहीं होती है, जिसका उल्लंघन किया जाता है।
-==समाधान के तरीके==
-कई प्रतिबंधित अनुकूलन एल्गोरिदम को अक्सर दंड पद्धति के उपयोग के माध्यम से, अप्रतिबंधित मामले में अनुकूलित किया जा सकता है। हालाँकि, अप्रतिबंधित विधि द्वारा उठाए गए खोज कदम बाधित समस्या के लिए अस्वीकार्य हो सकते हैं, जिससे अभिसरण की कमी हो सकती है। इसे मराटोस प्रभाव कहा जाता है।<ref>Wenyu Sun; Ya-Xiang Yuan (2010). ''Optimization Theory and Methods: Nonlinear Programming'', Springer, {{ISBN|978-1441937650}}. p. 541</ref>
+==हल करने की विधि==
+कई प्रतिबंधित अनुकूलन एल्गोरिदम को अधिकांशतः पेनैल्टी पद्धति के उपयोग के माध्यम से, अप्रतिबंधित स्थिति में अनुकूलित किया जा सकता है। चूंकि, अप्रतिबंधित विधि द्वारा उठाए गए खोज के लिए बढ़ाये गए इस चरण के लिए बाधित समस्या के लिए अस्वीकार्य हो सकते हैं, जिससे अभिसरण की कमी हो सकती है। इसे '''मराटोस प्रभाव''' कहा जाता है।<ref>Wenyu Sun; Ya-Xiang Yuan (2010). ''Optimization Theory and Methods: Nonlinear Programming'', Springer, {{ISBN|978-1441937650}}. p. 541</ref>
 ===समानता की बाधाएं===
 ====प्रतिस्थापन विधि====
-बहुत ही सरल समस्याओं के लिए, मान लें कि एकल समानता बाधा के अधीन दो चर का एक फ़ंक्शन, प्रतिस्थापन की विधि को लागू करना सबसे व्यावहारिक है।<ref>{{cite book |first=Mike |last=Prosser |title=अर्थशास्त्रियों के लिए बुनियादी गणित|location=New York |publisher=Routledge |year=1993 |isbn=0-415-08424-5 |chapter=Constrained Optimization by Substitution |pages=338–346 }}</ref> विचार एक फ़ंक्शन संरचना बनाने के लिए उद्देश्य फ़ंक्शन में बाधा को प्रतिस्थापित करने का है जो बाधा के प्रभाव को शामिल करता है। उदाहरण के लिए, मान लें कि उद्देश्य अधिकतम करना है <math>f(x,y) = x \cdot y</math> का विषय है <math>x + y = 10</math>. बाधा का तात्पर्य है <math>y = 10 - x</math>, जिसे बनाने के उद्देश्य फ़ंक्शन में प्रतिस्थापित किया जा सकता है <math>p(x) = x (10 - x) = 10x - x^{2}</math>. प्रथम-क्रम आवश्यक शर्त देता है <math>\frac{\partial p}{\partial x} = 10 - 2x = 0</math>, जिसका समाधान किया जा सकता है <math>x=5</math> और इसके परिणामस्वरूप, <math>y = 10 - 5 = 5</math>.
+बहुत ही सरल समस्याओं के लिए, मान लें कि एकल समानता बाधा के अधीन दो वैरियेबल के बीच के इस फंक्शन को '''प्रतिस्थापन विधि''' के द्वारा लागू करने पर सबसे व्यावहारिक माना जाता है।<ref>{{cite book |first=Mike |last=Prosser |title=अर्थशास्त्रियों के लिए बुनियादी गणित|location=New York |publisher=Routledge |year=1993 |isbn=0-415-08424-5 |chapter=Constrained Optimization by Substitution |pages=338–346 }}</ref> इस प्रकार को किसी विचार फंक्शन संरचना बनाने के लिए आब्जेक्टिव फंक्शन में बाधा को प्रतिस्थापित करने का है, जो इस बाधा के प्रभाव को सम्मिलित करता है। उदाहरण के लिए यदि मान लें कि उद्देश्य अधिकतम करना है, जिसके लिए <math>f(x,y) = x \cdot y</math> मुख्य रूप से <math>x + y = 10</math> का विषय है, यहाँ पर बाधा का तात्पर्य <math>y = 10 - x</math> से है, जिसे बनाने के आब्जेक्टिव फंक्शन <math>p(x) = x (10 - x) = 10x - x^{2}</math>में प्रतिस्थापित किया जा सकता है, इसका प्रथम-क्रम <math>\frac{\partial p}{\partial x} = 10 - 2x = 0</math> के लिए आवश्यक शर्त देता है, जिसका हल <math>x=5</math> और इसके परिणामस्वरूप, <math>y = 10 - 5 = 5</math> द्वारा किया जा सकता है।
 ====लैग्रेंज गुणक====
-{{main|Lagrange multipliers}}
+{{main|लैग्रेंज गुणक}}
-यदि बाधित समस्या में केवल समानता की बाधाएं हैं, तो [[लैग्रेंज गुणक]] की विधि का उपयोग इसे एक अप्रतिबंधित समस्या में बदलने के लिए किया जा सकता है, जिसके चर की संख्या चर की मूल संख्या और समानता बाधाओं की मूल संख्या है। वैकल्पिक रूप से, यदि बाधाएं सभी समानता बाधाएं हैं और सभी रैखिक हैं, तो उन्हें कुछ चर के लिए दूसरों के संदर्भ में हल किया जा सकता है, और पूर्व को उद्देश्य फ़ंक्शन से प्रतिस्थापित किया जा सकता है, जिससे कम संख्या में चर में एक अप्रतिबंधित समस्या रह जाती है।
+यदि बाधित समस्या में केवल समानता की बाधाएं हैं, तो [[लैग्रेंज गुणक]] की विधि का उपयोग इसे अप्रतिबंधित समस्या में परिवर्तित करने के लिए किया जा सकता है, जिसके वैरियेबल की संख्या वैरियेबल की मूल संख्या और समानता बाधाओं की मूल संख्या है। वैकल्पिक रूप से, यदि बाधाएं सभी समानता बाधाएं हैं और सभी लीनियर हैं, तो इस प्रकार उन्हें कुछ वैरियेबल के लिए दूसरों के संदर्भ में हल किया जा सकता है, और पूर्व को आब्जेक्टिव फंक्शन से प्रतिस्थापित किया जा सकता है, जिससे कम संख्या में वैरियेबल में अप्रतिबंधित समस्या रह जाती है।
 ===असमानता बाधाएं===
-असमानता की बाधाओं के साथ, समस्या को ज्यामितीय इष्टतमता स्थितियों, फ्रिट्ज़ जॉन स्थितियों और करुश-कुह्न-टकर स्थितियों के संदर्भ में वर्णित किया जा सकता है, जिसके तहत सरल समस्याएं हल हो सकती हैं।
+'''असमान बाधाओं''' के साथ, समस्या को ज्यामितीय इष्टतमता स्थितियों, फ्रिट्ज़ जॉन स्थितियों और करुश-कुह्न-टकर स्थितियों के संदर्भ में वर्णित किया जा सकता है, जिसके अनुसार सरल समस्याएं हल हो सकती हैं।
-====[[रैखिक प्रोग्रामिंग]]====
+====[[रैखिक प्रोग्रामिंग|लीनियर प्रोग्रामिंग]]====
-यदि उद्देश्य फ़ंक्शन और सभी कठिन बाधाएं रैखिक हैं और कुछ कठिन बाधाएं असमानताएं हैं, तो समस्या एक रैखिक प्रोग्रामिंग समस्या है। इसे सिंप्लेक्स विधि द्वारा हल किया जा सकता है, जो आमतौर पर समस्या के आकार में बहुपद समय में काम करता है लेकिन इसकी गारंटी नहीं है, या [[आंतरिक बिंदु विधि]]यों द्वारा जो बहुपद समय में काम करने की गारंटी देता है।
+यदि आब्जेक्टिव फंक्शन और सभी कठिन बाधाएं लीनियर हैं और कुछ कठिन बाधाएं असमानताएं हैं, तो समस्या लीनियर प्रोग्रामिंग समस्या है। इस प्रकार इसे सिंप्लेक्स विधि द्वारा हल किया जा सकता है, जो सामान्यतः इसकी समस्या के आकार में बहुपद समय में कार्य करता है, अपितु इसकी गारंटी नहीं है, या [[आंतरिक बिंदु विधि]]यों द्वारा जो बहुपद समय में कार्य करने की गारंटी देता है।
-====[[अरेखीय प्रोग्रामिंग]]====
+====[[अरेखीय प्रोग्रामिंग|नाॅन लीनियर प्रोग्रामिंग]]====
-यदि उद्देश्य फ़ंक्शन या कुछ बाधाएँ अरेखीय हैं, और कुछ बाधाएँ असमानताएँ हैं, तो समस्या एक अरेखीय प्रोग्रामिंग समस्या है।
+यदि आब्जेक्टिव फंक्शन या कुछ बाधाएँ नाॅन लीनियर हैं, और कुछ बाधाएँ असमानताएँ हैं, तो समस्या नाॅन लीनियर प्रोग्रामिंग समस्या है।
-====[[द्विघात प्रोग्रामिंग]]====
+====[[द्विघात प्रोग्रामिंग|क्वाडरैटिक प्रोग्रामिंग]]====
-यदि सभी कठिन बाधाएं रैखिक हैं और कुछ असमानताएं हैं, लेकिन उद्देश्य फ़ंक्शन द्विघात है, तो समस्या एक द्विघात प्रोग्रामिंग समस्या है। यह एक प्रकार की नॉनलाइनियर प्रोग्रामिंग है। यदि उद्देश्य फलन उत्तल फलन है तो इसे अभी भी दीर्घवृत्त विधि द्वारा बहुपद समय में हल किया जा सकता है; अन्यथा समस्या [[एनपी कठिन]] हो सकती है।
+यदि सभी कठिन बाधाएं लीनियर हैं और कुछ असमानताएं हैं, अपितु यह आब्जेक्टिव फंक्शन क्वाडरैटिक है, जो समस्या क्वाडरैटिक प्रोग्रामिंग समस्या के रूप से जाना जाता है। यह इस प्रकार की नॉनलाइनियर प्रोग्रामिंग है। यदि आब्जेक्टिव फंक्शन उत्तल फंक्शन है तो इसे अभी भी दीर्घवृत्त विधि द्वारा बहुपद समय में हल किया जा सकता है, अन्यथा इस समस्या [[एनपी कठिन]] हो सकती है।
-====केकेटी शर्तें====
+====केकेटी की शर्तें====
-असमानता की बाधाओं को दूर करते हुए, गैर-रेखीय प्रोग्रामिंग के लिए [[करुश-कुह्न-टकर स्थितियाँ]] स्थिति लैग्रेंज मल्टीप्लायरों की विधि को सामान्य बनाती है। इसे भिन्नता और उत्तलता के तहत लागू किया जा सकता है।
+असमानता की बाधाओं को दूर करते हुए, गैर-रेखीय प्रोग्रामिंग के लिए [[करुश-कुह्न-टकर स्थितियाँ|केकेटी]] स्थिति लैग्रेंज मल्टीप्लायरों की विधि को सामान्य बनाती है। इसे भिन्नता और उत्तलता के अनुसार लागू किया जा सकता है।
 ====शाखा और सीमा====
-बाधा अनुकूलन को शाखा-और-बाउंड एल्गोरिदम द्वारा हल किया जा सकता है। ये बैकट्रैकिंग एल्गोरिदम हैं जो निष्पादन के दौरान पाए गए सर्वोत्तम समाधान की लागत को संग्रहीत करते हैं और खोज के हिस्से से बचने के लिए इसका उपयोग करते हैं। अधिक सटीक रूप से, जब भी एल्गोरिदम को आंशिक समाधान का सामना करना पड़ता है जिसे संग्रहीत सर्वोत्तम लागत से बेहतर लागत का समाधान बनाने के लिए बढ़ाया नहीं जा सकता है, तो एल्गोरिदम इस समाधान को विस्तारित करने की कोशिश करने के बजाय पीछे हट जाता है।
+बाधा अनुकूलन को शाखा-और-बाउंड एल्गोरिदम द्वारा हल किया जा सकता है। ये बैकट्रैकिंग एल्गोरिदम हैं जो निष्पादन के समय पाए गए सर्वोत्तम हल की लागत को संग्रहीत करते हैं, और इस प्रकार खोज के भाग से बचने के लिए इसका उपयोग करते हैं। अधिक सटीक रूप से, जब भी एल्गोरिदम को आंशिक हल का सामना करना पड़ता है, जिसे संग्रहीत सर्वोत्तम लागत से उत्तम लागत का हल बनाने के लिए बढ़ाया नहीं जा सकता है, तो एल्गोरिदम इस हल को विस्तारित करने की प्रयास करने के अतिरिक्त पीछे हट जाता है।
-यह मानते हुए कि लागत को कम किया जाना है, इन एल्गोरिदम की दक्षता इस बात पर निर्भर करती है कि आंशिक समाधान के विस्तार से प्राप्त होने वाली लागत का मूल्यांकन कैसे किया जाता है। दरअसल, यदि एल्गोरिदम आंशिक समाधान से पीछे हट सकता है, तो खोज का हिस्सा छोड़ दिया जाता है। अनुमानित लागत जितनी कम होगी, एल्गोरिदम उतना ही बेहतर होगा, क्योंकि कम अनुमानित लागत अब तक पाए गए समाधान की सर्वोत्तम लागत से कम होने की अधिक संभावना है।
+यह मानते हुए कि लागत को कम किया जाना है, इन एल्गोरिदम की दक्षता इस बात पर निर्भर करती है कि आंशिक हल के विस्तार से प्राप्त होने वाली लागत का मूल्यांकन कैसे किया जाता है। इसके अतिरिक्त यदि एल्गोरिदम आंशिक हल से पीछे हट सकता है, तो खोज का हिस्सा छोड़ दिया जाता है। अनुमानित लागत जितनी कम होगी, इस प्रकार एल्गोरिदम उतना ही उत्तम होगा, क्योंकि कम अनुमानित लागत अब तक पाए गए हल की सर्वोत्तम लागत से कम होने की अधिक संभावना है।
-दूसरी ओर, यह अनुमानित लागत उस प्रभावी लागत से कम नहीं हो सकती है जो समाधान का विस्तार करके प्राप्त की जा सकती है, अन्यथा एल्गोरिदम पीछे हट सकता है जबकि अब तक पाए गए सर्वोत्तम समाधान से बेहतर समाधान मौजूद है। परिणामस्वरूप, एल्गोरिदम को लागत पर ऊपरी सीमा की आवश्यकता होती है जो आंशिक समाधान का विस्तार करके प्राप्त की जा सकती है, और यह ऊपरी सीमा यथासंभव छोटी होनी चाहिए।
+दूसरी ओर, यह अनुमानित लागत उस प्रभावी लागत से कम नहीं हो सकती है जो हल का विस्तार करके प्राप्त की जा सकती है, अन्यथा एल्गोरिदम पीछे हट सकता है जबकि अब तक पाए गए सर्वोत्तम हल से उत्तम हल उपस्थित है। इसके परिणामस्वरूप एल्गोरिदम की लागत पर ऊपरी सीमा की आवश्यकता होती है, जो इस प्रकार आंशिक हल का विस्तार करके प्राप्त की जा सकती है, और यह ऊपरी सीमा यथासंभव छोटी होनी चाहिए।
-इस दृष्टिकोण का एक रूपांतर जिसे हेन्सन विधि कहा जाता है, अंतराल अंकगणित#इतिहास का उपयोग करता है।<ref>{{cite book |last=Leader|first=Jeffery J. | title=संख्यात्मक विश्लेषण और वैज्ञानिक संगणना|year=2004|publisher=Addison Wesley |isbn= 0-201-73499-0 }}</ref> यह स्वाभाविक रूप से आयताकार बाधाओं को लागू करता है।
+इस दृष्टिकोण का रूपांतर जिसे '''हेन्सन विधि''' कहा जाता है, इसके अतिरिक्त यहाँ पर अंतराल अंकगणित इतिहास का उपयोग करता है।<ref>{{cite book |last=Leader|first=Jeffery J. | title=संख्यात्मक विश्लेषण और वैज्ञानिक संगणना|year=2004|publisher=Addison Wesley |isbn= 0-201-73499-0 }}</ref> यह स्वाभाविक रूप से आयताकार बाधाओं को लागू करता है।
-====पहली पसंद बाउंडिंग फ़ंक्शन====
+====बाउंडिंग फंक्शन====
-आंशिक समाधान के लिए इस ऊपरी सीमा का मूल्यांकन करने का एक तरीका प्रत्येक नरम बाधा पर अलग से विचार करना है। प्रत्येक सॉफ्ट बाधा के लिए, अनअसाइन्ड वेरिएबल्स के किसी भी असाइनमेंट के लिए अधिकतम संभव मान माना जाता है। इन मूल्यों का योग एक ऊपरी सीमा है क्योंकि नरम बाधाएं उच्च मूल्य नहीं मान सकती हैं। यह सटीक है क्योंकि नरम बाधाओं के अधिकतम मूल्य विभिन्न मूल्यांकनों से प्राप्त हो सकते हैं: एक नरम बाधा अधिकतम हो सकती है <math>x=a</math> जबकि एक अन्य बाधा अधिकतम है <math>x=b</math>.
+आंशिक हल के लिए इस ऊपरी सीमा का मूल्यांकन करने का तरीका प्रत्येक सरल बाधा पर अलग से विचार करना है। प्रत्येक सरल बाधा के लिए, अनअसाइन्ड वेरिएबल्स के किसी भी असाइनमेंट के लिए अधिकतम संभव मान माना जाता है। इन मूल्यों का योग ऊपरी सीमा है क्योंकि सरल बाधाएं उच्च मूल्य नहीं मान सकती हैं। यह सटीक है क्योंकि सरल बाधाओं के अधिकतम मूल्य विभिन्न मूल्यांकनों से प्राप्त हो सकते हैं: सरल बाधा अधिकतम <math>x=a</math> तक हो सकती है, जबकि अन्य बाधा अधिकतम <math>x=b</math> तक हो सकती है।
-=====रूसी गुड़िया खोज=====
+=====रूसी डाॅल की खोज=====
-यह विधि<ref>Verfaillie, Gérard, Michel Lemaître, and Thomas Schiex. "[https://web.archive.org/web/20180616030142/https://pdfs.semanticscholar.org/c83b/19ca9cc73aefb1a9e7b4780ba161b2149a03.pdf Russian doll search for solving constraint optimization problems]." AAAI/IAAI, Vol. 1. 1996.</ref> एक ब्रांच-एंड-बाउंड एल्गोरिदम चलाता है <math>n</math> समस्याएं, कहां <math>n</math> चरों की संख्या है. ऐसी प्रत्येक समस्या चरों के अनुक्रम को छोड़ने से प्राप्त उपसमस्या है <math>x_1,\ldots,x_i</math> मूल समस्या से, साथ ही उनमें मौजूद बाधाओं से। चर पर समस्या के बाद <math>x_{i+1},\ldots,x_n</math> हल हो जाने पर, इसकी इष्टतम लागत को अन्य समस्याओं को हल करते समय ऊपरी सीमा के रूप में उपयोग किया जा सकता है,
+यह विधि<ref>Verfaillie, Gérard, Michel Lemaître, and Thomas Schiex. "[https://web.archive.org/web/20180616030142/https://pdfs.semanticscholar.org/c83b/19ca9cc73aefb1a9e7b4780ba161b2149a03.pdf Russian doll search for solving constraint optimization problems]." AAAI/IAAI, Vol. 1. 1996.</ref> ब्रांच-एंड-बाउंड एल्गोरिदम <math>n</math> समस्याएं चलाता है, जहाँ <math>n</math> वैरियेबल्स की संख्या है, ऐसी प्रत्येक समस्या वैरियेबल्स के अनुक्रम को छोड़ने से प्राप्त उपसमस्या <math>x_1,\ldots,x_i</math> है, यहाँ पर इस प्रकार की मूल समस्या से, साथ ही उनमें उपस्थित बाधाओं से किया जाता हैं। इस प्रकार वैरियेबल पर समस्या के पश्चात <math>x_{i+1},\ldots,x_n</math> के हल हो जाने पर, इसकी इष्टतम लागत को अन्य समस्याओं को हल करते समय ऊपरी सीमा के रूप में उपयोग किया जा सकता है,
-विशेष रूप से, किसी समाधान की लागत का अनुमान <math>x_{i+1},\ldots,x_n</math> चूंकि असाइन किए गए चर को उस लागत में जोड़ा जाता है जो मूल्यांकन किए गए चर से प्राप्त होती है। वस्तुतः, यह मूल्यांकन किए गए चरों को अनदेखा करने और असाइन न किए गए चरों पर समस्या को हल करने के अनुरूप है, सिवाय इसके कि बाद वाली समस्या पहले ही हल हो चुकी है। अधिक सटीक रूप से, असाइन किए गए और अनअसाइन किए गए दोनों चर वाले नरम बाधाओं की लागत का अनुमान ऊपर दिया गया है (या एक मनमाने ढंग से अन्य विधि का उपयोग करके); इसके बजाय केवल अनिर्धारित चर वाले नरम बाधाओं की लागत का अनुमान संबंधित समस्या के इष्टतम समाधान का उपयोग करके लगाया जाता है, जो इस बिंदु पर पहले से ही ज्ञात है।
+विशेष रूप से, किसी हल की लागत का अनुमान <math>x_{i+1},\ldots,x_n</math> हैं, चूंकि असाइन किए गए वैरियेबल को उस लागत में जोड़ा जाता है जो मूल्यांकन किए गए वैरियेबल से प्राप्त होती है। वस्तुतः यह मूल्यांकन किए गए वैरियेबल्स को अनदेखा करने और असाइन न किए गए वैरियेबल्स पर समस्या को हल करने के अनुरूप है, इसके अतिरिक्त बाद वाली समस्याएं पहले ही हल हो चुकी है। इसका अधिक सटीक रूप से, असाइन किए गए और अनअसाइन किए गए दोनों वैरियेबल वाले सरल बाधाओं की लागत का अनुमान या मनमाने ढंग से अन्य विधि का उपयोग करके ऊपर दिया गया है, इसके अतिरिक्त केवल अनिर्धारित वैरियेबल वाले सरल बाधाओं की लागत का अनुमान संबंधित समस्या के इष्टतम हल का उपयोग करके लगाया जाता है, जो इस बिंदु पर पहले से ही ज्ञात है।
-रूसी गुड़िया खोज पद्धति और [[गतिशील प्रोग्रामिंग]] के बीच समानता है। गतिशील प्रोग्रामिंग की तरह, रूसी गुड़िया खोज पूरी समस्या को हल करने के लिए उप-समस्याओं को हल करती है। लेकिन, जबकि डायनामिक प्रोग्रामिंग
+रूसी डाॅल की खोज पद्धति और [[गतिशील प्रोग्रामिंग|डायनेमिक प्रोग्रामिंग]] के बीच समानता है। डायनेमिक प्रोग्रामिंग के समान रूसी डाॅल की खोज पूरी समस्या को हल करने के लिए उप-समस्याओं को हल करती है। अपितु, जबकि डायनामिक प्रोग्रामिंग मुख्यतः इस प्रकार की संपूर्ण समस्याओं का परिणाम प्राप्त करने के लिए उप-समस्याओं पर प्राप्त परिणामों को सीधे संयोजित करता है, इस प्रकार रूसी डाॅल की खोज केवल अपनी खोज के समय उन्हें सीमा के रूप में उपयोग करती है।
-संपूर्ण समस्या का परिणाम प्राप्त करने के लिए उप-समस्याओं पर प्राप्त परिणामों को सीधे संयोजित करता है, रूसी गुड़िया खोज केवल अपनी खोज के दौरान उन्हें सीमा के रूप में उपयोग करती है।
-====[[बाल्टी उन्मूलन]]====
+====[[बाल्टी उन्मूलन|बकेट उन्मूलन]]====
-बकेट एलिमिनेशन एल्गोरिदम को बाधा अनुकूलन के लिए अनुकूलित किया जा सकता है। किसी दिए गए वेरिएबल को वास्तव में सभी नरम बाधाओं को एक नए नरम बाधा के साथ प्रतिस्थापित करके समस्या से हटाया जा सकता है। इस नई बाधा की लागत की गणना हटाए गए चर के प्रत्येक मान के लिए अधिकतम मान मानकर की जाती है। औपचारिक रूप से, यदि <math>x</math> क्या वेरिएबल को हटाया जाना है, <math>C_1,\ldots,C_n</math> इसमें शामिल नरम बाधाएं हैं, और <math>y_1,\ldots,y_m</math> सिवाय उनके चर हैं <math>x</math>, नई नरम बाधा द्वारा परिभाषित किया गया है:
+बकेट एलिमिनेशन एल्गोरिदम को बाधा अनुकूलन के लिए अनुकूलित किया जा सकता है। किसी दिए गए वेरिएबल को वास्तव में सभी सरल बाधाओं को नए सरल बाधा के साथ प्रतिस्थापित करके समस्या से हटाया जा सकता है। इस नई बाधा की लागत की गणना हटाए गए वैरियेबल के प्रत्येक मान के लिए अधिकतम मान मानकर की जाती है। इस प्रकार औपचारिक रूप से, यदि <math>x</math> क्या वेरिएबल को हटाया जाना है, यहाँ पर <math>C_1,\ldots,C_n</math> में सम्मिलित सरल बाधाएं हैं, और <math>y_1,\ldots,y_m</math> के अतिरिक्त उनके वैरियेबल <math>x</math> हैं, इस प्रकार की नई सरल बाधाओं द्वारा इन्हें परिभाषित किया गया है:
-<!-- not exactly the correct notation, but clear enough -->
 :<math>C(y_1=a_1,\ldots,y_n=a_n) = \max_a \sum_i C_i(x=a,y_1=a_1,\ldots,y_n=a_n).</math>
-बकेट एलिमिनेशन वेरिएबल्स के (मनमाने) क्रम के साथ काम करता है। प्रत्येक चर बाधाओं की एक श्रृंखला से जुड़ा होता है; एक वेरिएबल की बकेट में वे सभी बाधाएं होती हैं जिनमें वेरिएबल का क्रम सबसे ऊंचा होता है। बकेट एलिमिनेशन अंतिम वेरिएबल से पहले तक आगे बढ़ता है। प्रत्येक वेरिएबल के लिए, वेरिएबल को हटाने के लिए बकेट की सभी बाधाओं को ऊपर बताए अनुसार बदल दिया जाता है। परिणामी बाधा को फिर उपयुक्त बाल्टी में रखा जाता है।
+बकेट एलिमिनेशन वेरिएबल्स के क्रम के साथ कार्य करता है। प्रत्येक वैरियेबल बाधाओं की श्रृंखला से जुड़ा होता है, वेरिएबल की बकेट में वे सभी बाधाएं होती हैं जिनमें वेरिएबल का क्रम सबसे ऊंचा होता है। बकेट एलिमिनेशन अंतिम वेरिएबल से पहले तक आगे बढ़ता है। इस प्रकार प्रत्येक वेरिएबल के लिए, वेरिएबल को हटाने के लिए बकेट की सभी बाधाओं को ऊपर बताए अनुसार परिवर्तित कर दिया जाता है। इसके अनुसार परिणामी बाधाओं को फिर उपयुक्त बकेट में रखा जाता है।
 ==यह भी देखें==
@@ Line 92: / Line 88: @@
 * [[बाधा प्रोग्रामिंग]]
 * [[पूर्णांक प्रोग्रामिंग]]
-*दंड विधि
+*पेनैल्टी विधि
 * [[श्रेष्ठीकरण]]
@@ Line 115: / Line 111: @@
 {{Optimization algorithms}}
-[[Category: गणितीय अनुकूलन]] [[Category: बाधा प्रोग्रामिंग]]
-[[Category: Machine Translated Page]]
+[[Category:Articles with hatnote templates targeting a nonexistent page]]
+[[Category:CS1 English-language sources (en)]]
+[[Category:Collapse templates]]
 [[Category:Created On 26/07/2023]]
+[[Category:Lua-based templates]]
+[[Category:Machine Translated Page]]
+[[Category:Navigational boxes| ]]
+[[Category:Navigational boxes without horizontal lists]]
+[[Category:Pages using duplicate arguments in template calls]]
+[[Category:Pages with script errors]]
+[[Category:Short description with empty Wikidata description]]
+[[Category:Sidebars with styles needing conversion]]
+[[Category:Template documentation pages|Documentation/doc]]
+[[Category:Templates Translated in Hindi]]
+[[Category:Templates Vigyan Ready]]
+[[Category:Templates generating microformats]]
+[[Category:Templates that add a tracking category]]
+[[Category:Templates that are not mobile friendly]]
+[[Category:Templates that generate short descriptions]]
+[[Category:Templates using TemplateData]]
+[[Category:Wikipedia metatemplates]]
+[[Category:गणितीय अनुकूलन]]
+[[Category:बाधा प्रोग्रामिंग]]

Anonymous

Search

प्रतिबंधित अनुकूलन: Difference between revisions

Namespaces

More

Page actions

Latest revision as of 16:01, 22 August 2023

Contents

बाधा-संतुष्टि का समस्याओं से संबंध

सामान्य प्रपत्र