सामान्यीकृत सिंप्लेक्स विधि। zlp . को हल करने के लिए सरल विधि

सिंप्लेक्स विधि एक रैखिक प्रोग्रामिंग समस्या की बाधाओं की प्रणाली के एक मूल समाधान (समाधान पॉलीहेड्रॉन का शीर्ष) से ​​अनुक्रमिक संक्रमण की एक विधि है जब तक कि लक्ष्य फ़ंक्शन इष्टतम मान (अधिकतम या न्यूनतम) नहीं लेता है।

सिंप्लेक्स विधि एक सार्वभौमिक विधि है जो किसी को भी हल कर सकती है रैखिक प्रोग्रामिंग समस्या, जबकि आलेखीय विधि केवल दो चरों वाले अवरोधों की प्रणाली के लिए उपयुक्त है।

1947 में अमेरिकी गणितज्ञ आर. डेंजिग द्वारा सिम्पलेक्स विधि प्रस्तावित की गई थी, तब से, उद्योग की जरूरतों के लिए, इस पद्धति का उपयोग अक्सर हजारों चर और बाधाओं के साथ रैखिक प्रोग्रामिंग समस्याओं को हल करने के लिए किया जाता है।

सिंप्लेक्स मेथड एल्गोरिथम पर आगे बढ़ने से पहले, कुछ परिभाषाएं.

बाधाओं की प्रणाली के किसी भी गैर-नकारात्मक समाधान को कहा जाता है स्वीकार्य निर्णय .

एक सिस्टम होने दो एमके साथ प्रतिबंध एनचर ( एमएन)।

स्वीकार्य बुनियादी समाधान युक्त एक समाधान है एमगैर नकारात्मक प्रमुख (बुनियादी ) चर और एन - एम गैर-प्रमुख ... (गैर-बुनियादी, या नि: शुल्क ) चर। मूल समाधान में छोटे चर शून्य के बराबर होते हैं, जबकि मुख्य चर, एक नियम के रूप में, गैर-शून्य होते हैं, अर्थात वे सकारात्मक संख्याएं होती हैं।

कोई भी एमसिस्टम चर एमके साथ रैखिक समीकरण एनचर कहलाते हैं मुख्य यदि उन पर गुणांकों का निर्धारक अशून्य है। फिर बाकी एन - एमचर कहलाते हैं गैर-प्रमुख (या नि: शुल्क ).

सिंप्लेक्स विधि एल्गोरिथ्म

• चरण 1... रैखिक प्रोग्रामिंग समस्या को विहित रूप में कम करें। ऐसा करने के लिए, मुक्त शर्तों को दाईं ओर स्थानांतरित करें (यदि इन मुक्त शर्तों में से नकारात्मक हैं, तो संबंधित समीकरण या असमानता को -1 से गुणा करें) और प्रत्येक बाधा में अतिरिक्त चर पेश करें (यदि मूल में प्लस चिह्न के साथ) असमानता का चिन्ह "से कम या उसके बराबर है, और ऋण चिह्न के साथ यदि" से बड़ा या बराबर ")।
• चरण 2... यदि प्राप्त प्रणाली में एमसमीकरण, तब एमचरों को मूल के रूप में लें, मूल चरों को गैर-बुनियादी के रूप में व्यक्त करें और संबंधित मूल समाधान खोजें। यदि पाया गया मूल समाधान स्वीकार्य हो जाता है, तो स्वीकार्य मूल समाधान पर जाएं।
• चरण 3... स्वीकार्य मूल समाधान के गैर-मूल चर के संदर्भ में लक्ष्य फ़ंक्शन को व्यक्त करें। यदि रैखिक रूप का अधिकतम (न्यूनतम) मांगा जाता है और इसकी अभिव्यक्ति में नकारात्मक (सकारात्मक) गुणांक वाले कोई मामूली चर नहीं हैं, तो इष्टतमता मानदंड पूरा हो गया है और प्राप्त मूल समाधान इष्टतम है - समाधान समाप्त हो गया है। यदि, रैखिक रूप का अधिकतम (न्यूनतम) ज्ञात करते समय, इसके व्यंजक में ऋणात्मक (सकारात्मक) गुणांक वाले एक या अधिक लघु चर शामिल हैं, तो एक नए मूल समाधान पर जाएँ।
• चरण 4... ऋणात्मक (सकारात्मक) गुणांकों के साथ रैखिक रूप में शामिल छोटे चरों में से, जो सबसे बड़े (निरपेक्ष मान में) गुणांक से मेल खाता है, उसे चुना जाता है और मूल में परिवर्तित किया जाता है। चरण 2 पर जाएं।

महत्वपूर्ण शर्तें

कुछ विशेष मामलों पर अलग-अलग लेखों में चर्चा की गई है: कब उद्देश्य फ़ंक्शन का अधिकतम अनंत है, कब सिस्टम का कोई समाधान नहीं है, और कब इष्टतम समाधान केवल एक ही नहीं है .

इसके बाद, आइए हम एक विशिष्ट उदाहरण का विश्लेषण करें, जब बाधाओं की प्रणाली संयुक्त होती है और अंतिम इष्टतम होता है, और केवल एक ही होता है। सिंप्लेक्स विधि का एक रूपांतर है परिवहन समस्या को हल करने के लिए वितरण विधि .

सिंप्लेक्स तालिकाओं के साथ सिंप्लेक्स विधि

बीजगणितीय परिवर्तनों का उपयोग करने की तुलना में सरल तालिकाओं का निर्माण करके रैखिक प्रोग्रामिंग समस्या को हल करना बहुत आसान है, जिसे अगले भाग में दिखाया गया है। सिंप्लेक्स टेबल बहुत वर्णनात्मक हैं। सिंप्लेक्स टेबल के साथ काम करने के लिए कई तरह के नियम हैं। हम उस पर एक नज़र डालेंगे जिसे आमतौर पर लीडिंग कॉलम और लीडिंग रो रूल कहा जाता है।

एक नई विंडो में मैन्युअल क्रियाओं को अंशों के साथ खोलना अतिश्योक्तिपूर्ण नहीं होगा: उनमें से पर्याप्त हैं, सरल विधि के लिए समस्याओं में अंश, इसे हल्के ढंग से रखने के लिए।

उदाहरण।

हम अतिरिक्त गैर-ऋणात्मक चर का परिचय देते हैं और असमानताओं की इस प्रणाली को समीकरणों की एक समान प्रणाली में कम करते हैं

.

यह निम्नलिखित नियम के अनुपालन में किया गया था: यदि मूल प्रतिबंध में चिह्न "कम या बराबर" है, तो अतिरिक्त चर जोड़ा जाना चाहिए, और यदि "अधिक या बराबर" है, तो अतिरिक्त चर घटाया जाना चाहिए।

पेश किए गए अतिरिक्त चर को मुख्य (मूल) के रूप में लिया जाता है। तब और गैर-मूल (मुक्त) चर हैं।

मुख्य (मूल) चरों को गैर-मूल (मुक्त) चरों के रूप में व्यक्त करने पर, हम प्राप्त करते हैं

हम लक्ष्य फलन को गैर-बुनियादी (मुक्त) चरों के रूप में भी व्यक्त कर सकते हैं:

चरों (अज्ञात) के गुणांकों से, हम पहली सिंप्लेक्स तालिका बनाते हैं।

तालिका की अंतिम पंक्ति, जिसमें लक्ष्य फ़ंक्शन और उसमें मुक्त चर के गुणांक शामिल हैं, को अनुक्रमणिका पंक्ति कहा जाएगा।

प्राप्त समाधान इष्टतम नहीं है, क्योंकि सूचकांक पंक्ति में मुक्त चर के गुणांक ऋणात्मक हैं। यानी इष्टतम समाधान वह होगा जिसमें सूचकांक पंक्ति में मुक्त चर के गुणांक शून्य से अधिक या उसके बराबर हों।

अगली तालिका में जाने के लिए, संख्याओं का सबसे बड़ा (मॉड्यूलो) ज्ञात कीजिए और। यह संख्या 2 है। इसलिए, प्रमुख स्तंभ वह स्तंभ है जिसमें यह लिखा है

अग्रणी पंक्ति को निर्धारित करने के लिए, हम मुक्त सदस्यों के अनुपात को प्रमुख कॉलम के तत्वों में न्यूनतम पाते हैं, और यदि अंश में एक सकारात्मक संख्या है, और हर नकारात्मक है, तो अनुपात को अनंत के बराबर माना जाता है।

.

इसलिए, अग्रणी पंक्ति वह है जिसमें यह लिखा है

इस प्रकार अग्रणी तत्व -2 है।

दूसरी सिम्प्लेक्स तालिका बनाएं।

हम पहली पंक्ति में एक नया मूल तत्व दर्ज करते हैं, और जिस कॉलम में यह खड़ा होता है, हम एक नया मुक्त चर दर्ज करते हैं

हम पहली पंक्ति भरते हैं। ऐसा करने के लिए, हम तालिका 1 की अग्रणी पंक्ति में सभी संख्याओं को धुरी तत्व से विभाजित करते हैं और उन्हें तालिका 2 की पहली पंक्ति के संगत कॉलम में लिखते हैं, केवल प्रमुख कॉलम में संख्या को छोड़कर, जहां धुरी के विपरीत तत्व लिखा है (अर्थात, प्रमुख तत्व द्वारा विभाजित इकाई)।

हम सहायक गुणांक के कॉलम में भरते हैं। तालिका 1 के प्रमुख कॉलम की इस संख्या के लिए, प्रमुख तत्व के अलावा, हम तालिका 2 के सहायक गुणांक के कॉलम में विपरीत संकेतों के साथ लिखते हैं।

जिन लोगों ने अभी तक एक नई विंडो में फ्रैक्शंस ट्यूटोरियल के साथ ऑपरेशन नहीं खोला है, वे इसे अभी कर सकते हैं, क्योंकि समय सही है।

तालिका 2 की शेष पंक्तियों को प्राप्त करने के लिए, इस तालिका की पहली पंक्ति में पहले से ही संख्याओं को भरने वाली पंक्ति में सहायक गुणांक से गुणा किया जाता है, और परिणाम के लिए हम तालिका 1 से संख्या को उसी पंक्ति में जोड़ते हैं। चर।

उदाहरण के लिए, दूसरी पंक्ति का मुक्त पद प्राप्त करने के लिए, हम संख्या 1 को 1 से गुणा करते हैं और तालिका 1 से संख्या -4 जोड़ते हैं। हमें -3 ​​मिलता है। दूसरी पंक्ति में गुणांक इसी तरह पाया जाता है: ... चूंकि पिछली तालिका में एक नए मुक्त चर के साथ एक स्तंभ नहीं है, एक नए मुक्त चर के स्तंभ में दूसरी पंक्ति का गुणांक होगा (अर्थात, तालिका 1 से हम 0 जोड़ते हैं, क्योंकि तालिका 1 में कोई स्तंभ c नहीं है)।

सूचकांक रेखा भी भरी जाती है:

इस तरह से प्राप्त समाधान फिर से इष्टतम नहीं है, क्योंकि सूचकांक पंक्ति में मुक्त चर के गुणांक फिर से नकारात्मक हैं।

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

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

.

इसलिए, अग्रणी रेखा वह है जिसमें यह लिखा गया है, और प्रमुख तत्व -3/2 है।

तीसरी सिंप्लेक्स तालिका बनाना

नई मूल चर पहली पंक्ति में लिखा गया है। जिस कॉलम में यह था, उसमें हम एक नया फ्री वेरिएबल दर्ज करते हैं।

पहली पंक्ति:

सहायक गुणांक:

प्राप्त समाधान फिर से इष्टतम नहीं है, क्योंकि सूचकांक पंक्ति में मुक्त अज्ञात के गुणांक फिर से नकारात्मक हैं।

चौथी सिंप्लेक्स तालिका में जाने के लिए, हम संख्याओं में से सबसे बड़ी और पाते हैं। यह संख्या है।

इसलिए, अग्रणी कॉलम वह है जिसमें यह लिखा गया है।

प्रमुख कॉलम के तत्वों के लिए मुक्त सदस्यों के संबंधों का न्यूनतम मॉड्यूल:

.

इसलिए, अग्रणी रेखा वह है जिसमें यह लिखा गया है, और अग्रणी तत्व 1/3 है।

चौथी सिंप्लेक्स तालिका में, पहली पंक्ति में नया मूल चर लिखा गया है। जिस कॉलम में यह था, उसमें हम एक नया फ्री वेरिएबल लिखते हैं।

पहली पंक्ति:

सहायक गुणांक:

दूसरी पंक्ति के उदाहरण का उपयोग करके शेष पंक्तियों की गणना:

प्राप्त समाधान भी इष्टतम नहीं है, लेकिन यह पिछले वाले की तुलना में पहले से बेहतर है, क्योंकि सूचकांक पंक्ति में मुक्त चर के गुणांक में से एक गैर-ऋणात्मक है।

योजना को बेहतर बनाने के लिए, आइए अगली सरल तालिका पर चलते हैं।

संख्या 4 और में से सबसे बड़ी खोजें। यह संख्या 4 है। इसलिए, प्रमुख स्तंभ।

अग्रणी लाइन खोजने के लिए, खोजें

.

इसलिए, अग्रणी पंक्ति वह है जिसमें यह लिखा गया है। लेकिन वे पहले से ही मुक्त चरों के बीच एक साथ थे। इसलिए, अगले चर को मुफ्त से मूल में स्थानांतरित करने के लिए, हम एक और प्रमुख कॉलम चुनते हैं - वह जिसमें यह लिखा गया है।

अग्रणी लाइन खोजने के लिए, खोजें

.

इसलिए, मुख्य पंक्ति वह है जिसमें यह लिखा गया है, और प्रमुख तत्व 1 है।

पाँचवीं सिंप्लेक्स तालिका में, हम पहली पंक्ति में नया मूल चर लिखते हैं। जिस कॉलम में यह था, उसमें हम एक नया फ्री वेरिएबल लिखते हैं।

पहली पंक्ति:

सहायक गुणांक:

आइए तुरंत पता लगाने की कोशिश करें कि क्या समाधान इष्टतम नहीं है। इसलिए, बाकी पंक्तियों के लिए, हम केवल मुक्त शर्तों की गणना करते हैं (मूल चर के मूल्यों का पता लगाने के लिए जब मुक्त चर शून्य के बराबर होते हैं) और सूचकांक पंक्ति में मुक्त चर के गुणांक।

मुक्त सदस्य:

दूसरी पंक्ति में;

तीसरी पंक्ति पर;

चौथी पंक्ति पर।

सूचकांक स्ट्रिंग:

हम सरल तालिका 5 को देखते हैं। हम देखते हैं कि इष्टतम समाधान प्राप्त किया गया है, क्योंकि सूचकांक पंक्ति में मुक्त अज्ञात के गुणांक गैर-ऋणात्मक हैं।

बीजगणितीय परिवर्तनों के साथ सिंप्लेक्स विधि

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

यदि रैखिक रूप का अधिकतम (न्यूनतम) मांगा जाता है और इसकी अभिव्यक्ति में सकारात्मक (नकारात्मक) गुणांक वाले कोई मामूली चर नहीं हैं, तो इष्टतमता मानदंड पूरा हो गया है और प्राप्त मूल समाधान इष्टतम है - समाधान समाप्त हो गया है। यदि, रैखिक रूप का अधिकतम (न्यूनतम) ज्ञात करते समय, इसके व्यंजक में धनात्मक (ऋणात्मक) गुणांकों वाले एक या अधिक लघु चर होते हैं, तो एक नए मूल समाधान पर जाएँ।

उदाहरण।बाधाओं के तहत अधिकतम फ़ंक्शन खोजें

चरण I। अतिरिक्त गैर-ऋणात्मक चर का परिचय दें और असमानताओं की इस प्रणाली को समीकरणों की एक समान प्रणाली में कम करें

.

पेश किए गए अतिरिक्त चर को मुख्य के रूप में लिया जाता है, क्योंकि इस मामले में सिस्टम का मूल समाधान आसानी से मिल सकता है। तब और मामूली चर हैं।

मुख्य चरों को गैर-मुख्य चरों के रूप में व्यक्त करने पर, हम प्राप्त करते हैं

नतीजतन, मूल और गैर-मूल में चर का दिया गया विभाजन मूल समाधान से मेल खाता है जो अमान्य है (दो चर ऋणात्मक हैं) और इसलिए इष्टतम नहीं है। आइए इस बुनियादी समाधान से बेहतर समाधान की ओर बढ़ते हैं।

यह तय करने के लिए कि किस चर को गैर-मूल से मूल में स्थानांतरित किया जाना चाहिए, नकारात्मक मुक्त शर्तों के साथ अंतिम प्रणाली के दो मौजूदा समीकरणों में से किसी पर विचार करें, उदाहरण के लिए, दूसरा। यह दर्शाता है कि अनुवाद करना और मुख्य चर में संभव है, क्योंकि इस समीकरण में उनके पास सकारात्मक गुणांक हैं (इसलिए, उनकी वृद्धि के साथ, और ऐसा होगा यदि हम उनमें से किसी को मुख्य चर में अनुवाद करते हैं, तो चर बढ़ जाएगा)।

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

उदाहरण 5.1.सिंप्लेक्स विधि का उपयोग करके निम्नलिखित रैखिक प्रोग्रामिंग समस्या को हल करें:

समाधान:

मैं पुनरावृत्ति:

x3, x4, x5, x6 x1,x2... आइए बुनियादी चरों को मुक्त चरों के रूप में व्यक्त करें:

आइए हम उद्देश्य फ़ंक्शन को निम्नलिखित रूप में लाते हैं:

प्राप्त समस्या के आधार पर, हम प्रारंभिक सिंप्लेक्स तालिका बनाएंगे:

तालिका 5.3

स्रोत सिंप्लेक्स तालिका

मूल समाधान की परिभाषा के अनुसार, मुक्त चर शून्य के बराबर होते हैं, और मूल चर के मान मुक्त संख्याओं के संगत मानों के बराबर होते हैं, अर्थात:

चरण 3: एलपीपी प्रतिबंध प्रणाली की अनुकूलता की जाँच करना।

इस पुनरावृत्ति पर (तालिका 5.3 में), प्रतिबंधों की प्रणाली (संकेत 1) की असंगति के संकेत का पता नहीं चला था (अर्थात, ऋणात्मक मुक्त संख्या के साथ कोई पंक्ति नहीं है (उद्देश्य फ़ंक्शन की रेखा को छोड़कर), जो करता है कम से कम एक ऋणात्मक तत्व न हो (अर्थात एक मुक्त चर पर ऋणात्मक गुणांक))।

इस पुनरावृत्ति पर (तालिका 5.3 में), उद्देश्य फ़ंक्शन (चिह्न 2) की असीमितता के संकेत की पहचान नहीं की गई थी (यानी, उद्देश्य फ़ंक्शन की पंक्ति में नकारात्मक तत्व वाला कोई कॉलम नहीं है (मुक्त के कॉलम को छोड़कर) संख्याएं), जिसमें कम से कम एक सकारात्मक तत्व नहीं है) ...

चूंकि पाए गए मूल समाधान में नकारात्मक घटक नहीं होते हैं, यह स्वीकार्य है।

चरण 6: इष्टतमता की जाँच करना।

पाया गया मूल समाधान इष्टतम नहीं है, क्योंकि, इष्टतमता मानदंड (फीचर 4) के अनुसार, उद्देश्य फ़ंक्शन की पंक्ति में कोई नकारात्मक तत्व नहीं होना चाहिए (इस सुविधा पर विचार करते समय इस लाइन की मुक्त संख्या को ध्यान में नहीं रखा जाता है) . इसलिए, सिंप्लेक्स विधि के एल्गोरिथ्म के अनुसार, हम 8 वें चरण में जाते हैं।

चूंकि पाया गया मूल समाधान स्वीकार्य है, समाधान कॉलम की खोज निम्न योजना के अनुसार की जाएगी: हम उद्देश्य फ़ंक्शन की पंक्ति में नकारात्मक तत्वों वाले कॉलम निर्धारित करते हैं (मुक्त संख्याओं के कॉलम को छोड़कर)। तालिका 5.3 के अनुसार, ऐसे दो स्तंभ हैं: स्तंभ " x1"और स्तंभ" x2". ऐसे कॉलम से, ऑब्जेक्टिव फंक्शन की लाइन में सबसे छोटा तत्व होता है, जिसे चुना जाता है। वह सुलझा रही होगी। वक्ता " x2"कॉलम की तुलना में सबसे छोटा तत्व (-3) शामिल है" x1

हल करने वाली रेखा को निर्धारित करने के लिए, हम अनुमति वाले कॉलम के तत्वों के लिए मुक्त संख्याओं के सकारात्मक अनुमानित अनुपात पाते हैं, जिस रेखा से सबसे छोटा सकारात्मक अनुमानित अनुपात मेल खाता है उसे अनुमति के रूप में लिया जाता है।

तालिका 5.4

स्रोत सिंप्लेक्स तालिका

तालिका 5.4 में, सबसे छोटा सकारात्मक अनुमानित अनुपात रेखा से मेल खाता है " x5”, इसलिए, यह हल हो जाएगा।

परमिटिंग कॉलम और परमिटिंग लाइन के चौराहे पर स्थित तत्व को परमिटिंग के रूप में स्वीकार किया जाता है। हमारे उदाहरण में, यह एक ऐसा तत्व है जो रेखा के चौराहे पर स्थित है " x5"और कॉलम" x2».

हल करने वाला तत्व एक मूल और एक मुक्त चर दिखाता है जिसे एक नए "बेहतर" मूल समाधान में जाने के लिए सरल तालिका में स्वैप किया जाना चाहिए। इस मामले में, ये चर हैं x5तथा x2, नई सिम्प्लेक्स तालिका (तालिका 5.5) में हम उन्हें स्वैप करते हैं।

9.1. संकल्प तत्व परिवर्तन।

तालिका 5.4 का अनुमेय तत्व इस प्रकार रूपांतरित होता है:

हम तालिका 5.5 में एक समान सेल में प्राप्त परिणाम दर्ज करते हैं।

9.2. संकल्प स्ट्रिंग कनवर्ट करना।

हम इस सिंप्लेक्स तालिका के समाधान तत्व द्वारा तालिका 5.4 की समाधान रेखा के तत्वों को विभाजित करते हैं, परिणाम नई सिंप्लेक्स तालिका (तालिका 5.5) के समान कोशिकाओं में फिट होते हैं। रिज़ॉल्यूशन लाइन के तत्वों के परिवर्तन तालिका 5.5 में दिए गए हैं।

9.3. संकल्प स्तंभ रूपांतरण।

तालिका 5.4 के हल करने वाले कॉलम के तत्वों को दी गई सरल तालिका के हल करने वाले तत्व से विभाजित किया जाता है, और परिणाम विपरीत चिह्न के साथ लिया जाता है। प्राप्त परिणाम नई सिंप्लेक्स तालिका (तालिका 5.5) की समान कोशिकाओं में फिट होते हैं। हल करने वाले कॉलम के तत्वों के परिवर्तन तालिका 5.5 में दिखाए गए हैं।

9.4. सिंप्लेक्स टेबल के बाकी तत्वों को कन्वर्ट करें।

सिंप्लेक्स तालिका के शेष तत्वों का परिवर्तन (अर्थात, समाधान रेखा और समाधान स्तंभ में स्थित तत्व नहीं) "आयत" नियम के अनुसार किया जाता है।

उदाहरण के लिए, स्ट्रिंग के चौराहे पर स्थित एक तत्व को बदलने पर विचार करें " x3"और कॉलम" ", हम पारंपरिक रूप से इसे इस रूप में नामित करेंगे" x3". तालिका 5.4 में, मानसिक रूप से एक आयत बनाएं, जिसका एक शीर्ष सेल में स्थित है, जिसका मूल्य हम बदलते हैं (अर्थात, सेल में " x3»), और दूसरा (विकर्ण शीर्ष) सेल में हल करने वाले तत्व के साथ है। अन्य दो शीर्ष (दूसरा विकर्ण) विशिष्ट रूप से निर्धारित होते हैं। तब सेल का रूपांतरित मान " x3"इस सेल के पिछले मान के बराबर होगा माइनस फ्रैक्शन, जिसके हर में एक सॉल्विंग एलिमेंट (तालिका 5.4 से) होता है, और अंश में दो अन्य अप्रयुक्त वर्टिस का उत्पाद होता है, अर्थात:

« x3»: .

अन्य कोशिकाओं के मान इसी तरह रूपांतरित होते हैं:

« x3 x1»: ;

« x4»: ;

« x4 x1»: ;

« x6»: ;

« x6 x1»: ;

«»: ;

« x1»: .

इन परिवर्तनों के परिणामस्वरूप, एक नई सिंप्लेक्स तालिका प्राप्त हुई (तालिका 5.5)।

द्वितीय पुनरावृत्ति:

चरण 1: एक सिंप्लेक्स टेबल बनाना।

तालिका 5.5

सिंप्लेक्स टेबलद्वितीय पुनरावृत्तियों

चरण 2: मूल समाधान का निर्धारण।

सिंप्लेक्स परिवर्तनों के परिणामस्वरूप, एक नया मूल समाधान प्राप्त हुआ (तालिका 5.5):

जैसा कि आप देख सकते हैं, इस मूल समाधान के लिए, उद्देश्य फलन का मान = 15, जो पिछले मूल समाधान से अधिक है।

तालिका 5.5 में विशेषता 1 के अनुसार प्रतिबंधों की प्रणाली की असंगति प्रकट नहीं हुई थी।

चरण 4: उद्देश्य समारोह की सीमितता की जाँच करना।

तालिका 5.5 में फीचर 2 के अनुसार उद्देश्य फ़ंक्शन की असीमितता प्रकट नहीं हुई थी।

चरण 5: मूल समाधान की स्वीकार्यता की जाँच करना।

फीचर 4 के अनुसार पाया गया मूल समाधान इष्टतम नहीं है, क्योंकि सिम्प्लेक्स टेबल (तालिका 5.5) के उद्देश्य फ़ंक्शन की रेखा में एक नकारात्मक तत्व होता है: -2 (इस पर विचार करते समय इस लाइन की मुक्त संख्या को ध्यान में नहीं रखा जाता है। विशेषता)। इसलिए, हम चरण 8 में जाते हैं।

चरण 8: समाधान करने वाले तत्व का निर्धारण।

8.1. संकल्प कॉलम की परिभाषा।

पाया गया मूल समाधान स्वीकार्य है, हम उद्देश्य फ़ंक्शन की पंक्ति में नकारात्मक तत्वों वाले कॉलम को परिभाषित करते हैं (मुक्त संख्याओं के कॉलम को छोड़कर)। तालिका 5.5 के अनुसार, केवल एक स्तंभ ही ऐसा स्तंभ है: " x1". इसलिए, हम इसे अनुमति के रूप में स्वीकार करते हैं।

8.2. अनुमति स्ट्रिंग का निर्धारण।

तालिका 5.6 में सकारात्मक मूल्यांकन अनुपात के प्राप्त मूल्यों के अनुसार, न्यूनतम रेखा के अनुरूप अनुपात है " x3". इसलिए, हम इसे अनुमति के रूप में स्वीकार करते हैं।

तालिका 5.6

सिंप्लेक्स टेबलद्वितीय पुनरावृत्तियों

चरण 9: सिंप्लेक्स तालिका का परिवर्तन।

सिम्प्लेक्स तालिका परिवर्तन (तालिका 5.6) उसी तरह से किए जाते हैं जैसे पिछले पुनरावृत्ति में। एक सिंप्लेक्स तालिका के तत्वों के परिवर्तन के परिणाम तालिका 5.7 में दिखाए गए हैं।

तृतीय यात्रा

पिछले पुनरावृत्ति के सिंप्लेक्स परिवर्तनों के परिणामों के आधार पर, हम एक नई सिंप्लेक्स तालिका बनाते हैं:

तालिका 5.7

सिंप्लेक्स टेबलतृतीय पुनरावृत्तियों

चरण 2: मूल समाधान का निर्धारण।

सिम्प्लेक्स परिवर्तनों के परिणामस्वरूप, एक नया मूल समाधान प्राप्त हुआ (तालिका 5.7):

चरण 3: बाधाओं की प्रणाली की स्थिरता की जाँच करना।

तालिका 5.7 में विशेषता 1 के अनुसार प्रतिबंधों की प्रणाली की असंगति प्रकट नहीं हुई थी।

चरण 4: उद्देश्य समारोह की सीमितता की जाँच करना।

तालिका 5.7 की विशेषता 2 के अनुसार उद्देश्य फलन की असीमता प्रकट नहीं हुई थी।

चरण 5: मूल समाधान की स्वीकार्यता की जाँच करना।

विशेषता 3 के अनुसार पाया गया मूल समाधान स्वीकार्य है, क्योंकि इसमें नकारात्मक घटक नहीं होते हैं।

चरण 6: पाए गए मूल समाधान की इष्टतमता की जाँच करना।

फीचर 4 के अनुसार पाया गया मूल समाधान इष्टतम नहीं है, क्योंकि सिम्प्लेक्स टेबल (तालिका 5.7) के उद्देश्य फ़ंक्शन की रेखा में एक नकारात्मक तत्व होता है: -3 (इस पर विचार करते समय इस लाइन की मुक्त संख्या को ध्यान में नहीं रखा जाता है) विशेषता)। इसलिए, हम चरण 8 में जाते हैं।

चरण 8: समाधान करने वाले तत्व का निर्धारण।

8.1. संकल्प कॉलम की परिभाषा।

पाया गया मूल समाधान स्वीकार्य है, हम उद्देश्य फ़ंक्शन की पंक्ति में नकारात्मक तत्वों वाले कॉलम को परिभाषित करते हैं (मुक्त संख्याओं के कॉलम को छोड़कर)। तालिका 5.7 के अनुसार, केवल एक स्तंभ ऐसा स्तंभ है: " x5". इसलिए, हम इसे अनुमति के रूप में स्वीकार करते हैं।

8.2. अनुमति स्ट्रिंग का निर्धारण।

तालिका 5.8 में सकारात्मक मूल्यांकन अनुपात के प्राप्त मूल्यों के अनुसार, न्यूनतम रेखा के अनुरूप अनुपात है " x4". इसलिए, हम इसे अनुमति के रूप में स्वीकार करते हैं।

तालिका 5.8

सिंप्लेक्स टेबलतृतीय पुनरावृत्तियों

चरण 9: सिंप्लेक्स तालिका का परिवर्तन।

सिम्प्लेक्स तालिका परिवर्तन (तालिका 5.8) उसी तरह से किए जाते हैं जैसे पिछले पुनरावृत्ति में। एक सिंप्लेक्स तालिका के तत्वों के परिवर्तन के परिणाम तालिका 5.9 में दिखाए गए हैं।

चतुर्थ यात्रा

चरण 1: एक नई सिंप्लेक्स तालिका बनाना।

पिछले पुनरावृत्ति के सिंप्लेक्स परिवर्तनों के परिणामों के आधार पर, हम एक नई सिंप्लेक्स तालिका बनाते हैं:

तालिका 5.9

सिंप्लेक्स टेबलचतुर्थ पुनरावृत्तियों

चरण 2: मूल समाधान का निर्धारण।

सिंप्लेक्स परिवर्तनों के परिणामस्वरूप, एक नया मूल समाधान प्राप्त किया गया था, तालिका 5.9 के अनुसार, समाधान इस प्रकार है:

चरण 3: बाधाओं की प्रणाली की स्थिरता की जाँच करना।

तालिका 5.9 में विशेषता 1 के अनुसार प्रतिबंधों की प्रणाली की असंगति का खुलासा नहीं किया गया था।

चरण 4: उद्देश्य समारोह की सीमितता की जाँच करना।

तालिका 5.9 में फीचर 2 के अनुसार उद्देश्य फ़ंक्शन की असीमता प्रकट नहीं हुई थी।

चरण 5: मूल समाधान की स्वीकार्यता की जाँच करना।

विशेषता 3 के अनुसार पाया गया मूल समाधान स्वीकार्य है, क्योंकि इसमें नकारात्मक घटक नहीं होते हैं।

चरण 6: पाए गए मूल समाधान की इष्टतमता की जाँच करना।

फीचर 4 के अनुसार पाया गया मूल समाधान इष्टतम है, क्योंकि सिम्प्लेक्स टेबल (तालिका 5.9) के उद्देश्य फ़ंक्शन की लाइन में कोई नकारात्मक तत्व नहीं हैं (इस सुविधा पर विचार करते समय इस लाइन की मुफ्त संख्या को ध्यान में नहीं रखा जाता है) .

चरण 7: समाधान के विकल्प की जाँच करना।

पाया गया समाधान केवल एक ही है, क्योंकि उद्देश्य फ़ंक्शन (तालिका 5.9) की पंक्ति में कोई शून्य तत्व नहीं हैं (इस सुविधा पर विचार करते समय इस पंक्ति की मुक्त संख्या को ध्यान में नहीं रखा जाता है)।

उत्तर: विचार की गई समस्या के उद्देश्य फ़ंक्शन का इष्टतम मूल्य = 24, जिसे प्राप्त किया जाता है।

उदाहरण 5.2.उपरोक्त रैखिक प्रोग्रामिंग समस्या को इस शर्त के तहत हल करें कि उद्देश्य फ़ंक्शन कम से कम हो:

समाधान:

मैं पुनरावृत्ति:

चरण 1: प्रारंभिक सिंप्लेक्स तालिका का निर्माण।

मूल रैखिक प्रोग्रामिंग समस्या एक मानक रूप में दी गई है। आइए हम असमानता बाधाओं में से प्रत्येक में एक अतिरिक्त गैर-ऋणात्मक चर पेश करके इसे इसके विहित रूप में लाएं, अर्थात।

समीकरणों की परिणामी प्रणाली में, हम अनुमत (मूल) चर के रूप में लेते हैं x3, x4, x5, x6, तो मुक्त चर होंगे x1,x2... आइए बुनियादी चरों को मुक्त चरों के रूप में व्यक्त करें।

अनुकूलन समस्याओं को हल करने के तरीकों में से एक ( आमतौर पर न्यूनतम या अधिकतम खोजने से जुड़ा होता है) रैखिक प्रोग्रामिंग कहा जाता है। सिंप्लेक्स विधिइसमें रैखिक प्रोग्रामिंग समस्याओं को हल करने के लिए एल्गोरिदम और विधियों का एक पूरा समूह शामिल है। प्रारंभिक डेटा की रिकॉर्डिंग और एक विशेष तालिका में उनके पुनर्गणना के लिए प्रदान करने वाली ऐसी विधियों में से एक को कहा जाता है सारणीबद्ध सिंप्लेक्स विधि.

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

सिंप्लेक्स विधि के लिए समस्या का प्रारंभिक डेटा

उद्यम 4 प्रकार के उत्पादों का उत्पादन करता है, उन्हें 3 मशीनों पर संसाधित करता है।

मैट्रिक्स ए द्वारा निर्धारित मशीनों पर उत्पादों के प्रसंस्करण के लिए समय दर (न्यूनतम/टुकड़ा।)

मशीन रनिंग टाइम फंड (मिनट) मैट्रिक्स बी में निर्दिष्ट है:

उत्पाद की प्रत्येक इकाई (रूबल / टुकड़ा) की बिक्री से लाभ मैट्रिक्स सी द्वारा दिया जाता है:

उत्पादन कार्य का उद्देश्य

एक उत्पादन योजना तैयार करें जिसमें उद्यम का लाभ अधिकतम होगा।

सारणीबद्ध सिंप्लेक्स विधि द्वारा समस्या का समाधान

(1) आइए X1, X2, X3, X4 को प्रत्येक प्रकार के उत्पादों की नियोजित मात्रा निर्दिष्ट करें। फिर वांछित योजना: ( एक्स1, एक्स2, एक्स3, एक्स4)

(2) आइए समीकरणों की एक प्रणाली के रूप में योजना की बाधाओं को लिखें:

(3) फिर लक्ष्य लाभ:

यानी उत्पादन योजना की पूर्ति से होने वाले लाभ को अधिकतम किया जाना चाहिए।

(4) एक सशर्त चरम के लिए परिणामी समस्या को हल करने के लिए, हम असमानताओं की प्रणाली को रैखिक समीकरणों की एक प्रणाली के साथ प्रतिस्थापित करते हैं, इसमें अतिरिक्त गैर-ऋणात्मक चर शामिल करते हैं ( एक्स5, एक्स6, एक्स7).

(5) आइए निम्नलिखित लें आधार योजना:

X1 = 0, X2 = 0, X3 = 0, X4 = 0, X5 = 252, X6 = 144, X7 = 80

(6) आइए डेटा दर्ज करें सिंप्लेक्स टेबल:

अंतिम पंक्ति में हम उद्देश्य फ़ंक्शन के गुणांक और इसके मान को विपरीत चिह्न के साथ दर्ज करते हैं;

(7) हम अंतिम पंक्ति में चयन करते हैं महानतम (सापेक्ष) एक ऋणात्मक संख्या।

आइए गणना करें b = N / Selected_Column_Elements

b के परिकलित मानों में से चुनें कम से कम.

चयनित कॉलम और पंक्ति का प्रतिच्छेदन हमें एक अनुमति देने वाला तत्व देगा। हम आधार को हल करने वाले तत्व के अनुरूप चर में बदलते हैं ( X5 से X1).

• समाधान करने वाला तत्व स्वयं 1 हो जाता है।
• हल करने वाली रेखा के तत्वों के लिए - a ij (*) = a ij / RE ( अर्थात्, प्रत्येक तत्व को हल करने वाले तत्व के मान से विभाजित किया जाता है और हमें नया डेटा मिलता है).
• अनुमेय स्तंभ तत्वों के लिए, उन्हें बस शून्य कर दिया जाता है।
• शेष तालिका तत्वों को आयत नियम के अनुसार पुनर्गणना किया जाता है।

एक आईजे (*) = एक आईजे - (ए * बी / आरई)

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

(9) अंतिम पंक्ति फिर से जांचें ( सी) पर ऋणात्मक संख्याओं की उपस्थिति... यदि वे नहीं हैं, तो इष्टतम योजना मिल गई है, हम समस्या को हल करने के अंतिम चरण में आगे बढ़ते हैं। यदि वहाँ है, तो योजना अभी तक इष्टतम नहीं है, और सिंप्लेक्स तालिका को फिर से पुनर्गणना करने की आवश्यकता है।

चूँकि हमारे पास अंतिम पंक्ति में फिर से ऋणात्मक संख्याएँ हैं, इसलिए हम गणनाओं की एक नई पुनरावृत्ति शुरू करते हैं।

(10) चूंकि अंतिम पंक्ति में कोई नकारात्मक तत्व नहीं हैं, इसका मतलब है कि हमें इष्टतम उत्पादन योजना मिल गई है! अर्थात्: हम उन उत्पादों का उत्पादन करेंगे जो "आधार" - X1 और X2 कॉलम में पारित हो गए हैं। हम उत्पादन की प्रत्येक इकाई के उत्पादन से होने वाले लाभ को जानते हैं ( मैट्रिक्स सी) यह उत्पादों 1 और 2 के उत्पादन की मात्रा को 1 टुकड़े से लाभ के साथ गुणा करने के लिए बनी हुई है, हमें अंतिम मिलता है ( ज्यादा से ज्यादा! ) किसी दी गई उत्पादन योजना के लिए लाभ।

उत्तर:

X1 = 32 पीसी।, X2 = 20 पीसी।, X3 = 0 पीसी।, X4 = 0 पीसी।

पी = 48 * 32 + 33 * 20 = 2 196 रूबल।

गल्याउतदीनोव आर.आर.

© सामग्री की प्रतिलिपि बनाने की अनुमति केवल तभी है जब के लिए कोई सीधा हाइपरलिंक हो

एलपी समस्याओं को हल करने की सार्वभौमिक विधि को सरल विधि कहा जाता है। इस पद्धति का अनुप्रयोग और इसका सबसे सामान्य संशोधन - द्वि-चरण सिंप्लेक्स विधि।

एलपी समस्याओं को हल करने के लिए ग्राफिकल विधि में, हमने वास्तव में असमानताओं की प्रणाली के समाधान के सेट की सीमा से संबंधित शिखरों के सेट से चुना है, जिस पर उद्देश्य फ़ंक्शन का मूल्य अधिकतम (न्यूनतम) तक पहुंच गया है। दो चर के मामले में, यह विधि पूरी तरह से दृश्य है और आपको समस्या का समाधान जल्दी से खोजने की अनुमति देती है।

यदि समस्या में तीन या अधिक चर हैं, और वास्तविक आर्थिक समस्याओं में ठीक यही स्थिति है, तो बाधाओं की प्रणाली के समाधान के क्षेत्र की कल्पना करना मुश्किल है। इस तरह के कार्यों का उपयोग करके हल किया जाता है सिंप्लेक्स विधि या क्रमिक सुधार की विधि द्वारा। विधि का विचार सरल है और इस प्रकार है।

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

आइए एक योजना तैयार करने की समस्या के एक विशिष्ट उदाहरण का उपयोग करके सरल विधि पर विचार करें।

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

आइए हम एक उत्पादन योजना की समस्या पर विचार करें, जिसने पहले एक मॉडल बनाया था और इसे एक विशेष रूप में घटाया था।

कार्य।

उत्पादों के निर्माण के लिए एतथा वीगोदाम कच्चे माल की 80 इकाइयों से अधिक नहीं जारी कर सकता है। इसके अलावा, उत्पाद के निर्माण के लिए एदो इकाइयों की खपत होती है, और उत्पाद वी- कच्चे माल की एक इकाई। उत्पादन की योजना बनाना आवश्यक है ताकि उत्पादों को सबसे बड़ा लाभ सुनिश्चित किया जा सके ए 50 से अधिक टुकड़े और उत्पाद बनाने की आवश्यकता नहीं है वी- 40 पीसी से अधिक नहीं। इसके अलावा, एक उत्पाद की बिक्री से लाभ ए- 5 रूबल, और से वी- 3 रूबल।

आइए हम एक गणितीय मॉडल की रचना करें, जो को निरूपित करता है एन एसयोजना में उत्पादों की 1 संख्या, के लिए एन एस 2 - उत्पादों की संख्या वी... तब प्रतिबंधों की प्रणाली इस तरह दिखेगी:

एक्स 1 50
एक्स 2 40
2x 1 + x 2 80
एक्स 1 0, एक्स 2 ≥0
5x 1 + 3x 2 → अधिकतम

आइए हम अतिरिक्त चर पेश करके समस्या को एक विहित रूप में लाते हैं:

एक्स 1 + एक्स 3 = 50
एक्स 2 + एक्स 4 = 40
2x 1 + x 2 + x 5 = 80
एक्स 1 0, एक्स 2 ≥0
5x 1 + 3x 2 → अधिकतम
-एफ = -5x 1 - 3x 2 → मिनट।

इस समस्या का एक विशेष रूप है (आधार के साथ, दाहिने हाथ गैर-ऋणात्मक हैं)। इसे सिंप्लेक्स विधि का उपयोग करके हल किया जा सकता है।

मैंमंच।एक सिंप्लेक्स टेबल पर एक कार्य लिखना। समस्या की बाधाओं की प्रणाली (3.10) और सिंप्लेक्स-टेबल के बीच एक-से-एक पत्राचार है। तालिका में जितनी पंक्तियाँ हैं, उतनी ही बाधा प्रणाली में समानताएँ हैं, और उतने ही स्तंभ हैं जितने मुक्त चर हैं। मूल चर पहले कॉलम को भरते हैं, मुक्त चर तालिका की शीर्ष पंक्ति को भरते हैं। नीचे की रेखा को सूचकांक रेखा कहा जाता है; इसमें उद्देश्य फ़ंक्शन में चर के गुणांक होते हैं। प्रारंभ में निचले दाएं कोने में 0 लिखा जाता है यदि फ़ंक्शन में कोई खाली शब्द नहीं है; अगर वहाँ है, तो हम इसे विपरीत चिन्ह के साथ लिखते हैं। इस स्थान पर (निचले दाएं कोने में) ऑब्जेक्टिव फंक्शन का मान होगा, जो एक टेबल से दूसरी टेबल पर जाने पर निरपेक्ष मान में बढ़ जाना चाहिए। इसलिए, प्रतिबंधों की हमारी प्रणाली तालिका 3.4 से मेल खाती है, और हम समाधान के द्वितीय चरण में आगे बढ़ सकते हैं।

तालिका 3.4

द्वितीयमंच... इष्टतमता के लिए समर्थन योजना की जाँच करना।

यह तालिका 3.4 निम्नलिखित आधार योजना से मेल खाती है:

(एन एस 1 , एन एस 2 , एन एस 3 , एन एस 4 , एन एस 5) = (0, 0, 50, 40, 80).

मुक्त चर एन एस 1 , एन एस 2 0 के बराबर हैं; एन एस 1 = 0, एन एस 2 = 0. और मूल चर एन एस 3 , एन एस 4 , एन एस 5 मूल्यों पर ले लो एन एस 3 = 50, एन एस 4 = 40, एन एस 5 = 80 - फ्री मेंबर्स कॉलम से। उद्देश्य फ़ंक्शन मान:

-एफ = - 5एन एस 1 - 3एन एस 2 = -5 0 - 3 0 = 0।

हमारा काम यह जांचना है कि दी गई बेसलाइन योजना इष्टतम है या नहीं। इसके लिए, आपको इंडेक्स लाइन - ऑब्जेक्टिव फंक्शन की लाइन देखने की जरूरत है एफ.

विभिन्न स्थितियां संभव हैं।

1. सूचकांक में एफ-स्ट्रिंग में कोई नकारात्मक तत्व नहीं है। इसका मतलब है कि योजना इष्टतम है, आप समस्या का समाधान लिख सकते हैं। उद्देश्य फलन अपने इष्टतम मान पर पहुंच गया है, जो निचले दाएं कोने में विपरीत चिह्न के साथ ली गई संख्या के बराबर है। हम IV चरण में जाते हैं।

2. अनुक्रमणिका पंक्ति में कम से कम एक ऋणात्मक तत्व होता है, जिसके स्तंभ में कोई धनात्मक तत्व नहीं होता है। तब हम यह निष्कर्ष निकालते हैं कि उद्देश्य फलन एफ→ अनिश्चित काल के लिए घटता है।

3. अनुक्रमणिका पंक्ति में एक ऋणात्मक अवयव होता है जिसके स्तंभ में कम से कम एक धनात्मक अवयव होता है। फिर हम अगले चरण III में जाते हैं। हम आधार रेखा में सुधार करते हुए तालिका का पुनर्गणना करते हैं।

तृतीयमंच... आधार रेखा में सुधार।

सूचकांक के नकारात्मक तत्वों से एफ-पंक्तियाँ मापांक में सबसे बड़ा चुनें, संबंधित कॉलम को हल करें और "" चिह्नित करें।

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

हमारे उदाहरण में, तत्व 2 अनुमेय है। इस तत्व से संबंधित रेखा को समाधान (सारणी 3.5) भी कहा जाता है।

तालिका 3.5

हल करने वाले तत्व को चुनने के बाद, हम नियमों के अनुसार तालिका की पुनर्गणना करते हैं:

1. पहले के समान आकार की नई तालिका में, हल करने वाली पंक्ति और स्तंभ के चर को स्वैप किया जाता है, जो एक नए आधार पर संक्रमण के अनुरूप होता है। हमारे उदाहरण में: एन एस 1 के बजाय, आधार में शामिल किया गया है एन एस 5, जो आधार छोड़ देता है और अब मुफ़्त है (सारणी 3.6)।

तालिका 3.6

2. हल करने वाले तत्व 2 के स्थान पर इसकी प्रतिलोम संख्या ½ लिखिए।

3. समाधान करने वाली रेखा के तत्वों को हल करने वाले तत्व से विभाजित किया जाता है।

4. समाधान करने वाले स्तंभ के तत्वों को हल करने वाले तत्व से विभाजित किया जाता है और विपरीत चिह्न के साथ लिखा जाता है।

5. तालिका 3.6 के शेष तत्वों को भरने के लिए, हम आयत नियम के अनुसार पुनर्गणना करते हैं। मान लीजिए कि हम तत्व को 50 की स्थिति में गिनना चाहते हैं।

हम इस तत्व को मानसिक रूप से हल करने वाले के साथ जोड़ते हैं, उत्पाद ढूंढते हैं, परिणामी आयत के दूसरे विकर्ण पर स्थित तत्वों के उत्पाद को घटाते हैं। हम अंतर को हल करने वाले तत्व से विभाजित करते हैं।

इसलिए, । हम उस स्थान पर 10 लिखते हैं जहां 50 था। इसी प्रकार:
, , , .

तालिका 3.7

हमारे पास एक नई तालिका 3.7 है, मूल चर अब चर हैं (x 3, x 4, x 1)। ऑब्जेक्टिव फंक्शन वैल्यू -200 के बराबर हो गई, यानी। घट गया। इष्टतमता के लिए इस मूल समाधान की जाँच करने के लिए, चरण II में फिर से जाना आवश्यक है। प्रक्रिया स्पष्ट रूप से सीमित है, रोक मानदंड द्वितीय चरण के बिंदु 1 और 2 हैं।

हम समस्या के समाधान को अंत तक लेकर आएंगे। ऐसा करने के लिए, सूचकांक पंक्ति की जांच करें और इसमें एक नकारात्मक तत्व -½ को देखते हुए, संबंधित कॉलम को हल करने के लिए कॉल करें और चरण III के अनुसार, तालिका को पुनर्गणना करें। संबंधों को संकलित करने और उनमें से न्यूनतम = 40 चुनने के बाद, हमने संकल्प तत्व 1 निर्धारित किया है। अब हम नियम 2-5 के अनुसार पुनर्गणना करते हैं।

तालिका 3.8

तालिका को पुनर्गणना करने के बाद, हम सुनिश्चित करते हैं कि सूचकांक पंक्ति में कोई नकारात्मक तत्व नहीं हैं, इसलिए समस्या हल हो गई है, आधार योजना इष्टतम है।

चतुर्थमंच... इष्टतम समाधान लिखना।

यदि चरण II के बिंदु 1 के अनुसार सिंप्लेक्स विधि बंद हो जाती है, तो समस्या का समाधान निम्नानुसार लिखा जाता है। मूल चर क्रमशः मुक्त सदस्य कॉलम के मूल्यों को लेते हैं। हमारे उदाहरण में एन एस 3 = 30, एन एस 2 = 40, एन एस 1 = 20. मुक्त चर 0 हैं, एन एस 5 = 0, एन एस 4 = 0. ऑब्जेक्टिव फंक्शन विपरीत चिन्ह वाले मुक्त सदस्यों के कॉलम के अंतिम तत्व का मान लेता है: - एफ = -220 → एफ= 220, हमारे उदाहरण में फ़ंक्शन की जांच न्यूनतम के लिए की गई थी, और प्रारंभ में एफ→ अधिकतम, तो संकेत वास्तव में दो बार बदल गया। इसलिए, एन एस* = (20, 40, 30, 0, 0), एफ* = 220. समस्या का उत्तर:

रिलीज़ योजना में इस प्रकार के 20 उत्पादों को शामिल करना आवश्यक है ए, बी प्रकार के 40 उत्पाद, जबकि लाभ अधिकतम होगा और 220 रूबल के बराबर होगा।

इस खंड के अंत में, हम सिम्प्लेक्स विधि एल्गोरिथ्म का एक ब्लॉक आरेख प्रस्तुत करते हैं, जो बिल्कुल चरणों को दोहराता है, लेकिन, शायद, कुछ पाठकों के लिए इसका उपयोग करना अधिक सुविधाजनक होगा, क्योंकि तीर कार्रवाई की स्पष्ट दिशा का संकेत देते हैं।

फ़्लोचार्ट में बक्सों के ऊपर के लिंक दिखाते हैं कि संबंधित परिवर्तन समूह किस चरण या उपखंड से संबंधित है। प्रारंभिक आधारभूत योजना खोजने का नियम खंड 3.7 में तैयार किया जाएगा।

एक उदाहरण। सरल विधि का उपयोग करके निम्नलिखित एलपी समस्या को विहित रूप में हल करें।
f (x) = x 1 + 9x 2 + 5x 3 + 3x 4 + 4x 5 + 14x 6 → मिनट
एक्स 1 + एक्स 4 = 20
एक्स 2 + एक्स 5 = 50
एक्स 3 + एक्स 6 = 30
x 4 + x 5 + x 6 = 60
एक्स मैं 0, मैं = 1, ..., 6
वे कहते हैं कि एक एलपी समस्या का एक विहित रूप होता है यदि सभी बाधाओं (चर की गैर-नकारात्मकता की शर्तों को छोड़कर) में समानता का रूप होता है, और सभी मुक्त शर्तें गैर-ऋणात्मक होती हैं। इसलिए हमें विहित रूप में समस्या है।
सिंप्लेक्स विधि के पीछे का विचार इस प्रकार है। सबसे पहले, आपको व्यवहार्य समाधान (प्रारंभिक व्यवहार्य मूल समाधान) के पॉलीहेड्रॉन के कुछ (प्रारंभिक) शीर्ष खोजने की आवश्यकता है। फिर आपको इष्टतमता के लिए इस समाधान की जांच करने की आवश्यकता है। यदि यह इष्टतम है, तो समाधान मिल गया है; यदि नहीं, तो पॉलीटॉप के दूसरे शीर्ष पर जाएं और फिर से इष्टतमता की जांच करें। "चरणों" की एक सीमित संख्या में पॉलीहेड्रॉन (एलपी समस्या की बाधाओं की परिमितता का परिणाम) के शिखर की सूक्ष्मता को देखते हुए हम आवश्यक न्यूनतम या अधिकतम बिंदु पाएंगे। यह ध्यान दिया जाना चाहिए कि जब एक शीर्ष से दूसरे शीर्ष पर जाते हैं, तो उद्देश्य फ़ंक्शन का मान घटता है (न्यूनतम के लिए समस्या में) या बढ़ता है (अधिकतम के लिए समस्या में)।
इस प्रकार, सिंप्लेक्स पद्धति का विचार एलपी समस्या के तीन गुणों पर आधारित है।
समाधान।प्रारंभिक व्यवहार्य मूल समाधान खोजने के लिए, अर्थात। बुनियादी चर निर्धारित करने के लिए, सिस्टम (5.6) को "विकर्ण" रूप में कम किया जाना चाहिए। गॉस विधि (अज्ञात के क्रमिक उन्मूलन की विधि) को लागू करने पर, हम (5.6) से प्राप्त करते हैं:
एक्स 2 + एक्स 1 + एक्स 3 = 40
एक्स 4 + एक्स 1 = 20
x 5 -x 1 -x 3 = 10
x 6 + x 3 = 30
इसलिए, मूल चर हैं एक्स 2, एक्स 4, एक्स 5, एक्स 6,हम उन्हें संबंधित स्ट्रिंग्स के मुक्त सदस्यों के बराबर मान प्रदान करते हैं: x 2 = 40, x 4 = 20, x 5 = 10, x 6 = 30,... चर एक्स 1तथा एक्स 3गैर-बुनियादी हैं: एक्स 1 = 0, एक्स 3 = 0.
आइए हम प्रारंभिक स्वीकार्य मूल समाधान का निर्माण करें
एक्स 0 = (0,40,0,20,10,30) (5.9)
पाए गए समाधान की इष्टतमता की जांच करने के लिए एक्स 0उद्देश्य फ़ंक्शन (सिस्टम (5.8) का उपयोग करके) से बुनियादी चर को बाहर करना और एक विशेष सरल तालिका का निर्माण करना आवश्यक है।
चरों को समाप्त करने के बाद, उद्देश्य फलन को आसानी से इस प्रकार लिखा जा सकता है:
एफ (एक्स) = -7x 1 - 14x 3 +880 (5.10)
अब, (5.8) - (5.10) का उपयोग करके, हम एक प्रारंभिक सरल तालिका बनाते हैं:

शून्य रेखा में उद्देश्य फ़ंक्शन के लिए संबंधित चर के विपरीत चिह्न वाले गुणांक होते हैं। इष्टतमता मानदंड (न्यूनतम खोजने की समस्या के लिए): स्वीकार्य मूल समाधान ( एक्स 0) इष्टतम है यदि शून्य रेखा में एक भी सख्ती से सकारात्मक संख्या नहीं है (उद्देश्य समारोह के मूल्य की गणना नहीं करना (880))। यह नियम निम्नलिखित पुनरावृत्तियों (तालिकाओं) पर भी लागू होता है। शून्य पंक्ति के तत्वों को कॉलम अनुमान कहा जाएगा।
तो प्रारंभिक स्वीकार्य मूल समाधान (5.9) इष्टतम नहीं है: 7>0, 14>0 .
शून्य कॉलम में मूल चर के मान होते हैं। वे गैर-ऋणात्मक होने चाहिए (समीकरण देखें (5.7))। पहली से चौथी पंक्तियों तक, सिस्टम से चर के गुणांक (5.8) लिखे गए हैं।
चूंकि एक्स 0इष्टतम नहीं है, तो आपको व्यवहार्य समाधानों के पॉलीहेड्रॉन के दूसरे शीर्ष पर जाने की आवश्यकता है (एक नया बीडी बनाएं)। ऐसा करने के लिए, आपको धुरी खोजने और एक निश्चित परिवर्तन (सरल परिवर्तन) करने की आवश्यकता है।
सबसे पहले, हम तालिका के अग्रणी तत्व को पाते हैं, जो अग्रणी कॉलम (उच्चतम सकारात्मक स्कोर वाला कॉलम) और अग्रणी पंक्ति (शून्य कॉलम के तत्वों के न्यूनतम अनुपात के अनुरूप पंक्ति) के चौराहे पर खड़ा होता है। प्रमुख कॉलम के संगत तत्व (सख्ती से सकारात्मक)।
तालिका 1 में, अग्रणी स्तंभ तीसरा स्तंभ है और अग्रणी पंक्ति चौथी पंक्ति है। (मिनट (40 / 1.30 / 1) = 30/1)तीरों द्वारा इंगित किया जाता है, और प्रमुख तत्व एक वृत्त द्वारा इंगित किया जाता है। मेजबान इंगित करता है कि अंतर्निहित चर एक्स 6एक गैर-मूल के साथ प्रतिस्थापित करने की आवश्यकता है एक्स 3... तब नए बुनियादी चर होंगे एक्स 2, एक्स 3, एक्स 4, एक्स 5,, और गैर-बुनियादी वाले - एक्स 1, एक्स 6,... इसका अर्थ है व्यवहार्य समाधानों के पॉलीहेड्रॉन के एक नए शीर्ष पर संक्रमण। नए व्यवहार्य बुनियादी समाधान के समन्वय मूल्यों को खोजने के लिए एक्स 00आपको एक नई सिंप्लेक्स तालिका बनाने और उसमें प्राथमिक परिवर्तन करने की आवश्यकता है:
ए)अग्रणी लाइन के सभी तत्वों को अग्रणी तत्व से विभाजित करें, जिससे अग्रणी तत्व को 1 में बदल दिया जाए (गणना की सादगी के लिए);
बी)अग्रणी तत्व (1 के बराबर) का उपयोग करके, अग्रणी कॉलम के सभी तत्वों को शून्य में बदल दें (अज्ञात को समाप्त करने की विधि के समान);
नतीजतन, शून्य कॉलम में, नए बुनियादी चर के मान प्राप्त होते हैं एक्स 2, एक्स 3, एक्स 4, एक्स 5,(तालिका 2 देखें) - नए शीर्ष के मूल घटक एक्स 00(गैर-मूल घटक एक्स 1 = 0, एक्स 6 = 0,).

जैसा कि तालिका 2 से पता चलता है, नया बुनियादी समाधान एक्स 00 = (0.10,30,20,40,0)गैर-इष्टतम (शून्य रेखा का गैर-ऋणात्मक स्कोर 7 है)। इसलिए, धुरी तत्व 1 (तालिका 2 देखें) के साथ, हम एक नई सिंप्लेक्स तालिका बनाते हैं, अर्थात। एक नए व्यवहार्य बुनियादी समाधान का निर्माण

तालिका 3 स्वीकार्य मूल समाधान से मेल खाती है एक्स 000 = (10,0,30,10,50,0)और यह इष्टतम है, क्योंकि शून्य रेखा में कोई सकारात्मक रेटिंग नहीं है। इसीलिए एफ (एक्स 000) = 390उद्देश्य समारोह का न्यूनतम मूल्य है।
उत्तर: x 000 = (10, 0, 30, 10, 50, 0)- न्यूनतम बिंदु, एफ (एक्स 000) = 390.

सशर्त रूप से मानक रैखिक प्रोग्रामिंग समस्या

1. प्रत्यक्ष समस्या के लिए इष्टतम योजना खोजें:
   ए) ग्राफिकल विधि;
   बी) सरल विधि (प्रारंभिक संदर्भ योजना के निर्माण के लिए कृत्रिम आधार विधि का उपयोग करने की अनुशंसा की जाती है)।
2. एक दोहरी समस्या का निर्माण करें।
3. पूरक सुस्त स्थितियों का उपयोग करते हुए सीधी रेखा के चित्रमय समाधान से दोहरी समस्या की इष्टतम योजना खोजें।
4. प्रत्यक्ष समस्या को हल करके प्राप्त अंतिम सिंप्लेक्स तालिका का उपयोग करके, पहले द्वैत प्रमेय द्वारा दोहरी समस्या के लिए इष्टतम योजना खोजें (आइटम 1 बी देखें)। कथन की जाँच करें "दोहरी समस्याओं की एक जोड़ी के उद्देश्य कार्यों के मूल्य उनके इष्टतम समाधानों पर मेल खाते हैं"।
5. द्वैध समस्या को सिंप्लेक्स विधि द्वारा हल करें, फिर, दोहरी समस्या की अंतिम सरल तालिका का उपयोग करके, पहले द्वैत प्रमेय के अनुसार प्रत्यक्ष समस्या की इष्टतम योजना खोजें। परिणाम की तुलना उस परिणाम से करें जो चित्रमय विधि द्वारा प्राप्त किया गया था (आइटम 1क देखें)।
6. इष्टतम पूर्णांक समाधान खोजें:
   ए) ग्राफिकल विधि;
   b) गोमोरी विधि द्वारा।
   पूर्णांक और गैर-पूर्णांक समाधान के कार्यों के मूल्यों की तुलना करें

आत्म-नियंत्रण के लिए प्रश्न

1. सिंप्लेक्स टेबल कैसे बनाया जाता है?
2. तालिका में आधार परिवर्तन कैसे परिलक्षित होता है?
3. सिंप्लेक्स विधि के लिए एक रोक मानदंड तैयार करें।
4. तालिका पुनर्गणना कैसे व्यवस्थित करें?
5. किस पंक्ति से तालिका का पुनर्गणना प्रारंभ करना सुविधाजनक है?

संक्षिप्त सिद्धांत

समस्या का समाधान

मॉडल का निर्माण

क्रमशः पहले, दूसरे और तीसरे प्रकार के सामानों के कारोबार को निरूपित करें।

तब लाभ को व्यक्त करने वाला उद्देश्य फलन है:

सामग्री और मौद्रिक संसाधनों पर प्रतिबंध:

इसके अलावा, समस्या के अर्थ के भीतर

हमें निम्नलिखित रैखिक प्रोग्रामिंग समस्या मिलती है:

हम 0 वें पुनरावृत्ति की सरल तालिका में भरते हैं।

चूंकि हम अधिकतम समस्या को हल करते हैं, इसलिए अधिकतम समस्या को हल करते समय सूचकांक पंक्ति में ऋणात्मक संख्याओं की उपस्थिति इंगित करती है कि हमने एक इष्टतम समाधान प्राप्त नहीं किया है और यह आवश्यक है कि 0 वीं पुनरावृत्ति की तालिका से अगले तक जाना आवश्यक हो।

अगले पुनरावृत्ति के लिए संक्रमण निम्नानुसार किया जाता है:

प्रमुख कॉलम मेल खाता है।

मुख्य पंक्ति मुक्त सदस्यों और प्रमुख कॉलम के सदस्यों के न्यूनतम अनुपात (सरल संबंध) द्वारा निर्धारित की जाती है:

कुंजी कॉलम और कुंजी पंक्ति के चौराहे पर, हम हल करने वाले तत्व को ढूंढते हैं, अर्थात 7.

अब आइए पहली पुनरावृत्ति को संकलित करना शुरू करें। एक इकाई सदिश के बजाय, हम एक सदिश का परिचय देते हैं।

नई तालिका में, हल करने वाले तत्व के स्थान पर, 1 लिखें, कुंजी कॉलम के अन्य सभी तत्व शून्य हैं। मुख्य लाइन तत्वों को अनुमति देने वाले तत्व में विभाजित किया गया है। तालिका के अन्य सभी तत्वों की गणना आयत नियम के अनुसार की जाती है।

हमें पहली पुनरावृत्ति की तालिका मिलती है:

पहले पुनरावृत्ति मिलान के लिए कुंजी कॉलम।

हम कुंजी स्ट्रिंग पाते हैं, इसके लिए हम परिभाषित करते हैं:

कुंजी कॉलम और कुंजी लाइन के चौराहे पर, हम हल करने वाले तत्व को ढूंढते हैं, यानी। 31/7.

वेक्टर को आधार से घटाया जाता है और वेक्टर पेश किया जाता है।

हमें दूसरी पुनरावृत्ति की तालिका मिलती है:

अनुक्रमणिका पंक्ति में सभी पद ऋणात्मक नहीं हैं, इसलिए रैखिक प्रोग्रामिंग समस्या का निम्नलिखित समाधान प्राप्त होता है (हम इसे मुक्त पदों के कॉलम से लिखते हैं):

इस प्रकार, 7.1 हजार रूबल बेचना आवश्यक है। 1 प्रकार का माल और 45.2 हजार रूबल। तीसरे प्रकार का माल। दूसरे प्रकार के सामान को बेचना लाभहीन है। इस मामले में, लाभ अधिकतम और राशि 237.4 हजार रूबल होगी। इष्टतम योजना के कार्यान्वयन के साथ, तीसरे प्रकार के संसाधन के शेष 701 इकाइयां होंगे।

यदि आपको अभी मदद की आवश्यकता नहीं है, लेकिन भविष्य में इसकी आवश्यकता हो सकती है, तो संपर्क न खोने के लिए,