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

{{short description|Algorithm}}
{{about|the linear programming algorithm|the non-linear optimization heuristic|Nelder–Mead method}}
<!-- {{Context|date=March 2012}} -->
ऑप्टिमाइज़ेशन (गणित) में, जॉर्ज डेंटज़िग का सिंप्लेक्स एल्गोरिथम (या सिम्प्लेक्स विधि) रैखिक प्रोग्रामिंग के लिए एक लोकप्रिय एल्गोरिथम है।<ref name="Murty">{{cite book|last=Murty|first=Katta G.|author-link=Katta G. Murty|title=रैखिक प्रोग्रामिंग|publisher=John Wiley & Sons Inc.1, 2000 |url=http://www.computer.org/csdl/mags/cs/2000/01/c1022.html}}</ref>
एल्गोरिथ्म का नाम एक सिम्प्लेक्स की अवधारणा से लिया गया है और थियोडोर मोत्ज़किन | टी द्वारा सुझाया गया था। एस मोत्ज़किन।<ref name="Murty22" >{{harvtxt|Murty|1983|loc=Comment 2.2}}</ref> सरलता का वास्तव में विधि में उपयोग नहीं किया जाता है, लेकिन इसकी एक व्याख्या यह है कि यह सरल शंकु (ज्यामिति) पर संचालित होता है, और ये एक अतिरिक्त बाधा के साथ उचित सरलता बन जाते हैं।<ref name="Murty39">{{harvtxt|Murty|1983|loc=Note 3.9}}</ref><ref name="StoneTovey">{{cite journal|last1=Stone|first1=Richard E.|last2=Tovey|first2=Craig A.|title=सिम्प्लेक्स और प्रोजेक्टिव स्केलिंग एल्गोरिदम को पुनरावृत्त रूप से कम से कम वर्ग विधियों के रूप में पुन: भारित किया जाता है|journal=SIAM Review|volume=33|year=1991|issue=2|pages=220–237
|mr=1124362|jstor=2031142|doi=10.1137/1033049}}</ref><ref>{{cite journal|last1=Stone|first1=Richard E.|last2=Tovey|first2=Craig A.|title=इरेटम: सिम्पलेक्स और प्रोजेक्टिव स्केलिंग एल्गोरिथम पुनरावृत्त रूप से कम से कम वर्गों के तरीकों को फिर से भारित करता है|journal=SIAM Review|volume=33|year=1991|issue=3|pages=461|mr=1124362|doi=10.1137/1033100|jstor=2031443}}</ref><ref  name="Strang">{{cite journal|last=Strang|first=Gilbert|author-link=Gilbert Strang|title=कर्मकार का एल्गोरिथम और अनुप्रयुक्त गणित में इसका स्थान|journal=[[The Mathematical Intelligencer]]|date=1 June 1987|issn=0343-6993|pages=4–10|volume=9|doi=10.1007/BF03025891|mr=883185|issue=2|s2cid=123541868}}</ref> प्रश्न में साधारण शंकु एक ज्यामितीय वस्तु के कोने (यानी, कोने के पड़ोस) हैं जिन्हें पॉलीटोप कहा जाता है। इस पॉलीटॉप के आकार को ऑब्जेक्टिव फ़ंक्शन पर लागू रैखिक असमानताओं की प्रणाली द्वारा परिभाषित किया गया है।

== इतिहास ==
जॉर्ज डेंटजिग ने द्वितीय विश्व युद्ध के दौरान डेस्क कैलकुलेटर का उपयोग करते हुए अमेरिकी सेना वायु सेना के लिए योजना बनाने के तरीकों पर काम किया। 1946 के दौरान उनके सहयोगी ने उन्हें दूसरी नौकरी लेने से विचलित करने के लिए नियोजन प्रक्रिया को यंत्रीकृत करने की चुनौती दी। डेंटज़िग ने वासिली लियोनटिफ़ के काम से प्रेरित रैखिक असमानताओं के रूप में समस्या को तैयार किया, हालाँकि, उस समय उन्होंने अपने सूत्रीकरण के हिस्से के रूप में एक उद्देश्य को शामिल नहीं किया था। एक उद्देश्य के बिना, बड़ी संख्या में समाधान संभव हो सकते हैं, और इसलिए सबसे अच्छा संभव समाधान खोजने के लिए, सैन्य-निर्दिष्ट जमीनी नियमों का उपयोग किया जाना चाहिए जो वर्णन करते हैं कि लक्ष्यों को कैसे प्राप्त किया जा सकता है, एक लक्ष्य को निर्दिष्ट करने के विपरीत। Dantzig की मुख्य अंतर्दृष्टि यह महसूस करना था कि ऐसे अधिकांश बुनियादी नियमों को एक रेखीय उद्देश्य समारोह में अनुवादित किया जा सकता है जिसे अधिकतम करने की आवश्यकता है।<ref>{{Cite journal|url = https://apps.dtic.mil/sti/pdfs/ADA112060.pdf|archive-url = https://web.archive.org/web/20150520183722/http://www.dtic.mil/cgi-bin/GetTRDoc?Location=U2&doc=GetTRDoc.pdf&AD=ADA112060|url-status = live|archive-date = May 20, 2015|title = रैखिक प्रोग्रामिंग की उत्पत्ति के बारे में यादें|date = April 1982|journal = Operations Research Letters|doi = 10.1016/0167-6377(82)90043-8|volume = 1|issue = 2 |pages=43–48|last1 = Dantzig|first1 = George B.}}</ref> सरल विधि का विकास विकासवादी था और लगभग एक वर्ष की अवधि में हुआ।<ref>{{Cite journal|url = http://www.phpsimplex.com/en/Dantzig_interview.htm|title = जॉर्ज बी. डेंट्ज़िग के साथ एक साक्षात्कार: रैखिक प्रोग्रामिंग के जनक|last = Albers and Reid|date = 1986|journal = College Mathematics Journal|volume = 17|issue = 4|doi = 10.1080/07468342.1986.11972971|pages = 292–314}}</ref>
1947 के मध्य में डेंटज़िग ने अपने सूत्रीकरण के हिस्से के रूप में एक उद्देश्य समारोह को शामिल करने के बाद, समस्या गणितीय रूप से अधिक सुगम थी। डेंटज़िग ने महसूस किया कि जॉर्ज डेंट्ज़िग#गणितीय सांख्यिकी को उनके प्रोफेसर जेरज़ी नेमैन की कक्षा में होमवर्क के रूप में (और वास्तव में बाद में हल किया गया) अनसुलझी समस्याओं में से एक, रैखिक कार्यक्रमों के लिए एक एल्गोरिथ्म खोजने के लिए लागू थी। इस समस्या में सामान्य रैखिक कार्यक्रमों के लिए बैनाच रिक्त स्थान पर लैग्रेंज मल्टीप्लायरों के अस्तित्व को खोजने में शामिल है, प्रत्येक शून्य और एक के बीच घिरा हुआ है, और लेबेसेग इंटीग्रल के रूप में व्यक्त रैखिक बाधाओं को संतुष्ट करता है। डेंटज़िग ने बाद में अपने डॉक्टरेट को अर्जित करने के लिए अपने होमवर्क को एक थीसिस के रूप में प्रकाशित किया। इस थीसिस में इस्तेमाल किए गए कॉलम ज्योमेट्री ने डेंटज़िग को अंतर्दृष्टि प्रदान की जिससे उन्हें विश्वास हो गया कि सिम्प्लेक्स विधि बहुत कुशल होगी।<ref>{{Cite encyclopedia|url = http://apps.dtic.mil/dtic/tr/fulltext/u2/a182708.pdf|archive-url = https://web.archive.org/web/20150529003047/http://www.dtic.mil/dtic/tr/fulltext/u2/a182708.pdf|url-status = live|archive-date = May 29, 2015|title = सिंप्लेक्स विधि की उत्पत्ति|last = Dantzig|first = George|date = May 1987|work = A History of Scientific Computing|editor-last=Nash|editor-first=Stephen G.|publisher=Association for Computing Machinery|pages = 141–151|doi = 10.1145/87252.88081|isbn = 978-0-201-50814-7}}</ref>


== अवलोकन ==
{{further|Linear programming}}
[[Image:Simplex-description-en.svg|thumb|240px|रैखिक असमानताओं की एक प्रणाली एक पॉलीटोप को एक व्यवहार्य क्षेत्र के रूप में परिभाषित करती है। सिंप्लेक्स एल्गोरिथ्म एक प्रारंभिक शीर्ष (ज्यामिति) से शुरू होता है और पॉलीटोप के किनारों के साथ चलता है जब तक कि यह शीर्ष तक नहीं पहुंच जाता
इष्टतम समाधान का।]]

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

यह दिखाया जा सकता है कि मानक रूप में एक रैखिक कार्यक्रम के लिए, यदि उद्देश्य फलन का व्यवहार्य क्षेत्र पर अधिकतम मान है, तो इसका यह मान (कम से कम) चरम बिंदुओं में से एक पर है।<ref>{{harvtxt|Murty|1983|loc=Theorem 3.3}}</ref> यह अपने आप में समस्या को एक सीमित गणना में कम कर देता है क्योंकि चरम बिंदुओं की एक सीमित संख्या होती है, लेकिन चरम बिंदुओं की संख्या सबसे छोटे रैखिक कार्यक्रमों के अलावा सभी के लिए असहनीय रूप से बड़ी होती है।<ref>{{harvtxt|Murty|1983|loc=Section 3.13|p=143}}</ref>
यह भी दिखाया जा सकता है कि, यदि एक चरम बिंदु वस्तुनिष्ठ कार्य का अधिकतम बिंदु नहीं है, तो बिंदु से युक्त एक किनारा होता है, ताकि बिंदु से दूर जाने वाले किनारे पर वस्तुनिष्ठ फलन का मान सख्ती से बढ़ रहा हो।<ref name="Murty137">{{harvtxt|Murty|1983|loc=Section 3.8|p=137}}</ref> यदि किनारा परिमित है, तो किनारा दूसरे चरम बिंदु से जुड़ता है जहां उद्देश्य फलन का मान अधिक होता है, अन्यथा उद्देश्य फलन किनारे पर ऊपर की ओर असीमित होता है और रैखिक कार्यक्रम का कोई समाधान नहीं होता है। सिम्पलेक्स एल्गोरिथम अधिक से अधिक वस्तुनिष्ठ मूल्यों के साथ पॉलीटॉप के किनारों के साथ-साथ चरम बिंदुओं पर चलकर इस अंतर्दृष्टि को लागू करता है। यह तब तक जारी रहता है जब तक अधिकतम मूल्य तक नहीं पहुंच जाता है, या एक असीमित किनारे का दौरा नहीं किया जाता है (निष्कर्ष निकाला जाता है कि समस्या का कोई समाधान नहीं है)। एल्गोरिथम हमेशा समाप्त होता है क्योंकि पॉलीटॉप में शीर्षों की संख्या परिमित होती है; इसके अलावा चूंकि हम हमेशा एक ही दिशा (उद्देश्य फलन की दिशा) में शीर्षों के बीच कूदते हैं, हम आशा करते हैं कि देखे गए शीर्षों की संख्या कम होगी।<ref name="Murty137"/>

एक रेखीय कार्यक्रम का समाधान दो चरणों में पूरा किया जाता है। पहले चरण में, चरण I के रूप में जाना जाता है, एक शुरुआती चरम बिंदु पाया जाता है। कार्यक्रम की प्रकृति के आधार पर यह तुच्छ हो सकता है, लेकिन सामान्य तौर पर इसे मूल कार्यक्रम के एक संशोधित संस्करण में सिम्पलेक्स एल्गोरिथम को लागू करके हल किया जा सकता है। प्रथम चरण के संभावित परिणाम या तो यह हैं कि एक बुनियादी व्यवहार्य समाधान मिल गया है या यह कि व्यवहार्य क्षेत्र खाली है। बाद के मामले में रैखिक कार्यक्रम को अव्यवहार्य कहा जाता है। दूसरे चरण में, द्वितीय चरण में, सरल एल्गोरिथम चरण I में प्रारंभिक बिंदु के रूप में पाए जाने वाले मूल व्यवहार्य समाधान का उपयोग करके लागू किया जाता है। चरण II से संभावित परिणाम या तो एक इष्टतम बुनियादी व्यवहार्य समाधान है या एक अनंत किनारा है जिस पर उद्देश्य फलन ऊपर असीमित है।<ref name="DantzigThapa1">[[George B. Dantzig]] and Mukund N. Thapa. 1997. ''Linear programming 1: Introduction''. Springer-Verlag.</ref><ref name="NeringTucker"/><ref name="Vanderbei">Robert J. Vanderbei, [http://www.princeton.edu/~rvdb/LPbook/ ''Linear Programming: Foundations and Extensions''], 3rd ed., International Series in Operations Research & Management Science, Vol. 114, Springer Verlag, 2008. {{isbn|978-0-387-74387-5}}. <!-- (An on-line second edition was formerly available. Vanderbei's site still contains extensive materials.) --></ref>


== मानक रूप ==
एक रेखीय कार्यक्रम का मानक रूप में एक में रूपांतरण निम्नानुसार पूरा किया जा सकता है।<ref>{{harvtxt|Murty|1983|loc=Section 2.2}}</ref> सबसे पहले, प्रत्येक चर के लिए 0 के अलावा निचली सीमा के साथ, एक नया चर पेश किया जाता है जो चर और बाध्य के बीच के अंतर का प्रतिनिधित्व करता है। मूल चर को तब प्रतिस्थापन द्वारा समाप्त किया जा सकता है। उदाहरण के लिए, बाधा को देखते हुए
:<math>x_1 \ge 5</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> \begin{align}
  x_2 + 2x_3 &\le 3\\
 -x_4 + 3x_5 &\ge 2
\end{align}</math>
के साथ बदल दिया जाता है
:<math> \begin{align}
  x_2 + 2x_3 + s_1 &= 3\\
 -x_4 + 3x_5 - s_2 &= 2\\
  s_1,\, s_2 &\ge 0
\end{align}</math>
इस रूप में असमानताओं पर बीजगणितीय हेरफेर करना बहुत आसान है। असमानताओं में जहां ≥ दूसरे के रूप में प्रकट होता है, कुछ लेखक चर के रूप में पेश किए गए चर का उल्लेख करते हैं {{anchor|Surplus variable}}अधिशेष चर।

तीसरा, प्रत्येक अप्रतिबंधित चर को रैखिक कार्यक्रम से हटा दिया जाता है। यह दो तरीकों से किया जा सकता है, एक है चर के लिए समीकरणों में से किसी एक में हल करके और फिर प्रतिस्थापन द्वारा चर को समाप्त करना। दूसरा चर को दो प्रतिबंधित चर के अंतर से बदलना है। उदाहरण के लिए, अगर <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>\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>
  \begin{bmatrix}
    1 & -\mathbf{c}^T & 0 \\
    0 & \mathbf{A} & \mathbf{b}
  \end{bmatrix}
</math>
पहली पंक्ति उद्देश्य फलन को परिभाषित करती है और शेष पंक्तियाँ व्यवरोधों को निर्दिष्ट करती हैं। पहले कॉलम में शून्य वेक्टर बी के समान आयाम के शून्य वेक्टर का प्रतिनिधित्व करता है (विभिन्न लेखक सटीक लेआउट के रूप में विभिन्न सम्मेलनों का उपयोग करते हैं)। यदि ए के स्तंभों को पुनर्व्यवस्थित किया जा सकता है ताकि इसमें ऑर्डर पी (ए में पंक्तियों की संख्या) की पहचान मैट्रिक्स हो, तो झांकी को विहित रूप में कहा जाता है।<ref>{{harvtxt|Murty|1983|loc=section 2.3.2}}</ref> पहचान मैट्रिक्स के कॉलम से संबंधित चर को मूल चर कहा जाता है जबकि शेष चर को गैर-मूल या मुक्त चर कहा जाता है। यदि गैर-मूल चरों के मान 0 पर सेट हैं, तो मूल चर के मान आसानी से बी में प्रविष्टियों के रूप में प्राप्त किए जाते हैं और यह समाधान एक बुनियादी व्यवहार्य समाधान है। यहां बीजगणितीय व्याख्या यह है कि प्रत्येक पंक्ति द्वारा दर्शाए गए रैखिक समीकरण के गुणांक या तो हैं <math>0</math>, <math>1</math>, या कोई अन्य संख्या। प्रत्येक पंक्ति में होगा <math>1</math> मूल्य के साथ स्तंभ <math>1</math>, <math>p-1</math> गुणांक वाले कॉलम <math>0</math>, और शेष कॉलम कुछ अन्य गुणांकों के साथ (ये अन्य चर हमारे गैर-मूल चर का प्रतिनिधित्व करते हैं)। गैर-मूल चर के मान को शून्य पर सेट करके हम प्रत्येक पंक्ति में यह सुनिश्चित करते हैं कि चर का मान a द्वारा दर्शाया गया है <math>1</math> इसके कॉलम में के बराबर है <math>b</math> उस पंक्ति पर मूल्य।

इसके विपरीत, एक बुनियादी व्यवहार्य समाधान दिया गया है, गैर-शून्य चर के अनुरूप स्तंभों को एक गैर-एकवचन मैट्रिक्स में विस्तारित किया जा सकता है। यदि संबंधित झांकी को इस मैट्रिक्स के व्युत्क्रम से गुणा किया जाता है तो परिणाम कैनोनिकल रूप में एक झांकी है।<ref>{{harvtxt|Murty|1983|loc=section 3.12}}</ref>
होने देना
:<math>
  \begin{bmatrix}
    1 & -\mathbf{c}^T_B & -\mathbf{c}^T_D & 0 \\
    0 & I & \mathbf{D} & \mathbf{b}
  \end{bmatrix}
</math>
विहित रूप में एक झाँकी हो। अतिरिक्त प्राथमिक मैट्रिक्स # पंक्ति-जोड़ परिवर्तन | गुणांक को हटाने के लिए पंक्ति-जोड़ परिवर्तन लागू किए जा सकते हैं {{SubSup|'''c'''|''B''|T|s=0}} उद्देश्य समारोह से। इस प्रक्रिया को प्राइसिंग आउट कहा जाता है और इसका परिणाम एक प्रामाणिक झांकी में होता है
:<math>
  \begin{bmatrix}
    1 & 0 & -\bar{\mathbf{c}}^T_D & z_B \\
    0 & I & \mathbf{D} & \mathbf{b}
  \end{bmatrix}
</math>
जहां जेड<sub>''B''</sub> संबंधित मूल व्यवहार्य समाधान पर उद्देश्य फ़ंक्शन का मान है। अद्यतन गुणांक, जिसे सापेक्ष लागत गुणांक के रूप में भी जाना जाता है, गैर-मूल चर के संबंध में उद्देश्य फ़ंक्शन के परिवर्तन की दर है।<ref name="NeringTucker" >
Evar D. Nering and [[Albert W. Tucker]], 1993, ''Linear Programs and Related Problems'', Academic Press. (elementary<!-- but profound -->)</ref>


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

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

=== उदाहरण ===
{{see also|Revised simplex algorithm#Numerical example}}
रैखिक कार्यक्रम पर विचार करें
:छोटा करना
::<math>Z = -2 x - 3 y - 4 z\,</math>
:का विषय है
::<math>\begin{align}
  3 x + 2 y + z &\le 10\\
  2 x + 5 y + 3 z &\le 15\\
  x,\,y,\,z &\ge 0
\end{align}</math>
सुस्त चर s और t के योग के साथ, यह विहित झांकी द्वारा दर्शाया गया है
:<math>
  \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}
</math>
जहां कॉलम 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 धुरी पंक्ति होनी चाहिए। धुरी का प्रदर्शन उत्पादन करता है
:<math>
  \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}
</math>
अब कॉलम 4 और 5 मूल चर z और s का प्रतिनिधित्व करते हैं और संबंधित बुनियादी व्यवहार्य समाधान है
:<math>x=y=t=0,\,z=5,\,s=5.</math>
अगले चरण के लिए, वस्तुनिष्ठ पंक्ति में कोई सकारात्मक प्रविष्टि नहीं है और वास्तव में
:<math>Z = \frac{-60+2x+11y+4t}{3} = -20 + \frac{2x+11y+4t}{3}</math>
इसलिए Z का न्यूनतम मान −20 है।

== एक प्रारंभिक विहित झांकी ढूँढना ==
सामान्य तौर पर, एक रेखीय कार्यक्रम विहित रूप में नहीं दिया जाएगा और सिम्पलेक्स एल्गोरिथम शुरू होने से पहले एक समकक्ष विहित झांकी मिलनी चाहिए। यह कृत्रिम चरों की शुरूआत के द्वारा पूरा किया जा सकता है। पहचान मैट्रिक्स के कॉलम इन चरों के लिए कॉलम वैक्टर के रूप में जोड़े जाते हैं। यदि एक बाधा समीकरण के लिए b मान ऋणात्मक है, तो पहचान मैट्रिक्स कॉलम जोड़ने से पहले समीकरण को नकार दिया जाता है। यह व्यवहार्य समाधान या इष्टतम समाधान के सेट को नहीं बदलता है, और यह सुनिश्चित करता है कि ढीले चर प्रारंभिक व्यवहार्य समाधान का गठन करेंगे। नई झांकी विहित रूप में है लेकिन यह मूल समस्या के समतुल्य नहीं है। तो कृत्रिम चर के योग के बराबर एक नया उद्देश्य फ़ंक्शन पेश किया जाता है और न्यूनतम खोजने के लिए सिंप्लेक्स एल्गोरिदम लागू किया जाता है; संशोधित रैखिक कार्यक्रम को चरण I समस्या कहा जाता है।<ref>{{harvtxt|Murty|1983|p=60}}</ref>
चरण I समस्या के लिए लागू सिंप्लेक्स एल्गोरिदम को नए उद्देश्य फ़ंक्शन के लिए न्यूनतम मान के साथ समाप्त होना चाहिए, क्योंकि गैर-ऋणात्मक चर का योग होने के कारण, इसका मान 0 से नीचे है। यदि न्यूनतम 0 है तो कृत्रिम चर को समाप्त किया जा सकता है परिणामी विहित झांकी मूल समस्या के समकक्ष एक विहित झांकी का निर्माण करती है। सिंप्लेक्स एल्गोरिथम तब समाधान खोजने के लिए लागू किया जा सकता है; इस चरण को चरण II कहा जाता है। यदि न्यूनतम सकारात्मक है तो चरण I समस्या का कोई व्यवहार्य समाधान नहीं है जहां कृत्रिम चर सभी शून्य हैं। इसका तात्पर्य यह है कि मूल समस्या के लिए व्यवहार्य क्षेत्र खाली है, और इसलिए मूल समस्या का कोई समाधान नहीं है।<ref name="DantzigThapa1"/><ref name="NeringTucker"/><ref name="Padberg"/>



=== उदाहरण ===
रैखिक कार्यक्रम पर विचार करें
:छोटा करना
::<math>Z = -2 x - 3 y - 4 z\,</math>
:का विषय है
::<math>\begin{align}
 3 x + 2 y + z &= 10\\
 2 x + 5 y + 3 z &= 15\\
 x,\, y,\, z &\ge 0
\end{align}</math>
यह (गैर-विहित) झांकी द्वारा दर्शाया गया है
:<math>
  \begin{bmatrix}
    1 & 2 & 3 & 4 &  0 \\   
    0 & 3 & 2 & 1 & 10 \\
    0 & 2 & 5 & 3 & 15
  \end{bmatrix}
</math>
एक नई झांकी देते हुए कृत्रिम चर u और v और वस्तुनिष्ठ फलन W = u + v का परिचय दें
:<math>
  \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}
</math>
मूल उद्देश्य फलन को परिभाषित करने वाले समीकरण को द्वितीय चरण की प्रत्याशा में बनाए रखा जाता है।

निर्माण के द्वारा, यू और वी दोनों मूल चर हैं क्योंकि वे प्रारंभिक पहचान मैट्रिक्स का हिस्सा हैं। हालाँकि, उद्देश्य फ़ंक्शन W वर्तमान में मानता है कि u और v दोनों 0 हैं। सही मान होने के लिए उद्देश्य फ़ंक्शन को समायोजित करने के लिए जहां u = 10 और v = 15, तीसरी और चौथी पंक्तियों को पहली पंक्ति में जोड़ें
:<math>
  \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}
</math>
स्तंभ 5 को पिवट कॉलम के रूप में चुनें, इसलिए पिवट पंक्ति पंक्ति 4 होनी चाहिए, और अपडेट की गई झांकी है
:<math>
  \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}
</math>
अब कॉलम 3 को पिवट कॉलम के रूप में चुनें, जिसके लिए पंक्ति 3 को पिवट पंक्ति होना चाहिए
:<math>
  \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}
</math>
कृत्रिम चर अब 0 हैं और उन्हें मूल समस्या के समतुल्य एक विहित झांकी देते हुए गिराया जा सकता है:
:<math>
  \begin{bmatrix}
    7 & 0 & -25 & 0 &  -130 \\   
    0 & 7 &   1 & 0 &    15 \\
    0 & 0 &  11 & 7 &    25 
  \end{bmatrix}
</math>
यह, सौभाग्य से, पहले से ही इष्टतम है और मूल रैखिक कार्यक्रम के लिए इष्टतम मूल्य −130/7 है।

==उन्नत विषय==

===कार्यान्वयन ===
{{main|Revised simplex algorithm}}
एल्गोरिथम का वर्णन करने के लिए ऊपर इस्तेमाल किया गया झांकी फॉर्म खुद को एक तत्काल कार्यान्वयन के लिए उधार देता है जिसमें झांकी को एक आयताकार (m + 1)-by-(m + n + 1) सरणी के रूप में बनाए रखा जाता है। पहचान मैट्रिक्स के m स्पष्ट स्तंभों को संग्रहीत करने से बचना सीधा है जो 'बी' के आधार पर ['ए', 'आई'] के स्तंभों का सबसेट होने के कारण झांकी के भीतर होगा। इस कार्यान्वयन को मानक सिम्पलेक्स एल्गोरिथम कहा जाता है। भंडारण और संगणना ओवरहेड ऐसा है कि बड़ी रैखिक प्रोग्रामिंग समस्याओं को हल करने के लिए मानक सिंप्लेक्स विधि निषेधात्मक रूप से महंगा तरीका है।

प्रत्येक सिम्प्लेक्स पुनरावृत्ति में, केवल आवश्यक डेटा झांकी की पहली पंक्ति, झांकी का (निर्णायक) स्तंभ है जो प्रवेश करने वाले चर और दाहिने हाथ की ओर से संबंधित है। उत्तरार्द्ध को मुख्य स्तंभ का उपयोग करके अद्यतन किया जा सकता है और झांकी की पहली पंक्ति को छोड़ने वाले चर के अनुरूप (निर्णायक) पंक्ति का उपयोग करके अद्यतन किया जा सकता है। मैट्रिक्स 'बी' और मैट्रिक्स-वेक्टर उत्पाद 'ए' का उपयोग करने वाले समीकरणों के रैखिक प्रणालियों के समाधान का उपयोग करके सीधे धुरी स्तंभ और धुरी पंक्ति दोनों की गणना की जा सकती है। ये अवलोकन संशोधित सिम्पलेक्स एल्गोरिथम को प्रेरित करते हैं, जिसके लिए कार्यान्वयनों को 'बी' के उनके उलटे प्रतिनिधित्व द्वारा अलग किया जाता है।<ref name="DantzigThapa2" >
[[George B. Dantzig]] and Mukund N. Thapa. 2003. ''Linear Programming 2: Theory and Extensions''. Springer-Verlag.</ref>
बड़ी रैखिक-प्रोग्रामिंग समस्याओं में A आमतौर पर एक विरल मैट्रिक्स होता है और, जब इसके उलटा प्रतिनिधित्व को बनाए रखते हुए B की परिणामी विरलता का शोषण किया जाता है, तो संशोधित सिंप्लेक्स एल्गोरिथ्म मानक सिंप्लेक्स विधि की तुलना में बहुत अधिक कुशल होता है। वाणिज्यिक सिंप्लेक्स सॉल्वर संशोधित सिम्प्लेक्स एल्गोरिथम पर आधारित हैं।<ref name="Padberg" >M. Padberg, ''Linear Optimization and Extensions'', Second Edition, Springer-Verlag, 1999.</ref><ref name="DantzigThapa2"/><ref>Dmitris Alevras and Manfred W. Padberg, ''Linear Optimization and Extensions: Problems and Extensions'', Universitext, Springer-Verlag, 2001. (Problems from Padberg with solutions.)</ref><ref name="MarosMitra" >{{cite book|last1=Maros|first1=István|last2=Mitra|first2=Gautam|chapter=Simplex algorithms|mr=1438309|title=रैखिक और पूर्णांक प्रोग्रामिंग में प्रगति|pages=1–46|editor=J. E. Beasley|publisher=Oxford Science|year=1996}}</ref><ref>{{cite book|mr=1960274|last=Maros|first=István|title=सिंप्लेक्स विधि की कम्प्यूटेशनल तकनीक|series=International Series in Operations Research & Management Science|volume=61|publisher=Kluwer Academic Publishers|location=Boston, MA|year=2003|pages=xx+325|isbn=978-1-4020-7332-8}}</ref>


=== अध: पतन: रुकना और साइकिल चलाना ===
यदि सभी बुनियादी चरों के मान सख्ती से सकारात्मक हैं, तो एक धुरी के परिणामस्वरूप उद्देश्य मूल्य में सुधार होना चाहिए। जब ऐसा हमेशा होता है तो बुनियादी चरों का कोई भी सेट दो बार नहीं होता है और सिम्प्लेक्स एल्गोरिथम को चरणों की एक सीमित संख्या के बाद समाप्त होना चाहिए। बुनियादी व्यवहार्य समाधान जहां कम से कम एक बुनियादी चर शून्य है, उन्हें पतित कहा जाता है और इसके परिणामस्वरूप ऐसे पिवट हो सकते हैं जिनके लिए उद्देश्य मूल्य में कोई सुधार नहीं होता है। इस मामले में समाधान में कोई वास्तविक परिवर्तन नहीं है बल्कि मूल चर के सेट में केवल एक परिवर्तन है। जब एक के बाद एक कई ऐसे पिवट होते हैं, तो कोई सुधार नहीं होता है; बड़े औद्योगिक अनुप्रयोगों में, अध: पतन आम है और इस तरह का ठहराव उल्लेखनीय है।
स्टालिंग से भी बदतर यह संभावना है कि मूल चर का एक ही सेट दो बार होता है, इस मामले में, सिम्प्लेक्स एल्गोरिथ्म के नियतात्मक धुरी नियम एक अनंत लूप, या चक्र का उत्पादन करेंगे। जबकि व्यवहार में पतन नियम है और रुकना आम है, व्यवहार में साइकिल चलाना दुर्लभ है। मैनफ्रेड डब्ल्यू पैडबर्ग में व्यावहारिक साइकिल चालन के एक उदाहरण की चर्चा होती है।<ref name="Padberg"/>ब्लैंड का नियम साइकिल चलाने से रोकता है और इस प्रकार यह गारंटी देता है कि सिम्पलेक्स एल्गोरिथम हमेशा समाप्त होता है।<ref name="Padberg"/><ref name="Bland">
{{cite journal|title=New finite pivoting rules for the simplex method|first=Robert G.|last=Bland|journal=Mathematics of Operations Research|volume=2|issue=2|date=May 1977|pages=103–107|doi=10.1287/moor.2.2.103|jstor=3689647|mr=459599|s2cid=18493293|url=https://semanticscholar.org/paper/874b988e359f63c8068226c53ef0a9bcd54e5e4d}}</ref><ref>{{harvtxt|Murty|1983|p=79}}</ref> एक और धुरी एल्गोरिथ्म, क्रिस-क्रॉस एल्गोरिथ्म कभी भी रैखिक कार्यक्रमों पर चक्र नहीं करता है।<ref>There are abstract optimization problems, called [[oriented matroid]] programs, on which Bland's rule cycles (incorrectly) while the [[criss-cross algorithm]] terminates correctly.</ref>
इतिहास-आधारित धुरी नियम जैसे कि ज़ादेह का नियम और कनिंघम का नियम भी रुकने और साइकिल चलाने के मुद्दे को रोकने की कोशिश करते हैं कि कितनी बार विशेष चर का उपयोग किया जा रहा है और फिर ऐसे चर का पक्ष लें जो कम से कम अक्सर उपयोग किए गए हैं।

=== सबसे खराब स्थिति में दक्षता ===
सिम्प्लेक्स विधि अभ्यास में उल्लेखनीय रूप से कुशल है और फूरियर-मोट्ज़किन उन्मूलन जैसे पहले के तरीकों पर एक बड़ा सुधार था। हालाँकि, 1972 में, विक्टर क्ले और मिन्टी<ref name="KleeMinty">{{cite book|title=असमानताओं III (कैलिफोर्निया विश्वविद्यालय, लॉस एंजिल्स, कैलिफ़ोर्निया में आयोजित असमानताओं पर तीसरे संगोष्ठी की कार्यवाही, 1-9 सितंबर, 1969, थियोडोर एस। मोट्ज़किन की स्मृति को समर्पित)|editor-first=Oved|editor-last=Shisha|publisher=Academic Press|location=New York-London|year=1972|mr=332165|last1=Klee|first1=Victor|author-link1=Victor Klee|last2=Minty|first2= George J.|author-link2=George J. Minty|chapter=How good is the simplex algorithm?|pages=159–175}}</ref> एक उदाहरण दिया, क्ले-मिन्टी क्यूब, यह दिखाते हुए कि डेंटज़िग द्वारा तैयार की गई सिंप्लेक्स विधि की सबसे खराब स्थिति घातीय समय है। तब से, पद्धति पर लगभग हर भिन्नता के लिए, यह दिखाया गया है कि रैखिक कार्यक्रमों का एक परिवार है जिसके लिए यह खराब प्रदर्शन करता है। बहुपद समय के साथ भिन्नता होने पर यह एक खुला प्रश्न है, हालांकि उप-घातीय धुरी नियम ज्ञात हैं।<ref>{{Citation
 | last1 = Hansen
 | first1 = Thomas
 | last2 = Zwick
 | first2 = Uri
 | author2-link = Uri Zwick
 | title = An Improved Version of the Random-Facet Pivoting Rule for the Simplex Algorithm
 | journal = Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing
 | pages = 209–218
 | year = 2015
 | doi = 10.1145/2746539.2746557
 | citeseerx = 10.1.1.697.2526
 | isbn = 9781450335362
 | s2cid = 1980659
 }}
</ref>
2014 में, यह साबित हो गया था कि सिंप्लेक्स विधि का एक विशेष प्रकार एनपी-शक्तिशाली है, अर्थात, इसका उपयोग बहुपद ओवरहेड के साथ हल करने के लिए किया जा सकता है, एल्गोरिथम के निष्पादन के दौरान एनपी में किसी भी समस्या का निहित रूप से उपयोग किया जा सकता है। इसके अलावा, यह तय करना कि किसी दिए गए इनपुट पर एल्गोरिथ्म के निष्पादन के दौरान एक दिया गया चर कभी भी आधार में प्रवेश करता है, और किसी समस्या को हल करने के लिए आवश्यक पुनरावृत्तियों की संख्या निर्धारित करना, दोनों एनपी-कठोरता | एनपी-हार्ड समस्याएं हैं।<ref>{{Cite journal|last1=Disser|first1=Yann|last2=Skutella|first2=Martin|date=2018-11-01|title=सिम्प्लेक्स एल्गोरिथम एनपी-माइटी है|journal=ACM Trans. Algorithms|volume=15|issue=1|pages=5:1–5:19|doi=10.1145/3280847|issn=1549-6325|arxiv=1311.5935|s2cid=54445546}}</ref> लगभग उसी समय यह दिखाया गया था कि एक कृत्रिम धुरी नियम मौजूद है जिसके लिए इसके आउटपुट की गणना PSPACE- पूर्ण है।<ref>{{Citation | last1 = Adler | first1 = Ilan | last2 = Christos | first2 = Papadimitriou | author2-link = Christos Papadimitriou | last3 = Rubinstein | first3 = Aviad | title = On Simplex Pivoting Rules and Complexity Theory | journal = International Conference on Integer Programming and Combinatorial Optimization | volume = 17 | pages = 13–24 | year = 2014 | arxiv = 1404.3320 | doi = 10.1007/978-3-319-07557-0_2| series = Lecture Notes in Computer Science | isbn = 978-3-319-07556-3 | s2cid = 891022 }}</ref> 2015 में, यह दिखाने के लिए इसे मजबूत किया गया था कि Dantzig के धुरी नियम के आउटपुट की गणना करना PSPACE-पूर्ण है।<ref>{{Citation | last1 = Fearnly | first1 = John | last2 = Savani | first2 = Rahul | title = The Complexity of the Simplex Method | journal = Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing | pages = 201–208 | year = 2015 | arxiv = 1404.0605 | doi = 10.1145/2746539.2746558| isbn = 9781450335362 | s2cid = 2116116 }}</ref>


=== व्यवहार में दक्षता ===
अवलोकन का विश्लेषण और परिमाणीकरण कि सिम्प्लेक्स एल्गोरिथ्म व्यवहार में कुशल है, इसके बावजूद इसकी सबसे खराब स्थिति जटिलता के अन्य उपायों के विकास के लिए प्रेरित हुई है। सिंप्लेक्स एल्गोरिथ्म में बहुपद-समय सबसे अच्छा, सबसे खराब और औसत मामला है | विभिन्न संभाव्यता वितरणों के तहत औसत-केस जटिलता, यादृच्छिक मैट्रिक्स के लिए संभाव्यता वितरण की पसंद के आधार पर सिम्प्लेक्स एल्गोरिदम के सटीक औसत-केस प्रदर्शन के साथ।<ref name="Schrijver">[[Alexander Schrijver]], ''Theory of Linear and Integer Programming''. John Wiley & sons, 1998, {{isbn|0-471-98232-6}} (mathematical)</ref><ref name="Borgwardt">The simplex algorithm takes on average ''D'' steps for a cube. {{harvtxt|Borgwardt|1987}}: {{cite book|last=Borgwardt|first=Karl-Heinz|title=The simplex method: A probabilistic analysis|series=Algorithms and Combinatorics (Study and Research Texts)|volume=1|publisher=Springer-Verlag|location=Berlin|year=1987|pages=xii+268|isbn=978-3-540-17096-9|mr=868467}}</ref> झरझरा सेट का अध्ययन करने के लिए एक अन्य दृष्टिकोण सामान्य टोपोलॉजी से बेयर श्रेणी सिद्धांत का उपयोग करता है, और यह दिखाने के लिए कि (टोपोलॉजिकल रूप से) अधिकांश मैट्रिसेस को बहुपद संख्या में चरणों में सिम्प्लेक्स एल्गोरिथ्म द्वारा हल किया जा सकता है।{{Citation needed|date=June 2019}}
सिम्प्लेक्स एल्गोरिथम के प्रदर्शन का विश्लेषण करने का एक अन्य तरीका छोटे गड़बड़ी के तहत सबसे खराब स्थिति के व्यवहार का अध्ययन करता है - क्या सबसे खराब स्थिति एक छोटे से बदलाव (संरचनात्मक स्थिरता के अर्थ में) के तहत स्थिर है, या क्या वे ट्रैक्टेबल हो जाते हैं? शोध के इस क्षेत्र, जिसे सुगम विश्लेषण कहा जाता है, को विशेष रूप से सरल विधि का अध्ययन करने के लिए पेश किया गया था। दरअसल, शोर के साथ इनपुट पर सिम्प्लेक्स विधि का चलने का समय चर की संख्या और गड़बड़ी के परिमाण में बहुपद है।<ref>{{Cite book | last1=Spielman | first1=Daniel | last2=Teng | first2=Shang-Hua | author2-link=Shanghua Teng | title=कम्प्यूटिंग के सिद्धांत पर तीस-तीसरे वार्षिक एसीएम संगोष्ठी की कार्यवाही| publisher=ACM | isbn=978-1-58113-349-3 | doi=10.1145/380752.380813 | year=2001 | chapter=Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time| pages=296–305 | arxiv=cs/0111050| s2cid=1471 }}</ref><ref>{{Cite journal|last1=Dadush|first1=Daniel|last2=Huiberts|first2=Sophie|date=2020-01-01|title=सिंप्लेक्स विधि का एक अनुकूल चिकना विश्लेषण|url=https://epubs.siam.org/doi/abs/10.1137/18M1197205|journal=SIAM Journal on Computing|volume=49|issue=5|pages=STOC18–449|doi=10.1137/18M1197205|s2cid=226351624|issn=0097-5397}}</ref>


== अन्य एल्गोरिदम ==
रैखिक-प्रोग्रामिंग समस्याओं को हल करने के लिए अन्य एल्गोरिदम का वर्णन रैखिक प्रोग्रामिंग | रैखिक-प्रोग्रामिंग लेख में किया गया है। एक अन्य आधार-विनिमय धुरी एल्गोरिथम क्रिस-क्रॉस एल्गोरिथम है।<ref>{{cite journal|last1=Terlaky|first1=Tamás|last2=Zhang|first2=Shu Zhong|title=लीनियर प्रोग्रामिंग के लिए धुरी नियम: हाल के सैद्धांतिक विकास पर एक सर्वेक्षण|issue=1|journal=Annals of Operations Research|volume=46–47|year=1993|pages=203–233|doi=10.1007/BF02096264|mr=1260019|citeseerx = 10.1.1.36.7658 |s2cid=6058077|issn=0254-5330}}</ref><ref>{{cite news|first1=Komei|last1=Fukuda|author1-link=Komei Fukuda|first2=Tamás|last2=Terlaky|author2-link=Tamás Terlaky|title=क्रिस-क्रॉस विधियाँ: धुरी एल्गोरिदम पर एक नया दृश्य|journal=Mathematical Programming, Series B|volume=79|number=1–3|pages=369–395|editor1=Thomas M. Liebling |editor2=Dominique de Werra|publisher=North-Holland Publishing |location=Amsterdam|year=1997|doi=10.1007/BF02614325|mr=1464775}}</ref> रेखीय प्रोग्रामिंग के लिए बहुपद-समय के एल्गोरिदम हैं जो आंतरिक बिंदु विधियों का उपयोग करते हैं: इनमें खाचियन के दीर्घवृत्तीय एल्गोरिथ्म, कर्मकार के कर्मकार के एल्गोरिथ्म और आंतरिक बिंदु विधि | पथ-निम्नलिखित एल्गोरिदम शामिल हैं।<ref name="Vanderbei"/>


== रैखिक-भिन्नात्मक प्रोग्रामिंग ==
{{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><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|
pages=198–214|year=1999|issn=0377-2217|doi=10.1016/S0377-2217(98)00049-6|first1=Tibor|last1=Illés|first2=Ákos|last2=Szirmai|first3=Tamás|last3=Terlaky|url=http://www.cas.mcmaster.ca/~terlaky/files/dut-twi-96-103.ps.gz |citeseerx=10.1.1.36.7090}}</ref>


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


==टिप्पणियाँ==
{{reflist|2}}


==संदर्भ==
* {{cite book|last=Murty|first=Katta G.|author-link=Katta G. Murty|title=Linear programming|publisher=John Wiley & Sons, Inc.|location=New York|year=1983|pages=xix+482|isbn=978-0-471-09725-9|mr=720547}}


== अग्रिम पठन ==
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.&nbsp;790&ndash;804.
* Frederick S. Hillier and Gerald J. Lieberman: ''Introduction to Operations Research'', 8th edition. McGraw-Hill. {{isbn|0-07-123828-X}}
* {{cite book|title=Optimization in operations research|first=Ronald L.|last=Rardin|year=1997|publisher=Prentice Hall|pages=919|isbn=978-0-02-398415-0}}



==इस पृष्ठ में अनुपलब्ध आंतरिक कड़ियों की सूची==

==बाहरी संबंध==
{{wikibooks|Operations Research|The Simplex Method}}
*[http://www.isye.gatech.edu/~spyros/LP/LP.html 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) [http://glossary.computing.society.informs.org/notes/Klee-Minty.pdf PDF download]
*[http://www.lokminglui.com/lpch3.pdf Simplex Method] A tutorial for Simplex Method with examples (also two-phase and M-method).
* [https://www.mathstools.com/section/main/simplex_online_calculator Mathstools] Simplex Calculator from www.mathstools.com
*[http://math.uww.edu/~mcfarlat/s-prob.htm Example of Simplex Procedure for a Standard Linear Programming Problem] by Thomas McFarland of the University of Wisconsin-Whitewater.
*[http://www.phpsimplex.com/simplex/simplex.htm?l=en PHPSimplex: online tool to solve Linear Programming Problems] by Daniel Izquierdo and Juan José Ruiz of the University of Málaga (UMA, Spain)
* [http://www.simplex-m.com simplex-m] Online Simplex Solver

{{Optimization algorithms|convex}}
{{Mathematical programming}}
{{Authority control}}

{{DEFAULTSORT:Simplex Algorithm}}[[Category: अनुकूलन एल्गोरिदम और विधियां]]
[[Category: कंप्यूटिंग में 1947]]
[[Category: एक्सचेंज एल्गोरिदम]]
[[Category:रैखिक प्रोग्रामिंग]]
[[Category:1947 में कंप्यूटर से संबंधित परिचय]]


[[Category: Machine Translated Page]]
[[Category:Created On 14/11/2022]]