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