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

Revision as of 22:06, 10 August 2023

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

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

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

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

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

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

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

\sum _{a,b\in P}w(a,b)\cdot d(f(a),f(b))

न्यूनतम किया गया है.

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

\sum _{a,b\in P}w_{a,b}d_{f(a),f(b)}

मैट्रिक्स संकेतन में:

\min _{X\in \Pi _{n}}\operatorname {trace} (WXDX^{T})

कहाँ $\Pi _{n}$ का सेट है $n\times n$ क्रमपरिवर्तन मैट्रिक्स, $W$ वजन मैट्रिक्स है और $D$ दूरी मैट्रिक्स है.

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

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

अनुप्रयोग

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

यह भी देखें

द्विघात बाधा असाइनमेंट समस्या

संदर्भ

Notes

↑ Koopmans TC, Beckmann M (1957). Assignment problems and the location of economic activities. Econometrica 25(1):53-76
↑ 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

Michael R. Garey and David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 0-7167-1045-5. A2.5: ND43, pg.218.

बाहरी संबंध

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
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

[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.

[1]

[2]

@@ Line 1: / Line 1: @@
 {{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 सुविधाओं का सेट और n स्थानों का सेट है। स्थानों की प्रत्येक जोड़ी के लिए, दूरी निर्दिष्ट की जाती है और प्रत्येक जोड़ी सुविधाओं के लिए वजन या प्रवाह निर्दिष्ट किया जाता है (उदाहरण के लिए, दो सुविधाओं के बीच परिवहन की गई आपूर्ति की मात्रा)। समस्या संबंधित प्रवाह द्वारा गुणा की गई दूरियों के योग को कम करने के लक्ष्य के साथ सभी सुविधाओं को विभिन्न स्थानों पर आवंटित करने की है।
 सहज रूप से, लागत फ़ंक्शन एक-दूसरे के बीच उच्च प्रवाह वाली सुविधाओं को एक-दूसरे के करीब रखने के लिए प्रोत्साहित करता है।
@@ Line 13: / Line 13: @@
 द्विघात असाइनमेंट समस्या की औपचारिक परिभाषा इस प्रकार है:
-: समान आकार के दो सेट, 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>
@@ Line 28: / Line 28: @@
 == कम्प्यूटेशनल जटिलता ==
-समस्या [[ एनपी कठिन ]] है, इसलिए बहुपद समय में इस समस्या को हल करने के लिए कोई ज्ञात [[कलन विधि]] नहीं है, और यहां तक कि छोटे उदाहरणों के लिए भी लंबे गणना समय की आवश्यकता हो सकती है। यह भी सिद्ध हुआ कि समस्या में किसी भी (स्थिर) कारक के लिए बहुपद समय में चलने वाला एक सन्निकटन एल्गोरिदम नहीं है, जब तक कि पी = एनपी न हो।<ref>{{Cite journal|title = P-Complete Approximation Problems
+समस्या [[ एनपी कठिन |एनपी कठिन]] है, इसलिए बहुपद समय में इस समस्या को हल करने के लिए कोई ज्ञात [[कलन विधि]] नहीं है, और यहां तक कि छोटे उदाहरणों के लिए भी लंबे गणना समय की आवश्यकता हो सकती है। यह भी सिद्ध हुआ कि समस्या में किसी भी (स्थिर) कारक के लिए बहुपद समय में चलने वाला सन्निकटन एल्गोरिदम नहीं है, जब तक कि पी = एनपी न हो।<ref>{{Cite journal|title = P-Complete Approximation Problems
 |last1 = Sahni|first1 = Sartaj
 |last2 = Gonzalez |first2 = Teofilo
@@ Line 35: / Line 35: @@
 |pages = 555–565
 |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 53: @@
 ==बाहरी संबंध==
 * 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://apps.microsoft.com/store/detail/qapsolver/9N7WMCFB6NZZ - Metaheuristic QAP solver for Windows 10/11

Anonymous

Search

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

Namespaces

More

Page actions

Revision as of 22:06, 10 August 2023

Contents

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

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

अनुप्रयोग

यह भी देखें

संदर्भ

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Revision as of 22:06, 10 August 2023

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

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

अनुप्रयोग

यह भी देखें

संदर्भ

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories