सिम्प्लेक्स एल्गोरिथम: Difference between revisions

Latest revision as of 14:33, 30 November 2022

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

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

इतिहास

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

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

अवलोकन

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

3डी में सिम्पलेक्स कलनविधि का बहुफलक

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

अधिकतम

{\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$ (संभवतः अबाधित) उत्तल पॉलीटोप है। इस पॉलीटॉप के चरम बिंदु या शीर्ष को मूल साध्य हल (बीएफएस) के रूप में जाना जाता है।

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

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

एक रैखिक प्रोग्रामन का हल दो चरणों में पूर्ण होता है। प्रथम चरण में, जिसे अवस्था I के रूप में जाना जाता है, प्रारंभिक चरम बिंदु प्राप्त होता है। फलन की प्रकृति के आधार पर यह सतहीय (ट्राईवियल) हो सकता है, परन्तु सामान्यतः इसे मूल या आरंभिक फलन के संशोधित संस्करण में सिम्पलेक्स कलनविधि लागू करके हल किया जा सकता है। अवस्था I के दो संभावित परिणाम इस प्रकार हैं की या तो एक मूल साध्य हल प्राप्त हो गया है या यह कि साध्य क्षेत्र रिक्त है। पश्चात के स्थिति में रैखिक प्रोग्राम को असुसंगत कहा जाता है। द्वितीय चरण में, अवस्था II सिम्पलेक्स कलनविधि अवस्था I में प्रारंभिक बिंदु के रूप में मिले मूल साध्य हल का उपयोग करके लागू किया जाता है। अवस्था II से संभावित परिणाम या तो एक इष्टतम मूल साध्य हल है या एक अपरिमित किनारा है जिस पर ऊपर उद्देश्य फलन असीम है।^[13]^[14]^[15]

मानक रूप

रेखीय फलन को एक मानक रूप में बदलना निम्नानुसार प्रमाणित किया जा सकता है।^[16] सर्व प्रथम, प्रत्येक चर के लिए 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}$ में आधिक्य समीकरण हैं जिन्हें छोड़ा जा सकता है, या सिस्टम असंगत है और रैखिक प्रोग्राम का कोई हल नहीं है।^[17]

सिम्प्लेक्स सारणी

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

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

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

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

माना

{\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 संबंधित मूल साध्य हल पर उद्देश्य फलन का मान है। अद्यतित गुणांक, जिसे सापेक्ष लागत गुणांक के रूप में भी जाना जाता है, गैर मूल चर के संबंध में उद्देश्य फलन के परिवर्तन की दरें हैं।^[14]

ध्रुराग्र संक्रिया

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

कलनविधि

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

चर चयन प्रविष्टि

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

यदि एक से अधिक स्तंभ हैं ताकि कर्मकारक पंक्ति में प्रविष्टि धनात्मक हो तो मूल चर के सेट में से किसे जोड़ना है इसका चयन कुछ मनमाना है और कई चर विकल्प नियम प्रविष्टि^[20] जैसे डेवेक्स कलनविधि^[21] विकसित किए गए हैं।

यदि कर्मकारक पंक्ति में सभी प्रविष्टियाँ 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 हो। इसे न्यूनतम अनुपात परीक्षण कहते हैं।^[20] यदि एक से अधिक पंक्तियाँ है जिसके लिए न्यूनतम मान प्राप्त किया जाता है तो निर्धारण करने के लिए पातन चर विकल्प नियम^[22] का उपयोग किया जा सकता है।

उदाहरण

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

न्यूनतमीकरण

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 समस्या कहा जाता है।^[23]

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

उदाहरण

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

न्यूनतमीकरण

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}}

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

निर्माण के द्वारा, u और v दोनों मूल चर हैं, क्योंकि वे प्रारंभिक तत्समक आव्यूह का हिस्सा हैं। हालाँकि, वस्तुनिष्ठ फलन 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 है।

उन्नत विषय

कार्यान्वयन

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

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

बड़ी रेखीय-प्रोग्रामिंग समस्याओं में A सामान्यतः एक विरल आव्यूह है और, जब इसके व्युत्क्रम प्रतिनिधित्व को बनाए रखते हुए B की परिणामी विरलता का शोषण किया जाता है, तो संशोधित सिंप्लेक्स एल्गोरिथ्म मानक सिम्प्लेक्स विधि की तुलना में बहुत अधिक कुशल होता है। वाणिज्यिक सिंप्लेक्स सॉल्वर संशोधित सिंप्लेक्स कलनविधि पर आधारित हैं।^[24]^[25]^[26]^[27]^[28]

विकृति: स्तंभन और चक्रण

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

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

निकृष्टतम स्थिति में दक्षता

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

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

वास्तविकता में दक्षता

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

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

अन्य कलनविधि

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

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

रैखिक-भिन्नात्मक प्रोग्रामिंग (एलएफपी) रैखिक प्रोग्रामिंग (एलपी) का सामान्यीकरण है। एलपी में उद्देश्य फलन एक रैखिक फलन है, जबकि रैखिक-भिन्नात्मक प्रोग्राम का उद्देश्य फलन दो रैखिक फलन्स का अनुपात है। दूसरे शब्दों में, एक रेखीय फलन एक भिन्नात्मक-रैखिक फलन है जिसमें भाजक एक नियत फलन होता है जिसका मान प्रत्येक स्थान पर एक प्राप्त होता है। रेखीय-भिन्नात्मक फलन को सिम्प्लेक्स कलनविधि^[43]^[44]^[45]^[46] या क्रिस-क्रॉस कलनविधि के एक संस्करण द्वारा हल किया जा सकता है।^[47]

यह भी देखें

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

↑ Murty, Katta G. रैखिक प्रोग्रामिंग. John Wiley & Sons Inc.1, 2000.
↑ Murty (1983, Comment 2.2)
↑ Murty (1983, Note 3.9)
↑ Stone, Richard E.; Tovey, Craig A. (1991). "सिम्प्लेक्स और प्रोजेक्टिव स्केलिंग एल्गोरिदम को पुनरावृत्त रूप से कम से कम वर्ग विधियों के रूप में पुन: भारित किया जाता है". SIAM Review. 33 (2): 220–237. doi:10.1137/1033049. JSTOR 2031142. MR 1124362.
↑ Stone, Richard E.; Tovey, Craig A. (1991). "इरेटम: सिम्पलेक्स और प्रोजेक्टिव स्केलिंग एल्गोरिथम पुनरावृत्त रूप से कम से कम वर्गों के तरीकों को फिर से भारित करता है". SIAM Review. 33 (3): 461. doi:10.1137/1033100. JSTOR 2031443. MR 1124362.
↑ Strang, Gilbert (1 June 1987). "कर्मकार का एल्गोरिथम और अनुप्रयुक्त गणित में इसका स्थान". The Mathematical Intelligencer. 9 (2): 4–10. doi:10.1007/BF03025891. ISSN 0343-6993. MR 0883185. S2CID 123541868.
↑ Dantzig, George B. (April 1982). "रैखिक प्रोग्रामिंग की उत्पत्ति के बारे में यादें" (PDF). Operations Research Letters. 1 (2): 43–48. doi:10.1016/0167-6377(82)90043-8. Archived from the original on May 20, 2015.
↑ Albers and Reid (1986). "जॉर्ज बी. डेंट्ज़िग के साथ एक साक्षात्कार: रैखिक प्रोग्रामिंग के जनक". College Mathematics Journal. 17 (4): 292–314. doi:10.1080/07468342.1986.11972971.
↑ Dantzig, George (May 1987). Nash, Stephen G. (ed.). सिंप्लेक्स विधि की उत्पत्ति (PDF). pp. 141–151. doi:10.1145/87252.88081. ISBN 978-0-201-50814-7. Archived (PDF) from the original on May 29, 2015. {{cite encyclopedia}}: |work= ignored (help)
↑ Murty (1983, Theorem 3.3)
↑ Murty (1983, p. 143, Section 3.13)
↑ ^12.0 ^12.1 Murty (1983, p. 137, Section 3.8)
↑ ^13.0 ^13.1 ^13.2 George B. Dantzig and Mukund N. Thapa. 1997. Linear programming 1: Introduction. Springer-Verlag.
↑ ^14.0 ^14.1 ^14.2 ^14.3 Evar D. Nering and Albert W. Tucker, 1993, Linear Programs and Related Problems, Academic Press. (elementary)
↑ ^15.0 ^15.1 Robert J. Vanderbei, Linear Programming: Foundations and Extensions, 3rd ed., International Series in Operations Research & Management Science, Vol. 114, Springer Verlag, 2008. ISBN 978-0-387-74387-5.
↑ Murty (1983, Section 2.2)
↑ Murty (1983, p. 173)
↑ Murty (1983, section 2.3.2)
↑ Murty (1983, section 3.12)
↑ ^20.0 ^20.1 Murty (1983, p. 66)
↑ Harris, Paula MJ. "Pivot selection methods of the Devex LP code." Mathematical programming 5.1 (1973): 1–28
↑ Murty (1983, p. 67)
↑ Murty (1983, p. 60)
↑ ^24.0 ^24.1 ^24.2 ^24.3 M. Padberg, Linear Optimization and Extensions, Second Edition, Springer-Verlag, 1999.
↑ ^25.0 ^25.1 George B. Dantzig and Mukund N. Thapa. 2003. Linear Programming 2: Theory and Extensions. Springer-Verlag.
↑ Dmitris Alevras and Manfred W. Padberg, Linear Optimization and Extensions: Problems and Extensions, Universitext, Springer-Verlag, 2001. (Problems from Padberg with solutions.)
↑ Maros, István; Mitra, Gautam (1996). "Simplex algorithms". In J. E. Beasley (ed.). रैखिक और पूर्णांक प्रोग्रामिंग में प्रगति. Oxford Science. pp. 1–46. MR 1438309.
↑ Maros, István (2003). सिंप्लेक्स विधि की कम्प्यूटेशनल तकनीक. International Series in Operations Research & Management Science. Vol. 61. Boston, MA: Kluwer Academic Publishers. pp. xx+325. ISBN 978-1-4020-7332-8. MR 1960274.
↑ Bland, Robert G. (May 1977). "New finite pivoting rules for the simplex method". Mathematics of Operations Research. 2 (2): 103–107. doi:10.1287/moor.2.2.103. JSTOR 3689647. MR 0459599. S2CID 18493293.
↑ Murty (1983, p. 79)
↑ There are abstract optimization problems, called oriented matroid programs, on which Bland's rule cycles (incorrectly) while the criss-cross algorithm terminates correctly.
↑ Klee, Victor; Minty, George J. (1972). "How good is the simplex algorithm?". In Shisha, Oved (ed.). असमानताओं III (कैलिफोर्निया विश्वविद्यालय, लॉस एंजिल्स, कैलिफ़ोर्निया में आयोजित असमानताओं पर तीसरे संगोष्ठी की कार्यवाही, 1-9 सितंबर, 1969, थियोडोर एस। मोट्ज़किन की स्मृति को समर्पित). New York-London: Academic Press. pp. 159–175. MR 0332165.
↑ Hansen, Thomas; Zwick, Uri (2015), "An Improved Version of the Random-Facet Pivoting Rule for the Simplex Algorithm", Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing: 209–218, CiteSeerX 10.1.1.697.2526, doi:10.1145/2746539.2746557, ISBN 9781450335362, S2CID 1980659
↑ Disser, Yann; Skutella, Martin (2018-11-01). "सिम्प्लेक्स एल्गोरिथम एनपी-माइटी है". ACM Trans. Algorithms. 15 (1): 5:1–5:19. arXiv:1311.5935. doi:10.1145/3280847. ISSN 1549-6325. S2CID 54445546.
↑ Adler, Ilan; Christos, Papadimitriou; Rubinstein, Aviad (2014), "On Simplex Pivoting Rules and Complexity Theory", International Conference on Integer Programming and Combinatorial Optimization, Lecture Notes in Computer Science, 17: 13–24, arXiv:1404.3320, doi:10.1007/978-3-319-07557-0_2, ISBN 978-3-319-07556-3, S2CID 891022
↑ Fearnly, John; Savani, Rahul (2015), "The Complexity of the Simplex Method", Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing: 201–208, arXiv:1404.0605, doi:10.1145/2746539.2746558, ISBN 9781450335362, S2CID 2116116
↑ Alexander Schrijver, Theory of Linear and Integer Programming. John Wiley & sons, 1998, ISBN 0-471-98232-6 (mathematical)
↑ The simplex algorithm takes on average D steps for a cube. Borgwardt (1987): Borgwardt, Karl-Heinz (1987). The simplex method: A probabilistic analysis. Algorithms and Combinatorics (Study and Research Texts). Vol. 1. Berlin: Springer-Verlag. pp. xii+268. ISBN 978-3-540-17096-9. MR 0868467.
↑ Spielman, Daniel; Teng, Shang-Hua (2001). "Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time". कम्प्यूटिंग के सिद्धांत पर तीस-तीसरे वार्षिक एसीएम संगोष्ठी की कार्यवाही. ACM. pp. 296–305. arXiv:cs/0111050. doi:10.1145/380752.380813. ISBN 978-1-58113-349-3. S2CID 1471.
↑ Dadush, Daniel; Huiberts, Sophie (2020-01-01). "सिंप्लेक्स विधि का एक अनुकूल चिकना विश्लेषण". SIAM Journal on Computing. 49 (5): STOC18–449. doi:10.1137/18M1197205. ISSN 0097-5397. S2CID 226351624.
↑ Terlaky, Tamás; Zhang, Shu Zhong (1993). "लीनियर प्रोग्रामिंग के लिए धुरी नियम: हाल के सैद्धांतिक विकास पर एक सर्वेक्षण". Annals of Operations Research. 46–47 (1): 203–233. CiteSeerX 10.1.1.36.7658. doi:10.1007/BF02096264. ISSN 0254-5330. MR 1260019. S2CID 6058077.
↑ Fukuda, Komei; Terlaky, Tamás (1997). Thomas M. Liebling; Dominique de Werra (eds.). "क्रिस-क्रॉस विधियाँ: धुरी एल्गोरिदम पर एक नया दृश्य". Mathematical Programming, Series B. Vol. 79, no. 1–3. Amsterdam: North-Holland Publishing. pp. 369–395. doi:10.1007/BF02614325. MR 1464775.
↑ Murty (1983, Chapter 3.20 (pp. 160–164) and pp. 168 and 179)
↑ Chapter five: Craven, B. D. (1988). Fractional programming. Sigma Series in Applied Mathematics. Vol. 4. Berlin: Heldermann Verlag. p. 145. ISBN 978-3-88538-404-5. MR 0949209.
↑ Kruk, Serge; Wolkowicz, Henry (1999). "स्यूडोलिनियर प्रोग्रामिंग". SIAM Review. 41 (4): 795–805. Bibcode:1999SIAMR..41..795K. CiteSeerX 10.1.1.53.7355. doi:10.1137/S0036144598335259. JSTOR 2653207. MR 1723002.
↑ Mathis, Frank H.; Mathis, Lenora Jane (1995). "अस्पताल प्रबंधन के लिए एक गैर-रेखीय प्रोग्रामिंग एल्गोरिदम". SIAM Review. 37 (2): 230–234. doi:10.1137/1037046. JSTOR 2132826. MR 1343214.
↑ Illés, Tibor; Szirmai, Ákos; Terlaky, Tamás (1999). "अतिशयोक्तिपूर्ण प्रोग्रामिंग के लिए परिमित क्रिस-क्रॉस विधि". European Journal of Operational Research. 114 (1): 198–214. CiteSeerX 10.1.1.36.7090. doi:10.1016/S0377-2217(98)00049-6. ISSN 0377-2217.

संदर्भ

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 =

| below =

Software

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

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

}}

[Murty-1] Murty, Katta G. रैखिक प्रोग्रामिंग. John Wiley & Sons Inc.1, 2000.

[Murty22-2] Murty (1983, Comment 2.2)

[Murty39-3] Murty (1983, Note 3.9)

[StoneTovey-4] Stone, Richard E.; Tovey, Craig A. (1991). "सिम्प्लेक्स और प्रोजेक्टिव स्केलिंग एल्गोरिदम को पुनरावृत्त रूप से कम से कम वर्ग विधियों के रूप में पुन: भारित किया जाता है". SIAM Review. 33 (2): 220–237. doi:10.1137/1033049. JSTOR 2031142. MR 1124362.

[5] Stone, Richard E.; Tovey, Craig A. (1991). "इरेटम: सिम्पलेक्स और प्रोजेक्टिव स्केलिंग एल्गोरिथम पुनरावृत्त रूप से कम से कम वर्गों के तरीकों को फिर से भारित करता है". SIAM Review. 33 (3): 461. doi:10.1137/1033100. JSTOR 2031443. MR 1124362.

[Strang-6] Strang, Gilbert (1 June 1987). "कर्मकार का एल्गोरिथम और अनुप्रयुक्त गणित में इसका स्थान". The Mathematical Intelligencer. 9 (2): 4–10. doi:10.1007/BF03025891. ISSN 0343-6993. MR 0883185. S2CID 123541868.

[7] Dantzig, George B. (April 1982). "रैखिक प्रोग्रामिंग की उत्पत्ति के बारे में यादें" (PDF). Operations Research Letters. 1 (2): 43–48. doi:10.1016/0167-6377(82)90043-8. Archived from the original on May 20, 2015.

[8] Albers and Reid (1986). "जॉर्ज बी. डेंट्ज़िग के साथ एक साक्षात्कार: रैखिक प्रोग्रामिंग के जनक". College Mathematics Journal. 17 (4): 292–314. doi:10.1080/07468342.1986.11972971.

[9] Dantzig, George (May 1987). Nash, Stephen G. (ed.). सिंप्लेक्स विधि की उत्पत्ति (PDF). pp. 141–151. doi:10.1145/87252.88081. ISBN 978-0-201-50814-7. Archived (PDF) from the original on May 29, 2015. {{cite encyclopedia}}: |work= ignored (help)

[10] Murty (1983, Theorem 3.3)

[11] Murty (1983, p. 143, Section 3.13)

[Murty137-12] 12.0 ^12.1 Murty (1983, p. 137, Section 3.8)

[DantzigThapa1-13] 13.0 ^13.1 ^13.2 George B. Dantzig and Mukund N. Thapa. 1997. Linear programming 1: Introduction. Springer-Verlag.

[NeringTucker-14] 14.0 ^14.1 ^14.2 ^14.3 Evar D. Nering and Albert W. Tucker, 1993, Linear Programs and Related Problems, Academic Press. (elementary)

[Vanderbei-15] 15.0 ^15.1 Robert J. Vanderbei, Linear Programming: Foundations and Extensions, 3rd ed., International Series in Operations Research & Management Science, Vol. 114, Springer Verlag, 2008. ISBN 978-0-387-74387-5.

[16] Murty (1983, Section 2.2)

[17] Murty (1983, p. 173)

[18] Murty (1983, section 2.3.2)

[19] Murty (1983, section 3.12)

[Murty66-20] 20.0 ^20.1 Murty (1983, p. 66)

[21] Harris, Paula MJ. "Pivot selection methods of the Devex LP code." Mathematical programming 5.1 (1973): 1–28

[22] Murty (1983, p. 67)

[23] Murty (1983, p. 60)

[Padberg-24] 24.0 ^24.1 ^24.2 ^24.3 M. Padberg, Linear Optimization and Extensions, Second Edition, Springer-Verlag, 1999.

[DantzigThapa2-25] 25.0 ^25.1 George B. Dantzig and Mukund N. Thapa. 2003. Linear Programming 2: Theory and Extensions. Springer-Verlag.

[26] Dmitris Alevras and Manfred W. Padberg, Linear Optimization and Extensions: Problems and Extensions, Universitext, Springer-Verlag, 2001. (Problems from Padberg with solutions.)

[MarosMitra-27] Maros, István; Mitra, Gautam (1996). "Simplex algorithms". In J. E. Beasley (ed.). रैखिक और पूर्णांक प्रोग्रामिंग में प्रगति. Oxford Science. pp. 1–46. MR 1438309.

[28] Maros, István (2003). सिंप्लेक्स विधि की कम्प्यूटेशनल तकनीक. International Series in Operations Research & Management Science. Vol. 61. Boston, MA: Kluwer Academic Publishers. pp. xx+325. ISBN 978-1-4020-7332-8. MR 1960274.

[Bland-29] Bland, Robert G. (May 1977). "New finite pivoting rules for the simplex method". Mathematics of Operations Research. 2 (2): 103–107. doi:10.1287/moor.2.2.103. JSTOR 3689647. MR 0459599. S2CID 18493293.

[30] Murty (1983, p. 79)

[31] There are abstract optimization problems, called oriented matroid programs, on which Bland's rule cycles (incorrectly) while the criss-cross algorithm terminates correctly.

[KleeMinty-32] Klee, Victor; Minty, George J. (1972). "How good is the simplex algorithm?". In Shisha, Oved (ed.). असमानताओं III (कैलिफोर्निया विश्वविद्यालय, लॉस एंजिल्स, कैलिफ़ोर्निया में आयोजित असमानताओं पर तीसरे संगोष्ठी की कार्यवाही, 1-9 सितंबर, 1969, थियोडोर एस। मोट्ज़किन की स्मृति को समर्पित). New York-London: Academic Press. pp. 159–175. MR 0332165.

[33] Hansen, Thomas; Zwick, Uri (2015), "An Improved Version of the Random-Facet Pivoting Rule for the Simplex Algorithm", Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing: 209–218, CiteSeerX 10.1.1.697.2526, doi:10.1145/2746539.2746557, ISBN 9781450335362, S2CID 1980659

[34] Disser, Yann; Skutella, Martin (2018-11-01). "सिम्प्लेक्स एल्गोरिथम एनपी-माइटी है". ACM Trans. Algorithms. 15 (1): 5:1–5:19. arXiv:1311.5935. doi:10.1145/3280847. ISSN 1549-6325. S2CID 54445546.

[35] Adler, Ilan; Christos, Papadimitriou; Rubinstein, Aviad (2014), "On Simplex Pivoting Rules and Complexity Theory", International Conference on Integer Programming and Combinatorial Optimization, Lecture Notes in Computer Science, 17: 13–24, arXiv:1404.3320, doi:10.1007/978-3-319-07557-0_2, ISBN 978-3-319-07556-3, S2CID 891022

[36] Fearnly, John; Savani, Rahul (2015), "The Complexity of the Simplex Method", Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing: 201–208, arXiv:1404.0605, doi:10.1145/2746539.2746558, ISBN 9781450335362, S2CID 2116116

[Schrijver-37] Alexander Schrijver, Theory of Linear and Integer Programming. John Wiley & sons, 1998, ISBN 0-471-98232-6 (mathematical)

[Borgwardt-38] The simplex algorithm takes on average D steps for a cube. Borgwardt (1987): Borgwardt, Karl-Heinz (1987). The simplex method: A probabilistic analysis. Algorithms and Combinatorics (Study and Research Texts). Vol. 1. Berlin: Springer-Verlag. pp. xii+268. ISBN 978-3-540-17096-9. MR 0868467.

[39] Spielman, Daniel; Teng, Shang-Hua (2001). "Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time". कम्प्यूटिंग के सिद्धांत पर तीस-तीसरे वार्षिक एसीएम संगोष्ठी की कार्यवाही. ACM. pp. 296–305. arXiv:cs/0111050. doi:10.1145/380752.380813. ISBN 978-1-58113-349-3. S2CID 1471.

[40] Dadush, Daniel; Huiberts, Sophie (2020-01-01). "सिंप्लेक्स विधि का एक अनुकूल चिकना विश्लेषण". SIAM Journal on Computing. 49 (5): STOC18–449. doi:10.1137/18M1197205. ISSN 0097-5397. S2CID 226351624.

[41] Terlaky, Tamás; Zhang, Shu Zhong (1993). "लीनियर प्रोग्रामिंग के लिए धुरी नियम: हाल के सैद्धांतिक विकास पर एक सर्वेक्षण". Annals of Operations Research. 46–47 (1): 203–233. CiteSeerX 10.1.1.36.7658. doi:10.1007/BF02096264. ISSN 0254-5330. MR 1260019. S2CID 6058077.

[42] Fukuda, Komei; Terlaky, Tamás (1997). Thomas M. Liebling; Dominique de Werra (eds.). "क्रिस-क्रॉस विधियाँ: धुरी एल्गोरिदम पर एक नया दृश्य". Mathematical Programming, Series B. Vol. 79, no. 1–3. Amsterdam: North-Holland Publishing. pp. 369–395. doi:10.1007/BF02614325. MR 1464775.

[43] Murty (1983, Chapter 3.20 (pp. 160–164) and pp. 168 and 179)

[44] Chapter five: Craven, B. D. (1988). Fractional programming. Sigma Series in Applied Mathematics. Vol. 4. Berlin: Heldermann Verlag. p. 145. ISBN 978-3-88538-404-5. MR 0949209.

[45] Kruk, Serge; Wolkowicz, Henry (1999). "स्यूडोलिनियर प्रोग्रामिंग". SIAM Review. 41 (4): 795–805. Bibcode:1999SIAMR..41..795K. CiteSeerX 10.1.1.53.7355. doi:10.1137/S0036144598335259. JSTOR 2653207. MR 1723002.

[46] Mathis, Frank H.; Mathis, Lenora Jane (1995). "अस्पताल प्रबंधन के लिए एक गैर-रेखीय प्रोग्रामिंग एल्गोरिदम". SIAM Review. 37 (2): 230–234. doi:10.1137/1037046. JSTOR 2132826. MR 1343214.

[47] Illés, Tibor; Szirmai, Ákos; Terlaky, Tamás (1999). "अतिशयोक्तिपूर्ण प्रोग्रामिंग के लिए परिमित क्रिस-क्रॉस विधि". European Journal of Operational Research. 114 (1): 198–214. CiteSeerX 10.1.1.36.7090. doi:10.1016/S0377-2217(98)00049-6. ISSN 0377-2217.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]

[33]

[34]

[35]

[36]

[37]

[38]

[39]

[40]

[41]

[42]

[43]

[44]

[45]

[46]

[47]

v t e Complementarity problems and algorithms
Complementarity Problems	Linear programming (LP) Quadratic programming (QP) Linear complementarity problem (LCP) Mixed linear (MLCP) Mixed (MCP) Nonlinear(NCP)
Basis-exchange algorithms	Simplex (Dantzig) Revised simplex Criss-cross Lemke

Anonymous

Search

सिम्प्लेक्स एल्गोरिथम: Difference between revisions

Namespaces

More

Page actions

Latest revision as of 14:33, 30 November 2022

Contents

इतिहास

अवलोकन

मानक रूप

सिम्प्लेक्स सारणी

ध्रुराग्र संक्रिया

कलनविधि

चर चयन प्रविष्टि

निकासीचर चयन

उदाहरण

एक प्रारंभिक विहित सारणी निष्कर्ष

उदाहरण

उन्नत विषय

कार्यान्वयन

विकृति: स्तंभन और चक्रण

निकृष्टतम स्थिति में दक्षता

वास्तविकता में दक्षता

अन्य कलनविधि

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

यह भी देखें

टिप्पणियाँ

संदर्भ

अग्रिम पठन

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

@@ Line 1: / Line 1: @@
 {{short description|Algorithm}}
-{{about|the linear programming algorithm|the non-linear optimization heuristic|Nelder–Mead method}}
+{{about|रैखिक प्रोग्रामिंग एल्गोरिथ्म|अरैखिक अनुकूलन अनुमानी|नेल्डर-मीड पद्धति}}
-<!-- {{Context|date=March 2012}} -->
-ऑप्टिमाइज़ेशन (गणित) में, जॉर्ज डेंटज़िग का सिंप्लेक्स एल्गोरिथम (या सिम्प्लेक्स विधि) रैखिक प्रोग्रामिंग के लिए एक लोकप्रिय एल्गोरिथम है।<ref name="Murty">{{cite book|last=Murty|first=Katta G.|author-link=Katta G. Murty|title=रैखिक प्रोग्रामिंग|publisher=John Wiley & Sons Inc.1, 2000 |url=http://www.computer.org/csdl/mags/cs/2000/01/c1022.html}}</ref>
+गणितीय अनुकूलन में, डेंटज़िग का '''सिम्प्लेक्स कलनविधि''' (एल्गोरिथम) (या '''सिंप्लेक्स विधि''') रैखिक प्रोग्रामिंग के लिए एक लोकप्रिय कलनविधि है।<ref name="Murty">{{cite book|last=Murty|first=Katta G.|author-link=Katta G. Murty|title=रैखिक प्रोग्रामिंग|publisher=John Wiley & Sons Inc.1, 2000 |url=http://www.computer.org/csdl/mags/cs/2000/01/c1022.html}}</ref>
-एल्गोरिथ्म का नाम एक सिम्प्लेक्स की अवधारणा से लिया गया है और थियोडोर मोत्ज़किन | टी द्वारा सुझाया गया था। एस मोत्ज़किन।<ref name="Murty22" >{{harvtxt|Murty|1983|loc=Comment 2.2}}</ref> सरलता का वास्तव में विधि में उपयोग नहीं किया जाता है, लेकिन इसकी एक व्याख्या यह है कि यह सरल शंकु (ज्यामिति) पर संचालित होता है, और ये एक अतिरिक्त बाधा के साथ उचित सरलता बन जाते हैं।<ref name="Murty39">{{harvtxt|Murty|1983|loc=Note 3.9}}</ref><ref name="StoneTovey">{{cite journal|last1=Stone|first1=Richard E.|last2=Tovey|first2=Craig A.|title=सिम्प्लेक्स और प्रोजेक्टिव स्केलिंग एल्गोरिदम को पुनरावृत्त रूप से कम से कम वर्ग विधियों के रूप में पुन: भारित किया जाता है|journal=SIAM Review|volume=33|year=1991|issue=2|pages=220–237
-|mr=1124362|jstor=2031142|doi=10.1137/1033049}}</ref><ref>{{cite journal|last1=Stone|first1=Richard E.|last2=Tovey|first2=Craig A.|title=इरेटम: सिम्पलेक्स और प्रोजेक्टिव स्केलिंग एल्गोरिथम पुनरावृत्त रूप से कम से कम वर्गों के तरीकों को फिर से भारित करता है|journal=SIAM Review|volume=33|year=1991|issue=3|pages=461|mr=1124362|doi=10.1137/1033100|jstor=2031443}}</ref><ref  name="Strang">{{cite journal|last=Strang|first=Gilbert|author-link=Gilbert Strang|title=कर्मकार का एल्गोरिथम और अनुप्रयुक्त गणित में इसका स्थान|journal=[[The Mathematical Intelligencer]]|date=1 June 1987|issn=0343-6993|pages=4–10|volume=9|doi=10.1007/BF03025891|mr=883185|issue=2|s2cid=123541868}}</ref> प्रश्न में साधारण शंकु एक ज्यामितीय वस्तु के कोने (यानी, कोने के पड़ोस) हैं जिन्हें पॉलीटोप कहा जाता है। इस पॉलीटॉप के आकार को ऑब्जेक्टिव फ़ंक्शन पर लागू रैखिक असमानताओं की प्रणाली द्वारा परिभाषित किया गया है।
+कलनविधि का नाम सिम्प्लेक्स की अवधारणा से लिया गया है और इसका सुझाव टी.एस. मोत्ज़किन ने दिया था।<ref name="Murty22">{{harvtxt|Murty|1983|loc=Comment 2.2}}</ref> वास्तव में इस पद्धति में सरलीकरण का उपयोग नहीं किया जाता है, परन्तु इसकी एक व्याख्या यह है कि यह सिम्प्लिसिअल ''शंकुओं'' पर कार्यकारी होता है, और ये अतिरिक्त अवरोध के साथ उचित सिम्प्लिसेज़ बन जाते हैं।<ref name="Murty39">{{harvtxt|Murty|1983|loc=Note 3.9}}</ref><ref name="StoneTovey">{{cite journal|last1=Stone|first1=Richard E.|last2=Tovey|first2=Craig A.|title=सिम्प्लेक्स और प्रोजेक्टिव स्केलिंग एल्गोरिदम को पुनरावृत्त रूप से कम से कम वर्ग विधियों के रूप में पुन: भारित किया जाता है|journal=SIAM Review|volume=33|year=1991|issue=2|pages=220–237
+|mr=1124362|jstor=2031142|doi=10.1137/1033049}}</ref><ref>{{cite journal|last1=Stone|first1=Richard E.|last2=Tovey|first2=Craig A.|title=इरेटम: सिम्पलेक्स और प्रोजेक्टिव स्केलिंग एल्गोरिथम पुनरावृत्त रूप से कम से कम वर्गों के तरीकों को फिर से भारित करता है|journal=SIAM Review|volume=33|year=1991|issue=3|pages=461|mr=1124362|doi=10.1137/1033100|jstor=2031443}}</ref><ref name="Strang">{{cite journal|last=Strang|first=Gilbert|author-link=Gilbert Strang|title=कर्मकार का एल्गोरिथम और अनुप्रयुक्त गणित में इसका स्थान|journal=[[The Mathematical Intelligencer]]|date=1 June 1987|issn=0343-6993|pages=4–10|volume=9|doi=10.1007/BF03025891|mr=883185|issue=2|s2cid=123541868}}</ref> प्रश्नगत सिम्प्लिसिअल शंकु एक ज्यामितीय वस्तु के कोने (अर्थात, शीर्ष के प्रतिवैस) होते हैं, जिसे पॉलीटोप कहा जाता है। इस पॉलीटॉप के आकार को उदेश्य फलन पर लागू बाध्यता (कंस्ट्रेंट्स) से परिभाषित किया गया है।
 == इतिहास ==
-जॉर्ज डेंटजिग ने द्वितीय विश्व युद्ध के दौरान डेस्क कैलकुलेटर का उपयोग करते हुए अमेरिकी सेना वायु सेना के लिए योजना बनाने के तरीकों पर काम किया। 1946 के दौरान उनके सहयोगी ने उन्हें दूसरी नौकरी लेने से विचलित करने के लिए नियोजन प्रक्रिया को यंत्रीकृत करने की चुनौती दी। डेंटज़िग ने वासिली लियोनटिफ़ के काम से प्रेरित रैखिक असमानताओं के रूप में समस्या को तैयार किया, हालाँकि, उस समय उन्होंने अपने सूत्रीकरण के हिस्से के रूप में एक उद्देश्य को शामिल नहीं किया था। एक उद्देश्य के बिना, बड़ी संख्या में समाधान संभव हो सकते हैं, और इसलिए सबसे अच्छा संभव समाधान खोजने के लिए, सैन्य-निर्दिष्ट जमीनी नियमों का उपयोग किया जाना चाहिए जो वर्णन करते हैं कि लक्ष्यों को कैसे प्राप्त किया जा सकता है, एक लक्ष्य को निर्दिष्ट करने के विपरीत। Dantzig की मुख्य अंतर्दृष्टि यह महसूस करना था कि ऐसे अधिकांश बुनियादी नियमों को एक रेखीय उद्देश्य समारोह में अनुवादित किया जा सकता है जिसे अधिकतम करने की आवश्यकता है।<ref>{{Cite journal|url = https://apps.dtic.mil/sti/pdfs/ADA112060.pdf|archive-url = https://web.archive.org/web/20150520183722/http://www.dtic.mil/cgi-bin/GetTRDoc?Location=U2&doc=GetTRDoc.pdf&AD=ADA112060|url-status = live|archive-date = May 20, 2015|title = रैखिक प्रोग्रामिंग की उत्पत्ति के बारे में यादें|date = April 1982|journal = Operations Research Letters|doi = 10.1016/0167-6377(82)90043-8|volume = 1|issue = 2 |pages=43–48|last1 = Dantzig|first1 = George B.}}</ref> सरल विधि का विकास विकासवादी था और लगभग एक वर्ष की अवधि में हुआ।<ref>{{Cite journal|url = http://www.phpsimplex.com/en/Dantzig_interview.htm|title = जॉर्ज बी. डेंट्ज़िग के साथ एक साक्षात्कार: रैखिक प्रोग्रामिंग के जनक|last = Albers and Reid|date = 1986|journal = College Mathematics Journal|volume = 17|issue = 4|doi = 10.1080/07468342.1986.11972971|pages = 292–314}}</ref>
+जॉर्ज डेंटजिग ने द्वितीय विश्व युद्ध के दौरान डेस्क परिकलित्र का उपयोग करते हुए अमेरिकी सेना वायु सेना के लिए नियोजन विधियों पर काम किया था। 1946 के दौरान उनके सहयोगी ने उन्हें दूसरी नौकरी लेने से विचलित करने के लिए योजना प्रक्रिया को मशीनीकृत करने की चुनौती दी थी। डेंटज़िग ने वासिली लियोनटिफ़ के काम से प्रेरित रैखिक असमानताओं के रूप में समस्या को तैयार किया, हालांकि, उस समय उन्होंने अपने सूत्रीकरण के अंश के रूप में एक उद्देश्य सम्मिलित नहीं किया था। किसी उद्देश्य के बिना, बड़ी संख्या में हल संभव हो सकते हैं, और इसलिए "सर्वश्रेष्ठ" साध्य हल खोजने के लिए, सैन्य-निर्दिष्ट "जमीनी नियम" का उपयोग किया जाना चाहिए जो वर्णन करता है कि लक्ष्यों को कैसे प्राप्त किया जा सकता है, एक लक्ष्य को निर्दिष्ट करने के विरोध में। डेंटज़िग की मुख्य अंतर्दृष्टि यह महसूस करना था कि इस तरह के अधिकांश मूल नियमों को एक रैखिक उद्देश्य फलन में अनुदित किया जा सकता है जिसे अधिकतम करने की आवश्यकता है।<ref>{{Cite journal|url = https://apps.dtic.mil/sti/pdfs/ADA112060.pdf|archive-url = https://web.archive.org/web/20150520183722/http://www.dtic.mil/cgi-bin/GetTRDoc?Location=U2&doc=GetTRDoc.pdf&AD=ADA112060|url-status = live|archive-date = May 20, 2015|title = रैखिक प्रोग्रामिंग की उत्पत्ति के बारे में यादें|date = April 1982|journal = Operations Research Letters|doi = 10.1016/0167-6377(82)90043-8|volume = 1|issue = 2 |pages=43–48|last1 = Dantzig|first1 = George B.}}</ref> सिम्पलेक्स विधि का विकास क्रमिक था और लगभग एक वर्ष की अवधि में हुआ था।<ref>{{Cite journal|url = http://www.phpsimplex.com/en/Dantzig_interview.htm|title = जॉर्ज बी. डेंट्ज़िग के साथ एक साक्षात्कार: रैखिक प्रोग्रामिंग के जनक|last = Albers and Reid|date = 1986|journal = College Mathematics Journal|volume = 17|issue = 4|doi = 10.1080/07468342.1986.11972971|pages = 292–314}}</ref>
-के मध्य में डेंटज़िग ने अपने सूत्रीकरण के हिस्से के रूप में एक उद्देश्य समारोह को शामिल करने के बाद, समस्या गणितीय रूप से अधिक सुगम थी। डेंटज़िग ने महसूस किया कि जॉर्ज डेंट्ज़िग#गणितीय सांख्यिकी को उनके प्रोफेसर जेरज़ी नेमैन की कक्षा में होमवर्क के रूप में (और वास्तव में बाद में हल किया गया) अनसुलझी समस्याओं में से एक, रैखिक कार्यक्रमों के लिए एक एल्गोरिथ्म खोजने के लिए लागू थी। इस समस्या में सामान्य रैखिक कार्यक्रमों के लिए बैनाच रिक्त स्थान पर लैग्रेंज मल्टीप्लायरों के अस्तित्व को खोजने में शामिल है, प्रत्येक शून्य और एक के बीच घिरा हुआ है, और लेबेसेग इंटीग्रल के रूप में व्यक्त रैखिक बाधाओं को संतुष्ट करता है। डेंटज़िग ने बाद में अपने डॉक्टरेट को अर्जित करने के लिए अपने होमवर्क को एक थीसिस के रूप में प्रकाशित किया। इस थीसिस में इस्तेमाल किए गए कॉलम ज्योमेट्री ने डेंटज़िग को अंतर्दृष्टि प्रदान की जिससे उन्हें विश्वास हो गया कि सिम्प्लेक्स विधि बहुत कुशल होगी।<ref>{{Cite encyclopedia|url = http://apps.dtic.mil/dtic/tr/fulltext/u2/a182708.pdf|archive-url = https://web.archive.org/web/20150529003047/http://www.dtic.mil/dtic/tr/fulltext/u2/a182708.pdf|url-status = live|archive-date = May 29, 2015|title = सिंप्लेक्स विधि की उत्पत्ति|last = Dantzig|first = George|date = May 1987|work = A History of Scientific Computing|editor-last=Nash|editor-first=Stephen G.|publisher=Association for Computing Machinery|pages = 141–151|doi = 10.1145/87252.88081|isbn = 978-0-201-50814-7}}</ref>
+के मध्य के दौरान डेंटज़िग ने अपने सूत्रीकरण के भाग के रूप में एक वस्तुनिष्ठ फलन को सम्मिलित करने के पश्चात, समस्या गणितीय रूप से अधिक सुगम हो गई। डेंटज़िग ने महसूस किया कि अनसुलझी समस्याओं में से एक जिसे उन्होंने अपने प्रोफेसर जेरज़ी नेमैन की कक्षा में होमवर्क के रूप में गलत समझा था (और वास्तव में पश्चात में हल हो गया), रैखिक फलनों के लिए एक एल्गोरिथ्म खोजने के लिए लागू था। इस समस्या में चरों की एक निरंतरता पर सामान्य रैखिक फलनों के लिए लग्रेंज मल्टीप्लायरों के अस्तित्व का पता लगाना सम्मिलित था, प्रत्येक शून्य और एक के बीच घिरा हुआ था, और लेबेसेग पूर्णांक के रूप में व्यक्त रैखिक बाध्यताओ (कंस्ट्रेंट्स) को संतुष्ट करता था। डेंटज़िग ने पश्चात में अपने "होमवर्क" को अपने डॉक्टरेट की कमाई के लिए एक अभिधारणा के रूप में प्रकाशित किया। इस अभिधारणा में प्रयुक्त स्तंभ (कॉलम) ज्यामिति ने डेंट्ज़िग अंतर्दृष्टि प्रदान की जिससे उन्हें विश्वास हो गया कि सिम्पलेक्स विधि बहुत कुशल होगी।<ref>{{Cite encyclopedia|url = http://apps.dtic.mil/dtic/tr/fulltext/u2/a182708.pdf|archive-url = https://web.archive.org/web/20150529003047/http://www.dtic.mil/dtic/tr/fulltext/u2/a182708.pdf|url-status = live|archive-date = May 29, 2015|title = सिंप्लेक्स विधि की उत्पत्ति|last = Dantzig|first = George|date = May 1987|work = A History of Scientific Computing|editor-last=Nash|editor-first=Stephen G.|publisher=Association for Computing Machinery|pages = 141–151|doi = 10.1145/87252.88081|isbn = 978-0-201-50814-7}}</ref>
 == अवलोकन ==
-{{further|Linear programming}}
+{{further|रैखिक प्रोग्रामिंग}}
-[[Image:Simplex-description-en.svg|thumb|240px|रैखिक असमानताओं की एक प्रणाली एक पॉलीटोप को एक व्यवहार्य क्षेत्र के रूप में परिभाषित करती है। सिंप्लेक्स एल्गोरिथ्म एक प्रारंभिक शीर्ष (ज्यामिति) से शुरू होता है और पॉलीटोप के किनारों के साथ चलता है जब तक कि यह शीर्ष तक नहीं पहुंच जाता
+[[Image:Simplex-description-en.svg|thumb|240px|रेखीय असमानताओं की एक प्रणाली एक पॉलीटोप को एक साध्य क्षेत्र के रूप में परिभाषित करती है। सिम्प्लेक्स कलनविधि प्रारंभिक शीर्ष पर शुरू होता है और पॉलीटॉप के किनारों के साथ चलता है जब तक कि यह इष्टतम हल के शीर्ष तक नहीं पहुंच जाता।]]
-इष्टतम समाधान का।]]
-[[Image:Simplex-method-3-dimensions.png|thumb|240px|3D . में सिम्प्लेक्स एल्गोरिथम का पॉलीहेड्रॉन]]सिम्प्लेक्स एल्गोरिथ्म विहित रूप में रैखिक कार्यक्रमों पर काम करता है
+[[Image:Simplex-method-3-dimensions.png|thumb|240px|3डी में सिम्पलेक्स कलनविधि का बहुफलक]]सिम्पलेक्स कलनविधि विहित रूप में रैखिक फलनों पर कार्यरत होता है
 :अधिकतम <math display="inline">\mathbf{c^T} \mathbf{x}</math>
-:का विषय है <math>A\mathbf{x} \leq \mathbf{b}</math> तथा <math>\mathbf{x} \ge 0</math>
+:<math>A\mathbf{x} \leq \mathbf{b}</math> तथा <math>\mathbf{x} \ge 0</math> के अधीन
-साथ <math>\mathbf{c} = (c_1,\, \dots,\, c_n)</math> उद्देश्य समारोह के गुणांक, <math>(\cdot)^\mathrm{T}</math> मैट्रिक्स स्थानांतरण है, और <math> \mathbf{x} = (x_1,\, \dots,\, x_n)</math> समस्या के चर हैं, <math>A</math> एक p×n मैट्रिक्स है, और <math> \mathbf{b} = (b_1,\, \dots,\, b_p)</math>. किसी भी रैखिक कार्यक्रम को मानक रूप में एक में बदलने की एक सीधी प्रक्रिया है, इसलिए रैखिक कार्यक्रमों के इस रूप का उपयोग करने से व्यापकता का कोई नुकसान नहीं होता है।
+<math>\mathbf{c} = (c_1,\, \dots,\, c_n)</math> के साथ उद्देश्य फलन के गुणांक, <math>(\cdot)^\mathrm{T}</math> आव्यूह पक्षांतर होता है, और <math> \mathbf{x} = (x_1,\, \dots,\, x_n)</math> समस्या के चर होते हैं, <math>A</math> एक  ''p''×''n'' आव्यूह है, और <math> \mathbf{b} = (b_1,\, \dots,\, b_p)</math> है। किसी भी रैखिक फलन को मानक रूप में एक में बदलने की एक स्पष्ट व सिम्पलेक्स प्रक्रिया है, इसलिए रैखिक फलनों के इस रूप का उपयोग करने से व्यापकता में कोई कमी नहीं आती है।
-ज्यामितीय शब्दों में, के सभी मूल्यों द्वारा परिभाषित व्यवहार्य क्षेत्र <math>\mathbf{x}</math> ऐसा है कि <math display="inline">A\mathbf{x} \le \mathbf{b}</math> तथा <math>\forall i, x_i \ge 0 </math> एक (संभवतः अबाधित) उत्तल पॉलीटॉप है। इस पॉलीटोप का एक चरम बिंदु या शीर्ष मूल व्यवहार्य समाधान (बीएफएस) के रूप में जाना जाता है।
+ज्यामितीय शब्दों में, <math>\mathbf{x}</math> के सभी मानों द्वारा परिभाषित साध्य क्षेत्र जैसे कि <math display="inline">A\mathbf{x} \le \mathbf{b}</math> और <math>\forall i, x_i \ge 0 </math> (संभवतः अबाधित) उत्तल पॉलीटोप है। इस पॉलीटॉप के चरम बिंदु या शीर्ष को ''मूल साध्य हल'' (बीएफएस) के रूप में जाना जाता है।
-यह दिखाया जा सकता है कि मानक रूप में एक रैखिक कार्यक्रम के लिए, यदि उद्देश्य फलन का व्यवहार्य क्षेत्र पर अधिकतम मान है, तो इसका यह मान (कम से कम) चरम बिंदुओं में से एक पर है।<ref>{{harvtxt|Murty|1983|loc=Theorem 3.3}}</ref> यह अपने आप में समस्या को एक सीमित गणना में कम कर देता है क्योंकि चरम बिंदुओं की एक सीमित संख्या होती है, लेकिन चरम बिंदुओं की संख्या सबसे छोटे रैखिक कार्यक्रमों के अलावा सभी के लिए असहनीय रूप से बड़ी होती है।<ref>{{harvtxt|Murty|1983|loc=Section 3.13|p=143}}</ref>
+यह दिखाया जा सकता है कि मानक रूप में एक रेखीय फलन के लिए, यदि उद्देश्य फलन का साध्य क्षेत्र पर अधिकतम मान है, तो इसका यह मान (कम से कम) चरम बिंदुओं में से एक पर है।<ref>{{harvtxt|Murty|1983|loc=Theorem 3.3}}</ref> यह अपने आप में समस्या को परिमित संगणना तक कम कर देता है क्योंकि चरम बिंदुओं की एक सीमित संख्या होती है, परन्तु चरम बिंदुओं की संख्या सबसे छोटे रैखिक फलनों के अतिरिक्त सभी के लिए असहनीय रूप से बड़ी होती है।<ref>{{harvtxt|Murty|1983|loc=Section 3.13|p=143}}</ref>
-यह भी दिखाया जा सकता है कि, यदि एक चरम बिंदु वस्तुनिष्ठ कार्य का अधिकतम बिंदु नहीं है, तो बिंदु से युक्त एक किनारा होता है, ताकि बिंदु से दूर जाने वाले किनारे पर वस्तुनिष्ठ फलन का मान सख्ती से बढ़ रहा हो।<ref name="Murty137">{{harvtxt|Murty|1983|loc=Section 3.8|p=137}}</ref> यदि किनारा परिमित है, तो किनारा दूसरे चरम बिंदु से जुड़ता है जहां उद्देश्य फलन का मान अधिक होता है, अन्यथा उद्देश्य फलन किनारे पर ऊपर की ओर असीमित होता है और रैखिक कार्यक्रम का कोई समाधान नहीं होता है। सिम्पलेक्स एल्गोरिथम अधिक से अधिक वस्तुनिष्ठ मूल्यों के साथ पॉलीटॉप के किनारों के साथ-साथ चरम बिंदुओं पर चलकर इस अंतर्दृष्टि को लागू करता है। यह तब तक जारी रहता है जब तक अधिकतम मूल्य तक नहीं पहुंच जाता है, या एक असीमित किनारे का दौरा नहीं किया जाता है (निष्कर्ष निकाला जाता है कि समस्या का कोई समाधान नहीं है)। एल्गोरिथम हमेशा समाप्त होता है क्योंकि पॉलीटॉप में शीर्षों की संख्या परिमित होती है; इसके अलावा चूंकि हम हमेशा एक ही दिशा (उद्देश्य फलन की दिशा) में शीर्षों के बीच कूदते हैं, हम आशा करते हैं कि देखे गए शीर्षों की संख्या कम होगी।<ref name="Murty137"/>
-एक रेखीय कार्यक्रम का समाधान दो चरणों में पूरा किया जाता है। पहले चरण में, चरण I के रूप में जाना जाता है, एक शुरुआती चरम बिंदु पाया जाता है। कार्यक्रम की प्रकृति के आधार पर यह तुच्छ हो सकता है, लेकिन सामान्य तौर पर इसे मूल कार्यक्रम के एक संशोधित संस्करण में सिम्पलेक्स एल्गोरिथम को लागू करके हल किया जा सकता है। प्रथम चरण के संभावित परिणाम या तो यह हैं कि एक बुनियादी व्यवहार्य समाधान मिल गया है या यह कि व्यवहार्य क्षेत्र खाली है। बाद के मामले में रैखिक कार्यक्रम को अव्यवहार्य कहा जाता है। दूसरे चरण में, द्वितीय चरण में, सरल एल्गोरिथम चरण I में प्रारंभिक बिंदु के रूप में पाए जाने वाले मूल व्यवहार्य समाधान का उपयोग करके लागू किया जाता है। चरण II से संभावित परिणाम या तो एक इष्टतम बुनियादी व्यवहार्य समाधान है या एक अनंत किनारा है जिस पर उद्देश्य फलन ऊपर असीमित है।<ref name="DantzigThapa1">[[George B. Dantzig]] and Mukund N. Thapa. 1997. ''Linear programming 1: Introduction''. Springer-Verlag.</ref><ref name="NeringTucker"/><ref name="Vanderbei">Robert J. Vanderbei, [http://www.princeton.edu/~rvdb/LPbook/ ''Linear Programming: Foundations and Extensions''], 3rd ed., International Series in Operations Research & Management Science, Vol. 114, Springer Verlag, 2008. {{isbn|978-0-387-74387-5}}. <!-- (An on-line second edition was formerly available. Vanderbei's site still contains extensive materials.) --></ref>
+यह भी दिखाया जा सकता है कि, यदि कोई चरम बिंदु वस्तुनिष्ठ कार्य का अधिकतम बिंदु नहीं है, तो बिंदु से युक्त एक किनारा होता है ताकि बिंदु से दूर जाने वाले किनारे पर वस्तुनिष्ठ कार्य का मान सख्ती से बढ़ रहा हो।<ref name="Murty137">{{harvtxt|Murty|1983|loc=Section 3.8|p=137}}</ref> यदि किनारा परिमित है, तो किनारा दूसरे चरम बिंदु से जुड़ता है जहां उद्देश्य फलन का मान अधिक होता है, अन्यथा उद्देश्य फलन किनारे पर ऊपर की ओर असंबद्ध होता है और रैखिक फलन का कोई हल नहीं होता है। सिम्पलेक्स कलनविधि अधिक से अधिक वस्तुनिष्ठ मूल्यों के साथ पॉलीटॉप के किनारों पर चरम बिंदुओं पर चलकर इस अंतर्दृष्टि को लागू करता है। यह तब तक जारी रहता है जब तक कि अधिकतम मूल्य तक नहीं पहुंच जाता है, या एक असीमित किनारे का दौरा नहीं किया जाता है (निष्कर्ष निकाला है कि समस्या का कोई हल नहीं है)। कलनविधि सदैव निलम्बित होता है क्योंकि पॉलीटॉप में शीर्षों की संख्या परिमित होती है; इसके अतिरिक्त चूंकि हम शीर्षों के बीच सदैव एक ही दिशा में स्थानांतरित होते हैं (उद्देश्य फलन की दिशा में), हम आशा करते हैं कि देखे गए शीर्षों की संख्या कम होगी।<ref name="Murty137" />
+एक रैखिक प्रोग्रामन का हल दो चरणों में पूर्ण होता है। प्रथम चरण में, जिसे अवस्था I के रूप में जाना जाता है, प्रारंभिक चरम बिंदु प्राप्त होता है। फलन की प्रकृति के आधार पर यह सतहीय (ट्राईवियल) हो सकता है, परन्तु सामान्यतः इसे मूल या आरंभिक फलन के संशोधित संस्करण में सिम्पलेक्स कलनविधि लागू करके हल किया जा सकता है। अवस्था I के दो संभावित परिणाम इस प्रकार हैं की या तो एक मूल साध्य हल प्राप्त हो गया है या यह कि साध्य क्षेत्र रिक्त है। पश्चात के स्थिति में रैखिक प्रोग्राम को असुसंगत कहा जाता है। द्वितीय चरण में, अवस्था II सिम्पलेक्स कलनविधि अवस्था I में प्रारंभिक बिंदु के रूप में मिले मूल साध्य हल का उपयोग करके लागू किया जाता है। अवस्था II से संभावित परिणाम या तो एक इष्टतम मूल साध्य हल है या एक अपरिमित किनारा है जिस पर ऊपर उद्देश्य फलन असीम है।<ref name="DantzigThapa1">[[George B. Dantzig]] and Mukund N. Thapa. 1997. ''Linear programming 1: Introduction''. Springer-Verlag.</ref><ref name="NeringTucker">
+Evar D. Nering and [[Albert W. Tucker]], 1993, ''Linear Programs and Related Problems'', Academic Press. (elementary<!-- but profound -->)</ref><ref name="Vanderbei">Robert J. Vanderbei, [http://www.princeton.edu/~rvdb/LPbook/ ''Linear Programming: Foundations and Extensions''], 3rd ed., International Series in Operations Research & Management Science, Vol. 114, Springer Verlag, 2008. {{isbn|978-0-387-74387-5}}. <!-- (An on-line second edition was formerly available. Vanderbei's site still contains extensive materials.) --></ref>
 == मानक रूप ==
-एक रेखीय कार्यक्रम का मानक रूप में एक में रूपांतरण निम्नानुसार पूरा किया जा सकता है।<ref>{{harvtxt|Murty|1983|loc=Section 2.2}}</ref> सबसे पहले, प्रत्येक चर के लिए 0 के अलावा निचली सीमा के साथ, एक नया चर पेश किया जाता है जो चर और बाध्य के बीच के अंतर का प्रतिनिधित्व करता है। मूल चर को तब प्रतिस्थापन द्वारा समाप्त किया जा सकता है। उदाहरण के लिए, बाधा को देखते हुए
+रेखीय फलन को एक मानक रूप में बदलना निम्नानुसार प्रमाणित किया जा सकता है।<ref>{{harvtxt|Murty|1983|loc=Section 2.2}}</ref> सर्व प्रथम, प्रत्येक चर के लिए 0 के अतिरिक्त निम्न सीमा के साथ, एक नवीन चर प्रस्तुत किया जाता है जो चर और सीमांकन के बीच के अंतर को दर्शाता है। तब मूल चर को प्रतिस्थापन द्वारा समाप्त किया जा सकता है। उदाहरण के लिए, दी गई बाध्यता (कन्सट्रैन्ट)
 :<math>x_1 \ge 5</math>
-एक नया चर, <math>y_1</math>, के साथ पेश किया गया है
+नवीन चर, <math>y_1</math>, के साथ प्रस्तुत किया गया है
 :<math> \begin{align} y_1 = x_1 - 5\\x_1 = y_1 + 5 \end{align}</math>
-दूसरे समीकरण का उपयोग समाप्त करने के लिए किया जा सकता है <math>x_1</math> रैखिक कार्यक्रम से। इस तरह, सभी निचली बाध्य बाधाओं को गैर-नकारात्मकता प्रतिबंधों में बदला जा सकता है।
+दूसरे समीकरण का उपयोग रेखीय फलन से <math>x_1</math> को निष्कासित करने के लिए किया जा सकता है। इस प्रकार, सभी निम्न सीमा बाध्यताओं (कंस्ट्रेंट्स) को अऋणात्मक बाध्यताओं (कंस्ट्रेंट्स) में परिवर्तित जा सकता है।
-दूसरा, प्रत्येक शेष असमानता बाधा के लिए, एक नया चर, जिसे ढीला चर कहा जाता है, बाधा को समानता बाधा में बदलने के लिए पेश किया जाता है। यह चर असमानता के दो पक्षों के बीच अंतर का प्रतिनिधित्व करता है और इसे गैर-नकारात्मक माना जाता है। उदाहरण के लिए, असमानताएँ
+दूसरा, प्रत्येक शेष असमानता बाध्यता (कंस्ट्रेंट्) के लिए, एक नया चर, जिसे ''न्यूनतापूरक चर'' कहा जाता है, बाध्यता (कन्सट्रैन्ट) को एक समानता बाध्यता (कन्सट्रैन्ट) में बदलने के लिए प्रस्तुत किया जाता है। यह चर असमानता के दो पक्षों के बीच के अंतर को दर्शाता है और इसे अऋणात्मक माना जाता है। उदाहरण के लिए, विषमताएँ
 :<math> \begin{align}
    x_2 + 2x_3 &\le 3\\
@@ Line 48: / Line 47: @@
    s_1,\, s_2 &\ge 0
 \end{align}</math>
-इस रूप में असमानताओं पर बीजगणितीय हेरफेर करना बहुत आसान है। असमानताओं में जहां ≥ दूसरे के रूप में प्रकट होता है, कुछ लेखक चर के रूप में पेश किए गए चर का उल्लेख करते हैं {{anchor|Surplus variable}}अधिशेष चर।
+इस रूप में असमानताओं पर बीजगणितीय जोड़-तोड़ करना बहुत आसान है। असमानताओं में जहां ≥ दूसरे वाले के रूप में प्रकट होता है, कुछ लेखक ''आधिक्यचर'' के रूप में प्रस्तुत किए गए चर का उल्लेख करते हैं।
-तीसरा, प्रत्येक अप्रतिबंधित चर को रैखिक कार्यक्रम से हटा दिया जाता है। यह दो तरीकों से किया जा सकता है, एक है चर के लिए समीकरणों में से किसी एक में हल करके और फिर प्रतिस्थापन द्वारा चर को समाप्त करना। दूसरा चर को दो प्रतिबंधित चर के अंतर से बदलना है। उदाहरण के लिए, अगर <math>z_1</math> अप्रतिबंधित है तो लिखो
+तीसरा, प्रत्येक अप्रतिबंधित चर को रैखिक प्रोग्राम से हटा दिया जाता है। यह दो तरीकों से किया जा सकता है, एक है चर के लिए समीकरणों में से किसी एक में हल करके और फिर प्रतिस्थापन द्वारा चर को समाप्त करना। अन्य चर को दो प्रतिबंधित चर के अंतर से बदलना है। उदाहरण के लिए, यदि <math>z_1</math> अप्रतिबंधित है, तो लिखिए
 :<math>\begin{align}
    &z_1 = z_1^+ - z_1^-\\
    &z_1^+,\, z_1^- \ge 0
 \end{align}</math>
-समीकरण को खत्म करने के लिए इस्तेमाल किया जा सकता है <math>z_1</math> रैखिक कार्यक्रम से।
+रैखिक फलन से <math>z_1</math> को निष्कासित करने के लिए समीकरण का उपयोग किया जा सकता है।
-जब यह प्रक्रिया पूरी हो जाएगी तो सम्भाव्य क्षेत्र के रूप में होगा
+जब यह प्रक्रिया पूरी हो जाती है तो साध्य क्षेत्र के रूप में हो जाएगा
 :<math>\mathbf{A}\mathbf{x} = \mathbf{b},\, \forall i \ x_i \ge 0</math>
-यह मान लेना भी उपयोगी है कि की रैंक <math>\mathbf{A}</math> पंक्तियों की संख्या है। इसके परिणामस्वरूप सामान्यता का कोई नुकसान नहीं होता है अन्यथा या तो प्रणाली <math>\mathbf{A}\mathbf{x} = \mathbf{b}</math> निरर्थक समीकरण हैं जिन्हें छोड़ा जा सकता है, या सिस्टम असंगत है और रैखिक कार्यक्रम का कोई समाधान नहीं है।<ref>{{harvtxt|Murty|1983|p=173}}</ref>
+यह मान लेना भी उपयोगी है कि <math>\mathbf{A}</math> की कोटि पंक्तियों की संख्या है। इसका परिणाम सामान्यता में कोई कमी नहीं है क्योंकि अन्यथा या तो सिस्टम <math>\mathbf{A}\mathbf{x} = \mathbf{b}</math> में आधिक्य समीकरण हैं जिन्हें छोड़ा जा सकता है, या सिस्टम असंगत है और रैखिक प्रोग्राम का कोई हल नहीं है।<ref>{{harvtxt|Murty|1983|p=173}}</ref>
+== सिम्प्लेक्स सारणी ==
+मानक रूप में एक रेखीय फलन को निम्न रूप की ''सारणी'' के रूप में दर्शाया जा सकता है
-== सिम्प्लेक्स झांकी ==
-मानक रूप में एक रेखीय कार्यक्रम को प्रपत्र की झांकी के रूप में दर्शाया जा सकता है
 :<math>
    \begin{bmatrix}
@@ Line 70: / Line 67: @@
    \end{bmatrix}
 </math>
-पहली पंक्ति उद्देश्य फलन को परिभाषित करती है और शेष पंक्तियाँ व्यवरोधों को निर्दिष्ट करती हैं। पहले कॉलम में शून्य वेक्टर बी के समान आयाम के शून्य वेक्टर का प्रतिनिधित्व करता है (विभिन्न लेखक सटीक लेआउट के रूप में विभिन्न सम्मेलनों का उपयोग करते हैं)। यदि ए के स्तंभों को पुनर्व्यवस्थित किया जा सकता है ताकि इसमें ऑर्डर पी (ए में पंक्तियों की संख्या) की पहचान मैट्रिक्स हो, तो झांकी को विहित रूप में कहा जाता है।<ref>{{harvtxt|Murty|1983|loc=section 2.3.2}}</ref> पहचान मैट्रिक्स के कॉलम से संबंधित चर को मूल चर कहा जाता है जबकि शेष चर को गैर-मूल या मुक्त चर कहा जाता है। यदि गैर-मूल चरों के मान 0 पर सेट हैं, तो मूल चर के मान आसानी से बी में प्रविष्टियों के रूप में प्राप्त किए जाते हैं और यह समाधान एक बुनियादी व्यवहार्य समाधान है। यहां बीजगणितीय व्याख्या यह है कि प्रत्येक पंक्ति द्वारा दर्शाए गए रैखिक समीकरण के गुणांक या तो हैं <math>0</math>, <math>1</math>, या कोई अन्य संख्या। प्रत्येक पंक्ति में होगा <math>1</math> मूल्य के साथ स्तंभ <math>1</math>, <math>p-1</math> गुणांक वाले कॉलम <math>0</math>, और शेष कॉलम कुछ अन्य गुणांकों के साथ (ये अन्य चर हमारे गैर-मूल चर का प्रतिनिधित्व करते हैं)। गैर-मूल चर के मान को शून्य पर सेट करके हम प्रत्येक पंक्ति में यह सुनिश्चित करते हैं कि चर का मान a द्वारा दर्शाया गया है <math>1</math> इसके कॉलम में के बराबर है <math>b</math> उस पंक्ति पर मूल्य।
+सरणी की प्रथम पंक्ति उद्देश्य फलन को परिभाषित करती है और शेष पंक्तियाँ बाध्यताओं (कंस्ट्रेंट्स) को निर्दिष्ट करती हैं। प्रथम स्तंभ में शून्य सदिश ''b'' के समान आयाम के शून्य सदिश का प्रतिनिधित्व करता है (विभिन्न लेखक अलग-अलग सम्मेलनों का उपयोग यथार्थ अनुविक्षेप के रूप में करते हैं)। यदि A के स्तंभों को पुनर्व्यवस्थित किया जा सकता है ताकि इसमें क्रम ''p'' (A में पंक्तियों की संख्या) का तत्समक (आइडेंटिटी) आव्यूह हो, तो सारणी ''विहित (कैनोनिकल) रूप'' में होती है।<ref>{{harvtxt|Murty|1983|loc=section 2.3.2}}</ref> तत्समक आव्यूह के स्तंभ से संबंधित चरों को ''मूल चरों'' कहा जाता है जबकि बाकी चरों को ''गैर-मूल या मुक्त चर'' कहा जाता है। यदि गैर-मूल चर के मान 0 पर सेट हैं, तो मूल चर के मान आसानी से ''b'' में प्रविष्टियों के रूप में प्राप्त किए जाते हैं और यह हल एक मूल साध्य हल है। यहाँ बीजीय व्याख्या यह है कि प्रत्येक पंक्ति द्वारा दर्शाए गए रैखिक समीकरण के गुणांक या तो <math>0</math>, <math>1</math>, या कोई अन्य संख्या हैं। प्रत्येक पंक्ति में <math>1</math> मान के साथ <math>1</math> स्तंभ होंगे, गुणांक <math>p-1</math> के साथ <math>0</math> स्तंभ होंगे, और शेष स्तंभ कुछ अन्य गुणांक के साथ होंगे (ये अन्य चर हमारे गैर-मूल चर का प्रतिनिधित्व करते हैं)। गैर-मूल चर के मानों को शून्य पर सेट करके हम प्रत्येक पंक्ति में यह सुनिश्चित करते हैं कि उसके स्तंभ में <math>1</math> द्वारा दर्शाए गए चर का मान उस पंक्ति के <math>b</math> मान के बराबर है।
-इसके विपरीत, एक बुनियादी व्यवहार्य समाधान दिया गया है, गैर-शून्य चर के अनुरूप स्तंभों को एक गैर-एकवचन मैट्रिक्स में विस्तारित किया जा सकता है। यदि संबंधित झांकी को इस मैट्रिक्स के व्युत्क्रम से गुणा किया जाता है तो परिणाम कैनोनिकल रूप में एक झांकी है।<ref>{{harvtxt|Murty|1983|loc=section 3.12}}</ref>
+इसके विपरीत, एक मूल साध्य हल दिया गया है, अशून्य चर के अनुरूप स्तंभ को एक व्युत्क्रमणीय आव्यूह तक विस्तारित किया जा सकता है। यदि संबंधित सारणी को इस आव्यूह के व्युत्क्रम से गुणा किया जाता है तो परिणाम विहित रूप में एक सारणी है।<ref>{{harvtxt|Murty|1983|loc=section 3.12}}</ref>
-होने देना
+माना
 :<math>
    \begin{bmatrix}
@@ Line 80: / Line 78: @@
    \end{bmatrix}
 </math>
-विहित रूप में एक झाँकी हो। अतिरिक्त प्राथमिक मैट्रिक्स # पंक्ति-जोड़ परिवर्तन | गुणांक को हटाने के लिए पंक्ति-जोड़ परिवर्तन लागू किए जा सकते हैं {{SubSup|'''c'''|''B''|T|s=0}} उद्देश्य समारोह से। इस प्रक्रिया को प्राइसिंग आउट कहा जाता है और इसका परिणाम एक प्रामाणिक झांकी में होता है
+ऊपर विहित रूप में एक सारणी प्रदर्शित की गई है। उद्देश्य फलन से गुणांक {{SubSup|'''c'''|''B''|T|s=0}} को हटाने के लिए अतिरिक्त पंक्ति-जोड़ परिवर्तन लागू किए जा सकते हैं। इस प्रक्रिया को ''मूल्य निर्धारण'' (''प्राइसिंग आउट'') कहा जाता है और इसका परिणाम एक प्रामाणिक सारणी के रूप में सामने आता है
 :<math>
    \begin{bmatrix}
@@ Line 87: / Line 85: @@
    \end{bmatrix}
 </math>
-जहां जेड<sub>''B''</sub> संबंधित मूल व्यवहार्य समाधान पर उद्देश्य फ़ंक्शन का मान है। अद्यतन गुणांक, जिसे सापेक्ष लागत गुणांक के रूप में भी जाना जाता है, गैर-मूल चर के संबंध में उद्देश्य फ़ंक्शन के परिवर्तन की दर है।<ref name="NeringTucker" >
+जहां ''z<sub>B</sub>'' संबंधित मूल साध्य हल पर उद्देश्य फलन का मान है। अद्यतित गुणांक, जिसे ''सापेक्ष लागत गुणांक'' के रूप में भी जाना जाता है, गैर मूल चर के संबंध में उद्देश्य फलन के परिवर्तन की दरें हैं।<ref name="NeringTucker" />
-Evar D. Nering and [[Albert W. Tucker]], 1993, ''Linear Programs and Related Problems'', Academic Press. (elementary<!-- but profound -->)</ref>
+== ध्रुराग्र संक्रिया ==
+मूल साध्य हल से आसन्न मूल साध्य हल में जाने का ज्यामितीय संक्रिया एक ''ध्रुराग्र संक्रिया'' के रूप में लागू किया जाता है। सर्व प्रथम, एक अशून्य ध्रुराग्र तत्व को एक गैर-मूल स्तंभ में चुना जाता है। इस तत्व वाली पंक्ति को इस तत्व को 1 में बदलने के लिए इसके व्युत्क्रम से गुणा किया जाता है, और फिर स्तंभ में अन्य प्रविष्टियों को 0 में बदलने के लिए पंक्ति के गुणकों को दूसरी पंक्तियों में जोड़ा जाता है। परिणाम यह है कि, यदि पिवोट तत्व एक पंक्ति ''r'' में है, तो स्तंभ तत्समक आव्यूह का ''r''-वें स्तंभ बन जाता है। इस स्तंभ के लिए चर अब एक मूल चर है, चर की जगह जो संक्रिया से पहले तत्समक आव्यूह के ''r''-वें स्तंभ के अनुरूप था। वास्तव में, ध्रुराग्र स्तंभ से संबंधित चर मूल चर के सेट में प्रवेश करता है और इसे ''प्रविष्ट चर'' कहा जाता है, और जिस चर को प्रतिस्थापित किया जा रहा है वह मूल चर के सेट को छोड़ देता है और इसे ''निकासीचर'' कहा जाता है। सारणी अभी भी विहित रूप में है परन्तु मूल चर के सेट के साथ एक तत्व बदल गया है।<ref name="DantzigThapa1"/><ref name="NeringTucker"/>
+== कलनविधि ==
+माना विहित सरणी द्वारा दिया गया रैखिक प्रोग्राम है। सिम्पलेक्स कलनविधि उत्तरोत्तर ध्रुराग्र संक्रिया करके आगे बढ़ता है, जिनमें से प्रत्येक एक बेहतर मूल साध्य हल देता है; प्रत्येक चरण में ध्रुराग्र तत्व का चयन काफी हद तक इस आवश्यकता से निर्धारित होता है कि यह ध्रुराग्र हल को बेहतर बनाती है।
+=== चर चयन प्रविष्टि ===
+चूंकि प्रवेश करने वाला चर, सामान्य रूप से, 0 से एक धनात्मक संख्या तक बढ़ जाता है, यदि इस चर के संबंध में उद्देश्य फलन का व्युत्पन्न नकारात्मक है, तो उद्देश्य फलन का मान घट जाएगा। समतुल्य रूप से, यदि ध्रुराग्र स्तंभ का चयन किया जाता है, तो उद्देश्य फलन का मान बढ़ जाता है ताकि सारणी की उद्देश्य पंक्ति में संबंधित प्रविष्टि धनात्मक हो।
-== धुरी संचालन ==
+यदि एक से अधिक स्तंभ हैं ताकि कर्मकारक पंक्ति में प्रविष्टि धनात्मक हो तो मूल चर के सेट में से किसे जोड़ना है इसका चयन कुछ मनमाना है और कई ''चर विकल्प नियम प्रविष्टि''<ref name="Murty66">{{harvtxt|Murty|1983|p=66}}</ref> जैसे डेवेक्स कलनविधि<ref>Harris, Paula MJ. "Pivot selection methods of the Devex LP code." Mathematical programming 5.1 (1973): 1–28</ref> विकसित किए गए हैं।
-बुनियादी व्यवहार्य समाधान से आसन्न बुनियादी व्यवहार्य समाधान में जाने का ज्यामितीय संचालन एक पिवट ऑपरेशन के रूप में कार्यान्वित किया जाता है। सबसे पहले, एक नॉनज़रो पिवट एलिमेंट को नॉनबेसिक कॉलम में चुना जाता है। इस तत्व से युक्त पंक्ति इस तत्व को 1 में बदलने के लिए इसके पारस्परिक द्वारा प्राथमिक मैट्रिक्स # पंक्ति-गुणा परिवर्तन है, और फिर स्तंभ में अन्य प्रविष्टियों को 0. में बदलने के लिए पंक्ति के गुणकों को अन्य पंक्तियों में जोड़ा जाता है। परिणाम यह है कि , यदि धुरी तत्व एक पंक्ति r में है, तो स्तंभ पहचान मैट्रिक्स का r-th स्तंभ बन जाता है। इस स्तंभ के लिए चर अब एक मूल चर है, चर की जगह जो ऑपरेशन से पहले पहचान मैट्रिक्स के आर-वें कॉलम के अनुरूप था। वास्तव में, धुरी स्तंभ से संबंधित चर मूल चर के सेट में प्रवेश करता है और इसे प्रवेश चर कहा जाता है, और जिस चर को प्रतिस्थापित किया जा रहा है वह मूल चर के सेट को छोड़ देता है और इसे छोड़ने वाला चर कहा जाता है। झांकी अभी भी विहित रूप में है लेकिन मूल चर के सेट के साथ एक तत्व द्वारा बदल दिया गया है।<ref name="DantzigThapa1"/><ref name="NeringTucker"/>
+यदि कर्मकारक पंक्ति में सभी प्रविष्टियाँ 0 से कम या उसके बराबर हैं तो चर में प्रवेश करने का कोई विकल्प नहीं बनाया जा सकता है और हल वास्तव में इष्टतम है। यह आसानी से इष्टतम माना जाता है क्योंकि कर्मकारक पंक्ति अब प्रपत्र के एक समीकरण से मेल खाती है
-== एल्गोरिथम ==
-चलो एक रैखिक कार्यक्रम एक विहित झांकी द्वारा दिया जाता है। सिम्पलेक्स एल्गोरिथम लगातार पिवट संचालन करके आगे बढ़ता है, जिनमें से प्रत्येक एक बेहतर बुनियादी व्यवहार्य समाधान देता है; प्रत्येक चरण में धुरी तत्व का चुनाव काफी हद तक इस आवश्यकता से निर्धारित होता है कि यह धुरी समाधान में सुधार करती है।
-=== चर चयन दर्ज करना ===
-चूंकि प्रवेश करने वाला चर, सामान्य रूप से, 0 से एक सकारात्मक संख्या तक बढ़ जाएगा, यदि इस चर के संबंध में उद्देश्य फ़ंक्शन का व्युत्पन्न ऋणात्मक है, तो उद्देश्य फ़ंक्शन का मान घट जाएगा। समतुल्य रूप से, यदि धुरी स्तंभ का चयन किया जाता है, तो वस्तुनिष्ठ फ़ंक्शन का मान बढ़ जाता है ताकि झांकी की उद्देश्य पंक्ति में संबंधित प्रविष्टि सकारात्मक हो।
-यदि एक से अधिक कॉलम हैं ताकि वस्तुनिष्ठ पंक्ति में प्रविष्टि सकारात्मक हो तो मूल चर के सेट में किस एक को जोड़ना है इसका चुनाव कुछ हद तक मनमाना है और कई चर चयन नियम दर्ज करना<ref name="Murty66">{{harvtxt|Murty|1983|p=66}}</ref> जैसे डेवेक्स एल्गोरिथम<ref>Harris, Paula MJ. "Pivot selection methods of the Devex LP code." Mathematical programming 5.1 (1973): 1–28</ref> विकसित किया गया है।
-यदि वस्तुनिष्ठ पंक्ति में सभी प्रविष्टियाँ 0 से कम या उसके बराबर हैं तो चर में प्रवेश करने का कोई विकल्प नहीं बनाया जा सकता है और समाधान वास्तव में इष्टतम है। इसे आसानी से इष्टतम माना जाता है क्योंकि उद्देश्य पंक्ति अब फॉर्म के समीकरण से मेल खाती है
 :<math>z(\mathbf{x})=z_B+\text{non - positive terms corresponding to non - basic variables}</math>
-एंट्री वेरिएबल चॉइस रूल को बदलकर ताकि यह एक कॉलम का चयन करे जहां ऑब्जेक्टिव रो में एंट्री नेगेटिव है, एल्गोरिथ्म को बदल दिया जाता है ताकि यह अधिकतम के बजाय ऑब्जेक्टिव फ़ंक्शन का न्यूनतम पता लगा सके।
+चर विकल्प नियम प्रविष्टि को बदलकर ताकि यह एक स्तंभ का चयन करे जहां कर्मकारक पंक्ति में प्रविष्टि ऋणात्मक होती है, कलनविधि को बदल दिया जाता है ताकि यह अधिकतम के बजाय उद्देश्य फलन का न्यूनतम पता लगा सके।
-=== परिवर्तनीय चयन छोड़ना ===
+=== निकासीचर चयन ===
-एक बार पिवट कॉलम का चयन करने के बाद, पिवट पंक्ति का चुनाव काफी हद तक इस आवश्यकता से निर्धारित होता है कि परिणामी समाधान व्यवहार्य हो। सबसे पहले, पिवट कॉलम में केवल सकारात्मक प्रविष्टियों पर विचार किया जाता है क्योंकि यह गारंटी देता है कि प्रवेश करने वाले चर का मान गैर-ऋणात्मक होगा। यदि पिवट कॉलम में कोई सकारात्मक प्रविष्टियाँ नहीं हैं, तो प्रवेश करने वाला चर कोई भी गैर-ऋणात्मक मान ले सकता है, जिसका समाधान संभव है। इस मामले में उद्देश्य समारोह नीचे असीमित है और कोई न्यूनतम नहीं है।
+एक बार ध्रुराग्र स्तंभ का चयन हो जाने के पश्चात, ध्रुराग्र पंक्ति का चयन मोटे तौर पर इस आवश्यकता से निर्धारित होता है कि परिणामी हल संभव हो। सर्व प्रथम, ध्रुराग्र स्तंभ में केवल धनात्मक प्रविष्टियों पर विचार किया जाता है क्योंकि यह गारंटी देता है कि प्रवेश चर का मान अऋणात्मक होगा। यदि ध्रुराग्र स्तंभ में कोई धनात्मक प्रविष्टियां नहीं हैं, तो प्रवेश करने वाला चर कोई भी गैर-ऋणात्मक मान ले सकता है, जिसका हल साध्य रहता है। इस स्थिति में वस्तुनिष्ठ फलन नीचे असीमित है और कोई न्यूनतम नहीं है।
-इसके बाद, धुरी पंक्ति का चयन किया जाना चाहिए ताकि अन्य सभी बुनियादी चर सकारात्मक बने रहें। एक गणना से पता चलता है कि यह तब होता है जब प्रवेश करने वाले चर का परिणामी मूल्य न्यूनतम होता है। दूसरे शब्दों में, यदि पिवट कॉलम c है, तो पिवट रो r को चुना जाता है ताकि
+इसके पश्चात, ध्रुराग्र पंक्ति का चयन किया जाना चाहिए ताकि अन्य सभी मूल चर धनात्मक बने रहें। एक गणना से पता चलता है कि ऐसा तब होता है जब प्रवेश करने वाले चर का परिणामी मूल्य न्यूनतम होता है। दूसरे शब्दों में, यदि ध्रुराग्र स्तंभ ''c'' है, तो ध्रुराग्र पंक्ति ''r'' को चुना जाता है ताकि
 :<math>b_r / a_{rc}\,</math>
-सभी r पर न्यूनतम है ताकि a<sub>''rc''</sub> > 0. इसे न्यूनतम अनुपात परीक्षण कहते हैं।<ref name="Murty66"/>यदि एक से अधिक पंक्तियाँ हैं जिनके लिए न्यूनतम प्राप्त किया गया है तो ड्रॉपिंग वेरिएबल चॉइस रूल<ref>{{harvtxt|Murty|1983|p=67}}</ref> निर्धारण करने के लिए उपयोग किया जा सकता है।
+सभी ''r'' पर न्यूनतम है ताकि ''a<sub>rc</sub>'' > 0 हो। इसे ''न्यूनतम अनुपात परीक्षण'' कहते हैं।<ref name="Murty66"/> यदि एक से अधिक पंक्तियाँ है जिसके लिए न्यूनतम मान प्राप्त किया जाता है तो निर्धारण करने के लिए ''पातन चर विकल्प नियम''<ref>{{harvtxt|Murty|1983|p=67}}</ref> का उपयोग किया जा सकता है।
 === उदाहरण ===
-{{see also|Revised simplex algorithm#Numerical example}}
+{{see also|संशोधित सिम्पलेक्स कलनविधि#संख्यात्मक उदाहरण}}
-रैखिक कार्यक्रम पर विचार करें
-:छोटा करना
+रैखिक प्रोग्राम पर विचार करें
+:न्यूनतमीकरण
 ::<math>Z = -2 x - 3 y - 4 z\,</math>
-:का विषय है
+:के अधीन
 ::<math>\begin{align}
 x + 2 y + z &\le 10\\
@@ Line 125: / Line 119: @@
    x,\,y,\,z &\ge 0
 \end{align}</math>
-सुस्त चर s और t के योग के साथ, यह विहित झांकी द्वारा दर्शाया गया है
+न्यूनतापूरक चर ''s'' और ''t'' के जोड़ के साथ, यह विहित सारणी द्वारा दर्शाया गया है
 :<math>
    \begin{bmatrix}
@@ Line 133: / Line 127: @@
    \end{bmatrix}
 </math>
-जहां कॉलम 5 और 6 मूल चर s और t का प्रतिनिधित्व करते हैं और संबंधित मूल व्यवहार्य समाधान है
+जहां स्तंभ 5 और 6 मूल चर s और t का प्रतिनिधित्व करते हैं और संबंधित मूल साध्य हल है
 :<math>x=y=z=0,\,s=10,\,t=15.</math>
-कॉलम 2, 3 और 4 को पिवट कॉलम के रूप में चुना जा सकता है, इस उदाहरण के लिए कॉलम 4 का चयन किया गया है। पिवट पंक्तियों के रूप में पंक्तियों 2 और 3 के चुनाव के परिणामस्वरूप z के मान क्रमशः 10/1 = 10 और 15/3 = 5 हैं। इनमें से न्यूनतम 5 है, इसलिए पंक्ति 3 धुरी पंक्ति होनी चाहिए। धुरी का प्रदर्शन उत्पादन करता है
+स्तंभ 2, 3 और 4 को ध्रुराग्र स्तंभ के रूप में चुना जा सकता है, इस उदाहरण के लिए स्तंभ 4 को चुना गया है। पंक्ति 2 और 3 को ध्रुराग्र पंक्तियों के रूप में चुनने से उत्पन्न ''z'' के मान क्रमशः 10/1 = 10 और 15/3 = 5 हैं। इनमें से कम से कम 5 है, इसलिए पंक्ति 3 को ध्रुराग्र पंक्ति होना चाहिए। ध्रुराग्र का प्रदर्शन करता है
 :<math>
    \begin{bmatrix}
@@ Line 143: / Line 137: @@
    \end{bmatrix}
 </math>
-अब कॉलम 4 और 5 मूल चर z और s का प्रतिनिधित्व करते हैं और संबंधित बुनियादी व्यवहार्य समाधान है
+अब स्तंभ 4 और 5 मूल चर z और s का प्रतिनिधित्व करते हैं और संबंधित मूल साध्य हल है
 :<math>x=y=t=0,\,z=5,\,s=5.</math>
-अगले चरण के लिए, वस्तुनिष्ठ पंक्ति में कोई सकारात्मक प्रविष्टि नहीं है और वास्तव में
+अगले चरण के लिए, कर्मकारक पंक्ति में कोई धनात्मक प्रविष्टि नहीं है और वास्तव में
 :<math>Z = \frac{-60+2x+11y+4t}{3} = -20 + \frac{2x+11y+4t}{3}</math>
 इसलिए Z का न्यूनतम मान −20 है।
-== एक प्रारंभिक विहित झांकी ढूँढना ==
-सामान्य तौर पर, एक रेखीय कार्यक्रम विहित रूप में नहीं दिया जाएगा और सिम्पलेक्स एल्गोरिथम शुरू होने से पहले एक समकक्ष विहित झांकी मिलनी चाहिए। यह कृत्रिम चरों की शुरूआत के द्वारा पूरा किया जा सकता है। पहचान मैट्रिक्स के कॉलम इन चरों के लिए कॉलम वैक्टर के रूप में जोड़े जाते हैं। यदि एक बाधा समीकरण के लिए b मान ऋणात्मक है, तो पहचान मैट्रिक्स कॉलम जोड़ने से पहले समीकरण को नकार दिया जाता है। यह व्यवहार्य समाधान या इष्टतम समाधान के सेट को नहीं बदलता है, और यह सुनिश्चित करता है कि ढीले चर प्रारंभिक व्यवहार्य समाधान का गठन करेंगे। नई झांकी विहित रूप में है लेकिन यह मूल समस्या के समतुल्य नहीं है। तो कृत्रिम चर के योग के बराबर एक नया उद्देश्य फ़ंक्शन पेश किया जाता है और न्यूनतम खोजने के लिए सिंप्लेक्स एल्गोरिदम लागू किया जाता है; संशोधित रैखिक कार्यक्रम को चरण I समस्या कहा जाता है।<ref>{{harvtxt|Murty|1983|p=60}}</ref>
-चरण I समस्या के लिए लागू सिंप्लेक्स एल्गोरिदम को नए उद्देश्य फ़ंक्शन के लिए न्यूनतम मान के साथ समाप्त होना चाहिए, क्योंकि गैर-ऋणात्मक चर का योग होने के कारण, इसका मान 0 से नीचे है। यदि न्यूनतम 0 है तो कृत्रिम चर को समाप्त किया जा सकता है परिणामी विहित झांकी मूल समस्या के समकक्ष एक विहित झांकी का निर्माण करती है। सिंप्लेक्स एल्गोरिथम तब समाधान खोजने के लिए लागू किया जा सकता है; इस चरण को चरण II कहा जाता है। यदि न्यूनतम सकारात्मक है तो चरण I समस्या का कोई व्यवहार्य समाधान नहीं है जहां कृत्रिम चर सभी शून्य हैं। इसका तात्पर्य यह है कि मूल समस्या के लिए व्यवहार्य क्षेत्र खाली है, और इसलिए मूल समस्या का कोई समाधान नहीं है।<ref name="DantzigThapa1"/><ref name="NeringTucker"/><ref name="Padberg"/>
+== एक प्रारंभिक विहित सारणी निष्कर्ष ==
+सामान्यतः एक रेखीय प्रोग्राम विहित रूप में नहीं दिया जाता है और सिंप्लेक्स कलनविधि शुरू होने से पहले एक समकक्ष विहित सारणी स्थापित करना। यह ''कृत्रिम चर'' के परिचय से पूरा किया जा सकता है। इन चरों के लिए तत्समक आव्यूह के स्तंभ को स्तंभ वैक्टर के रूप में जोड़ा जाता है। यदि बाध्यता (कन्सट्रैन्ट) समीकरण के लिए बी मान ऋणात्मक है, तो तत्समक आव्यूह स्तंभ जोड़ने से पहले समीकरण को अस्वीकार कर दिया गया है। यह संभव हल या इष्टतम हल के सेट को नहीं बदलता है, और यह सुनिश्चित करता है कि ढीले चर एक प्रारंभिक साध्य हल का गठन करेंगे। नई सारणी विहित रूप में है परन्तु यह मूल समस्या के बराबर नहीं है। तो कृत्रिम चर के योग के बराबर एक नया उद्देश्य फलन प्रस्तुत किया जाता है और न्यूनतम खोजने के लिए सिम्पलेक्स कलनविधि लागू किया जाता है; संशोधित रेखीय फलन को ''अवस्था I'' समस्या कहा जाता है।<ref>{{harvtxt|Murty|1983|p=60}}</ref>
+अवस्था I समस्या के लिए लागू सिंप्लेक्स एल्गोरिथ्म को नए उद्देश्य फलन के लिए न्यूनतम मूल्य के साथ समाप्त होना चाहिए, क्योंकि अऋणात्मक चर का योग होने के कारण, इसका मान 0 से नीचे है। यदि न्यूनतम 0 है तो मूल समस्या के समतुल्य एक विहित सारणी का निर्माण करने वाली परिणामी विहित सारणी से कृत्रिम चर को समाप्त किया जा सकता है। हल खोजने के लिए सिम्प्लेक्स कलनविधि को लागू किया जा सकता है; इस चरण को ''अवस्था II'' कहा जाता है। यदि न्यूनतम धनात्मक है तो प्रथम चरण की समस्या के लिए कोई साध्य हल नहीं है जहाँ कृत्रिम चर सभी शून्य हैं। इसका मतलब यह है कि मूल समस्या के लिए संभव क्षेत्र रिक्त है, और इसलिए मूल समस्या का कोई हल नहीं है।<ref name="DantzigThapa1" /><ref name="NeringTucker" /><ref name="Padberg">M. Padberg, ''Linear Optimization and Extensions'', Second Edition, Springer-Verlag, 1999.</ref>
 === उदाहरण ===
-रैखिक कार्यक्रम पर विचार करें
+रैखिक प्रोग्राम पर विचार करें
-:छोटा करना
+:न्यूनतमीकरण
 ::<math>Z = -2 x - 3 y - 4 z\,</math>
-:का विषय है
+:के अधीन
 ::<math>\begin{align}
 x + 2 y + z &= 10\\
@@ Line 165: / Line 157: @@
   x,\, y,\, z &\ge 0
 \end{align}</math>
-यह (गैर-विहित) झांकी द्वारा दर्शाया गया है
+यह (गैर-विहित) सारणी द्वारा दर्शाया गया है
 :<math>
    \begin{bmatrix}
@@ Line 173: / Line 165: @@
    \end{bmatrix}
 </math>
-एक नई झांकी देते हुए कृत्रिम चर u और v और वस्तुनिष्ठ फलन W = u + v का परिचय दें
+एक नई सारणी देते हुए कृत्रिम चर ''u'' और ''v'' और वस्तुनिष्ठ फलन ''W = u + v'' का परिचय दें
 :<math>
    \begin{bmatrix}
@@ Line 184: / Line 176: @@
 मूल उद्देश्य फलन को परिभाषित करने वाले समीकरण को द्वितीय चरण की प्रत्याशा में बनाए रखा जाता है।
-निर्माण के द्वारा, यू और वी दोनों मूल चर हैं क्योंकि वे प्रारंभिक पहचान मैट्रिक्स का हिस्सा हैं। हालाँकि, उद्देश्य फ़ंक्शन W वर्तमान में मानता है कि u और v दोनों 0 हैं। सही मान होने के लिए उद्देश्य फ़ंक्शन को समायोजित करने के लिए जहां u = 10 और v = 15, तीसरी और चौथी पंक्तियों को पहली पंक्ति में जोड़ें
+निर्माण के द्वारा, ''u'' और ''v'' दोनों मूल चर हैं, क्योंकि वे प्रारंभिक तत्समक आव्यूह का हिस्सा हैं। हालाँकि, वस्तुनिष्ठ फलन ''W'' इस समय ''u'' और ''v'' दोनों को 0 मानता हैं। वस्तुनिष्ठ फलन को सही मान के लिए समायोजित करने के लिए जहाँ ''u'' = 10 और ''v'' = 15, पहली पंक्ति में तीसरी और चौथी पंक्तियाँ जोड़ें
 :<math>
    \begin{bmatrix}
@@ Line 193: / Line 185: @@
    \end{bmatrix}
 </math>
-स्तंभ 5 को पिवट कॉलम के रूप में चुनें, इसलिए पिवट पंक्ति पंक्ति 4 होनी चाहिए, और अपडेट की गई झांकी है
+स्तंभ 5 को ध्रुराग्र स्तंभ के रूप में चुनें, इसलिए ध्रुराग्र पंक्ति पंक्ति 4 होनी चाहिए, और अपडेट की गई सारणी है
 :<math>
    \begin{bmatrix}
@@ Line 202: / Line 194: @@
    \end{bmatrix}
 </math>
-अब कॉलम 3 को पिवट कॉलम के रूप में चुनें, जिसके लिए पंक्ति 3 को पिवट पंक्ति होना चाहिए
+अब स्तंभ 3 को ध्रुराग्र स्तंभ के रूप में चुनें, जिसके लिए पंक्ति 3 को ध्रुराग्र पंक्ति होना चाहिए
 :<math>
    \begin{bmatrix}
@@ Line 211: / Line 203: @@
    \end{bmatrix}
 </math>
-कृत्रिम चर अब 0 हैं और उन्हें मूल समस्या के समतुल्य एक विहित झांकी देते हुए गिराया जा सकता है:
+कृत्रिम चर अब 0 हैं और उन्हें मूल समस्या के समतुल्य एक विहित सारणी देते हुए गिराया जा सकता है:
 :<math>
    \begin{bmatrix}
@@ Line 219: / Line 211: @@
    \end{bmatrix}
 </math>
-यह, सौभाग्य से, पहले से ही इष्टतम है और मूल रैखिक कार्यक्रम के लिए इष्टतम मूल्य −130/7 है।
+यह, सौभाग्य से, पहले से ही इष्टतम है और मूल रैखिक फलन के लिए इष्टतम मूल्य −130/7 है।
 ==उन्नत विषय==
 ===कार्यान्वयन ===
-{{main|Revised simplex algorithm}}
+{{main|संशोधित सिंप्लेक्स कलनविधि}}
-एल्गोरिथम का वर्णन करने के लिए ऊपर इस्तेमाल किया गया झांकी फॉर्म खुद को एक तत्काल कार्यान्वयन के लिए उधार देता है जिसमें झांकी को एक आयताकार (m + 1)-by-(m + n + 1) सरणी के रूप में बनाए रखा जाता है। पहचान मैट्रिक्स के m स्पष्ट स्तंभों को संग्रहीत करने से बचना सीधा है जो 'बी' के आधार पर ['ए', 'आई'] के स्तंभों का सबसेट होने के कारण झांकी के भीतर होगा। इस कार्यान्वयन को मानक सिम्पलेक्स एल्गोरिथम कहा जाता है। भंडारण और संगणना ओवरहेड ऐसा है कि बड़ी रैखिक प्रोग्रामिंग समस्याओं को हल करने के लिए मानक सिंप्लेक्स विधि निषेधात्मक रूप से महंगा तरीका है।
-प्रत्येक सिम्प्लेक्स पुनरावृत्ति में, केवल आवश्यक डेटा झांकी की पहली पंक्ति, झांकी का (निर्णायक) स्तंभ है जो प्रवेश करने वाले चर और दाहिने हाथ की ओर से संबंधित है। उत्तरार्द्ध को मुख्य स्तंभ का उपयोग करके अद्यतन किया जा सकता है और झांकी की पहली पंक्ति को छोड़ने वाले चर के अनुरूप (निर्णायक) पंक्ति का उपयोग करके अद्यतन किया जा सकता है। मैट्रिक्स 'बी' और मैट्रिक्स-वेक्टर उत्पाद 'ए' का उपयोग करने वाले समीकरणों के रैखिक प्रणालियों के समाधान का उपयोग करके सीधे धुरी स्तंभ और धुरी पंक्ति दोनों की गणना की जा सकती है। ये अवलोकन संशोधित सिम्पलेक्स एल्गोरिथम को प्रेरित करते हैं, जिसके लिए कार्यान्वयनों को 'बी' के उनके उलटे प्रतिनिधित्व द्वारा अलग किया जाता है।<ref name="DantzigThapa2" >
+कलनविधि का वर्णन करने के लिए ऊपर इस्तेमाल किया गया सारणी फॉर्म खुद को एक तत्काल कार्यान्वयन के लिए उधार देता है जिसमें सारणी को एक आयताकार (''m'' + 1)-द्वारा-(''m'' + ''n'' + 1) सरणी के रूप में बनाए रखा जाता है। तत्समक आव्यूह के m स्पष्ट स्तंभों को संग्रहीत करने से बचना सीधा है जो '''B''' के आधार पर ['''A''', '''I'''] के स्तंभों का सबसेट होने के कारण सारणी के भीतर होगा। इस कार्यान्वयन को "मानक सिंप्लेक्स कलनविधि" के रूप में जाना जाता है। भंडारण और संगणना ओवरहेड ऐसा है कि बड़ी रैखिक प्रोग्रामिंग समस्याओं को हल करने के लिए मानक सिंप्लेक्स विधि एक निषेधात्मक रूप से महंगा दृष्टिकोण है।
+प्रत्येक सिम्प्लेक्स पुनरावृत्ति में, केवल आवश्यक डेटा सारणी की पहली पंक्ति है, सारणी का (निर्णायक) स्तंभ प्रवेश करने वाले चर और दाईं ओर के अनुरूप है। पश्चात वाले को मुख्य स्तंभ का उपयोग करके अद्यतन किया जा सकता है और सारणी की पहली पंक्ति को छोड़ने वाले चर के अनुरूप (निर्णायक) पंक्ति का उपयोग करके अद्यतन किया जा सकता है। आव्यूह '''B''' और एक आव्यूह-सदिश उत्पाद '''A''' का उपयोग करके सम्मिलित समीकरणों के रैखिक प्रणालियों के हल का उपयोग करके सीधे ध्रुराग्र स्तंभ और ध्रुराग्र पंक्ति दोनों की गणना की जा सकती है। ये अवलोकन "''संशोधित'' सिम्प्लेक्स कलनविधि" को प्रेरित करते हैं, जिसके लिए कार्यान्वयन '''B''' के उनके उलटा प्रतिनिधित्व द्वारा प्रतिष्ठित हैं।<ref name="DantzigThapa2">
 [[George B. Dantzig]] and Mukund N. Thapa. 2003. ''Linear Programming 2: Theory and Extensions''. Springer-Verlag.</ref>
-बड़ी रैखिक-प्रोग्रामिंग समस्याओं में A आमतौर पर एक विरल मैट्रिक्स होता है और, जब इसके उलटा प्रतिनिधित्व को बनाए रखते हुए B की परिणामी विरलता का शोषण किया जाता है, तो संशोधित सिंप्लेक्स एल्गोरिथ्म मानक सिंप्लेक्स विधि की तुलना में बहुत अधिक कुशल होता है। वाणिज्यिक सिंप्लेक्स सॉल्वर संशोधित सिम्प्लेक्स एल्गोरिथम पर आधारित हैं।<ref name="Padberg" >M. Padberg, ''Linear Optimization and Extensions'', Second Edition, Springer-Verlag, 1999.</ref><ref name="DantzigThapa2"/><ref>Dmitris Alevras and Manfred W. Padberg, ''Linear Optimization and Extensions: Problems and Extensions'', Universitext, Springer-Verlag, 2001. (Problems from Padberg with solutions.)</ref><ref name="MarosMitra" >{{cite book|last1=Maros|first1=István|last2=Mitra|first2=Gautam|chapter=Simplex algorithms|mr=1438309|title=रैखिक और पूर्णांक प्रोग्रामिंग में प्रगति|pages=1–46|editor=J. E. Beasley|publisher=Oxford Science|year=1996}}</ref><ref>{{cite book|mr=1960274|last=Maros|first=István|title=सिंप्लेक्स विधि की कम्प्यूटेशनल तकनीक|series=International Series in Operations Research & Management Science|volume=61|publisher=Kluwer Academic Publishers|location=Boston, MA|year=2003|pages=xx+325|isbn=978-1-4020-7332-8}}</ref>
+बड़ी रेखीय-प्रोग्रामिंग समस्याओं में '''A''' सामान्यतः एक विरल आव्यूह है और, जब इसके व्युत्क्रम प्रतिनिधित्व को बनाए रखते हुए '''B''' की परिणामी विरलता का शोषण किया जाता है, तो संशोधित सिंप्लेक्स एल्गोरिथ्म मानक सिम्प्लेक्स विधि की तुलना में बहुत अधिक कुशल होता है। वाणिज्यिक सिंप्लेक्स सॉल्वर संशोधित सिंप्लेक्स कलनविधि पर आधारित हैं।<ref name="Padberg" /><ref name="DantzigThapa2" /><ref>Dmitris Alevras and Manfred W. Padberg, ''Linear Optimization and Extensions: Problems and Extensions'', Universitext, Springer-Verlag, 2001. (Problems from Padberg with solutions.)</ref><ref name="MarosMitra">{{cite book|last1=Maros|first1=István|last2=Mitra|first2=Gautam|chapter=Simplex algorithms|mr=1438309|title=रैखिक और पूर्णांक प्रोग्रामिंग में प्रगति|pages=1–46|editor=J. E. Beasley|publisher=Oxford Science|year=1996}}</ref><ref>{{cite book|mr=1960274|last=Maros|first=István|title=सिंप्लेक्स विधि की कम्प्यूटेशनल तकनीक|series=International Series in Operations Research & Management Science|volume=61|publisher=Kluwer Academic Publishers|location=Boston, MA|year=2003|pages=xx+325|isbn=978-1-4020-7332-8}}</ref>
+=== विकृति: स्तंभन और चक्रण ===
+यदि सभी मूल चरों के मान पूरी तरह से धनात्मक हैं, तो एक ध्रुराग्र के परिणामस्वरूप उद्देश्य मूल्य में सुधार होना चाहिए। जब यह सदैव होता है तो मूल चर का कोई सेट दो बार नहीं होता है और सिंप्लेक्स एल्गोरिथ्म को सीमित चरणों के पश्चात समाप्त होना चाहिए। मूल साध्य हल जहां कम से कम एक मूल चर शून्य है, उसे पतित कहा जाता है और इसके परिणामस्वरूप पिवोट्स हो सकते हैं जिसके लिए उद्देश्य मूल्य में कोई सुधार नहीं होता है। इस स्थिति में हल में कोई वास्तविक परिवर्तन नहीं होता है, परन्तु केवल मूल चर के सेट में परिवर्तितव होता है। जब इस तरह के कई पिवोट्स एक के पश्चात एक होते हैं, तो कोई सुधार नहीं होता है; बड़े औद्योगिक अनुप्रयोगों में अध: पतन आम है और इस तरह के "''स्तंभन''" उल्लेखनीय है। रुकने से भी बदतर यह संभावना है कि मूल चर का एक ही सेट दो बार होता है, इस स्थिति में, सिंप्लेक्स एल्गोरिथ्म के नियतात्मक ध्रुराग्र नियम एक अनंत लूप, या "चक्र" उत्पन्न करेंगे। जबकि अध: पतन वास्तविकता में नियम है और स्टाल लगाना आम है, साइकिल चलाना वास्तविकता में दुर्लभ है। पैडबर्ग में व्यावहारिक साइकिल चालन के उदाहरण की चर्चा होती है।<ref name="Padberg"/> ब्लैंड का नियम साइकिल चलाने से रोकता है और इस प्रकार यह गारंटी देता है कि सिम्पलेक्स कलनविधि सदैव समाप्त हो जाता है।<ref name="Padberg"/><ref name="Bland">
+{{cite journal|title=New finite pivoting rules for the simplex method|first=Robert G.|last=Bland|journal=Mathematics of Operations Research|volume=2|issue=2|date=May 1977|pages=103–107|doi=10.1287/moor.2.2.103|jstor=3689647|mr=459599|s2cid=18493293|url=https://semanticscholar.org/paper/874b988e359f63c8068226c53ef0a9bcd54e5e4d}}</ref><ref>{{harvtxt|Murty|1983|p=79}}</ref> एक और पिवोटिंग कलनविधि, क्रिस-क्रॉस कलनविधि कभी भी रैखिक प्रोग्राम पर साइकिल नहीं चलाता है।<ref>There are abstract optimization problems, called [[oriented matroid]] programs, on which Bland's rule cycles (incorrectly) while the [[criss-cross algorithm]] terminates correctly.</ref>
-=== अध: पतन: रुकना और साइकिल चलाना ===
+ज़ादेह के नियम और कनिंघम के नियम जैसे इतिहास-आधारित ध्रुराग्र नियम भी इस बात पर नज़र रखते हुए कि कितनी बार विशेष चर का उपयोग किया जा रहा है और फिर ऐसे चर का समर्थन करते हैं जो कम से कम बार उपयोग किए गए हैं, स्तंभन और साइकिल चलाने के मुद्दे को दरकिनार करने की कोशिश करते हैं।
-यदि सभी बुनियादी चरों के मान सख्ती से सकारात्मक हैं, तो एक धुरी के परिणामस्वरूप उद्देश्य मूल्य में सुधार होना चाहिए। जब ऐसा हमेशा होता है तो बुनियादी चरों का कोई भी सेट दो बार नहीं होता है और सिम्प्लेक्स एल्गोरिथम को चरणों की एक सीमित संख्या के बाद समाप्त होना चाहिए। बुनियादी व्यवहार्य समाधान जहां कम से कम एक बुनियादी चर शून्य है, उन्हें पतित कहा जाता है और इसके परिणामस्वरूप ऐसे पिवट हो सकते हैं जिनके लिए उद्देश्य मूल्य में कोई सुधार नहीं होता है। इस मामले में समाधान में कोई वास्तविक परिवर्तन नहीं है बल्कि मूल चर के सेट में केवल एक परिवर्तन है। जब एक के बाद एक कई ऐसे पिवट होते हैं, तो कोई सुधार नहीं होता है; बड़े औद्योगिक अनुप्रयोगों में, अध: पतन आम है और इस तरह का ठहराव उल्लेखनीय है।
-स्टालिंग से भी बदतर यह संभावना है कि मूल चर का एक ही सेट दो बार होता है, इस मामले में, सिम्प्लेक्स एल्गोरिथ्म के नियतात्मक धुरी नियम एक अनंत लूप, या चक्र का उत्पादन करेंगे। जबकि व्यवहार में पतन नियम है और रुकना आम है, व्यवहार में साइकिल चलाना दुर्लभ है। मैनफ्रेड डब्ल्यू पैडबर्ग में व्यावहारिक साइकिल चालन के एक उदाहरण की चर्चा होती है।<ref name="Padberg"/>ब्लैंड का नियम साइकिल चलाने से रोकता है और इस प्रकार यह गारंटी देता है कि सिम्पलेक्स एल्गोरिथम हमेशा समाप्त होता है।<ref name="Padberg"/><ref name="Bland">
-{{cite journal|title=New finite pivoting rules for the simplex method|first=Robert G.|last=Bland|journal=Mathematics of Operations Research|volume=2|issue=2|date=May 1977|pages=103–107|doi=10.1287/moor.2.2.103|jstor=3689647|mr=459599|s2cid=18493293|url=https://semanticscholar.org/paper/874b988e359f63c8068226c53ef0a9bcd54e5e4d}}</ref><ref>{{harvtxt|Murty|1983|p=79}}</ref> एक और धुरी एल्गोरिथ्म, क्रिस-क्रॉस एल्गोरिथ्म कभी भी रैखिक कार्यक्रमों पर चक्र नहीं करता है।<ref>There are abstract optimization problems, called [[oriented matroid]] programs, on which Bland's rule cycles (incorrectly) while the [[criss-cross algorithm]] terminates correctly.</ref>
-इतिहास-आधारित धुरी नियम जैसे कि ज़ादेह का नियम और कनिंघम का नियम भी रुकने और साइकिल चलाने के मुद्दे को रोकने की कोशिश करते हैं कि कितनी बार विशेष चर का उपयोग किया जा रहा है और फिर ऐसे चर का पक्ष लें जो कम से कम अक्सर उपयोग किए गए हैं।
-=== सबसे खराब स्थिति में दक्षता ===
+=== निकृष्टतम स्थिति में दक्षता ===
-सिम्प्लेक्स विधि अभ्यास में उल्लेखनीय रूप से कुशल है और फूरियर-मोट्ज़किन उन्मूलन जैसे पहले के तरीकों पर एक बड़ा सुधार था। हालाँकि, 1972 में, विक्टर क्ले और मिन्टी<ref name="KleeMinty">{{cite book|title=असमानताओं III (कैलिफोर्निया विश्वविद्यालय, लॉस एंजिल्स, कैलिफ़ोर्निया में आयोजित असमानताओं पर तीसरे संगोष्ठी की कार्यवाही, 1-9 सितंबर, 1969, थियोडोर एस। मोट्ज़किन की स्मृति को समर्पित)|editor-first=Oved|editor-last=Shisha|publisher=Academic Press|location=New York-London|year=1972|mr=332165|last1=Klee|first1=Victor|author-link1=Victor Klee|last2=Minty|first2= George J.|author-link2=George J. Minty|chapter=How good is the simplex algorithm?|pages=159–175}}</ref> एक उदाहरण दिया, क्ले-मिन्टी क्यूब, यह दिखाते हुए कि डेंटज़िग द्वारा तैयार की गई सिंप्लेक्स विधि की सबसे खराब स्थिति घातीय समय है। तब से, पद्धति पर लगभग हर भिन्नता के लिए, यह दिखाया गया है कि रैखिक कार्यक्रमों का एक परिवार है जिसके लिए यह खराब प्रदर्शन करता है। बहुपद समय के साथ भिन्नता होने पर यह एक खुला प्रश्न है, हालांकि उप-घातीय धुरी नियम ज्ञात हैं।<ref>{{Citation
+सिम्प्लेक्स विधि वास्तविकता में उल्लेखनीय रूप से कुशल है और फूरियर-मोट्ज़किन उन्मूलन जैसे पहले के तरीकों पर एक बड़ा सुधार था। हालांकि, 1972 में, क्ले और मिन्टी<ref name="KleeMinty">{{cite book|title=असमानताओं III (कैलिफोर्निया विश्वविद्यालय, लॉस एंजिल्स, कैलिफ़ोर्निया में आयोजित असमानताओं पर तीसरे संगोष्ठी की कार्यवाही, 1-9 सितंबर, 1969, थियोडोर एस। मोट्ज़किन की स्मृति को समर्पित)|editor-first=Oved|editor-last=Shisha|publisher=Academic Press|location=New York-London|year=1972|mr=332165|last1=Klee|first1=Victor|author-link1=Victor Klee|last2=Minty|first2= George J.|author-link2=George J. Minty|chapter=How good is the simplex algorithm?|pages=159–175}}</ref> ने क्ले-मिन्टी क्यूब का एक उदाहरण दिया, जिसमें दिखाया गया कि डेंटज़िग द्वारा तैयार की गई सिम्पलेक्स विधि की सबसे खराब स्थिति सम्मिश्रता घातीय समय है। तब से, विधि पर लगभग हर परिवर्तितव के लिए, यह दिखाया गया है कि रैखिक फलनों का एक परिवार है जिसके लिए यह खराब प्रदर्शन करता है। यह एक खुला प्रश्न है कि क्या बहुपद समय के साथ कोई भिन्नता है, हालांकि उप-घातीय ध्रुराग्र नियम ज्ञात हैं।<ref>{{Citation
   | last1 = Hansen
   | first1 = Thomas
@@ Line 255: / Line 247: @@
   }}
 </ref>
-में, यह साबित हो गया था कि सिंप्लेक्स विधि का एक विशेष प्रकार एनपी-शक्तिशाली है, अर्थात, इसका उपयोग बहुपद ओवरहेड के साथ हल करने के लिए किया जा सकता है, एल्गोरिथम के निष्पादन के दौरान एनपी में किसी भी समस्या का निहित रूप से उपयोग किया जा सकता है। इसके अलावा, यह तय करना कि किसी दिए गए इनपुट पर एल्गोरिथ्म के निष्पादन के दौरान एक दिया गया चर कभी भी आधार में प्रवेश करता है, और किसी समस्या को हल करने के लिए आवश्यक पुनरावृत्तियों की संख्या निर्धारित करना, दोनों एनपी-कठोरता | एनपी-हार्ड समस्याएं हैं।<ref>{{Cite journal|last1=Disser|first1=Yann|last2=Skutella|first2=Martin|date=2018-11-01|title=सिम्प्लेक्स एल्गोरिथम एनपी-माइटी है|journal=ACM Trans. Algorithms|volume=15|issue=1|pages=5:1–5:19|doi=10.1145/3280847|issn=1549-6325|arxiv=1311.5935|s2cid=54445546}}</ref> लगभग उसी समय यह दिखाया गया था कि एक कृत्रिम धुरी नियम मौजूद है जिसके लिए इसके आउटपुट की गणना PSPACE- पूर्ण है।<ref>{{Citation | last1 = Adler | first1 = Ilan | last2 = Christos | first2 = Papadimitriou | author2-link = Christos Papadimitriou | last3 = Rubinstein | first3 = Aviad | title = On Simplex Pivoting Rules and Complexity Theory | journal = International Conference on Integer Programming and Combinatorial Optimization | volume = 17 | pages = 13–24 | year = 2014 | arxiv = 1404.3320 | doi = 10.1007/978-3-319-07557-0_2| series = Lecture Notes in Computer Science | isbn = 978-3-319-07556-3 | s2cid = 891022 }}</ref> 2015 में, यह दिखाने के लिए इसे मजबूत किया गया था कि Dantzig के धुरी नियम के आउटपुट की गणना करना PSPACE-पूर्ण है।<ref>{{Citation | last1 = Fearnly | first1 = John | last2 = Savani | first2 = Rahul | title = The Complexity of the Simplex Method | journal = Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing | pages = 201–208 | year = 2015 | arxiv = 1404.0605 | doi = 10.1145/2746539.2746558| isbn = 9781450335362 | s2cid = 2116116 }}</ref>
-=== व्यवहार में दक्षता ===
-अवलोकन का विश्लेषण और परिमाणीकरण कि सिम्प्लेक्स एल्गोरिथ्म व्यवहार में कुशल है, इसके बावजूद इसकी सबसे खराब स्थिति जटिलता के अन्य उपायों के विकास के लिए प्रेरित हुई है। सिंप्लेक्स एल्गोरिथ्म में बहुपद-समय सबसे अच्छा, सबसे खराब और औसत मामला है | विभिन्न संभाव्यता वितरणों के तहत औसत-केस जटिलता, यादृच्छिक मैट्रिक्स के लिए संभाव्यता वितरण की पसंद के आधार पर सिम्प्लेक्स एल्गोरिदम के सटीक औसत-केस प्रदर्शन के साथ।<ref name="Schrijver">[[Alexander Schrijver]], ''Theory of Linear and Integer Programming''. John Wiley & sons, 1998, {{isbn|0-471-98232-6}} (mathematical)</ref><ref name="Borgwardt">The simplex algorithm takes on average ''D'' steps for a cube. {{harvtxt|Borgwardt|1987}}: {{cite book|last=Borgwardt|first=Karl-Heinz|title=The simplex method: A probabilistic analysis|series=Algorithms and Combinatorics (Study and Research Texts)|volume=1|publisher=Springer-Verlag|location=Berlin|year=1987|pages=xii+268|isbn=978-3-540-17096-9|mr=868467}}</ref> झरझरा सेट का अध्ययन करने के लिए एक अन्य दृष्टिकोण सामान्य टोपोलॉजी से बेयर श्रेणी सिद्धांत का उपयोग करता है, और यह दिखाने के लिए कि (टोपोलॉजिकल रूप से) अधिकांश मैट्रिसेस को बहुपद संख्या में चरणों में सिम्प्लेक्स एल्गोरिथ्म द्वारा हल किया जा सकता है।{{Citation needed|date=June 2019}}
-सिम्प्लेक्स एल्गोरिथम के प्रदर्शन का विश्लेषण करने का एक अन्य तरीका छोटे गड़बड़ी के तहत सबसे खराब स्थिति के व्यवहार का अध्ययन करता है - क्या सबसे खराब स्थिति एक छोटे से बदलाव (संरचनात्मक स्थिरता के अर्थ में) के तहत स्थिर है, या क्या वे ट्रैक्टेबल हो जाते हैं? शोध के इस क्षेत्र, जिसे सुगम विश्लेषण कहा जाता है, को विशेष रूप से सरल विधि का अध्ययन करने के लिए पेश किया गया था। दरअसल, शोर के साथ इनपुट पर सिम्प्लेक्स विधि का चलने का समय चर की संख्या और गड़बड़ी के परिमाण में बहुपद है।<ref>{{Cite book | last1=Spielman | first1=Daniel | last2=Teng | first2=Shang-Hua | author2-link=Shanghua Teng | title=कम्प्यूटिंग के सिद्धांत पर तीस-तीसरे वार्षिक एसीएम संगोष्ठी की कार्यवाही| publisher=ACM | isbn=978-1-58113-349-3 | doi=10.1145/380752.380813 | year=2001 | chapter=Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time| pages=296–305 | arxiv=cs/0111050| s2cid=1471 }}</ref><ref>{{Cite journal|last1=Dadush|first1=Daniel|last2=Huiberts|first2=Sophie|date=2020-01-01|title=सिंप्लेक्स विधि का एक अनुकूल चिकना विश्लेषण|url=https://epubs.siam.org/doi/abs/10.1137/18M1197205|journal=SIAM Journal on Computing|volume=49|issue=5|pages=STOC18–449|doi=10.1137/18M1197205|s2cid=226351624|issn=0097-5397}}</ref>
-== अन्य एल्गोरिदम ==
-रैखिक-प्रोग्रामिंग समस्याओं को हल करने के लिए अन्य एल्गोरिदम का वर्णन रैखिक प्रोग्रामिंग | रैखिक-प्रोग्रामिंग लेख में किया गया है। एक अन्य आधार-विनिमय धुरी एल्गोरिथम क्रिस-क्रॉस एल्गोरिथम है।<ref>{{cite journal|last1=Terlaky|first1=Tamás|last2=Zhang|first2=Shu Zhong|title=लीनियर प्रोग्रामिंग के लिए धुरी नियम: हाल के सैद्धांतिक विकास पर एक सर्वेक्षण|issue=1|journal=Annals of Operations Research|volume=46–47|year=1993|pages=203–233|doi=10.1007/BF02096264|mr=1260019|citeseerx = 10.1.1.36.7658 |s2cid=6058077|issn=0254-5330}}</ref><ref>{{cite news|first1=Komei|last1=Fukuda|author1-link=Komei Fukuda|first2=Tamás|last2=Terlaky|author2-link=Tamás Terlaky|title=क्रिस-क्रॉस विधियाँ: धुरी एल्गोरिदम पर एक नया दृश्य|journal=Mathematical Programming, Series B|volume=79|number=1–3|pages=369–395|editor1=Thomas M. Liebling |editor2=Dominique de Werra|publisher=North-Holland Publishing |location=Amsterdam|year=1997|doi=10.1007/BF02614325|mr=1464775}}</ref> रेखीय प्रोग्रामिंग के लिए बहुपद-समय के एल्गोरिदम हैं जो आंतरिक बिंदु विधियों का उपयोग करते हैं: इनमें खाचियन के दीर्घवृत्तीय एल्गोरिथ्म, कर्मकार के कर्मकार के एल्गोरिथ्म और आंतरिक बिंदु विधि | पथ-निम्नलिखित एल्गोरिदम शामिल हैं।<ref name="Vanderbei"/>
+में, यह साबित हो गया था कि सिंप्लेक्स विधि का एक विशेष प्रकार एनपी-शक्तिशाली है, अर्थात, इसका उपयोग बहुपद ओवरहेड के साथ हल करने के लिए किया जा सकता है, कलनविधि के निष्पादन के दौरान एनपी में कोई समस्या निहित है। इसके अतिरिक्त, यह तय करना कि क्या दिया गया चर किसी दिए गए इनपुट पर कलनविधि के निष्पादन के दौरान कभी भी आधार में प्रवेश करता है, और किसी समस्या को हल करने के लिए आवश्यक पुनरावृत्तियों की संख्या का निर्धारण करना, दोनों ही एनपी-कठोर समस्याएं हैं।<ref>{{Cite journal|last1=Disser|first1=Yann|last2=Skutella|first2=Martin|date=2018-11-01|title=सिम्प्लेक्स एल्गोरिथम एनपी-माइटी है|journal=ACM Trans. Algorithms|volume=15|issue=1|pages=5:1–5:19|doi=10.1145/3280847|issn=1549-6325|arxiv=1311.5935|s2cid=54445546}}</ref> लगभग उसी समय यह दिखाया गया था कि एक कृत्रिम ध्रुराग्र नियम मौजूद है जिसके लिए इसके आउटपुट की गणना पीएसपीएसीई-पूर्ण है।<ref>{{Citation | last1 = Adler | first1 = Ilan | last2 = Christos | first2 = Papadimitriou | author2-link = Christos Papadimitriou | last3 = Rubinstein | first3 = Aviad | title = On Simplex Pivoting Rules and Complexity Theory | journal = International Conference on Integer Programming and Combinatorial Optimization | volume = 17 | pages = 13–24 | year = 2014 | arxiv = 1404.3320 | doi = 10.1007/978-3-319-07557-0_2| series = Lecture Notes in Computer Science | isbn = 978-3-319-07556-3 | s2cid = 891022 }}</ref> 2015 में, यह दिखाने के लिए इसे मजबूत किया गया था कि डेंटज़िग के ध्रुराग्र नियम के आउटपुट की गणना करना पीएसपीएसीई-पूर्ण है।<ref>{{Citation | last1 = Fearnly | first1 = John | last2 = Savani | first2 = Rahul | title = The Complexity of the Simplex Method | journal = Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing | pages = 201–208 | year = 2015 | arxiv = 1404.0605 | doi = 10.1145/2746539.2746558| isbn = 9781450335362 | s2cid = 2116116 }}</ref>
+=== वास्तविकता में दक्षता ===
+अवलोकन का विश्लेषण और परिमाण निर्धारित करना कि सिम्प्लेक्स कलनविधि वास्तविकता में प्रभावशाली होता है, इसकी चरघातांकी निकृष्‍टतम् सम्मिश्रता ने सम्मिश्रता के अन्य मापों के विकास को प्रेरित किया है। सिम्पलेक्स कलनविधि में विभिन्न संभाव्यता वितरणों के तहत बहुपद-समय औसत-विभक्ति सम्मिश्रता है, सिंप्लेक्स कलनविधि के यथार्थ औसत-केस प्रदर्शन के साथ यादृच्छिक आव्यूह के लिए संभाव्यता वितरण के विकल्प पर निर्भर करता है।<ref name="Schrijver">[[Alexander Schrijver]], ''Theory of Linear and Integer Programming''. John Wiley & sons, 1998, {{isbn|0-471-98232-6}} (mathematical)</ref><ref name="Borgwardt">The simplex algorithm takes on average ''D'' steps for a cube. {{harvtxt|Borgwardt|1987}}: {{cite book|last=Borgwardt|first=Karl-Heinz|title=The simplex method: A probabilistic analysis|series=Algorithms and Combinatorics (Study and Research Texts)|volume=1|publisher=Springer-Verlag|location=Berlin|year=1987|pages=xii+268|isbn=978-3-540-17096-9|mr=868467}}</ref> "विशिष्ट घटना" का अध्ययन करने के लिए एक अन्य दृष्टिकोण सामान्य टोपोलॉजी से बायर श्रेणी के सिद्धांत का उपयोग करता है, और यह दिखाने के लिए कि (सांख्यिकीय रूप से) "अधिकांश" आव्यूह को बहुपद चरणों की संख्या में सिम्पलेक्स एल्गोरिथ्म द्वारा हल किया जा सकता है।{{Citation needed|date=June 2019}}
+सिम्पलेक्स कलनविधि के प्रदर्शन का विश्लेषण करने के लिए एक अन्य विधि छोटे गड़बड़ी के तहत सबसे खराब स्थिति के व्यवहार का अध्ययन करती है - क्या सबसे खराब स्थिति एक छोटे से परिवर्तितव (संरचनात्मक स्थिरता के अर्थ में) के तहत स्थिर होती है, या क्या वे ट्रैक्टेबल हो जाते हैं? शोध के इस क्षेत्र, जिसे स्मूथेड एनालिसिस कहा जाता है, को विशेष रूप से सिम्पलेक्स विधि का अध्ययन करने के लिए प्रस्तुत किया गया था। दरअसल, शोर के साथ इनपुट पर सिम्प्लेक्स विधि का चलने का समय चरों की संख्या और क्षोभ के परिमाण में बहुपद है।<ref>{{Cite book | last1=Spielman | first1=Daniel | last2=Teng | first2=Shang-Hua | author2-link=Shanghua Teng | title=कम्प्यूटिंग के सिद्धांत पर तीस-तीसरे वार्षिक एसीएम संगोष्ठी की कार्यवाही| publisher=ACM | isbn=978-1-58113-349-3 | doi=10.1145/380752.380813 | year=2001 | chapter=Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time| pages=296–305 | arxiv=cs/0111050| s2cid=1471 }}</ref><ref>{{Cite journal|last1=Dadush|first1=Daniel|last2=Huiberts|first2=Sophie|date=2020-01-01|title=सिंप्लेक्स विधि का एक अनुकूल चिकना विश्लेषण|url=https://epubs.siam.org/doi/abs/10.1137/18M1197205|journal=SIAM Journal on Computing|volume=49|issue=5|pages=STOC18–449|doi=10.1137/18M1197205|s2cid=226351624|issn=0097-5397}}</ref>
+== अन्य कलनविधि ==
+रैखिक-प्रोग्रामिंग समस्याओं को हल करने के लिए अन्य कलनविधि रैखिक-प्रोग्रामिंग आलेख में वर्णित हैं। एक अन्य आधार-विनिमय कीलकन कलनविधि क्रिस-क्रॉस कलनविधि है।<ref>{{cite journal|last1=Terlaky|first1=Tamás|last2=Zhang|first2=Shu Zhong|title=लीनियर प्रोग्रामिंग के लिए धुरी नियम: हाल के सैद्धांतिक विकास पर एक सर्वेक्षण|issue=1|journal=Annals of Operations Research|volume=46–47|year=1993|pages=203–233|doi=10.1007/BF02096264|mr=1260019|citeseerx = 10.1.1.36.7658 |s2cid=6058077|issn=0254-5330}}</ref><ref>{{cite news|first1=Komei|last1=Fukuda|author1-link=Komei Fukuda|first2=Tamás|last2=Terlaky|author2-link=Tamás Terlaky|title=क्रिस-क्रॉस विधियाँ: धुरी एल्गोरिदम पर एक नया दृश्य|journal=Mathematical Programming, Series B|volume=79|number=1–3|pages=369–395|editor1=Thomas M. Liebling |editor2=Dominique de Werra|publisher=North-Holland Publishing |location=Amsterdam|year=1997|doi=10.1007/BF02614325|mr=1464775}}</ref> रेखीय प्रोग्रामिंग के लिए बहुपद-काल कलनविधि हैं जो आंतरिक बिंदु विधियों का उपयोग करते हैं: इनमें खाचियान का दीर्घवृत्तीय एल्गोरिथ्म, कर्मकार का प्रक्षेपी एल्गोरिथ्म और पथ-अनुवर्ती कलनविधि सम्मिलित हैं।<ref name="Vanderbei"/>
 == रैखिक-भिन्नात्मक प्रोग्रामिंग ==
-{{Main|Linear-fractional programming}}
+{{Main|रेखीय-भिन्नात्मक प्रोग्रामिंग}}
-रैखिक-भिन्नात्मक प्रोग्रामिंग | रैखिक-भिन्नात्मक प्रोग्रामिंग (एलएफपी) रैखिक प्रोग्रामिंग (एलपी) का एक सामान्यीकरण है। एलपी में उद्देश्य समारोह एक रैखिक कार्यात्मक है, जबकि एक रैखिक-आंशिक कार्यक्रम का उद्देश्य कार्य दो रैखिक कार्यों का अनुपात है। दूसरे शब्दों में, एक रेखीय कार्यक्रम एक भिन्नात्मक-रैखिक कार्यक्रम है जिसमें भाजक एक स्थिर कार्य होता है जिसका मान हर जगह होता है। एक रेखीय-आंशिक कार्यक्रम को सिम्प्लेक्स एल्गोरिथम के एक संस्करण द्वारा हल किया जा सकता है<ref>{{harvtxt|Murty|1983|loc=Chapter 3.20 (pp. 160–164) and pp. 168 and 179}}</ref><ref>Chapter five: {{cite book|last=Craven|first=B. D.|title=Fractional programming|series=Sigma Series in Applied Mathematics|volume=4|publisher=Heldermann Verlag|location=Berlin|year=1988|pages=145|isbn=978-3-88538-404-5|mr=949209}}</ref><ref>{{cite journal|last1=Kruk|first1=Serge|last2=Wolkowicz|first2=Henry|title=स्यूडोलिनियर प्रोग्रामिंग|journal=[[SIAM Review]]|volume=41|year=1999|issue=4|pages=795–805|mr=1723002|jstor=2653207|doi=10.1137/S0036144598335259|citeseerx=10.1.1.53.7355|bibcode=1999SIAMR..41..795K}}
+रैखिक-भिन्नात्मक प्रोग्रामिंग (एलएफपी) रैखिक प्रोग्रामिंग (एलपी) का सामान्यीकरण है। एलपी में उद्देश्य फलन एक रैखिक फलन है, जबकि रैखिक-भिन्नात्मक प्रोग्राम का उद्देश्य फलन दो रैखिक फलन्स का अनुपात है। दूसरे शब्दों में, एक रेखीय फलन एक भिन्नात्मक-रैखिक फलन है जिसमें भाजक एक नियत फलन होता है जिसका मान प्रत्येक स्थान पर एक प्राप्त होता है। रेखीय-भिन्नात्मक फलन को सिम्प्लेक्स कलनविधि<ref>{{harvtxt|Murty|1983|loc=Chapter 3.20 (pp. 160–164) and pp. 168 and 179}}</ref><ref>Chapter five: {{cite book|last=Craven|first=B. D.|title=Fractional programming|series=Sigma Series in Applied Mathematics|volume=4|publisher=Heldermann Verlag|location=Berlin|year=1988|pages=145|isbn=978-3-88538-404-5|mr=949209}}</ref><ref>{{cite journal|last1=Kruk|first1=Serge|last2=Wolkowicz|first2=Henry|title=स्यूडोलिनियर प्रोग्रामिंग|journal=[[SIAM Review]]|volume=41|year=1999|issue=4|pages=795–805|mr=1723002|jstor=2653207|doi=10.1137/S0036144598335259|citeseerx=10.1.1.53.7355|bibcode=1999SIAMR..41..795K}}
 </ref><ref>{{cite journal|last1=Mathis|first1=Frank H.|last2=Mathis|first2=Lenora Jane|title=अस्पताल प्रबंधन के लिए एक गैर-रेखीय प्रोग्रामिंग एल्गोरिदम|journal=[[SIAM Review]]|volume=37 |year=1995 |issue=2 |pages=230–234|mr=1343214|jstor=2132826|doi=10.1137/1037046}}
-</ref> या क्रिस-क्रॉस एल्गोरिथम द्वारा।<ref>{{cite journal|title=अतिशयोक्तिपूर्ण प्रोग्रामिंग के लिए परिमित क्रिस-क्रॉस विधि|journal=European Journal of Operational Research|volume=114|issue=1|
+</ref> या क्रिस-क्रॉस कलनविधि के एक संस्करण द्वारा हल किया जा सकता है।<ref>{{cite journal|title=अतिशयोक्तिपूर्ण प्रोग्रामिंग के लिए परिमित क्रिस-क्रॉस विधि|journal=European Journal of Operational Research|volume=114|issue=1|
 pages=198–214|year=1999|issn=0377-2217|doi=10.1016/S0377-2217(98)00049-6|first1=Tibor|last1=Illés|first2=Ákos|last2=Szirmai|first3=Tamás|last3=Terlaky|url=http://www.cas.mcmaster.ca/~terlaky/files/dut-twi-96-103.ps.gz |citeseerx=10.1.1.36.7090}}</ref>
 == यह भी देखें ==
 {{div col}}
-* क्रिस-क्रॉस एल्गोरिथम
+* क्रिस-क्रॉस कलनविधि
-* कटिंग-प्लेन विधि
+* कर्तनतल विधि
-* डेवेक्स एल्गोरिथम
+* डेवेक्स कलनविधि
-* फूरियर-मोट्ज़किन उन्मूलन
+* फोरियर-मोट्ज़किन उन्मूलन
-* ढतला हुआ वंश
+* प्रवणता अन्वय
-* कर्मकार का एल्गोरिदम
+* कर्मकार का कलनविधि
-* नेल्डर-मीड पद्धति | नेल्डर-मीड सरल अनुमानी
+* नेल्डर-मीड पद्धति | नेल्डर-मीड सरल स्वानुभविक
-* ब्लैंड का नियम, जो साइकिल चलाने से परहेज करता है
+* ब्लैंड का धुराग्र नियम, जो चक्रण से बचता है
 {{colend}}
 ==टिप्पणियाँ==
 {{reflist|2}}
@@ Line 303: / Line 287: @@
-==इस पृष्ठ में अनुपलब्ध आंतरिक कड़ियों की सूची==
 ==बाहरी संबंध==
@@ Line 320: / Line 302: @@
 {{Authority control}}
-{{DEFAULTSORT:Simplex Algorithm}}[[Category: अनुकूलन एल्गोरिदम और विधियां]]
+{{DEFAULTSORT:Simplex Algorithm}}
-[[Category: कंप्यूटिंग में 1947]]
-[[Category: एक्सचेंज एल्गोरिदम]]
-[[Category:रैखिक प्रोग्रामिंग]]
-[[Category:1947 में कंप्यूटर से संबंधित परिचय]]
-[[Category: Machine Translated Page]]
+[[Category:1947 में कंप्यूटर से संबंधित परिचय|Simplex Algorithm]]
-[[Category:Created On 14/11/2022]]
+[[Category:AC with 0 elements|Simplex Algorithm]]
+[[Category:All articles with unsourced statements|Simplex Algorithm]]
+[[Category:Articles with hatnote templates targeting a nonexistent page|Simplex Algorithm]]
+[[Category:Articles with short description|Simplex Algorithm]]
+[[Category:Articles with unsourced statements from June 2019|Simplex Algorithm]]
+[[Category:CS1]]
+[[Category:Created On 14/11/2022|Simplex Algorithm]]
+[[Category:Lua-based templates|Simplex Algorithm]]
+[[Category:Machine Translated Page|Simplex Algorithm]]
+[[Category:Multi-column templates|Simplex Algorithm]]
+[[Category:Pages using div col with small parameter|Simplex Algorithm]]
+[[Category:Short description with empty Wikidata description|Simplex Algorithm]]
+[[Category:Templates that add a tracking category|Simplex Algorithm]]
+[[Category:Templates using TemplateData|Simplex Algorithm]]
+[[Category:Templates using under-protected Lua modules|Simplex Algorithm]]
+[[Category:Wikipedia fully protected templates|Div col]]
+[[Category:अनुकूलन एल्गोरिदम और विधियां|Simplex Algorithm]]
+[[Category:एक्सचेंज एल्गोरिदम|Simplex Algorithm]]
+[[Category:कंप्यूटिंग में 1947|Simplex Algorithm]]
+[[Category:रैखिक प्रोग्रामिंग|Simplex Algorithm]]

Anonymous

Search

सिम्प्लेक्स एल्गोरिथम: Difference between revisions

Latest revision as of 14:33, 30 November 2022

इतिहास

अवलोकन

मानक रूप

सिम्प्लेक्स सारणी

ध्रुराग्र संक्रिया

कलनविधि

चर चयन प्रविष्टि

निकासीचर चयन

उदाहरण

एक प्रारंभिक विहित सारणी निष्कर्ष

उदाहरण

उन्नत विषय

कार्यान्वयन

विकृति: स्तंभन और चक्रण

निकृष्टतम स्थिति में दक्षता

वास्तविकता में दक्षता

अन्य कलनविधि

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

यह भी देखें

टिप्पणियाँ

संदर्भ

अग्रिम पठन

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories