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

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 के दो संभावित परिणाम इस प्रकार हैं की या तो एक मूल साध्य हल प्राप्त हो गया है या यह कि साध्य क्षेत्र रिक्त है। बाद के स्थिति में रैखिक प्रोग्राम को असुसंगत कहा जाता है। द्वितीय चरण में, अवस्था II सिम्पलेक्स कलनविधि अवस्था 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}}$

सरणी की प्रथम पंक्ति उद्देश्य फलन को परिभाषित करती है और शेष पंक्तियाँ बाध्यताओं (कंस्ट्रेंट्स) को निर्दिष्ट करती हैं। प्रथम स्तंभ में शून्य सदिश b के समान आयाम के शून्य सदिश का प्रतिनिधित्व करता है (विभिन्न लेखक अलग-अलग सम्मेलनों का उपयोग यथार्थ अनुविक्षेप के रूप में करते हैं)। यदि 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 =* सॉफ्टवेयर

}}