Gomory विधि। पूर्णांक कार्यक्रम समस्या समाधान

आर्थिक, योजना को वजन समस्या र पूर्णाङ्कहरुको सम्बन्धित चर सम्बन्धित मानव जीवन समस्या अन्य क्षेत्रहरू देखि मुद्दाहरू पनि। आफ्नो विश्लेषण को परिणाम र चरम चुनौतीहरू को धारणा सम्बोधन गर्न सबै भन्दा राम्रो तरिका को लागि खोज रूपमा। यसको सुविधाहरू माथि सुविधा एक पूर्णांक मूल्य लिन्छ छ, र कार्य नै पूर्णांक कार्यक्रम रूपमा गणित मानिन्छ।

चर, एक पूर्णांक समस्या को मुख्य प्रयोगहरू, अनुकूलन छ। एक पूर्णांक प्रयोग गर्ने विधि रैखिक कार्यक्रम, पनि काटिएको विधि भनिन्छ।

Gomory विधि पहिलो 1957-1958 अल्गोरिदम विकास अझै पनि व्यापक पूर्णांक रैखिक कार्यक्रम समस्या समाधान गर्न प्रयोग गरिन्छ, गणितज्ञ पछि नाम थियो। पूर्णाङ्क कार्यक्रम समस्या को प्रमाणिक फारम पहुँच अनुमति दिन्छ र पूर्णतया यो विधि को लाभ खुलासा।

Gomori विधि एक रैखिक कार्यक्रम लागू निकै इष्टतम मान फेला को कार्य complicates। integrality पछि आधारभूत आवश्यकता, समस्या थप सबै मापदण्डहरु छ। मान्य (पूर्णांक) योजना गरेर समस्या, मा उपस्थिति हुँदा अवस्थामा छन् को उद्देश्य समारोह को स्वीकार गर्न सकिने सेट मा प्रतिबंध को, निर्णय अधिकतम प्राप्त गर्न आउँछ। यो कमी अभिन्न समाधान छ यो कारण छ। एउटै अवस्था बिना, नियम, निर्णय को रूप मा उपयुक्त सदिश छ।

त्यहाँ विभिन्न अवस्थामा थप superimposition पूरा गर्न आवश्यक छ समस्या सुलझाने लागि संख्यात्मक एल्गोरिदम सफाइ।

Gomory को विधि प्रयोग गरेर सीमित polyhedron समाधान को तथाकथित समस्याको लागि धेरै योजना सामान्यतया विचार गर्नुहोस्। यो आधारमा सबै अभिन्न योजना को सेट कार्य को लागि एक परिमित मान छ।

साथै, ग्यारेन्टी अभिन्न समारोह लागि गुणांकहरूको को मान पनि पूर्णांक हो कि मान। यी अवस्था खुलारूपमा बावजूद, कमजोर तिनीहरूले केही व्यवस्थापन गर्नुहोस्।

Gomory विधि अनिवार्य हो कि nonintegral छैन समाधान कटौती जो भवन प्रतिबन्ध, समावेश छ। यस मामला मा, कुनै काटिएको कुनै पूर्णांक समाधान योजना छ।

को समस्या समाधान को लागि अल्गोरिदम उपयुक्त विकल्प फेला समावेश , सिमप्लेक्स विधि खातामा integrality को अवस्था लिइरहेको बिना। इष्टतम योजना सबै घटक समावेश पूर्णाङ्कहरुको सम्बन्धित निर्णय भने, यो पूर्णांक कार्यक्रम लक्ष्य हासिल छ कल्पित गर्न सकिन्छ। सायद त्यो समस्या को insolubility पाइन्छ, त्यसैले हामी पूर्णांक कार्यक्रम समस्या कुनै समाधान छ भन्ने कुराको प्रमाण छ।

इष्टतम समाधान को घटक समावेश गर्दा गैर-पूर्णांक नम्बर भेद। यस मामला मा, एक नयाँ प्रतिबन्ध समस्या सबै अवरोध थपिएको छ। नयाँ प्रतिबन्ध गुण को एक नम्बर द्वारा विशेषता छन्। सबै को पहिलो, यो रैखिक हुनुपर्छ, बन्द गैर-पूर्णांक इष्टतम योजना को फेला सेट काट्न गर्नुपर्छ। न त पूर्णांक समाधान छैन नष्ट गर्नुपर्छ, कट।

जब निर्माण प्रतिबन्ध उच्चतम अंश संग सर्वोत्कृष्ट योजना को घटक रोजेको हुनुपर्छ। यो सीमा अवस्थित सिमप्लेक्स तालिका थपिनेछ छ।

हामी परिणामस्वरूप समस्या पारंपरिक सिमप्लेक्स परिवर्तन प्रयोग को समाधान पाउन। हामी एक पूर्णांक इष्टतम योजना अस्तित्व मा समस्या को समाधान जाँच, अवस्था सन्तुष्ट छ भने, त्यसपछि समस्या हल भएको छ। परिणाम गैर-पूर्णांक समाधान उपस्थिति फेरि प्राप्त भएको थियो भने, त्यसपछि हामी थप अनुमानप्रकार परिचय, र गणना प्रक्रिया दोहोर्याउनुहोस्।

पुनरावृत्ति को एक परिमित नम्बर बाहिर भएको, हामी पूर्णांक कार्यक्रम अगाडि खडा समस्या को सर्वोत्कृष्ट कार्यक्रम हासिल वा समस्या को insolubility प्रमाणित।