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

Revision as of 10:51, 21 November 2022

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

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

इतिहास

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

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

अवलोकन

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

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

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

अधिकतम

{\textstyle \mathbf {c^{T}} \mathbf {x} }

A\mathbf {x} \leq \mathbf {b}

तथा

\mathbf {x} \geq 0

के अधीन

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

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

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

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

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

पहली पंक्ति उद्देश्य फलन को परिभाषित करती है और शेष पंक्तियाँ बाध्यताएं (कंस्ट्रेंट्स) को निर्दिष्ट करती हैं। पहले कॉलम में शून्य वेक्टर बी के समान आयाम के शून्य वेक्टर का प्रतिनिधित्व करता है (विभिन्न लेखक अलग-अलग सम्मेलनों का उपयोग सटीक लेआउट के रूप में करते हैं)। यदि A के स्तंभों को पुनर्व्यवस्थित किया जा सकता है ताकि इसमें क्रम p (A में पंक्तियों की संख्या) का पहचान आव्यूह हो, तो झांकी को विहित रूप में कहा जाता है।^[18] आइडेंटिटी आव्यूह के कॉलम से संबंधित चर्स को बेसिक चर्स कहा जाता है जबकि बाकी चर्स को नॉनबेसिक या फ्री वैरिएबल कहा जाता है। यदि गैर-मूल चर के मान 0 पर सेट हैं, तो मूल चर के मान आसानी से बी में प्रविष्टियों के रूप में प्राप्त किए जाते हैं और यह हल एक मूल साध्य हल है। यहाँ बीजीय व्याख्या यह है कि प्रत्येक पंक्ति द्वारा दर्शाए गए रैखिक समीकरण के गुणांक या तो $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 में बदलने के लिए पंक्ति के गुणकों को दूसरी पंक्तियों में जोड़ा जाता है। परिणाम यह है कि, यदि पिवोट तत्व एक पंक्ति आर में है, तो कॉलम पहचान आव्यूह का आर-वें कॉलम बन जाता है। इस स्तंभ के लिए चर अब एक मूल चर है, चर की जगह जो ऑपरेशन से पहले पहचान आव्यूह के आर-वें कॉलम के अनुरूप था। वास्तव में, धुरी स्तंभ से संबंधित चर मूल चर के सेट में प्रवेश करता है और इसे प्रवेश चर कहा जाता है, और जिस चर को प्रतिस्थापित किया जा रहा है वह मूल चर के सेट को छोड़ देता है और इसे छोड़ने वाला चर कहा जाता है। झांकी अभी भी विहित रूप में है लेकिन मूल चर के सेट के साथ एक तत्व बदल गया है।^[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 है तो मूल समस्या के समतुल्य एक विहित झांकी का निर्माण करने वाली परिणामी विहित झांकी से कृत्रिम चर को समाप्त किया जा सकता है। हल खोजने के लिए सिम्प्लेक्स एल्गोरिदम को लागू किया जा सकता है; इस कदम को द्वितीय चरण कहा जाता है। यदि न्यूनतम धनात्मक है तो प्रथम चरण की समस्या के लिए कोई साध्य हल नहीं है जहाँ कृत्रिम चर सभी शून्य हैं। इसका मतलब यह है कि मूल समस्या के लिए संभव क्षेत्र खाली है, और इसलिए मूल समस्या का कोई हल नहीं है।^[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}}

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

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

उन्नत विषय

कार्यान्वयन

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

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

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

@@ Line 8: / Line 8: @@
 == इतिहास ==
-जॉर्ज डेंटजिग ने द्वितीय विश्व युद्ध के दौरान डेस्क परिकलित्र का उपयोग करते हुए अमेरिकी सेना वायु सेना के लिए नियोजन विधियों पर काम किया। 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>
+जॉर्ज डेंटजिग ने द्वितीय विश्व युद्ध के दौरान डेस्क परिकलित्र का उपयोग करते हुए अमेरिकी सेना वायु सेना के लिए नियोजन विधियों पर काम किया। 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|रैखिक प्रोग्रामिंग}}
-[[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|3D . में सिम्प्लेक्स कलनविधि का पॉलीहेड्रॉन]]सिम्पलेक्स कलनविधि कैनोनिकल रूप में रैखिक फलनों पर कार्यरत होता है
 :अधिकतम <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" />
+यह भी दिखाया जा सकता है कि, यदि कोई चरम बिंदु वस्तुनिष्ठ कार्य का अधिकतम बिंदु नहीं है, तो बिंदु से युक्त एक किनारा होता है ताकि बिंदु से दूर जाने वाले किनारे पर वस्तुनिष्ठ कार्य का मान सख्ती से बढ़ रहा हो।<ref name="Murty137">{{harvtxt|Murty|1983|loc=Section 3.8|p=137}}</ref> यदि किनारा परिमित है, तो किनारा दूसरे चरम बिंदु से जुड़ता है जहां उद्देश्य फलन का मान अधिक होता है, अन्यथा उद्देश्य फलन किनारे पर ऊपर की ओर असंबद्ध होता है और रैखिक फलन का कोई हल नहीं होता है। सिम्पलेक्स कलनविधि अधिक से अधिक वस्तुनिष्ठ मूल्यों के साथ पॉलीटॉप के किनारों पर चरम बिंदुओं पर चलकर इस अंतर्दृष्टि को लागू करता है। यह तब तक जारी रहता है जब तक कि अधिकतम मूल्य तक नहीं पहुंच जाता है, या एक असीमित किनारे का दौरा नहीं किया जाता है (निष्कर्ष निकाला है कि समस्या का कोई हल नहीं है)। कलनविधि सदैव निलम्बित होता है क्योंकि पॉलीटॉप में शीर्षों की संख्या परिमित होती है; इसके अतिरिक्त चूंकि हम शीर्षों के बीच सदैव एक ही दिशा में स्थानांतरित होते हैं (उद्देश्य फलन की दिशा में), हम आशा करते हैं कि देखे गए शीर्षों की संख्या कम होगी।<ref name="Murty137" />
-एक रेखीय कार्यक्रम का हल दो चरणों में पूरा होता है। पहले चरण में, जिसे चरण I के रूप में जाना जाता है, एक प्रारंभिक चरम बिंदु पाया जाता है। कार्यक्रम की प्रकृति के आधार पर यह तुच्छ हो सकता है, लेकिन सामान्य तौर पर इसे मूल कार्यक्रम के संशोधित संस्करण में सिम्पलेक्स कलनविधि लागू करके हल किया जा सकता है। चरण I के संभावित परिणाम या तो यह हैं कि एक बुनियादी व्यवहार्य हल मिल गया है या यह कि संभव क्षेत्र खाली है। बाद के मामले में रैखिक कार्यक्रम को अक्षम कहा जाता है। दूसरे चरण में, द्वितीय चरण में, सरल कलनविधि चरण I में प्रारंभिक बिंदु के रूप में मिले बुनियादी व्यवहार्य हल का उपयोग करके लागू किया जाता है। चरण II से संभावित परिणाम या तो एक इष्टतम बुनियादी व्यवहार्य हल है या एक अनंत किनारा है जिस पर ऊपर उद्देश्य फलन असीम है।<ref name="DantzigThapa1">[[George B. Dantzig]] and Mukund N. Thapa. 1997. ''Linear programming 1: Introduction''. Springer-Verlag.</ref><ref name="NeringTucker">
+एक रेखीय फलन का हल दो चरणों में पूरा होता है। पहले चरण में, जिसे चरण I के रूप में जाना जाता है, प्रारंभिक चरम बिंदु पाया जाता है। फलन की प्रकृति के आधार पर यह तुच्छ हो सकता है, लेकिन सामान्य तौर पर इसे मूल फलन के संशोधित संस्करण में सिम्पलेक्स कलनविधि लागू करके हल किया जा सकता है। चरण I के संभावित परिणाम या तो यह हैं कि एक मूल साध्य हल मिल गया है या यह कि संभव क्षेत्र खाली है। बाद के मामले में रैखिक फलन को अक्षम कहा जाता है। दूसरे चरण में, द्वितीय चरण में, सरल कलनविधि चरण 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 48: @@
    s_1,\, s_2 &\ge 0
 \end{align}</math>
-इस रूप में असमानताओं पर बीजगणितीय जोड़-तोड़ करना बहुत आसान है। असमानताओं में जहां ≥ दूसरे वाले के रूप में प्रकट होता है, कुछ लेखक अधिशेष चर के रूप में पेश किए गए चर का उल्लेख करते हैं।
+इस रूप में असमानताओं पर बीजगणितीय जोड़-तोड़ करना बहुत आसान है। असमानताओं में जहां ≥ दूसरे वाले के रूप में प्रकट होता है, कुछ लेखक अधिशेष चर के रूप में प्रस्तुत किए गए चर का उल्लेख करते हैं।
-तीसरा, प्रत्येक अप्रतिबंधित चर को लीनियर प्रोग्राम से हटा दिया जाता है। यह दो तरीकों से किया जा सकता है, एक है चर के लिए समीकरणों में से किसी एक में हल करके और फिर चर को प्रतिस्थापन द्वारा हटाकर। अन्य चर को दो प्रतिबंधित चर के अंतर से बदलना है। उदाहरण के लिए, यदि <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 68: / Line 68: @@
    \end{bmatrix}
 </math>
-पहली पंक्ति उद्देश्य फलन को परिभाषित करती है और शेष पंक्तियाँ बाधाओं को निर्दिष्ट करती हैं। पहले कॉलम में शून्य वेक्टर बी के समान आयाम के शून्य वेक्टर का प्रतिनिधित्व करता है (विभिन्न लेखक अलग-अलग सम्मेलनों का उपयोग सटीक लेआउट के रूप में करते हैं)। यदि A के स्तंभों को पुनर्व्यवस्थित किया जा सकता है ताकि इसमें क्रम p (A में पंक्तियों की संख्या) का पहचान मैट्रिक्स हो, तो झांकी को विहित रूप में कहा जाता है।<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> कॉलम होंगे, और शेष कॉलम कुछ अन्य गुणांक के साथ होंगे (ये अन्य चर हमारे गैर-मूल चर का प्रतिनिधित्व करते हैं)। गैर-मूल चर के मानों को शून्य पर सेट करके हम प्रत्येक पंक्ति में यह सुनिश्चित करते हैं कि उसके कॉलम में <math>1</math> द्वारा दर्शाए गए चर का मान उस पंक्ति के <math>b</math> मान के बराबर है।
+पहली पंक्ति उद्देश्य फलन को परिभाषित करती है और शेष पंक्तियाँ बाध्यताएं (कंस्ट्रेंट्स) को निर्दिष्ट करती हैं। पहले कॉलम में शून्य वेक्टर बी के समान आयाम के शून्य वेक्टर का प्रतिनिधित्व करता है (विभिन्न लेखक अलग-अलग सम्मेलनों का उपयोग सटीक लेआउट के रूप में करते हैं)। यदि A के स्तंभों को पुनर्व्यवस्थित किया जा सकता है ताकि इसमें क्रम p (A में पंक्तियों की संख्या) का पहचान आव्यूह हो, तो झांकी को विहित रूप में कहा जाता है।<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> कॉलम होंगे, और शेष कॉलम कुछ अन्य गुणांक के साथ होंगे (ये अन्य चर हमारे गैर-मूल चर का प्रतिनिधित्व करते हैं)। गैर-मूल चर के मानों को शून्य पर सेट करके हम प्रत्येक पंक्ति में यह सुनिश्चित करते हैं कि उसके कॉलम में <math>1</math> द्वारा दर्शाए गए चर का मान उस पंक्ति के <math>b</math> मान के बराबर है।
-इसके विपरीत, एक बुनियादी व्यवहार्य हल दिया गया है, गैर-शून्य चर के अनुरूप कॉलम को एक गैर-एकवचन मैट्रिक्स तक विस्तारित किया जा सकता है। यदि संबंधित झांकी को इस मैट्रिक्स के व्युत्क्रम से गुणा किया जाता है तो परिणाम विहित रूप में एक झांकी है।<ref>{{harvtxt|Murty|1983|loc=section 3.12}}</ref>
+इसके विपरीत, एक मूल साध्य हल दिया गया है, गैर-शून्य चर के अनुरूप कॉलम को एक गैर-एकवचन आव्यूह तक विस्तारित किया जा सकता है। यदि संबंधित झांकी को इस आव्यूह के व्युत्क्रम से गुणा किया जाता है तो परिणाम विहित रूप में एक झांकी है।<ref>{{harvtxt|Murty|1983|loc=section 3.12}}</ref>
 माना
@@ Line 86: / Line 86: @@
    \end{bmatrix}
 </math>
-जहां z<sub>''B''</sub> संबंधित बुनियादी व्यवहार्य हल पर उद्देश्य फलन का मान है। अद्यतित गुणांक, जिसे सापेक्ष लागत गुणांक के रूप में भी जाना जाता है, गैर बुनियादी चर के संबंध में उद्देश्य फलन के परिवर्तन की दरें हैं।<ref name="NeringTucker" />
+जहां z<sub>''B''</sub> संबंधित मूल साध्य हल पर उद्देश्य फलन का मान है। अद्यतित गुणांक, जिसे सापेक्ष लागत गुणांक के रूप में भी जाना जाता है, गैर मूल चर के संबंध में उद्देश्य फलन के परिवर्तन की दरें हैं।<ref name="NeringTucker" />
 == धुरी संचालन ==
-बुनियादी व्यवहार्य हल से आसन्न बुनियादी व्यवहार्य हल में जाने का ज्यामितीय संचालन एक पिवट ऑपरेशन के रूप में लागू किया जाता है। सबसे पहले, एक गैर-शून्य धुरी तत्व को एक गैर-मूल स्तंभ में चुना जाता है। इस तत्व वाली पंक्ति को इस तत्व को 1 में बदलने के लिए इसके व्युत्क्रम से गुणा किया जाता है, और फिर कॉलम में अन्य प्रविष्टियों को 0 में बदलने के लिए पंक्ति के गुणकों को दूसरी पंक्तियों में जोड़ा जाता है। परिणाम यह है कि, यदि पिवोट तत्व एक पंक्ति आर में है, तो कॉलम पहचान मैट्रिक्स का आर-वें कॉलम बन जाता है। इस स्तंभ के लिए चर अब एक मूल चर है, चर की जगह जो ऑपरेशन से पहले पहचान मैट्रिक्स के आर-वें कॉलम के अनुरूप था। वास्तव में, धुरी स्तंभ से संबंधित चर बुनियादी चर के सेट में प्रवेश करता है और इसे प्रवेश चर कहा जाता है, और जिस चर को प्रतिस्थापित किया जा रहा है वह बुनियादी चर के सेट को छोड़ देता है और इसे छोड़ने वाला चर कहा जाता है। झांकी अभी भी विहित रूप में है लेकिन बुनियादी चर के सेट के साथ एक तत्व बदल गया है।<ref name="DantzigThapa1"/><ref name="NeringTucker"/>
+मूल साध्य हल से आसन्न मूल साध्य हल में जाने का ज्यामितीय संचालन एक पिवट ऑपरेशन के रूप में लागू किया जाता है। सर्व प्रथम, एक गैर-शून्य धुरी तत्व को एक गैर-मूल स्तंभ में चुना जाता है। इस तत्व वाली पंक्ति को इस तत्व को 1 में बदलने के लिए इसके व्युत्क्रम से गुणा किया जाता है, और फिर कॉलम में अन्य प्रविष्टियों को 0 में बदलने के लिए पंक्ति के गुणकों को दूसरी पंक्तियों में जोड़ा जाता है। परिणाम यह है कि, यदि पिवोट तत्व एक पंक्ति आर में है, तो कॉलम पहचान आव्यूह का आर-वें कॉलम बन जाता है। इस स्तंभ के लिए चर अब एक मूल चर है, चर की जगह जो ऑपरेशन से पहले पहचान आव्यूह के आर-वें कॉलम के अनुरूप था। वास्तव में, धुरी स्तंभ से संबंधित चर मूल चर के सेट में प्रवेश करता है और इसे प्रवेश चर कहा जाता है, और जिस चर को प्रतिस्थापित किया जा रहा है वह मूल चर के सेट को छोड़ देता है और इसे छोड़ने वाला चर कहा जाता है। झांकी अभी भी विहित रूप में है लेकिन मूल चर के सेट के साथ एक तत्व बदल गया है।<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> विकसित किए गए हैं।
+यदि एक से अधिक कॉलम हैं ताकि वस्तुनिष्ठ पंक्ति में प्रविष्टि सकारात्मक हो तो मूल चर के सेट में से किसे जोड़ना है इसका चुनाव कुछ मनमाना है और कई एंट्री चर चॉइस रूल्स<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 को चुना जाता है ताकि
 :<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}}
-रैखिक कार्यक्रम पर विचार करें
+रैखिक फलन पर विचार करें
 :छोटा करना
 ::<math>Z = -2 x - 3 y - 4 z\,</math>
@@ Line 127: / 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 को पिवट पंक्ति होना चाहिए। पिवट का प्रदर्शन करता है
@@ Line 137: / Line 137: @@
    \end{bmatrix}
 </math>
-अब कॉलम 4 और 5 मूल चर z और s का प्रतिनिधित्व करते हैं और संबंधित बुनियादी व्यवहार्य हल है
+अब कॉलम 4 और 5 मूल चर z और s का प्रतिनिधित्व करते हैं और संबंधित मूल साध्य हल है
 :<math>x=y=t=0,\,z=5,\,s=5.</math>
 अगले चरण के लिए, वस्तुनिष्ठ पंक्ति में कोई सकारात्मक प्रविष्टि नहीं है और वास्तव में
@@ Line 144: / Line 144: @@
 == एक प्रारंभिक विहित झांकी ढूँढना ==
-सामान्य तौर पर, एक रेखीय कार्यक्रम विहित रूप में नहीं दिया जाएगा और सिंप्लेक्स कलनविधि शुरू होने से पहले एक समकक्ष विहित झांकी मिलनी चाहिए। यह कृत्रिम चर के परिचय से पूरा किया जा सकता है। इन चरों के लिए आइडेंटिटी मैट्रिक्स के कॉलम को कॉलम वैक्टर के रूप में जोड़ा जाता है। यदि बाधा समीकरण के लिए बी मान ऋणात्मक है, तो पहचान मैट्रिक्स कॉलम जोड़ने से पहले समीकरण को अस्वीकार कर दिया गया है। यह संभव हल या इष्टतम हल के सेट को नहीं बदलता है, और यह सुनिश्चित करता है कि ढीले चर एक प्रारंभिक व्यवहार्य हल का गठन करेंगे। नई झांकी विहित रूप में है लेकिन यह मूल समस्या के बराबर नहीं है। तो कृत्रिम चर के योग के बराबर एक नया उद्देश्य फलन पेश किया जाता है और न्यूनतम खोजने के लिए सरल एल्गोरिदम लागू किया जाता है; संशोधित रेखीय कार्यक्रम को चरण I समस्या कहा जाता है।<ref>{{harvtxt|Murty|1983|p=60}}</ref>
+सामान्य तौर पर, एक रेखीय फलन विहित रूप में नहीं दिया जाएगा और सिंप्लेक्स कलनविधि शुरू होने से पहले एक समकक्ष विहित झांकी मिलनी चाहिए। यह कृत्रिम चर के परिचय से पूरा किया जा सकता है। इन चरों के लिए आइडेंटिटी आव्यूह के कॉलम को कॉलम वैक्टर के रूप में जोड़ा जाता है। यदि बाध्यता (कन्सट्रैन्ट) समीकरण के लिए बी मान ऋणात्मक है, तो पहचान आव्यूह कॉलम जोड़ने से पहले समीकरण को अस्वीकार कर दिया गया है। यह संभव हल या इष्टतम हल के सेट को नहीं बदलता है, और यह सुनिश्चित करता है कि ढीले चर एक प्रारंभिक साध्य हल का गठन करेंगे। नई झांकी विहित रूप में है लेकिन यह मूल समस्या के बराबर नहीं है। तो कृत्रिम चर के योग के बराबर एक नया उद्देश्य फलन प्रस्तुत किया जाता है और न्यूनतम खोजने के लिए सरल एल्गोरिदम लागू किया जाता है; संशोधित रेखीय फलन को चरण I समस्या कहा जाता है।<ref>{{harvtxt|Murty|1983|p=60}}</ref>
-चरण I समस्या के लिए लागू सिंप्लेक्स एल्गोरिथ्म को नए उद्देश्य फलन के लिए न्यूनतम मूल्य के साथ समाप्त होना चाहिए, क्योंकि गैर-नकारात्मक चर का योग होने के कारण, इसका मान 0 से नीचे है। यदि न्यूनतम 0 है तो मूल समस्या के समतुल्य एक विहित झांकी का निर्माण करने वाली परिणामी विहित झांकी से कृत्रिम चर को समाप्त किया जा सकता है। हल खोजने के लिए सिम्प्लेक्स एल्गोरिदम को लागू किया जा सकता है; इस कदम को द्वितीय चरण कहा जाता है। यदि न्यूनतम धनात्मक है तो प्रथम चरण की समस्या के लिए कोई व्यवहार्य हल नहीं है जहाँ कृत्रिम चर सभी शून्य हैं। इसका मतलब यह है कि मूल समस्या के लिए संभव क्षेत्र खाली है, और इसलिए मूल समस्या का कोई हल नहीं है।<ref name="DantzigThapa1" /><ref name="NeringTucker" /><ref name="Padberg">M. Padberg, ''Linear Optimization and Extensions'', Second Edition, Springer-Verlag, 1999.</ref>
+चरण I समस्या के लिए लागू सिंप्लेक्स एल्गोरिथ्म को नए उद्देश्य फलन के लिए न्यूनतम मूल्य के साथ समाप्त होना चाहिए, क्योंकि अऋणात्मक चर का योग होने के कारण, इसका मान 0 से नीचे है। यदि न्यूनतम 0 है तो मूल समस्या के समतुल्य एक विहित झांकी का निर्माण करने वाली परिणामी विहित झांकी से कृत्रिम चर को समाप्त किया जा सकता है। हल खोजने के लिए सिम्प्लेक्स एल्गोरिदम को लागू किया जा सकता है; इस कदम को द्वितीय चरण कहा जाता है। यदि न्यूनतम धनात्मक है तो प्रथम चरण की समस्या के लिए कोई साध्य हल नहीं है जहाँ कृत्रिम चर सभी शून्य हैं। इसका मतलब यह है कि मूल समस्या के लिए संभव क्षेत्र खाली है, और इसलिए मूल समस्या का कोई हल नहीं है।<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>
@@ Line 176: / Line 176: @@
 मूल उद्देश्य फलन को परिभाषित करने वाले समीकरण को द्वितीय चरण की प्रत्याशा में बनाए रखा जाता है।
-निर्माण के द्वारा, यू और वी दोनों बुनियादी चर हैं, क्योंकि वे प्रारंभिक पहचान मैट्रिक्स का हिस्सा हैं। हालाँकि, वस्तुनिष्ठ फलन W वर्तमान में मानता है कि u और v दोनों 0 हैं। वस्तुनिष्ठ फलन को सही मान के लिए समायोजित करने के लिए जहाँ u = 10 और v = 15, पहली पंक्ति में तीसरी और चौथी पंक्तियाँ जोड़ें
+निर्माण के द्वारा, यू और वी दोनों मूल चर हैं, क्योंकि वे प्रारंभिक पहचान आव्यूह का हिस्सा हैं। हालाँकि, वस्तुनिष्ठ फलन W वर्तमान में मानता है कि u और v दोनों 0 हैं। वस्तुनिष्ठ फलन को सही मान के लिए समायोजित करने के लिए जहाँ u = 10 और v = 15, पहली पंक्ति में तीसरी और चौथी पंक्तियाँ जोड़ें
 :<math>
    \begin{bmatrix}
@@ Line 211: / Line 211: @@
    \end{bmatrix}
 </math>
-यह, सौभाग्य से, पहले से ही इष्टतम है और मूल रैखिक कार्यक्रम के लिए इष्टतम मूल्य −130/7 है।
+यह, सौभाग्य से, पहले से ही इष्टतम है और मूल रैखिक फलन के लिए इष्टतम मूल्य −130/7 है।
 ==उन्नत विषय==
@@ Line 217: / Line 217: @@
 ===कार्यान्वयन ===
 {{main|Revised simplex algorithm}}
-कलनविधि का वर्णन करने के लिए ऊपर इस्तेमाल किया गया झांकी फॉर्म खुद को एक तत्काल कार्यान्वयन के लिए उधार देता है जिसमें झांकी को एक आयताकार (एम + 1) -बाय- (एम + एन + 1) सरणी के रूप में बनाए रखा जाता है। पहचान मैट्रिक्स के m स्पष्ट स्तंभों को संग्रहीत करने से बचना सीधा है जो '''B''' के आधार पर ['''A''', '''I'''] के स्तंभों का सबसेट होने के कारण झांकी के भीतर होगा। इस कार्यान्वयन को "मानक सिंप्लेक्स कलनविधि" के रूप में जाना जाता है। भंडारण और संगणना ओवरहेड ऐसा है कि बड़ी रैखिक प्रोग्रामिंग समस्याओं को हल करने के लिए मानक सिंप्लेक्स विधि एक निषेधात्मक रूप से महंगा दृष्टिकोण है।
+कलनविधि का वर्णन करने के लिए ऊपर इस्तेमाल किया गया झांकी फॉर्म खुद को एक तत्काल कार्यान्वयन के लिए उधार देता है जिसमें झांकी को एक आयताकार (एम + 1) -बाय- (एम + एन + 1) सरणी के रूप में बनाए रखा जाता है। पहचान आव्यूह के m स्पष्ट स्तंभों को संग्रहीत करने से बचना सीधा है जो '''B''' के आधार पर ['''A''', '''I'''] के स्तंभों का सबसेट होने के कारण झांकी के भीतर होगा। इस कार्यान्वयन को "मानक सिंप्लेक्स कलनविधि" के रूप में जाना जाता है। भंडारण और संगणना ओवरहेड ऐसा है कि बड़ी रैखिक प्रोग्रामिंग समस्याओं को हल करने के लिए मानक सिंप्लेक्स विधि एक निषेधात्मक रूप से महंगा दृष्टिकोण है।
-प्रत्येक सिम्प्लेक्स पुनरावृत्ति में, केवल आवश्यक डेटा झांकी की पहली पंक्ति है, झांकी का (निर्णायक) स्तंभ प्रवेश करने वाले चर और दाईं ओर के अनुरूप है। बाद वाले को मुख्य स्तंभ का उपयोग करके अद्यतन किया जा सकता है और झांकी की पहली पंक्ति को छोड़ने वाले चर के अनुरूप (निर्णायक) पंक्ति का उपयोग करके अद्यतन किया जा सकता है। मैट्रिक्स बी और एक मैट्रिक्स-वेक्टर उत्पाद ए का उपयोग करके सम्मिलित समीकरणों के रैखिक प्रणालियों के हल का उपयोग करके सीधे धुरी स्तंभ और धुरी पंक्ति दोनों की गणना की जा सकती है। ये अवलोकन "संशोधित सिम्प्लेक्स कलनविधि" को प्रेरित करते हैं, जिसके लिए कार्यान्वयन बी के उनके उलटा प्रतिनिधित्व द्वारा प्रतिष्ठित हैं।<ref name="DantzigThapa2">
+प्रत्येक सिम्प्लेक्स पुनरावृत्ति में, केवल आवश्यक डेटा झांकी की पहली पंक्ति है, झांकी का (निर्णायक) स्तंभ प्रवेश करने वाले चर और दाईं ओर के अनुरूप है। बाद वाले को मुख्य स्तंभ का उपयोग करके अद्यतन किया जा सकता है और झांकी की पहली पंक्ति को छोड़ने वाले चर के अनुरूप (निर्णायक) पंक्ति का उपयोग करके अद्यतन किया जा सकता है। आव्यूह बी और एक आव्यूह-वेक्टर उत्पाद ए का उपयोग करके सम्मिलित समीकरणों के रैखिक प्रणालियों के हल का उपयोग करके सीधे धुरी स्तंभ और धुरी पंक्ति दोनों की गणना की जा सकती है। ये अवलोकन "संशोधित सिम्प्लेक्स कलनविधि" को प्रेरित करते हैं, जिसके लिए कार्यान्वयन बी के उनके उलटा प्रतिनिधित्व द्वारा प्रतिष्ठित हैं।<ref name="DantzigThapa2">
 [[George B. Dantzig]] and Mukund N. Thapa. 2003. ''Linear Programming 2: Theory and Extensions''. Springer-Verlag.</ref>
-बड़ी रेखीय-प्रोग्रामिंग समस्याओं में ए आमतौर पर एक विरल मैट्रिक्स है और, जब इसके उल्टे प्रतिनिधित्व को बनाए रखते हुए बी की परिणामी विरलता का शोषण किया जाता है, तो संशोधित सिंप्लेक्स एल्गोरिथ्म मानक सिम्प्लेक्स विधि की तुलना में बहुत अधिक कुशल होता है। वाणिज्यिक सिंप्लेक्स सॉल्वर संशोधित सिंप्लेक्स एल्गोरिदम पर आधारित हैं।<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="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">
+यदि सभी मूल चरों के मान पूरी तरह से सकारात्मक हैं, तो एक धुरी के परिणामस्वरूप उद्देश्य मूल्य में सुधार होना चाहिए। जब यह सदैव होता है तो मूल चर का कोई सेट दो बार नहीं होता है और सिंप्लेक्स एल्गोरिथ्म को सीमित चरणों के बाद समाप्त होना चाहिए। मूल साध्य हल जहां कम से कम एक मूल चर शून्य है, उसे पतित कहा जाता है और इसके परिणामस्वरूप पिवोट्स हो सकते हैं जिसके लिए उद्देश्य मूल्य में कोई सुधार नहीं होता है। इस मामले में हल में कोई वास्तविक परिवर्तन नहीं होता है, लेकिन केवल मूल चर के सेट में परिवर्तितव होता है। जब इस तरह के कई पिवोट्स एक के बाद एक होते हैं, तो कोई सुधार नहीं होता है; बड़े औद्योगिक अनुप्रयोगों में अध: पतन आम है और इस तरह के "स्टालिंग" उल्लेखनीय है। रुकने से भी बदतर यह संभावना है कि मूल चर का एक ही सेट दो बार होता है, इस मामले में, सिंप्लेक्स एल्गोरिथ्म के नियतात्मक धुरी नियम एक अनंत लूप, या "चक्र" उत्पन्न करेंगे। जबकि अध: पतन व्यवहार में नियम है और स्टाल लगाना आम है, साइकिल चलाना व्यवहार में दुर्लभ है। पैडबर्ग में व्यावहारिक साइकिल चालन के उदाहरण की चर्चा होती है।<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>
+{{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 247: / 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> लगभग उसी समय यह दिखाया गया था कि एक कृत्रिम धुरी नियम मौजूद है जिसके लिए इसके आउटपुट की गणना पीएसपीएसीई-पूर्ण है।<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>{{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 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 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=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}}
-रैखिक-भिन्नात्मक प्रोग्रामिंग (एलएफपी) रैखिक प्रोग्रामिंग (एलपी) का सामान्यीकरण है। एलपी में ऑब्जेक्टिव फंक्शन एक लीनियर फंक्शन है, जबकि लीनियर-फ्रैक्शनल प्रोग्राम का ऑब्जेक्टिव फंक्शन दो लीनियर फंक्शन्स का अनुपात है। दूसरे शब्दों में, एक रेखीय कार्यक्रम एक आंशिक-रैखिक कार्यक्रम है जिसमें भाजक एक स्थिर कार्य है जिसका मान हर जगह एक है। एक रेखीय-भिन्नात्मक कार्यक्रम को सिम्प्लेक्स कलनविधि<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|

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

Revision as of 10:51, 21 November 2022

Contents

इतिहास

अवलोकन

मानक रूप

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

धुरी संचालन

कलनविधि

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

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

उदाहरण

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

उदाहरण

उन्नत विषय

कार्यान्वयन

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

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

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

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

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

यह भी देखें

टिप्पणियाँ

संदर्भ

अग्रिम पठन

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Revision as of 10:51, 21 November 2022

इतिहास

अवलोकन

मानक रूप

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

धुरी संचालन

कलनविधि

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

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

उदाहरण

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

उदाहरण

उन्नत विषय

कार्यान्वयन

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

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

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

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

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

यह भी देखें

टिप्पणियाँ

संदर्भ

अग्रिम पठन

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories