बेसिक फीज़बल सलूशन

रैखिक प्रोग्रामिंग के सिद्धांत में, एक बुनियादी व्यवहार्य समाधान (बीएफएस) गैर-शून्य चर के न्यूनतम सेट वाला एक समाधान है। ज्यामितीय रूप से, प्रत्येक बीएफएस व्यवहार्य समाधानों के बहुतल के एक कोने से मेल खाता है। यदि कोई इष्टतम समाधान मौजूद है, तो एक इष्टतम बीएफएस भी मौजूद है। इसलिए, एक इष्टतम समाधान खोजने के लिए, बीएफएस-एस पर विचार करना पर्याप्त है। इस तथ्य का उपयोग सिम्प्लेक्स एल्गोरिथ्म द्वारा किया जाता है, जो अनिवार्य रूप से एक इष्टतम समाधान मिलने तक एक बीएफएस से दूसरे तक यात्रा करता है।

परिभाषाएँ

प्रारंभिक: रैखिक-स्वतंत्र पंक्तियों के साथ समीकरणात्मक रूप

नीचे दी गई परिभाषाओं के लिए, हम पहले रैखिक कार्यक्रम को तथाकथित समीकरणात्मक रूप में प्रस्तुत करते हैं:

अधिकतम करें ${\textstyle \mathbf {c^{T}} \mathbf {x} }$

का विषय है $A\mathbf {x} =\mathbf {b}$ और $\mathbf {x} \geq 0$

कहाँ:

• $\mathbf {c^{T}}$ और $\mathbf {x}$ आकार n (चरों की संख्या) के सदिश हैं;
• $\mathbf {b}$ आकार m (बाधाओं की संख्या) का एक वेक्टर है;
• $A$ एक एम-बाय-एन मैट्रिक्स है;
• $\mathbf {x} \geq 0$ इसका मतलब है कि सभी चर गैर-नकारात्मक हैं।

किसी भी रैखिक प्रोग्राम को सुस्त चर ्स जोड़कर समीकरणीय रूप में परिवर्तित किया जा सकता है।

प्रारंभिक सफ़ाई कदम के रूप में, हम सत्यापित करते हैं कि:

• प्रणाली $A\mathbf {x} =\mathbf {b}$ कम से कम एक समाधान है (अन्यथा पूरे एलपी के पास कोई समाधान नहीं है और करने के लिए और कुछ नहीं है);
• मैट्रिक्स की सभी एम पंक्तियाँ $A$ रैखिक रूप से स्वतंत्र हैं, यानी, इसकी रैंक एम है (अन्यथा हम एलपी को बदले बिना अनावश्यक पंक्तियों को हटा सकते हैं)।

संभव समाधान

एलपी का एक व्यवहार्य समाधान कोई भी वेक्टर है $\mathbf {x} \geq 0$ ऐसा है कि $A\mathbf {x} =\mathbf {b}$. हम मानते हैं कि कम से कम एक व्यवहार्य समाधान है। यदि m = n, तो केवल एक ही व्यवहार्य समाधान है। आमतौर पर m < n, इसलिए सिस्टम $A\mathbf {x} =\mathbf {b}$ कई समाधान हैं; ऐसे प्रत्येक समाधान को एलपी का व्यवहार्य समाधान कहा जाता है।

आधार

एलपी का आधार ए का एक उलटा मैट्रिक्स सबमैट्रिक्स है जिसमें सभी एम पंक्तियां और केवल एम<एन कॉलम हैं।

कभी-कभी, आधार शब्द का प्रयोग सबमैट्रिक्स के लिए नहीं, बल्कि उसके स्तंभों के सूचकांकों के सेट के लिए किया जाता है। मान लीजिए B {1,...,n} से m सूचकांकों का एक उपसमुच्चय है। द्वारा निरूपित करें $A_{B}$ वर्ग m-by-m मैट्रिक्स, m कॉलम से बना है $A$ बी द्वारा अनुक्रमित यदि $A_{B}$ बीजगणितीय वक्र#एकवचन है, बी द्वारा अनुक्रमित स्तंभ स्तंभ स्थान का एक आधार (रैखिक बीजगणित) हैं $A$. इस मामले में, हम बी को 'एलपी का आधार' कहते हैं।

के पद से $A$ एम है, इसका कम से कम एक आधार है; तब से $A$ इसमें n कॉलम हैं, इसमें अधिकतम है ${\binom {n}{m}}$ आधार.

बुनियादी व्यवहार्य समाधान

आधार बी दिए जाने पर, हम कहते हैं कि एक व्यवहार्य समाधान $\mathbf {x}$ आधार बी के साथ एक बुनियादी व्यवहार्य समाधान है यदि इसके सभी गैर-शून्य चर को बी द्वारा अनुक्रमित किया जाता है, अर्थात सभी के लिए $j\not \in B:~~x_{j}=0$.

गुण

1. एक बीएफएस केवल एलपी (मैट्रिक्स) की बाधाओं से निर्धारित होता है $A$ और वेक्टर $\mathbf {b}$); यह अनुकूलन उद्देश्य पर निर्भर नहीं है.

2. परिभाषा के अनुसार, एक BFS में अधिकतम m गैर-शून्य चर और कम से कम n-m शून्य चर होते हैं। एक BFS में m से कम गैर-शून्य चर हो सकते हैं; उस स्थिति में, इसके कई अलग-अलग आधार हो सकते हैं, जिनमें से सभी में इसके गैर-शून्य चर के सूचकांक शामिल हैं।

3. एक व्यवहार्य समाधान $\mathbf {x}$ यदि-और-केवल-यदि मैट्रिक्स के कॉलम बुनियादी हैं $A_{K}$ रैखिक रूप से स्वतंत्र हैं, जहां K गैर-शून्य तत्वों के सूचकांकों का समूह है $\mathbf {x}$.

4. प्रत्येक आधार एक अद्वितीय बीएफएस निर्धारित करता है: एम सूचकांकों के प्रत्येक आधार बी के लिए, अधिकतम एक बीएफएस होता है $\mathbf {x_{B}}$ आधार बी के साथ ऐसा इसलिए है क्योंकि $\mathbf {x_{B}}$ बाधा को पूरा करना होगा $A_{B}\mathbf {x_{B}} =b$, और आधार मैट्रिक्स की परिभाषा के अनुसार $A_{B}$ गैर-एकवचन है, इसलिए बाधा का एक अद्वितीय समाधान है: <ब्लॉककोट>$\mathbf {x_{B}} ={A_{B}}^{-1}\cdot b$ विपरीत सत्य नहीं है: प्रत्येक बीएफएस कई अलग-अलग आधारों से आ सकता है। यदि का अनोखा समाधान $\mathbf {x_{B}} ={A_{B}}^{-1}\cdot b$ गैर-नकारात्मकता बाधाओं को संतुष्ट करता है $\mathbf {x_{B}} \geq 0$, तो B को 'संभाव्य आधार' कहा जाता है।

5. यदि एक रैखिक प्रोग्राम का एक इष्टतम समाधान है (अर्थात, इसका एक व्यवहार्य समाधान है, और व्यवहार्य समाधानों का सेट घिरा हुआ है), तो इसमें एक इष्टतम बीएफएस है। यह बाउर अधिकतम सिद्धांत का परिणाम है: एक रैखिक कार्यक्रम का उद्देश्य उत्तल है; व्यवहार्य समाधानों का सेट उत्तल है (यह हाइपरस्पेस का प्रतिच्छेदन है); इसलिए उद्देश्य व्यवहार्य समाधानों के सेट के चरम बिंदु पर अपनी अधिकतम सीमा प्राप्त करता है।

चूँकि BFS-s की संख्या सीमित और परिबद्ध है ${\binom {n}{m}}$किसी भी एलपी के लिए एक इष्टतम समाधान सभी में उद्देश्य फ़ंक्शन का मूल्यांकन करके सीमित समय में पाया जा सकता है ${\binom {n}{m}}$बीएफएस-एस. एलपी को हल करने का यह सबसे कारगर तरीका नहीं है; सिम्प्लेक्स एल्गोरिदम बीएफएस-एस की अधिक कुशल तरीके से जांच करता है।

उदाहरण

निम्नलिखित बाधाओं वाले एक रैखिक कार्यक्रम पर विचार करें:

${\begin{aligned}x_{1}+5x_{2}+3x_{3}+4x_{4}+6x_{5}&=14\\x_{2}+3x_{3}+5x_{4}+6x_{5}&=7\\\forall i\in \{1,\ldots ,5\}:x_{i}&\geq 0\end{aligned}}$ मैट्रिक्स ए है:

$A={\begin{pmatrix}1&5&3&4&6\\0&1&3&5&6\end{pmatrix}}~~~~~\mathbf {b} =(14~~7)$ यहां, m=2 और 2 सूचकांकों के 10 उपसमुच्चय हैं, हालांकि, उनमें से सभी आधार नहीं हैं: सेट {3,5} कोई आधार नहीं है क्योंकि कॉलम 3 और 5 रैखिक रूप से निर्भर हैं।

मैट्रिक्स के बाद से सेट B={2,4} एक आधार है $A_{B}={\begin{pmatrix}5&4\\1&5\end{pmatrix}}$ गैर-एकवचन है.

इस आधार के अनुरूप अद्वितीय बीएफएस है $x_{B}=(0~~2~~0~~1~~0)$.

ज्यामितीय व्याख्या

100x100 पिक्सल

सभी व्यवहार्य समाधानों का समुच्चय आयाम का प्रतिच्छेदन है। इसलिए, यह एक उत्तल बहुफलक है। यदि यह घिरा हुआ है, तो यह एक उत्तल पॉलीटॉप है। प्रत्येक बीएफएस इस पॉलीटोप के एक शीर्ष से मेल खाता है।

दोहरी समस्या के लिए बुनियादी व्यवहार्य समाधान

जैसा कि ऊपर उल्लेख किया गया है, प्रत्येक आधार बी एक अद्वितीय बुनियादी व्यवहार्य समाधान को परिभाषित करता है $\mathbf {x_{B}} ={A_{B}}^{-1}\cdot b$ . इसी प्रकार, प्रत्येक आधार दोहरे रैखिक कार्यक्रम के समाधान को परिभाषित करता है:

छोटा करना ${\textstyle \mathbf {b^{T}} \mathbf {y} }$

का विषय है $A^{T}\mathbf {y} \geq \mathbf {c}$.

समाधान है $\mathbf {y_{B}} ={A_{B}^{T}}^{-1}\cdot c$.

एक इष्टतम बीएफएस ढूँढना

बीएफएस खोजने के लिए कई तरीके हैं जो इष्टतम भी हैं।

सिम्प्लेक्स एल्गोरिथ्म का उपयोग करना

व्यवहार में, इष्टतम बीएफएस खोजने का सबसे आसान तरीका सिंप्लेक्स एल्गोरिदम का उपयोग करना है। यह अपने निष्पादन के प्रत्येक बिंदु पर, एक वर्तमान आधार बी (एन चर में से एम का एक उपसमूह), एक वर्तमान बीएफएस और एक वर्तमान झांकी रखता है। झांकी रैखिक कार्यक्रम का प्रतिनिधित्व है जहां बुनियादी चर को गैर-बुनियादी के संदर्भ में व्यक्त किया जाता है:

$${\begin{aligned}x_{B}&=p+Qx_{N}\\z&=z_{0}+r^{T}x_{N}\end{aligned}}$$

कहाँ $x_{B}$ एम मूल चर का वेक्टर है, $x_{N}$ n गैर-बुनियादी चर का वेक्टर है, और $z$ अधिकतमीकरण उद्देश्य है. चूंकि गैर-बुनियादी चर 0 के बराबर हैं, वर्तमान बीएफएस है $p$, और वर्तमान अधिकतमीकरण उद्देश्य है $z_{0}$.

यदि सभी गुणांक में $r$ तो फिर, नकारात्मक हैं $z_{0}$ एक इष्टतम समाधान है, क्योंकि सभी चर (सभी गैर-बुनियादी चर सहित) कम से कम 0 होने चाहिए, इसलिए दूसरी पंक्ति का तात्पर्य है $z\leq z_{0}$.

यदि कुछ गुणांक में $r$ सकारात्मक हैं, तो अधिकतमीकरण लक्ष्य को बढ़ाना संभव हो सकता है। उदाहरण के लिए, यदि $x_{5}$ गैर-बुनियादी है और इसका गुणांक है $r$ सकारात्मक है, तो इसे 0 से ऊपर बढ़ाने पर बन सकता है $z$ बड़ा. यदि अन्य बाधाओं का उल्लंघन किए बिना ऐसा करना संभव है, तो बढ़ा हुआ चर बुनियादी हो जाता है (यह आधार में प्रवेश करता है), जबकि समानता की बाधाओं को बनाए रखने के लिए कुछ बुनियादी चर को घटाकर 0 कर दिया जाता है और इस प्रकार गैर-बुनियादी बन जाता है (यह आधार से बाहर हो जाता है)।

यदि यह प्रक्रिया सावधानीपूर्वक की जाए तो इसकी गारंटी संभव है $z$ तब तक बढ़ता है जब तक यह इष्टतम बीएफएस तक नहीं पहुंच जाता।

किसी भी इष्टतम समाधान को इष्टतम बीएफएस में परिवर्तित करना

सबसे खराब स्थिति में, सिम्प्लेक्स एल्गोरिदम को पूरा करने के लिए तेजी से कई चरणों की आवश्यकता हो सकती है। कमजोर बहुपद समय एल्गोरिदम में एलपी को हल करने के लिए एल्गोरिदम हैं | कमजोर-बहुपद समय, जैसे दीर्घवृत्त विधि; हालाँकि, वे आम तौर पर इष्टतम समाधान लौटाते हैं जो बुनियादी नहीं होते हैं।

हालाँकि, एलपी के किसी भी इष्टतम समाधान को देखते हुए, एक इष्टतम व्यवहार्य समाधान ढूंढना आसान है जो बुनियादी भी हो।

एक ऐसा आधार ढूंढना जो प्रारंभिक-इष्टतम और दोहरे-इष्टतम दोनों हो

यदि समाधान हो तो एलपी के आधार बी को 'दोहरा-इष्टतम' कहा जाता है $\mathbf {y_{B}} ={A_{B}^{T}}^{-1}\cdot c$ दोहरे रैखिक कार्यक्रम का एक इष्टतम समाधान है, अर्थात यह न्यूनतम करता है ${\textstyle \mathbf {b^{T}} \mathbf {y} }$. सामान्य तौर पर, एक प्रारंभिक-इष्टतम आधार आवश्यक रूप से दोहरे-इष्टतम नहीं होता है, और एक दोहरे-इष्टतम आधार आवश्यक रूप से प्रारंभिक-इष्टतम नहीं होता है (वास्तव में, एक प्रारंभिक-इष्टतम आधार का समाधान दोहरे के लिए भी अव्यवहार्य हो सकता है, और इसके विपरीत)।

अगर दोनों $\mathbf {x_{B}} ={A_{B}}^{-1}\cdot b$ प्राइमल एलपी का एक इष्टतम बीएफएस है, और $\mathbf {y_{B}} ={A_{B}^{T}}^{-1}\cdot c$ दोहरी एलपी का एक इष्टतम बीएफएस है, तो आधार बी को 'पीडी-इष्टतम' कहा जाता है। इष्टतम समाधान वाले प्रत्येक एलपी में पीडी-इष्टतम आधार होता है, और यह सिम्प्लेक्स एल्गोरिदम द्वारा पाया जाता है। हालाँकि, सबसे खराब स्थिति में इसका रन-टाइम तेजी से बढ़ता है। निम्रोद मेगिद्दो ने निम्नलिखित प्रमेय सिद्ध किये: * एक सशक्त बहुपद समय एल्गोरिदम मौजूद है जो प्रारंभिक एलपी के लिए एक इष्टतम समाधान और दोहरे एलपी के लिए एक इष्टतम समाधान इनपुट करता है, और एक इष्टतम आधार देता है।

• यदि एक सशक्त बहुपद समय एल्गोरिथ्म मौजूद है जो केवल प्रारंभिक एलपी (या केवल दोहरी एलपी) के लिए एक इष्टतम समाधान इनपुट करता है और एक इष्टतम आधार देता है, तो किसी भी रैखिक कार्यक्रम को हल करने के लिए एक दृढ़ता से बहुपद समय एल्गोरिदम मौजूद है (उत्तरार्द्ध एक प्रसिद्ध खुली समस्या है)।

मेगिद्दो के एल्गोरिदम को सिम्प्लेक्स एल्गोरिदम की तरह ही एक झांकी का उपयोग करके निष्पादित किया जा सकता है।

बाहरी संबंध

• How to move from an optimal feasible solution to an optimal basic feasible solution. Paul Robin, Operations Research Stack Exchange.