View source for पूर्ण दोहरी अभिन्नता

[[गणितीय अनुकूलन]] में, '''पूर्ण दोहरी अभिन्नता'''[[ अभिन्न बहुफलक | अभिन्न बहुफलक]] के लिए पर्याप्त शर्त है। इस प्रकार, ऐसे बहुफलक की [[पूर्णांक प्रोग्रामिंग]] [[रैखिक प्रोग्रामिंग]] की तकनीकों का उपयोग करके की जा सकती है।

एक रेखीय प्रणाली <math>Ax\le b</math>, जहाँ <math>A</math> और <math>b</math> तर्कसंगत हैं, यदि कोई हो तो इसे '''पूर्ण दोहरी अभिन्नता''' (टीडीआई) कहा जाता है <math>c \in \mathbb{Z}^n</math> जैसे कि रैखिक कार्यक्रम का एक व्यवहार्य, सीमित समाधान हो
:<math>
\begin{align}
&&\max c^\mathrm{T}x \\
&& Ax\le b,
\end{align}
</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="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}}


[[Category: रैखिक प्रोग्रामिंग]] 



[[Category: Machine Translated Page]]
[[Category:Created On 07/07/2023]]