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

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

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$ दूरी मैट्रिक्स है.

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

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

अनुप्रयोग

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

यह भी देखें

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

संदर्भ

Notes

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