द्विघात असाइनमेंट समस्या: Difference between revisions

From Vigyanwiki
(Created page with "{{Short description|Combinatorial optimization problem}} द्विघात असाइनमेंट समस्या (क्यूएपी) ऑप्टिमाइ...")
 
No edit summary
 
(4 intermediate revisions by 3 users not shown)
Line 1: Line 1:
{{Short description|Combinatorial optimization problem}}
{{Short description|Combinatorial optimization problem}}
द्विघात असाइनमेंट समस्या (क्यूएपी) ऑप्टिमाइज़ेशन (गणित) या गणित में संचालन अनुसंधान की शाखा में मूलभूत संयोजन अनुकूलन समस्याओं में से एक है, जो कि कोपमैन्स और बेकमैन द्वारा पहली बार शुरू की गई सुविधाओं की स्थान समस्याओं की श्रेणी से है।<ref>Koopmans TC, Beckmann M (1957). Assignment problems and the location of economic activities. Econometrica 25(1):53-76</ref>
'''द्विघात मानांकन समस्या''' (क्यूएपी) मुख्य रूप से ऑप्टिमाइज़ेशन (गणित) या गणित में संचालन होने वाले अनुसंधान की शाखा में मूलभूत संयोजन अनुकूलन समस्याओं में से प्रमुख है, जो कि कोपमैन्स और बेकमैन द्वारा पहली बार प्रारंभ की गई सुविधाओं की स्थान समस्याओं की श्रेणी से है।<ref>Koopmans TC, Beckmann M (1957). Assignment problems and the location of economic activities. Econometrica 25(1):53-76</ref> इस प्रकारी की समस्याएं निम्नलिखित वास्तविक जीवन की समस्याओं का प्रारूप तैयार करती है।
समस्या निम्नलिखित वास्तविक जीवन की समस्या का मॉडल तैयार करती है:


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


सहज रूप से, लागत फ़ंक्शन एक-दूसरे के बीच उच्च प्रवाह वाली सुविधाओं को एक-दूसरे के करीब रखने के लिए प्रोत्साहित करता है।
सहजता से, इस प्रकार के लागत फ़ंक्शन एक-दूसरे के बीच उच्च प्रवाह वाली सुविधाओं को एक-दूसरे के समीप रखने के लिए प्रोत्साहित किए जाते हैं।


समस्या कथन [[असाइनमेंट समस्या]] से मिलता-जुलता है, सिवाय इसके कि हानि फ़ंक्शन द्विघात असमानताओं के संदर्भ में व्यक्त किया जाता है, इसलिए नाम।
इस प्रकार की समस्या से जुड़े कथन के फलस्वरूप [[असाइनमेंट समस्या|मानांकन समस्या]] से मिलता जुलता है, इसके अतिरिक्त हानि फलन द्विघात असमानताओं के संदर्भ में व्यक्त किया जाता है।


==औपचारिक गणितीय परिभाषा==
==औपचारिक गणितीय परिभाषा==


द्विघात असाइनमेंट समस्या की औपचारिक परिभाषा इस प्रकार है:
द्विघात मानांकन समस्या की औपचारिक परिभाषा इस प्रकार है:


: समान आकार के दो सेट, P (सुविधाएं) और L (स्थान), एक [[वजन समारोह]] w: P × P → '[[वास्तविक संख्या]]' और एक दूरी फ़ंक्शन d: L × L → 'वास्तविक संख्या' के साथ दिए गए हैं। आक्षेप f : P → L (असाइनमेंट) इस प्रकार खोजें कि लागत फलन हो:
: समान आकार के दो समुच्चय, P (सुविधाएं) और L (स्थान), [[वजन समारोह|भार फलन]] w: P × P → '[[वास्तविक संख्या]]' और दूरी फ़ंक्शन d: L × L → 'वास्तविक संख्या' के साथ दिए गए हैं। इसके आक्षेप f : P → L (मानांकन) इस प्रकार खोजें कि लागत फलन को प्रदर्शित करता हैं:


::<math>\sum_{a,b\in P}w(a,b)\cdot d(f(a), f(b))</math>
::<math>\sum_{a,b\in P}w(a,b)\cdot d(f(a), f(b))</math>
:न्यूनतम किया गया है.
:यहाँ इसका न्यूनतम मान प्रदर्शित किया गया है।


आमतौर पर वजन और दूरी के कार्यों को वर्गाकार वास्तविक-मूल्य वाले [[मैट्रिक्स (गणित)]] के रूप में देखा जाता है, ताकि लागत फ़ंक्शन को इस प्रकार लिखा जाए:
सामान्यतः वजन और दूरी के कार्यों को वर्गाकार वास्तविक मान वाले [[मैट्रिक्स (गणित)|आव्यूह (गणित)]] के रूप में देखा जाता है, जिससे कि लागत फ़ंक्शन को इस प्रकार लिखा जाता हैं:


:<math>\sum_{a,b\in P}w_{a,b}d_{f(a),f(b)}</math>
:<math>\sum_{a,b\in P}w_{a,b}d_{f(a),f(b)}</math>
मैट्रिक्स संकेतन में:
आव्यूह संकेतन में:


:<math>\min_{X\in\Pi_n} \operatorname{trace}(WXDX^T)</math>
:<math>\min_{X\in\Pi_n} \operatorname{trace}(WXDX^T)</math>
कहाँ <math>\Pi_n</math> का सेट है <math>n \times n</math> क्रमपरिवर्तन मैट्रिक्स, <math>W</math> वजन मैट्रिक्स है और <math>D</math> दूरी मैट्रिक्स है.
जहाँ <math>\Pi_n</math> मुख्य रूप से <math>n \times n</math> समुच्चय है, इसके अनुसार क्रमपरिवर्तन आव्यूह, <math>W</math> मुख्यतः भार आव्यूह को प्रदर्शित करता है और <math>D</math> दूरी आव्यूह को प्रदर्शित करती है।


== कम्प्यूटेशनल जटिलता ==
== कम्प्यूटेशनल जटिलता ==


समस्या [[ एनपी कठिन ]] है, इसलिए बहुपद समय में इस समस्या को हल करने के लिए कोई ज्ञात [[कलन विधि]] नहीं है, और यहां तक ​​कि छोटे उदाहरणों के लिए भी लंबे गणना समय की आवश्यकता हो सकती है। यह भी सिद्ध हुआ कि समस्या में किसी भी (स्थिर) कारक के लिए बहुपद समय में चलने वाला एक सन्निकटन एल्गोरिदम नहीं है, जब तक कि पी = एनपी न हो।<ref>{{Cite journal|title = P-Complete Approximation Problems
यहाँ पर यह समस्या [[ एनपी कठिन |एनपी]] के लिए जटिल रहती है, इसलिए इस बहुपद के लिए उचित समय में इस समस्या को हल करने के लिए कोई ज्ञात [[कलन विधि]] नहीं है, और यहां तक ​​कि छोटे उदाहरणों के लिए भी लंबे गणना समय की आवश्यकता हो सकती है। यह भी सिद्ध हुआ कि समस्या में किसी भी (स्थिर) कारक के लिए बहुपद समय में चलने वाला सन्निकटन एल्गोरिदम नहीं है, जब तक कि P = NP के समान न हो जाये।<ref>{{Cite journal|title = P-Complete Approximation Problems
|last1 = Sahni|first1 = Sartaj
|last1 = Sahni|first1 = Sartaj
|last2 = Gonzalez |first2 = Teofilo  
|last2 = Gonzalez |first2 = Teofilo  
Line 35: Line 34:
|pages = 555–565
|pages = 555–565
|journal = Journal of the ACM|doi = 10.1145/321958.321975|hdl = 10338.dmlcz/103883
|journal = Journal of the ACM|doi = 10.1145/321958.321975|hdl = 10338.dmlcz/103883
|hdl-access = free}}</ref> [[ट्रैवलिंग सेल्समैन की समस्या]] (टीएसपी) को क्यूएपी के एक विशेष मामले के रूप में देखा जा सकता है यदि कोई मानता है कि प्रवाह सभी सुविधाओं को केवल एक रिंग के साथ जोड़ता है, सभी प्रवाह का गैर-शून्य (स्थिर) मान समान है और सभी दूरियां समान हैं टीएसपी उदाहरण की संबंधित दूरी। मानक संयोजन अनुकूलन समस्याओं की कई अन्य समस्याओं को इस रूप में लिखा जा सकता है।
|hdl-access = free}}</ref> इस प्रकार [[ट्रैवलिंग सेल्समैन की समस्या]] (टीएसपी) को क्यूएपी के विशेष स्थिति के रूप में देखा जा सकता है, यदि यह कोई मानता है कि प्रवाह सभी सुविधाओं को केवल वलय के साथ जोड़ता है, इसके आधार पर सभी प्रवाह का गैर-शून्य (स्थिर) मान समान है, और सभी दूरियां समान होती हैं, इसके आधार पर टीएसपी उदाहरण की संबंधित दूरी को प्रकट करती हैं। इसके मानक संयोजन के आधार पर अनुकूलन समस्याओं की कई अन्य समस्याओं को इस रूप में लिखा जा सकता है।


== अनुप्रयोग ==
== अनुप्रयोग ==


मूल संयंत्र स्थान सूत्रीकरण के अलावा, क्यूएपी एक [[मुद्रित सर्किट बोर्ड]] या एक एकीकृत सर्किट पर परस्पर जुड़े [[इलेक्ट्रॉनिक घटक]]ों की नियुक्ति की समस्या के लिए एक गणितीय मॉडल है, जो इलेक्ट्रॉनिक्स में [[कंप्यूटर एडेड डिजाइन]] के [[स्थान और मार्ग]] चरण का हिस्सा है। उद्योग।
मूल संयंत्र स्थान सूत्रीकरण के अतिरिक्त, क्यूएपी [[मुद्रित सर्किट बोर्ड]] या एकीकृत सर्किट पर परस्पर जुड़े [[इलेक्ट्रॉनिक घटक|इलेक्ट्रॉनिक घटकों]] की नियुक्ति की समस्या के लिए गणितीय प्रारूप है, जो इलेक्ट्रॉनिक्स में [[कंप्यूटर एडेड डिजाइन]] के [[स्थान और मार्ग|स्थान और मूल]] चरण का भाग है।


==यह भी देखें==
==यह भी देखें==
*[[द्विघात बाधा असाइनमेंट समस्या]]
*[[द्विघात बाधा असाइनमेंट समस्या|द्विघात समस्या के मूल्यांकन से जुड़ी समस्या]]


== संदर्भ ==
== संदर्भ ==
Line 53: Line 52:
==बाहरी संबंध==
==बाहरी संबंध==
* https://www.opt.math.tugraz.at/qaplib/ QAPLIB - A Quadratic Assignment Problem Library
* https://www.opt.math.tugraz.at/qaplib/ QAPLIB - A Quadratic Assignment Problem Library
* http://www.wiomax.com/team/xie/maos-qap-quadratic-assignment-problem-project-portal/ MAOS-QAP - Java-based Quadratic Assignment Problem Solver
* http://www.wiomax.com/team/xie/maos-qap-quadratic-assignment-problem-project-portal/ MAOS-QAP - Java-based Quadratic Assignment Problem Solver
* https://CRAN.R-project.org/package=qap - R package qap: Heuristics for the Quadratic Assignment Problem
* https://CRAN.R-project.org/package=qap - R package qap: Heuristics for the Quadratic Assignment Problem
* https://apps.microsoft.com/store/detail/qapsolver/9N7WMCFB6NZZ - Metaheuristic QAP solver for Windows 10/11
* https://apps.microsoft.com/store/detail/qapsolver/9N7WMCFB6NZZ - Metaheuristic QAP solver for Windows 10/11
[[Category: एनपी-कठिन समस्याएँ]] [[Category: संयुक्त अनुकूलन]]


[[Category: Machine Translated Page]]
[[Category:Created On 11/07/2023]]
[[Category:Created On 11/07/2023]]
[[Category:Lua-based templates]]
[[Category:Machine Translated Page]]
[[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:एनपी-कठिन समस्याएँ]]
[[Category:संयुक्त अनुकूलन]]

Latest revision as of 17:15, 21 August 2023

द्विघात मानांकन समस्या (क्यूएपी) मुख्य रूप से ऑप्टिमाइज़ेशन (गणित) या गणित में संचालन होने वाले अनुसंधान की शाखा में मूलभूत संयोजन अनुकूलन समस्याओं में से प्रमुख है, जो कि कोपमैन्स और बेकमैन द्वारा पहली बार प्रारंभ की गई सुविधाओं की स्थान समस्याओं की श्रेणी से है।[1] इस प्रकारी की समस्याएं निम्नलिखित वास्तविक जीवन की समस्याओं का प्रारूप तैयार करती है।

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

सहजता से, इस प्रकार के लागत फ़ंक्शन एक-दूसरे के बीच उच्च प्रवाह वाली सुविधाओं को एक-दूसरे के समीप रखने के लिए प्रोत्साहित किए जाते हैं।

इस प्रकार की समस्या से जुड़े कथन के फलस्वरूप मानांकन समस्या से मिलता जुलता है, इसके अतिरिक्त हानि फलन द्विघात असमानताओं के संदर्भ में व्यक्त किया जाता है।

औपचारिक गणितीय परिभाषा

द्विघात मानांकन समस्या की औपचारिक परिभाषा इस प्रकार है:

समान आकार के दो समुच्चय, P (सुविधाएं) और L (स्थान), भार फलन w: P × P → 'वास्तविक संख्या' और दूरी फ़ंक्शन d: L × L → 'वास्तविक संख्या' के साथ दिए गए हैं। इसके आक्षेप f : P → L (मानांकन) इस प्रकार खोजें कि लागत फलन को प्रदर्शित करता हैं:
यहाँ इसका न्यूनतम मान प्रदर्शित किया गया है।

सामान्यतः वजन और दूरी के कार्यों को वर्गाकार वास्तविक मान वाले आव्यूह (गणित) के रूप में देखा जाता है, जिससे कि लागत फ़ंक्शन को इस प्रकार लिखा जाता हैं:

आव्यूह संकेतन में:

जहाँ मुख्य रूप से समुच्चय है, इसके अनुसार क्रमपरिवर्तन आव्यूह, मुख्यतः भार आव्यूह को प्रदर्शित करता है और दूरी आव्यूह को प्रदर्शित करती है।

कम्प्यूटेशनल जटिलता

यहाँ पर यह समस्या एनपी के लिए जटिल रहती है, इसलिए इस बहुपद के लिए उचित समय में इस समस्या को हल करने के लिए कोई ज्ञात कलन विधि नहीं है, और यहां तक ​​कि छोटे उदाहरणों के लिए भी लंबे गणना समय की आवश्यकता हो सकती है। यह भी सिद्ध हुआ कि समस्या में किसी भी (स्थिर) कारक के लिए बहुपद समय में चलने वाला सन्निकटन एल्गोरिदम नहीं है, जब तक कि P = NP के समान न हो जाये।[2] इस प्रकार ट्रैवलिंग सेल्समैन की समस्या (टीएसपी) को क्यूएपी के विशेष स्थिति के रूप में देखा जा सकता है, यदि यह कोई मानता है कि प्रवाह सभी सुविधाओं को केवल वलय के साथ जोड़ता है, इसके आधार पर सभी प्रवाह का गैर-शून्य (स्थिर) मान समान है, और सभी दूरियां समान होती हैं, इसके आधार पर टीएसपी उदाहरण की संबंधित दूरी को प्रकट करती हैं। इसके मानक संयोजन के आधार पर अनुकूलन समस्याओं की कई अन्य समस्याओं को इस रूप में लिखा जा सकता है।

अनुप्रयोग

मूल संयंत्र स्थान सूत्रीकरण के अतिरिक्त, क्यूएपी मुद्रित सर्किट बोर्ड या एकीकृत सर्किट पर परस्पर जुड़े इलेक्ट्रॉनिक घटकों की नियुक्ति की समस्या के लिए गणितीय प्रारूप है, जो इलेक्ट्रॉनिक्स में कंप्यूटर एडेड डिजाइन के स्थान और मूल चरण का भाग है।

यह भी देखें

संदर्भ

Notes
  1. ↑ Koopmans TC, Beckmann M (1957). Assignment problems and the location of economic activities. Econometrica 25(1):53-76
  2. ↑ Sahni, Sartaj; Gonzalez, Teofilo (July 1976). "P-Complete Approximation Problems". Journal of the ACM. 23 (3): 555–565. doi:10.1145/321958.321975. hdl:10338.dmlcz/103883.
Sources


बाहरी संबंध

Retrieved from ‘https://www.vigyanwiki.in/index.php?title=द्विघात_असाइनमेंट_समस्या&oldid=251193’