सिंप्लेक्स विधि का विस्तृत विश्लेषण

प्रस्तावना

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

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

§1। रैखिक प्रोग्रामिंग समस्या का बयान

परिभाषा: रैखिक प्रोग्रामिंग एक गणितीय अनुशासन है जो रैखिक समीकरणों और असमानताओं की प्रणालियों द्वारा परिभाषित n-आयामी अंतरिक्ष के सेट पर चरम समस्याओं को हल करने के सिद्धांत और तरीकों के लिए समर्पित है।

रैखिक प्रोग्रामिंग का सामान्य कार्य (इसके बाद - एलपी) का रूप है:

§2। एलपी समस्या का विहित रूप

एलपी समस्या का विहित रूप:



नोट: एलपी की कोई भी समस्या कैनोनिकल को कम करती है।

विहित एल.पी. समस्या से विहित रूप में संक्रमण के लिए एल्गोरिथ्म:

1. नकारात्मक के साथ असमानता$$ $ इनलाइन $ b_i $ इनलाइन $ (-1) से गुणा करें।
2. यदि फॉर्म की असमानता (in) है, तो बाईं ओर जोड़ें$$ $ इनलाइन $ s_i $ इनलाइन $ एक अतिरिक्त चर है, और हम समानता प्राप्त करते हैं।
3. यदि फॉर्म की असमानता (in) है, तो बाईं ओर से घटाएं$$ $ इनलाइन $ s_i $ इनलाइन $ , और हम समानता प्राप्त करते हैं।
4. हम चरों का प्रतिस्थापन करते हैं:

• अगर$$ $ इनलाइन $ x_i ≤ 0 $ इनलाइन $ तो$$ $ इनलाइन $ x_i '= -x_i in 0 $ इनलाइन $
• अगर$$ $ इनलाइन $ x_i $ इनलाइन $ - कोई भी$$ $ इनलाइन $ x_i = x_i '- x_i' '$ इनलाइन $ जहाँ$$ $ इनलाइन $ x_i ', x_i'' $ 0 $ इनलाइन $

नोट: हम नंबर देंगे$$ $ इनलाइन $ s_i $ इनलाइन $ असमानता संख्या के हिसाब से हमने इसे जोड़ा।

टिप्पणी:$$ $ इनलाइन $ s_i $ इनलाइन $ ≥0।

§3। कॉर्नर पॉइंट्स। बुनियादी / मुफ्त चर। मूल समाधान

परिभाषा: बिंदु$$ $ इनलाइन $ X $ D $ इनलाइन $ एक कोने बिंदु कहा जाता है अगर प्रतिनिधित्व$$ $ इनलाइन $ X = αX ^ 1 + (1-α) X ^ 2, जहां X ^ 1, X ^ 2 ^ D; 0 <α <1 $ इनलाइन $ के साथ ही संभव है$$ $ इनलाइन $ X ^ 1 = X ^ 2 $ इनलाइन $ ।

दूसरे शब्दों में, इस क्षेत्र में दो बिंदुओं को खोजना असंभव है, जिसमें से गुजरने वाला अंतराल शामिल है$$ $ इनलाइन $ X $ इनलाइन $ (Ie$$ $ इनलाइन $ X $ इनलाइन $ एक आंतरिक बिंदु नहीं है)।

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

परिभाषा: चलो m समीकरणों और n अज्ञात (m <n) की एक प्रणाली हो। हम चर को दो सेटों में विभाजित करते हैं: (एनएम) हम चर को शून्य के बराबर सेट करते हैं, और शेष एम चर प्रारंभिक समीकरणों की प्रणाली को हल करके निर्धारित किए जाते हैं। यदि यह समाधान अद्वितीय है, तो नॉनज़रो एम चर को बुनियादी कहा जाता है; शून्य (एनएम) चर - मुक्त (गैर-मूल), और चर के संगत परिणामी मूल्य को मूल समाधान कहा जाता है।

§4। सिंप्लेक्स विधि

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

सिंप्लेक्स विधि को लागू करने के लिए आवश्यक शर्तें:

1. कार्य का एक विहित रूप होना चाहिए।
2. कार्य का एक स्पष्ट आधार होना चाहिए।

परिभाषा: स्पष्ट रूप से चयनित आधार फॉर्म का एक वेक्टर है:$$ $ इनलाइन $ (.. 0100 ..) ^ टी, (..010 ..) ^ टी, (.. 0010 ..) ^ टी ... $ इनलाइन $ , यानी। वेक्टर का केवल एक समन्वय नॉनजरो है और 1 के बराबर है।

नोट: आधार सदिश का आयाम (m * 1) है, जहाँ m समष्टि प्रणाली में समीकरणों की संख्या है।

गणना और विज़ुअलाइज़ेशन की सुविधा के लिए, सिम्प्लेक्स टेबल आमतौर पर उपयोग किए जाते हैं:

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

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

नोट: यदि मूल समस्या में बाधाओं को फार्म ≤ की असमानताओं द्वारा दर्शाया जाता है, तो जब समस्या को विहित रूप में कम किया जाता है, तो प्रस्तुत अतिरिक्त चर प्रारंभिक मूल समाधान बनाते हैं।

नोट: कार्यात्मक रेखा में गुणांक "-" चिह्न के साथ लिया जाता है।

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

1. एक चर चुनें जिसे हम आधार में पेश करेंगे। यह पहले दर्शाए गए सिद्धांत के अनुसार किया जाता है: हमें एक चर का चयन करना चाहिए जिसकी वृद्धि कार्यात्मक में वृद्धि का कारण बनेगी। चयन निम्नलिखित नियम के अनुसार किया जाता है:

• यदि कार्य न्यूनतम है, तो अंतिम पंक्ति में अधिकतम सकारात्मक तत्व चुनें।
• यदि कार्य अधिकतम है, तो न्यूनतम नकारात्मक चुनें।

इस तरह की पसंद, वास्तव में, ऊपर उल्लिखित सिद्धांत से मेल खाती है: यदि कार्य कम से कम है, तो हम जितनी बड़ी संख्या घटाते हैं, उतनी तेजी से कार्यात्मक घट जाती है; अधिकतम के लिए, इसके विपरीत - बड़ी संख्या को जोड़ा जाता है, तेजी से कार्यात्मक बढ़ता है।

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

परिभाषा: चयनित गुणांक के अनुरूप एक साधारण तालिका के एक स्तंभ को एक अग्रणी स्तंभ कहा जाता है।

2. एक चर चुनें जिसे हम आधार में पेश करेंगे। ऐसा करने के लिए, आपको यह निर्धारित करने की आवश्यकता है कि नया आधार चर बढ़ने पर कौन से आधार चर गायब होने की संभावना है। बीजगणितीय रूप से, यह निम्नानुसार किया जाता है:

• दाएं हाथ के भागों के वेक्टर को समापन कॉलम द्वारा विभाजित किया गया है
• प्राप्त मूल्यों के बीच न्यूनतम सकारात्मक चुनें (नकारात्मक और शून्य जवाब नहीं माना जाता है)

परिभाषा: इस तरह की रेखा को एक अग्रणी रेखा कहा जाता है और आधार से व्युत्पन्न होने के लिए एक चर से मेल खाती है।

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

3. हम अग्रणी पंक्ति और स्तंभ के चौराहे पर खड़े एक तत्व की तलाश कर रहे हैं।

परिभाषा: ऐसे तत्व को एक अग्रणी तत्व कहा जाता है।

4. पहले कॉलम में (बेस वेरिएबल्स के नाम के साथ) बाहर किए जाने वाले वेरिएबल के बजाय, उस वेरिएबल का नाम लिखें, जिसे हम आधार में दर्ज करते हैं।

5. इसके बाद, एक नए बुनियादी समाधान की गणना की प्रक्रिया शुरू होती है। यह जॉर्डन-गॉस विधि का उपयोग करके होता है।

• नई लीड लाइन = पुरानी लीड लाइन / लीड
• नई पंक्ति = नई पंक्ति - अग्रणी कॉलम में पंक्ति कारक * नई अग्रणी पंक्ति

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

6. उसके बाद, हम इष्टतम स्थिति की जांच करते हैं। यदि परिणामस्वरूप समाधान इष्टतम नहीं है, तो पूरी प्रक्रिया को फिर से दोहराएं।

§5। सिंप्लेक्स विधि के परिणाम की व्याख्या

1. आपाधापी

परिणामी समाधान के लिए इष्टतम स्थिति:

• यदि कार्य अधिकतम है, तो कार्यात्मक पंक्ति में कोई नकारात्मक गुणांक नहीं हैं (यानी, चर में किसी भी परिवर्तन के साथ, परिणामी कार्यात्मक का मूल्य नहीं बढ़ेगा)।
• यदि कार्य न्यूनतम है, तो कार्यात्मक पंक्ति में कोई सकारात्मक गुणांक नहीं हैं (यानी, चर में किसी भी परिवर्तन के साथ, परिणामी कार्यात्मक के मूल्य में कमी नहीं होगी)।

2. असीमित कार्यक्षमता

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

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

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

3. वैकल्पिक समाधान

इष्टतम समाधान खोजने पर, एक और विकल्प संभव है - वैकल्पिक समाधान हैं (एक अन्य कोने बिंदु जो कार्यात्मक का समान मूल्य देता है)।

एक विकल्प के अस्तित्व का बीजगणितीय संकेत:

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

इसका मतलब यह है कि शून्य गुणांक के साथ संगत चर की वृद्धि के साथ, कार्यात्मक का मूल्य नहीं बदलेगा और एक नया बुनियादी समाधान भी कार्यात्मक का इष्टतम देगा।

उपसंहार

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

थोड़ी देर बाद मैं सिंप्लेक्स विधि के व्यावहारिक कार्यान्वयन पर एक लेख लिखूंगा, साथ ही आर्टिफिशियल वेरिएबल्स की विधि (एम-विधि), गोमोरी विधि और शाखा और सीमा विधि पर कई लेख।

आपका ध्यान के लिए धन्यवाद!

पुनश्च

यदि आप पहले से ही सिम्पलेक्स विधि के कार्यान्वयन से परेशान हैं, तो मैं आपको सलाह देता हूं कि ए। ताहा द्वारा पुस्तक को पढ़ें; संचालन के अध्ययन का परिचय - वहाँ सब कुछ अच्छी तरह से विश्लेषण किया गया है, दोनों सिद्धांत और उदाहरण में; और matburo.ru समस्याओं को हल करने के उदाहरणों को भी देखें - यह कोड में कार्यान्वयन के साथ मदद करेगा।