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

This article is about रैखिक प्रोग्रामिंग एल्गोरिथ्म. For अरैखिक अनुकूलन अनुमानी, see नेल्डर-मीड पद्धति.

गणितीय अनुकूलन में, डेंटज़िग का सिम्प्लेक्स कलनविधि (एल्गोरिथम) (या सिंप्लेक्स विधि) रैखिक प्रोग्रामिंग के लिए एक लोकप्रिय कलनविधि है।

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

इतिहास

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

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

अवलोकन

Further information: रैखिक प्रोग्रामिंग

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

3D . में सिम्प्लेक्स कलनविधि का पॉलीहेड्रॉन

सिम्पलेक्स कलनविधि कैनोनिकल रूप में रैखिक कार्यक्रमों पर काम करता है

अधिकतम ${\textstyle \mathbf {c^{T}} \mathbf {x} }$

का विषय है $A\mathbf {x} \leq \mathbf {b}$ तथा $\mathbf {x} \geq 0$

$\mathbf {c} =(c_{1},\,\dots ,\,c_{n})$ के साथ उद्देश्य फलन के गुणांक, $(\cdot )^{\mathrm {T} }$ मैट्रिक्स ट्रांज़ोज़ है, और $\mathbf {x} =(x_{1},\,\dots ,\,x_{n})$ समस्या के चर हैं, $A$ एक p×n मैट्रिक्स है, और $\mathbf {b} =(b_{1},\,\dots ,\,b_{p})$ है। किसी भी रैखिक कार्यक्रम को मानक रूप में एक में बदलने की एक सीधी प्रक्रिया है, इसलिए रैखिक कार्यक्रमों के इस रूप का उपयोग करने से व्यापकता में कोई कमी नहीं आती है।

ज्यामितीय शब्दों में, $\mathbf {x}$ के सभी मानों द्वारा परिभाषित व्यवहार्य क्षेत्र जैसे कि ${\textstyle A\mathbf {x} \leq \mathbf {b} }$ और $\forall i,x_{i}\geq 0$ एक (संभवतः अबाधित) उत्तल पॉलीटोप है। इस पॉलीटॉप के एक चरम बिंदु या शीर्ष को बुनियादी व्यवहार्य हल (बीएफएस) के रूप में जाना जाता है।

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

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

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

मानक रूप

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

$x_{1}\geq 5$

एक नया चर, $y_{1}$, के साथ पेश किया गया है

${\begin{aligned}y_{1}=x_{1}-5\\x_{1}=y_{1}+5\end{aligned}}$

दूसरे समीकरण का उपयोग रेखीय कार्यक्रम से $x_{1}$ को हटाने के लिए किया जा सकता है। इस प्रकार, सभी निम्न बाध्य बाधाओं को गैर-नकारात्मकता प्रतिबंधों में बदला जा सकता है।

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

${\begin{aligned}x_{2}+2x_{3}&\leq 3\\-x_{4}+3x_{5}&\geq 2\end{aligned}}$

के साथ बदल दिया जाता है

${\begin{aligned}x_{2}+2x_{3}+s_{1}&=3\\-x_{4}+3x_{5}-s_{2}&=2\\s_{1},\,s_{2}&\geq 0\end{aligned}}$

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

तीसरा, प्रत्येक अप्रतिबंधित चर को लीनियर प्रोग्राम से हटा दिया जाता है। यह दो तरीकों से किया जा सकता है, एक है चर के लिए समीकरणों में से किसी एक में हल करके और फिर चर को प्रतिस्थापन द्वारा हटाकर। अन्य चर को दो प्रतिबंधित चर के अंतर से बदलना है। उदाहरण के लिए, यदि $z_{1}$ अप्रतिबंधित है, तो लिखिए

${\begin{aligned}&z_{1}=z_{1}^{+}-z_{1}^{-}\\&z_{1}^{+},\,z_{1}^{-}\geq 0\end{aligned}}$

रैखिक कार्यक्रम से $z_{1}$ को खत्म करने के लिए समीकरण का उपयोग किया जा सकता है।

जब यह प्रक्रिया पूरी हो जाती है तो सुसंगत क्षेत्र के रूप में हो जाएगा

$\mathbf {A} \mathbf {x} =\mathbf {b} ,\,\forall i\ x_{i}\geq 0$

यह मान लेना भी उपयोगी है कि $\mathbf {A}$ की कोटि पंक्तियों की संख्या है। इसका परिणाम सामान्यता में कोई कमी नहीं है क्योंकि अन्यथा या तो सिस्टम $\mathbf {A} \mathbf {x} =\mathbf {b}$ में निरर्थक समीकरण हैं जिन्हें छोड़ा जा सकता है, या सिस्टम असंगत है और रैखिक कार्यक्रम का कोई हल नहीं है।

सिम्प्लेक्स झांकी

मानक रूप में एक रेखीय कार्यक्रम को रूप की झांकी के रूप में दर्शाया जा सकता है

${\begin{bmatrix}1&-\mathbf {c} ^{T}&0\\0&\mathbf {A} &\mathbf {b} \end{bmatrix}}$

पहली पंक्ति उद्देश्य फलन को परिभाषित करती है और शेष पंक्तियाँ बाधाओं को निर्दिष्ट करती हैं। पहले कॉलम में शून्य वेक्टर बी के समान आयाम के शून्य वेक्टर का प्रतिनिधित्व करता है (विभिन्न लेखक अलग-अलग सम्मेलनों का उपयोग सटीक लेआउट के रूप में करते हैं)। यदि A के स्तंभों को पुनर्व्यवस्थित किया जा सकता है ताकि इसमें क्रम p (A में पंक्तियों की संख्या) का पहचान मैट्रिक्स हो, तो झांकी को विहित रूप में कहा जाता है। आइडेंटिटी मैट्रिक्स के कॉलम से संबंधित वेरिएबल्स को बेसिक वेरिएबल्स कहा जाता है जबकि बाकी वेरिएबल्स को नॉनबेसिक या फ्री वैरिएबल कहा जाता है। यदि गैर-मूल चर के मान 0 पर सेट हैं, तो मूल चर के मान आसानी से बी में प्रविष्टियों के रूप में प्राप्त किए जाते हैं और यह हल एक बुनियादी व्यवहार्य हल है। यहाँ बीजीय व्याख्या यह है कि प्रत्येक पंक्ति द्वारा दर्शाए गए रैखिक समीकरण के गुणांक या तो $0$, $1$, या कोई अन्य संख्या हैं। प्रत्येक पंक्ति में $1$ मान के साथ $1$ कॉलम होंगे, गुणांक $p-1$ के साथ $0$ कॉलम होंगे, और शेष कॉलम कुछ अन्य गुणांक के साथ होंगे (ये अन्य चर हमारे गैर-मूल चर का प्रतिनिधित्व करते हैं)। गैर-मूल चर के मानों को शून्य पर सेट करके हम प्रत्येक पंक्ति में यह सुनिश्चित करते हैं कि उसके कॉलम में $1$ द्वारा दर्शाए गए चर का मान उस पंक्ति के $b$ मान के बराबर है।

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

माना

${\begin{bmatrix}1&-\mathbf {c} _{B}^{T}&-\mathbf {c} _{D}^{T}&0\\0&I&\mathbf {D} &\mathbf {b} \end{bmatrix}}$

कैनोनिकल रूप में एक झाँकी बनें। उद्देश्य फलन से गुणांक cT
B  को हटाने के लिए अतिरिक्त पंक्ति-जोड़ परिवर्तन लागू किए जा सकते हैं। इस प्रक्रिया को प्राइसिंग आउट कहा जाता है और इसका परिणाम एक प्रामाणिक झांकी के रूप में सामने आता है

${\begin{bmatrix}1&0&-{\bar {\mathbf {c} }}_{D}^{T}&z_{B}\\0&I&\mathbf {D} &\mathbf {b} \end{bmatrix}}$

जहां z_B संबंधित बुनियादी व्यवहार्य हल पर उद्देश्य फलन का मान है। अद्यतित गुणांक, जिसे सापेक्ष लागत गुणांक के रूप में भी जाना जाता है, गैर बुनियादी चर के संबंध में उद्देश्य फलन के परिवर्तन की दरें हैं।

धुरी संचालन

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

कलनविधि

एक रेखीय कार्यक्रम को एक कैनोनिकल झांकी द्वारा दिया जाए। सिम्पलेक्स कलनविधि उत्तरोत्तर पिवट संचालन करके आगे बढ़ता है, जिनमें से प्रत्येक एक बेहतर बुनियादी व्यवहार्य हल देता है; प्रत्येक चरण में धुरी तत्व का चुनाव काफी हद तक इस आवश्यकता से निर्धारित होता है कि यह धुरी हल को बेहतर बनाती है।

चर चयन दर्ज करना

चूंकि प्रवेश करने वाला चर, सामान्य रूप से, 0 से एक सकारात्मक संख्या तक बढ़ जाएगा, यदि इस चर के संबंध में उद्देश्य फलन का व्युत्पन्न नकारात्मक है, तो उद्देश्य फलन का मान घट जाएगा। समतुल्य रूप से, यदि धुरी स्तंभ का चयन किया जाता है, तो उद्देश्य फलन का मान बढ़ जाता है ताकि झांकी की उद्देश्य पंक्ति में संबंधित प्रविष्टि सकारात्मक हो।

यदि एक से अधिक कॉलम हैं ताकि वस्तुनिष्ठ पंक्ति में प्रविष्टि सकारात्मक हो तो बुनियादी चर के सेट में से किसे जोड़ना है इसका चुनाव कुछ मनमाना है और कई एंट्री वेरिएबल चॉइस रूल्स जैसे डेवेक्स कलनविधि विकसित किए गए हैं।

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

$z(\mathbf {x} )=z_{B}+{\text{non - positive terms corresponding to non - basic variables}}$

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

परिवर्तनीय चयन छोड़ना

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

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

$b_{r}/a_{rc}\,$

सभी r पर न्यूनतम है ताकि a_rc > 0 हो। इसे न्यूनतम अनुपात परीक्षण कहते हैं। यदि एक से अधिक पंक्ति है जिसके लिए न्यूनतम हासिल किया जाता है तो निर्धारण करने के लिए ड्रॉपिंग वेरिएबल चॉइस रूल का उपयोग किया जा सकता है।

उदाहरण

See also: Revised simplex algorithm § Numerical example

रैखिक कार्यक्रम पर विचार करें

छोटा करना

$Z=-2x-3y-4z\,$

का विषय है

${\begin{aligned}3x+2y+z&\leq 10\\2x+5y+3z&\leq 15\\x,\,y,\,z&\geq 0\end{aligned}}$

सुस्त चर s और t के योग के साथ, यह विहित झांकी द्वारा दर्शाया गया है

${\begin{bmatrix}1&2&3&4&0&0&0\\0&3&2&1&1&0&10\\0&2&5&3&0&1&15\end{bmatrix}}$

जहां कॉलम 5 और 6 मूल चर s और t का प्रतिनिधित्व करते हैं और संबंधित मूल व्यवहार्य हल है

$x=y=z=0,\,s=10,\,t=15.$

कॉलम 2, 3 और 4 को पिवट कॉलम के रूप में चुना जा सकता है, इस उदाहरण के लिए कॉलम 4 को चुना गया है। पंक्ति 2 और 3 को धुरी पंक्तियों के रूप में चुनने से उत्पन्न z के मान क्रमशः 10/1 = 10 और 15/3 = 5 हैं। इनमें से कम से कम 5 है, इसलिए पंक्ति 3 को पिवट पंक्ति होना चाहिए। पिवट का प्रदर्शन करता है

${\begin{bmatrix}3&-2&-11&0&0&-4&-60\\0&7&1&0&3&-1&15\\0&2&5&3&0&1&15\end{bmatrix}}$

अब कॉलम 4 और 5 मूल चर z और s का प्रतिनिधित्व करते हैं और संबंधित बुनियादी व्यवहार्य हल है

$x=y=t=0,\,z=5,\,s=5.$

अगले चरण के लिए, वस्तुनिष्ठ पंक्ति में कोई सकारात्मक प्रविष्टि नहीं है और वास्तव में

$Z={\frac {-60+2x+11y+4t}{3}}=-20+{\frac {2x+11y+4t}{3}}$

इसलिए Z का न्यूनतम मान −20 है।

एक प्रारंभिक विहित झांकी ढूँढना

सामान्य तौर पर, एक रेखीय कार्यक्रम विहित रूप में नहीं दिया जाएगा और सिंप्लेक्स कलनविधि शुरू होने से पहले एक समकक्ष विहित झांकी मिलनी चाहिए। यह कृत्रिम चर के परिचय से पूरा किया जा सकता है। इन चरों के लिए आइडेंटिटी मैट्रिक्स के कॉलम को कॉलम वैक्टर के रूप में जोड़ा जाता है। यदि बाधा समीकरण के लिए बी मान ऋणात्मक है, तो पहचान मैट्रिक्स कॉलम जोड़ने से पहले समीकरण को अस्वीकार कर दिया गया है। यह संभव हल या इष्टतम हल के सेट को नहीं बदलता है, और यह सुनिश्चित करता है कि ढीले चर एक प्रारंभिक व्यवहार्य हल का गठन करेंगे। नई झांकी विहित रूप में है लेकिन यह मूल समस्या के बराबर नहीं है। तो कृत्रिम चर के योग के बराबर एक नया उद्देश्य फलन पेश किया जाता है और न्यूनतम खोजने के लिए सरल एल्गोरिदम लागू किया जाता है; संशोधित रेखीय कार्यक्रम को चरण I समस्या कहा जाता है।

चरण I समस्या के लिए लागू सिंप्लेक्स एल्गोरिथ्म को नए उद्देश्य फलन के लिए न्यूनतम मूल्य के साथ समाप्त होना चाहिए, क्योंकि गैर-नकारात्मक चर का योग होने के कारण, इसका मान 0 से नीचे है। यदि न्यूनतम 0 है तो मूल समस्या के समतुल्य एक विहित झांकी का निर्माण करने वाली परिणामी विहित झांकी से कृत्रिम चर को समाप्त किया जा सकता है। हल खोजने के लिए सिम्प्लेक्स एल्गोरिदम को लागू किया जा सकता है; इस कदम को द्वितीय चरण कहा जाता है। यदि न्यूनतम धनात्मक है तो प्रथम चरण की समस्या के लिए कोई व्यवहार्य हल नहीं है जहाँ कृत्रिम चर सभी शून्य हैं। इसका मतलब यह है कि मूल समस्या के लिए संभव क्षेत्र खाली है, और इसलिए मूल समस्या का कोई हल नहीं है।

उदाहरण

रैखिक कार्यक्रम पर विचार करें

छोटा करना

$Z=-2x-3y-4z\,$

का विषय है

${\begin{aligned}3x+2y+z&=10\\2x+5y+3z&=15\\x,\,y,\,z&\geq 0\end{aligned}}$

यह (गैर-विहित) झांकी द्वारा दर्शाया गया है

${\begin{bmatrix}1&2&3&4&0\\0&3&2&1&10\\0&2&5&3&15\end{bmatrix}}$

एक नई झांकी देते हुए कृत्रिम चर u और v और वस्तुनिष्ठ फलन W = u + v का परिचय दें

${\begin{bmatrix}1&0&0&0&0&-1&-1&0\\0&1&2&3&4&0&0&0\\0&0&3&2&1&1&0&10\\0&0&2&5&3&0&1&15\end{bmatrix}}$

मूल उद्देश्य फलन को परिभाषित करने वाले समीकरण को द्वितीय चरण की प्रत्याशा में बनाए रखा जाता है।

निर्माण के द्वारा, यू और वी दोनों बुनियादी चर हैं, क्योंकि वे प्रारंभिक पहचान मैट्रिक्स का हिस्सा हैं। हालाँकि, वस्तुनिष्ठ फलन W वर्तमान में मानता है कि u और v दोनों 0 हैं। वस्तुनिष्ठ फलन को सही मान के लिए समायोजित करने के लिए जहाँ u = 10 और v = 15, पहली पंक्ति में तीसरी और चौथी पंक्तियाँ जोड़ें

${\begin{bmatrix}1&0&5&7&4&0&0&25\\0&1&2&3&4&0&0&0\\0&0&3&2&1&1&0&10\\0&0&2&5&3&0&1&15\end{bmatrix}}$

स्तंभ 5 को पिवट कॉलम के रूप में चुनें, इसलिए पिवट पंक्ति पंक्ति 4 होनी चाहिए, और अपडेट की गई झांकी है

${\begin{bmatrix}3&0&7&1&0&0&-4&15\\0&3&-2&-11&0&0&-4&-60\\0&0&7&1&0&3&-1&15\\0&0&2&5&3&0&1&15\end{bmatrix}}$

अब कॉलम 3 को पिवट कॉलम के रूप में चुनें, जिसके लिए पंक्ति 3 को पिवट पंक्ति होना चाहिए

${\begin{bmatrix}7&0&0&0&0&-7&-7&0\\0&7&0&-25&0&2&-10&-130\\0&0&7&1&0&3&-1&15\\0&0&0&11&7&-2&3&25\end{bmatrix}}$

कृत्रिम चर अब 0 हैं और उन्हें मूल समस्या के समतुल्य एक विहित झांकी देते हुए गिराया जा सकता है:

${\begin{bmatrix}7&0&-25&0&-130\\0&7&1&0&15\\0&0&11&7&25\end{bmatrix}}$

यह, सौभाग्य से, पहले से ही इष्टतम है और मूल रैखिक कार्यक्रम के लिए इष्टतम मूल्य −130/7 है।

उन्नत विषय

कार्यान्वयन

Main article: Revised simplex algorithm

कलनविधि का वर्णन करने के लिए ऊपर इस्तेमाल किया गया झांकी फॉर्म खुद को एक तत्काल कार्यान्वयन के लिए उधार देता है जिसमें झांकी को एक आयताकार (एम + 1) -बाय- (एम + एन + 1) सरणी के रूप में बनाए रखा जाता है। पहचान मैट्रिक्स के m स्पष्ट स्तंभों को संग्रहीत करने से बचना सीधा है जो B के आधार पर [A, I] के स्तंभों का सबसेट होने के कारण झांकी के भीतर होगा। इस कार्यान्वयन को "मानक सिंप्लेक्स कलनविधि" के रूप में जाना जाता है। भंडारण और संगणना ओवरहेड ऐसा है कि बड़ी रैखिक प्रोग्रामिंग समस्याओं को हल करने के लिए मानक सिंप्लेक्स विधि एक निषेधात्मक रूप से महंगा दृष्टिकोण है।

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

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

अध: पतन: रुकना और साइकिल चलाना

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

ज़ादेह के नियम और कनिंघम के नियम जैसे इतिहास-आधारित पिवट नियम भी इस बात पर नज़र रखते हुए कि कितनी बार विशेष चर का उपयोग किया जा रहा है और फिर ऐसे चर का समर्थन करते हैं जो कम से कम बार उपयोग किए गए हैं, स्टालिंग और साइकिल चलाने के मुद्दे को दरकिनार करने की कोशिश करते हैं।

सबसे खराब स्थिति में दक्षता

सिम्प्लेक्स विधि व्यवहार में उल्लेखनीय रूप से कुशल है और फूरियर-मोट्ज़किन उन्मूलन जैसे पहले के तरीकों पर एक बड़ा सुधार था। हालांकि, 1972 में, क्ले और मिन्टी ने क्ले-मिन्टी क्यूब का एक उदाहरण दिया, जिसमें दिखाया गया कि डेंटज़िग द्वारा तैयार की गई सिम्पलेक्स विधि की सबसे खराब स्थिति जटिलता घातीय समय है। तब से, विधि पर लगभग हर बदलाव के लिए, यह दिखाया गया है कि रैखिक कार्यक्रमों का एक परिवार है जिसके लिए यह खराब प्रदर्शन करता है। यह एक खुला प्रश्न है कि क्या बहुपद समय के साथ कोई भिन्नता है, हालांकि उप-घातीय धुरी नियम ज्ञात हैं।

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

व्यवहार में दक्षता

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

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

अन्य एल्गोरिदम

लीनियर-प्रोग्रामिंग समस्याओं को हल करने के लिए अन्य एल्गोरिदम लीनियर-प्रोग्रामिंग आलेख में वर्णित हैं। एक अन्य बेसिस-एक्सचेंज पिवोटिंग कलनविधि क्रिस-क्रॉस कलनविधि है। रेखीय प्रोग्रामिंग के लिए बहुपद-काल एल्गोरिदम हैं जो आंतरिक बिंदु विधियों का उपयोग करते हैं: इनमें खाचियान का दीर्घवृत्तीय एल्गोरिथ्म, कर्मकार का प्रक्षेपी एल्गोरिथ्म और पथ-अनुवर्ती एल्गोरिदम सम्मिलित हैं।

रैखिक-भिन्नात्मक प्रोग्रामिंग

Main article: Linear-fractional programming

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

यह भी देखें

• क्रिस-क्रॉस एल्गोरिथम
• कटिंग-प्लेन विधि
• डेवेक्स एल्गोरिथम
• फूरियर-मोट्ज़किन उन्मूलन
• ढतला हुआ वंश
• कर्मकार का एल्गोरिदम
• नेल्डर-मीड पद्धति | नेल्डर-मीड सरल अनुमानी
• ब्लैंड का नियम, जो साइकिल चलाने से परहेज करता है

संदर्भ

• Murty, Katta G. (1983). Linear programming. New York: John Wiley & Sons, Inc. pp. xix+482. ISBN 978-0-471-09725-9. MR 0720547.

अग्रिम पठन

These introductions are written for students of computer science and operations research:

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 29.3: The simplex algorithm, pp. 790–804.
• Frederick S. Hillier and Gerald J. Lieberman: Introduction to Operations Research, 8th edition. McGraw-Hill. ISBN 0-07-123828-X
• Rardin, Ronald L. (1997). Optimization in operations research. Prentice Hall. p. 919. ISBN 978-0-02-398415-0.

बाहरी संबंध

• An Introduction to Linear Programming and the Simplex Algorithm by Spyros Reveliotis of the Georgia Institute of Technology.
• Greenberg, Harvey J., Klee–Minty Polytope Shows Exponential Time Complexity of Simplex Method the University of Colorado at Denver (1997) PDF download
• Simplex Method A tutorial for Simplex Method with examples (also two-phase and M-method).
• Mathstools Simplex Calculator from www.mathstools.com
• Example of Simplex Procedure for a Standard Linear Programming Problem by Thomas McFarland of the University of Wisconsin-Whitewater.
• PHPSimplex: online tool to solve Linear Programming Problems by Daniel Izquierdo and Juan José Ruiz of the University of Málaga (UMA, Spain)
• simplex-m Online Simplex Solver

| group5 = Metaheuristics | abbr5 = heuristic | list5 =

• Evolutionary algorithm
• Hill climbing
• Local search
• Simulated annealing
• Tabu search

| below =

• Software

}} | group5 =Metaheuuristic |abbr5 = heuristic | list5 =*विकासवादी एल्गोरिथ्म

• पहाड़ी की चढ़ाई
• स्थानीय खोज
• तैयार किए हुयी धातु पे पानी चढाने की कला
• तब्बू खोज

| below =* सॉफ्टवेयर

}}