पूर्ण दोहरी अभिन्नता: Difference between revisions
From Vigyanwiki
(Created page with "गणितीय अनुकूलन में, कुल दोहरी अभिन्नता अभिन्न बहुफलक के लिए पर...") |
No edit summary |
||
| Line 1: | Line 1: | ||
[[गणितीय अनुकूलन]] में, | [[गणितीय अनुकूलन]] में, '''पूर्ण दोहरी अभिन्नता'''[[ अभिन्न बहुफलक | अभिन्न बहुफलक]] के लिए पर्याप्त शर्त है। इस प्रकार, ऐसे बहुफलक की [[पूर्णांक प्रोग्रामिंग]] [[रैखिक प्रोग्रामिंग]] की तकनीकों का उपयोग करके की जा सकती है। | ||
एक रेखीय प्रणाली <math>Ax\le b</math>, | एक रेखीय प्रणाली <math>Ax\le b</math>, जहाँ <math>A</math> और <math>b</math> तर्कसंगत हैं, यदि कोई हो तो इसे '''पूर्ण दोहरी अभिन्नता''' (टीडीआई) कहा जाता है <math>c \in \mathbb{Z}^n</math> जैसे कि रैखिक कार्यक्रम का एक व्यवहार्य, सीमित समाधान हो | ||
:<math> | :<math> | ||
\begin{align} | \begin{align} | ||
| Line 9: | Line 9: | ||
</math> | </math> | ||
एक पूर्णांक इष्टतम दोहरा समाधान है।<ref name="gilesPulleyblank">{{cite journal|last=Giles|first=F.R.|author2=W.R. Pulleyblank|author2-link=William R. Pulleyblank |title=कुल दोहरी अखंडता और पूर्णांक पॉलीहेड्रा|journal=Linear Algebra and its Applications|year=1979|volume=25|pages=191–196|doi=10.1016/0024-3795(79)90018-1|doi-access=free}}</ref><ref name="EdmondsGiles">{{cite journal|last=Edmonds|first=J.|author-link=Jack Edmonds|author2=R. Giles |title=ग्राफ़ पर सबमॉड्यूलर फ़ंक्शंस के लिए न्यूनतम-अधिकतम संबंध|journal=Annals of Discrete Mathematics|year=1977|volume=1|pages=185–204}}</ref><ref>{{cite journal|last=Schrijver|first=A.|title=संपूर्ण दोहरी अखंडता पर|journal=Linear Algebra and its Applications|year=1981|volume=38|pages=27–32|doi=10.1016/0024-3795(81)90005-7|doi-access=free}}</ref> | एक पूर्णांक इष्टतम दोहरा समाधान है।<ref name="gilesPulleyblank">{{cite journal|last=Giles|first=F.R.|author2=W.R. Pulleyblank|author2-link=William R. Pulleyblank |title=कुल दोहरी अखंडता और पूर्णांक पॉलीहेड्रा|journal=Linear Algebra and its Applications|year=1979|volume=25|pages=191–196|doi=10.1016/0024-3795(79)90018-1|doi-access=free}}</ref><ref name="EdmondsGiles">{{cite journal|last=Edmonds|first=J.|author-link=Jack Edmonds|author2=R. Giles |title=ग्राफ़ पर सबमॉड्यूलर फ़ंक्शंस के लिए न्यूनतम-अधिकतम संबंध|journal=Annals of Discrete Mathematics|year=1977|volume=1|pages=185–204}}</ref><ref>{{cite journal|last=Schrijver|first=A.|title=संपूर्ण दोहरी अखंडता पर|journal=Linear Algebra and its Applications|year=1981|volume=38|pages=27–32|doi=10.1016/0024-3795(81)90005-7|doi-access=free}}</ref> | ||
एडमंड्स और जाइल्स<ref name="EdmondsGiles" />दिखाया कि यदि एक बहुफलक <math>P</math> टीडीआई प्रणाली का समाधान समुच्चय है <math>Ax\le b</math>, जहाँ <math>b</math> सभी पूर्णांक प्रविष्टियाँ हैं, फिर प्रत्येक शीर्ष <math>P</math> पूर्णांक-मूल्यवान है. इस प्रकार, यदि उपरोक्त के अनुसार एक रैखिक प्रोग्राम को [[सिम्प्लेक्स एल्गोरिथ्म]] द्वारा हल किया जाता है, तो लौटाया गया इष्टतम समाधान पूर्णांक होगा। इसके अलावा, जाइल्स और पुलीब्लैंक<ref name="gilesPulleyblank" />दिखाया कि अगर <math>P</math> एक पॉलीटोप है जिसके सभी शीर्ष पूर्णांक मान वाले हैं <math>P</math> कुछ टीडीआई प्रणाली का समाधान समुच्चय है <math>Ax\le b</math>, जहाँ <math>b</math> पूर्णांक का मान है. | |||
ध्यान दें कि टीडीआई यूनिमॉड्यूलर मैट्रिक्स #पूर्ण_यूनिमॉड्यूलरिटी की तुलना में अभिन्नता के लिए एक अशक्त पर्याप्त शर्त है।<ref>{{cite web|last=Chekuri|first=C.|title=संयुक्त अनुकूलन व्याख्यान नोट्स|url=http://courses.engr.illinois.edu/cs598csc/sp2010/Lectures/Lecture12.pdf}}</ref> | |||
==संदर्भ== | ==संदर्भ== | ||
{{Reflist}} | {{Reflist}} | ||
Revision as of 23:26, 14 July 2023
गणितीय अनुकूलन में, पूर्ण दोहरी अभिन्नता अभिन्न बहुफलक के लिए पर्याप्त शर्त है। इस प्रकार, ऐसे बहुफलक की पूर्णांक प्रोग्रामिंग रैखिक प्रोग्रामिंग की तकनीकों का उपयोग करके की जा सकती है।
एक रेखीय प्रणाली , जहाँ और तर्कसंगत हैं, यदि कोई हो तो इसे पूर्ण दोहरी अभिन्नता (टीडीआई) कहा जाता है जैसे कि रैखिक कार्यक्रम का एक व्यवहार्य, सीमित समाधान हो
एक पूर्णांक इष्टतम दोहरा समाधान है।[1][2][3]
एडमंड्स और जाइल्स[2]दिखाया कि यदि एक बहुफलक टीडीआई प्रणाली का समाधान समुच्चय है , जहाँ सभी पूर्णांक प्रविष्टियाँ हैं, फिर प्रत्येक शीर्ष पूर्णांक-मूल्यवान है. इस प्रकार, यदि उपरोक्त के अनुसार एक रैखिक प्रोग्राम को सिम्प्लेक्स एल्गोरिथ्म द्वारा हल किया जाता है, तो लौटाया गया इष्टतम समाधान पूर्णांक होगा। इसके अलावा, जाइल्स और पुलीब्लैंक[1]दिखाया कि अगर एक पॉलीटोप है जिसके सभी शीर्ष पूर्णांक मान वाले हैं कुछ टीडीआई प्रणाली का समाधान समुच्चय है , जहाँ पूर्णांक का मान है.
ध्यान दें कि टीडीआई यूनिमॉड्यूलर मैट्रिक्स #पूर्ण_यूनिमॉड्यूलरिटी की तुलना में अभिन्नता के लिए एक अशक्त पर्याप्त शर्त है।[4]
संदर्भ
- ↑ 1.0 1.1 Giles, F.R.; W.R. Pulleyblank (1979). "कुल दोहरी अखंडता और पूर्णांक पॉलीहेड्रा". Linear Algebra and its Applications. 25: 191–196. doi:10.1016/0024-3795(79)90018-1.
- ↑ 2.0 2.1 Edmonds, J.; R. Giles (1977). "ग्राफ़ पर सबमॉड्यूलर फ़ंक्शंस के लिए न्यूनतम-अधिकतम संबंध". Annals of Discrete Mathematics. 1: 185–204.
- ↑ Schrijver, A. (1981). "संपूर्ण दोहरी अखंडता पर". Linear Algebra and its Applications. 38: 27–32. doi:10.1016/0024-3795(81)90005-7.
- ↑ Chekuri, C. "संयुक्त अनुकूलन व्याख्यान नोट्स" (PDF).
