सिंप्लेक्स एल्गोरिथ्म और चरम बिंदु
इस प्रश्न के लिए मेरा लघु-हाथ एलपी = रैखिक कार्यक्रम, बीएफएस = मूल व्यवहार्य समाधान, एसईएफ = मानक समानता रूप है।
चूंकि सिम्प्लेक्स एल्गोरिथ्म चरम बिंदु से चरम बिंदु तक पहुंचता है (इस तथ्य के अनुसार कि सिम्प्लेक्स बीएफएस से बीएफएस के लिए पुनरावृत्ति करता है जब एलपी एसईएफ में होता है), सिम्पलेक्स एल्गोरिथम ज्यामितीय रूप से कैसे काम करता है जब संभव क्षेत्र एक पॉलीहेड्रॉन है जिसे महसूस नहीं किया जा सकता है। SEF (जैसे एक आधा क्षेत्र)? मान लीजिए कि हमारे पास एक एलपी है, जिसके लिए संभव क्षेत्र में कोई चरम बिंदु नहीं है। फिर हम एक 'समतुल्य' एलपी लिख सकते हैं जो एसईएफ में है और इसके स्थान पर सिम्पलेक्स एल्गोरिथ्म चलाएं। लेकिन इस नए पॉलीहेड्रॉन के लिए चरम बिंदु हैं, जबकि धारणा के द्वारा मूल के लिए कोई भी नहीं हैं। मैंने मूल रूप से सोचा था कि एक एलपी के चरम बिंदु दूसरे के चरम बिंदुओं के अनुरूप हैं, लेकिन यह स्पष्ट रूप से ऐसा नहीं है।
तो जब मूल रूप से चरम बिंदुओं के लिए जैविक रूप से एलपी के एसईएफ संस्करण के चरम बिंदु होते हैं? और आगे, जब ऐसी कोई आपत्ति नहीं होती है, तो हमें मूल एलपी के संदर्भ में ज्यामितीय रूप से व्याख्या करने के लिए कैसे समझा जाता है कि सिम्प्लेक्स एल्गोरिथ्म क्या कर रहा है?
जवाब
सिम्प्लेक्स एल्गोरिथ्म चरम बिंदु से चरम बिंदु तक पुनरावृत्त होता है
तकनीकी रूप से, नहीं। सिंप्लेक्स एल्गोरिथ्म से iterates आधार के लिए आधार । यह सिर्फ ऐसा होता है कि संभव बुनियादी समाधान चरम बिंदुओं के अनुरूप हैं। (उदाहरण के लिए, दोहरी सिंप्लेक्स दोहरे-व्यवहार्य बुनियादी समाधानों के माध्यम से पुनरावृत्ति करता है, जो कि प्राण-व्यवहार्य क्षेत्र के चरम बिंदु नहीं हैं)।
मानक रूप में एक एलपी पर विचार करें, जो लिखता है \begin{align} \min \ \ \ & c^{T}x\\ \text{s.t.} \ \ \ & Ax = b\\ &x \geq 0 \end{align}एलपी का संभाव्य क्षेत्र हमेशा पॉलीहेड्रल है। यदि इसके कोई चरम बिंदु नहीं हैं, तो यह या तो खाली है (और कोई बुनियादी संभव समाधान नहीं हैं), या एक उप-उप-स्थान$\mathbb{R}^{n}$। अब, बाद वाला मामला नहीं हो सकता है, क्योंकि कोई भी उप-स्थान नहीं हो सकता है$\mathbb{R}_{+}^{n}$।
अब, आपके मूल प्रश्न पर वापस आना (जो मुझे लगता है) आपका मूल प्रश्न है: इसके लिए एक मूल पॉलीहेड्रॉन और एक एसईएफ प्रतिनिधित्व दिया गया है, क्या उस प्रतिनिधित्व के चरम बिंदु हैं, और क्या वे मूल पॉलीडरन के चरम बिंदुओं के अनुरूप हैं? इसका उत्तर है: हां, एसईएफ में चरम बिंदु होंगे, और नहीं, वे हमेशा आपके मूल पॉलीहेड्रॉन के चरम बिंदुओं के अनुरूप नहीं हो सकते हैं।
यहाँ एक सरल उदाहरण है: ले लो $\mathcal{P} = \{x \in \mathbb{R}\}$, जो 1-आयामी पॉलीहेड्रॉन है। इसके निर्माण में एक मुक्त चर है और कोई बाधा नहीं है।
एसईएफ प्रतिनिधित्व बनाने के लिए, प्रतिस्थापित करें $x$ द्वारा द्वारा $x^{+} - x^{-}$ साथ से $x^{\pm} \geq 0$। अभी,$(0, 0)$ उस SEF का एक चरम बिंदु है, जो उससे मेल खाता है $x=0$, जो एक चरम बिंदु नहीं है $\mathcal{P}$।
सुनिश्चित नहीं है कि मैं आपके प्रश्न को पूरी तरह से समझता हूं, लेकिन मुझे लगता है कि आपका भ्रम इस धारणा से उपजा है कि एक मूल समाधान एक "चरम बिंदु" है। एक बुनियादी (जरूरी नहीं कि प्राइमल या ड्युअल फिजिबल) सॉल्यूशन सिर्फ पंक्तियों की संख्या की कमी का अंतर है (जिनमें से कुछ सीमाएं हो सकती हैं)। यह संभव है कि किसी समस्या का एक व्यावहारिक या दोहरा संभव समाधान न हो, जिसके परिणामस्वरूप या तो वह अनम्य या अप्रभावित है। पाठ्यपुस्तक सिम्प्लेक्स एल्गोरिदम कभी-कभी इस तथ्य को छोड़ देते हैं कि बीएफएस स्थापित करने के लिए चरण 1 दृष्टिकोण के कुछ रूप को वास्तव में एल्गोरिदम को शुरू करने की आवश्यकता होती है। यह संभव है कि एक प्राइमल फेज 1 समस्या को पारमार्थिक पाता है और यह भी संभव है कि एक ड्यूल फेज 1 समस्या को अनबाउंड पाए।
अद्यतन: mtanneau द्वारा जवाब शायद सभी कह रहा है कि एक ही बाधा के लिए एक ही चर के साथ एक ही लागू होता है। मैं बस यह जोड़ना चाहता हूं कि सिम्पलेक्स कार्यान्वयन सीधे मुक्त चर के साथ काम करते हैं और उन्हें 0. से बंधे हुए दो चर में परिवर्तित नहीं करते हैं, लेकिन एक ही धारण, एल्गोरिथ्म मूल समाधानों पर निर्भर करता है और सम्मेलन बनाया जाता है कि गैर-बुनियादी मुक्त चर मूल्य लेते हैं 0. यह भी ध्यान दें कि बंधे हुए पॉलीहेड्रा के लिए, मूल समाधान चरम बिंदुओं के अनुरूप हैं।