1.सिम्पलैक्स विधि सिद्धान्त (Theory of Simplex Method):

Theory of Simplex Method

सिम्पलैक्स विधि सिद्धान्त (Theory of Simplex Method):रैखिक प्रोग्रामन का आधारभूत प्रमेय (Fundamental Theorem of L.P.P.):
प्रमेय (Theorem):1.यदि रैखिक प्रोग्रामन समस्या अधिकतम Z=CX जबकि A X=b, X \geq 0 का इष्टतम (Optimal) हल विद्यमान हो तो कम से कम एक आधारी सुसंगत हल (B.F.S.) इष्टतम होता है।
(If the L.P.P. Max.Z=CX s.t. A X=b, X \geq 0 admits an optimal solution,then at least one basic feasible solution must be optimal.)
उपपत्ति (Proof):माना कि समस्या की गुणांक मैट्रिक्स A एक m × n क्रम की मैट्रिक्स है।जहाँ A=\left(\alpha_{1}, \alpha_{2}, \alpha_{3}, \ldots, \alpha_{n}\right) है।माना कि X^{*}=\left(x_{1}, x_{2}, x_{3},\ldots,x_{n}\right) समस्या का इष्टतम (optimal) हल है और इस हल के संगत Z^{*} उद्देश्य फलन का अधिकतम मान है।
चूँकि इष्टतम हल में कुछ चरों का मान शून्य हो सकता है तो
मान लो X^{*}=\left(x_{1}, x_{2}, x_{3}, \ldots, x_{k}, 0,0,0, \ldots, 0\right)
जहाँ हमने X^{*} के प्रथम k अवयव को शून्येत्तर एवं शेष (n-k) अवयवों को शून्य माना है।
अब चूँकि X^{*}, रैखिक प्रोग्रामन समस्या का एकैकी हल है,अत: A X^{*}=b \\ \Rightarrow \left(\alpha_{1}, \alpha_{2},\alpha_{3}, \ldots, \alpha_{n}\right)\left[\begin{array}{c}x_{1} \\x_{2} \\x_{3} \\ \cdot \\ \cdot \\ x_{k} \\ \cdot \\ \cdot \\ 0 \end{array}\right]=b \\ \Rightarrow \alpha_{1} x_{1}+\alpha_{2} x_{2}+\alpha_{3} x_{3}+\ldots+\alpha_{k} x_{k}=b \\ \Rightarrow \sum_{j=1}^{K} \alpha_{j} x_{j}=b \cdots (1)
और अधिकतम Z=Z^{*}=c_{1} x_{1}+c_{2} x_{2}+c_{3} x_{3}+\cdots+c_{k} x_{k}=\sum_{j=1}^{k} c_{j} x_{j} \cdots(2)
अब \alpha_{1}, \alpha_{2}, \alpha_{3}, \ldots , \alpha_{k} के लिए दो स्थितियाँ संभव हैं।
स्थिति:I.यदि \alpha_{1}, \alpha_{2}, \alpha_{3}, \ldots , \alpha_{k} एकघातत: स्वतन्त्र हो (If \alpha_{1}, \alpha_{2}, \alpha_{3}, \ldots , \alpha_{k} are L.I.)
इस स्थिति में X^{*} एक आधारी सुसंगत हल होगा।क्योंकि यदि किसी सुसंगत हल के शून्येत्तर चरों के सदिश गुणांक एकघातत: स्वतन्त्र हो तो वह आधारी सुसंगत (B.F.S.) हल होता है।
स्थिति:II.यदि \alpha_{1}, \alpha_{2}, \alpha_{3}, \ldots , \alpha_{k} एकघातत: परतन्त्र हो (If \alpha_{1}, \alpha_{2}, \alpha_{3}, \ldots , \alpha_{k} are L.D.)
इस स्थिति में हम एक नया इष्टतम हल ज्ञात करेंगे जिसमें शून्येत्तर चरों की संख्या पूर्व से कम हो।
इस स्थिति में चूँकि \alpha_{1}, \alpha_{2}, \alpha_{3}, \ldots , \alpha_{k} एकघातत: परतन्त्र है,अतः परिभाषानुसार

\sum_{j=1}^{k} \lambda_{i} \alpha_{j}=0 \cdots(3)
जहाँ O शून्य सदिश है तथा जहाँ \lambda_{1}, \lambda_{2}, \lambda_{3}, \cdots, \lambda_{k} में से कम से कम एक अदिश शून्येत्तर है।माना कि इनमें से कम से कम एक \lambda_{j} धनात्मक है, यदि नहीं तो समीकरण (3) को -1 से गुणाकर इसे धनात्मक बना लेते हैं।अब माना कि
v=अधिकतम \left(\frac{\lambda_{i}}{x_{j}}\right) ; 1 \leq j \leq k \cdots(4)
स्पष्टतः v>0 क्योंकि x_{j}>0,j=1,2,3,.......,k और कम से कम एक \lambda_{j}>0 है।
(1) में से सम्बन्ध (3) को \frac{1}{v} से गुणा करके घटाने पर:

\sum_{j=1}^{K} \alpha_{j} x_{j}-\frac{1}{v} \sum_{j=1}^{k} \lambda_{j} \alpha_{j}=b-0 \\ \Rightarrow \sum_{j=1}^{K}\left(x_{j}-\frac{\lambda_{i}}{v}\right) \alpha_{j}=b \cdots(5)
यदि हम \left(x_{j}-\frac{\lambda_{i}}{v}\right) को x_{j}^{\prime} लिखें तब (5) से:

\sum_{j=1}^{k} x_{j}^{\prime} \alpha_{j}=b \cdots(6)
अतः सम्बन्ध (1) व (6) की तुलना से स्पष्ट है कि

X^{\prime}=\left(x_{1}^{\prime}, x_{2}^{\prime}, x_{3}^{\prime} \ldots \ldots x_{k}^{\prime}, 0,0,0,\ldots, 0\right)\\ X^{\prime}=\left(x_{1}-\frac{\lambda_{1}}{\nu}, x_{2}-\frac{\lambda_{2}}{v},\ldots \ldots x_{k}-\frac{\lambda_{k}}{v}, 0,0,\ldots, 0\right)
अतः X^{\prime} भी AX=b का एक नया हल है।
अब समीकरण (4) से:
v \geq \frac{\lambda_{j}}{x_{j}} ; 1 \leq j \leq k \\ \Rightarrow x_{j} \geq \frac{\lambda_{j}}{v} [चूँकि x_{j} तथा v दोनों धनात्मक हैं]

\Rightarrow x_{j} -\frac{\lambda_{j}}{v} \geq 0 \forall j=1,2,3,\ldots, k \\ \Rightarrow x_{j} \geq 0, \forall j=1,2,3,\ldots, k
अतः सभी x^{\prime}_{j} के मान शून्य या धनात्मक है,
अतः X^{\prime} रैखिक प्रोग्रामन समस्या का एक सुसंगत हल [F.S.] है।
पुनः समीकरण (4) से:
v=\frac{\lambda_{j}}{x_{j}}, j के कम से कम एक मान के लिए
\Rightarrow x_{j}=\frac{\lambda_{j}}{v}, j के कम से कम एक मान के लिए
\Rightarrow x_{j}-\frac{\lambda_{j}}{v}=0, j के कम से कम एक मान के लिए
अतः नये सुसंगत हल X^{\prime} में प्रथम k चरों में से किसी एक का मान शून्य है।अर्थात् सुसंगत हल X^{\prime} में शून्येत्तर चरों की संख्या k-1 या इससे कम होगी अर्थात् हमने एक इष्टतम हल X^{*} से ऐसा नया सुसंगत हल (F.S.) ज्ञात कर लिया है जिसमें शून्येत्तर चरों की संख्या, इष्टतम हलों में चरों की संख्या \left(x_{1}, x_{2}, x_{3},\ldots, x_{k}\right) से कम है।
अब हम दर्शायेंगे कि X^{\prime} भी समस्या का एक इष्टतम हल है।
मानलो X^{\prime} हल के लिए उद्देश्य फलन का मान Z^{\prime} है।

Z^{\prime}=C X^{\prime}=\sum_{j=1}^{K} c_{j} x_{j}^{\prime}=\sum_{j=1}^{K} c_{j}\left(x_{j}-\frac{\lambda_{j}}{v}\right) \\ =\sum_{j=1}^{k} c_{j} x_{j}-\sum_{j=1}^{k} c_{j} \frac{\lambda_{j}^{\prime}}{v}=Z^{*}-\frac{1}{v} \sum_{j=1}^{K} C_{j} \lambda_{j}=0[(2) से ]
यदि X^{\prime} इष्टतम है तो Z^{\prime}=Z^{*} होगा, यह तभी सम्भव है जब

\sum_{j=1}^{K} C_{j} \lambda_{j}=0 \cdots(9)
(9) के सत्यापन के लिए हम विरोधाभास विधि का आश्रय लेते हैं।
मान लो \sum_{j=1}^{K} c_{j} \lambda_{j} \neq 0
तो \theta \sum_{j=1}^{k} c_{j} \lambda_{j}>0 , जहाँ \theta एक उपयुक्त वास्तविक संख्या है।

\Rightarrow \sum_{j=1}^{k} c_{j}\left(\theta \lambda_{j}\right)>0 \\ \Rightarrow \sum_{j=1}^{k} c_{j} \left(\theta \lambda_{j} \right)+\sum_{j=1}^{k} c_{j} x_{j}> \sum_{j=1}^{K} c_{j} x_{j} \\ \Rightarrow \sum_{j=1}^{k} c_{j}\left(x_{j}+ \theta \lambda_{j}\right)> \sum_{j=1}^{k} c_{j} x_{j}=Z^{*} \cdots (10)
अतः \left(x_{1}+\theta \lambda_{1}, x_{2}+\theta \lambda_{2}, x_{3}+\theta \lambda_{3}, \cdots, x_{k}+\theta \lambda_{k}, 0,0, \cdots 0\right) भी AX=b का एक हल है क्योंकि (3) \theta को से गुणा कर (1) में जोड़ने पर यह प्राप्त हो जाता है।
चूँकि \theta एक उपयुक्त वास्तविक संख्या है,अतः उपयुक्त हल ऋणेत्तर प्रतिबन्ध को भी सन्तुष्ट करना चाहिए जिसे हम निम्न प्रकार से प्रदर्शित करते हैं:
ऋणेत्तर प्रतिबन्ध के लिए

x_{j}+\theta \lambda_{j} \geq 0, 1 \leq j \leq k \\ \theta \lambda_{j} \geq -x_{j}, j=1,2,3,\ldots,k \\ \left. \begin{matrix} \theta \geq -\frac{x_{i}}{\lambda_{j}} \text{ जबकि } \lambda_{j}>0 \\  \text{ या } \theta \leq-\frac{x_{j}}{\lambda_{j}} \text{ जबकि } \lambda_{j}<0 \end{matrix}\right\}
और जब \lambda_{j}=0 हो तो \theta असीमित हो जाता है अर्थात् \theta का मान इस प्रकार हो कि
अधिकतम \left(\frac{-x_{j}}{\lambda_{j}}\right) \leq \theta \leq निम्नतम \left(\frac{-x_{j}}{\lambda_{j}}\right) \cdots(10)

\quad \quad \quad  \lambda_{j}>0 \quad \quad \quad \quad \quad  \lambda_{j}<0
तो x_{j}+\theta \lambda_{j}>0, \quad 1 \leq j \leq k
अतः नया हल एक सुसंगत (F.S.) है।लेकिन (10) से हम पाते हैं कि इस सुसंगत हल पर Z का मान Z^{*} से बड़ा हो जाता है जो कि Z^{*}=अधिकतम (Z),का विरोधाभास (Contradiction) है।
अतः हमारा मानना है कि \sum_{j=1}^{k} c_{j} \lambda_{j} \neq 0 सही नहीं है अर्थात् \sum_{j=1}^{k} c_{j} \lambda_{j}= 0 होगा।अब (8) से Z^{\prime}=Z^{*}, अर्थात् X^{\prime} रैखिक प्रोग्रामन समस्या का इष्टतम हल है।यदि इस X^{\prime} के चर \left(x_{1}^{\prime}, x_{2}^{\prime}, x_{3}^{\prime}, \cdots x_{k}^{\prime}\right) से सम्बद्ध सदिश एकघातत: स्वतन्त्र (L.I.) है तो X^{\prime} एक आधारी सुसंगत हल है जो कि प्रमेय को सत्यापित करती है।यदि ये सदिश एकघातत: परतन्त्र (L.D.) हों तो उपर्युक्त विधि को पुनः लागू करके हम इष्टतम हल प्राप्त करेंगे।जिनमें शून्येत्तर चरों की संख्या k-2 से ज्यादा नहीं होगी।इस प्रकार इस विधि को बार-बार लागू करने पर एक आधरी सुसंगत हल प्राप्त होगा जिस पर Z का मान इष्टतम होगा।
एक सुसंगत हल से आधारी सुसंगत हल प्राप्त करना (To obtain a B.F.S. From a F.S.)
प्रमेय (Theorem):2.यदि किसी निकाय AX=b,X \geq 0 (जहाँ A एक m×n मैट्रिक्स है और m<n) का एक सुसंगत हल विद्यमान है तो उसका आधारी सुसंगत हल भी विद्यमान होगा।
(If there is a feasible solution of the system AX=b,X \geq 0 Where A is a m×n matrix and m<n,there is also a basic feasible solution.)
उपपत्ति (Proof):माना कि X^{*}=\left(x_{1}, x_{2}, x_{3}, \cdots x_{n}\right) निकाय AX=b का सुसंगत हल (F.S.) है।माना कि n-घटकों में से k-घटक शून्येत्तर एवं n-k घटक शून्य है अर्थात्

X^{*}=\left(x_{1}, x_{2}, x_{3}, \cdots x_{k}, 0,0, \cdots 0\right)
चूँकि X^{*} निकाय का सुसंगत हल है इसलिए AX^{*}=b\\\Rightarrow \left(\alpha_{1}, \alpha_{2}, \alpha_{3}, \cdots, \alpha_{n}\right)\left[\begin{array}{c} x_{1} \\ x_{2} \\ x_{3} \\ \cdot \\ \cdot \\ x_{k} \\ 0 \\ 0 \\ \cdot \\0 \end{array}\right]=b \\ \Rightarrow \sum_{j=1}^{K} x_{j} \alpha_{j}=b \cdots(1)
जहाँ \alpha_{1}, \alpha_{2}, \alpha_{3}, ,\ldots,\alpha_{k} मैट्रिक्स A में क्रमशः \left(x_{1}, x_{2}, x_{3}, \cdots x_{k}\right) से सम्बन्धित सदिश है।
अब सदिश \alpha_{1}, \alpha_{2}, \alpha_{3}, ,\ldots,\alpha_{k} के लिए दो स्थितियाँ हैं।
स्थिति:I.जब \alpha_{1}, \alpha_{2}, \alpha_{3}, ,\ldots,\alpha_{k} एकघाती स्वतन्त्र हो (L.I.)
हम जानते हैं कि शून्येत्तर चरों से सम्बद्ध सदिश यदि एकघाती स्वतन्त्र (L.I.) हो तो सुसंगत हल, आधारी हल होता है।अतः भी आधारी सुसंगत हल है।
स्थिति:II.जब सदिश \alpha_{1}, \alpha_{2}, \alpha_{3}, ,\ldots,\alpha_{k} एकघाती परतन्त्र (L.D.) हो
ऐसी स्थिति में k>m होगा।अतः हम क्रमिक विधि से धनात्मक चरों की संख्या तब तक घटाते जाएंगे जब तक शून्येत्तर चरों से सम्बन्धित सदिश \left ( \alpha_{j} S\right ) एकघातत: स्वतन्त्र न हो जाए जिससे कि नया सुसंगत हल फिर आधारी सुसंगत हल हो जाएगा।
अब एकघातत: परतन्त्र की परिभाषा

\sum_{j=1}^{k} \alpha_{j} \lambda_{j}=0 \ldots(2)
जहाँ \lambda_{1}, \lambda_{2}, \lambda_{3}, \cdots, \lambda_{k} अदिश राशियाँ है जिसमें कम से कम एक \lambda_{j} शून्येत्तर धनात्मक है।यदि नहीं तो (2) को (-1) से गुणा कर, इसे धनात्मक बना लेते हैं।
मानलो v=अधिकतम \left ( \frac{\lambda_{j}}{x_{j}} \right ), i \leq j \leq k
अतः v>0 होगा चूँकि x_{j}>0,i \leq j \leq k
(2) को \frac{1}{v} से गुणा कर (1) में से घटाने पर:

\sum_{j=1}^{K} \alpha_{j} x_{j}-\frac{1}{v} \sum_{j=1}^{k} \lambda_{j} \alpha_{j}=b
या \sum_{j=1}^{k}\left(x_{j}-\frac{\lambda_{j}}{v}\right) \alpha_{j}=b \cdots(4)
अर्थात् X^{\prime}=\left(x_{1}-\frac{\lambda_{1}}{\nu}, x_{2}-\frac{\lambda_{2}}{v},\ldots \ldots x_{k}-\frac{\lambda_{k}}{v}, 0,0,\ldots, 0\right)
अब (3) से:
v \geq \frac{\lambda_{j}}{x_{j}}, 1 \leq j \leq k \\ \Rightarrow x_{j} \geq \frac{\lambda_{j}}{V} [v, x_{j} दोनों धनात्मक हैं]

\Rightarrow x_{j}-\frac{\lambda_{i}}{v} \geq 0,1 \leq j \leq k
अब X^{\prime} ऋणेत्तर प्रतिबन्ध को भी सन्तुष्ट करता है।इस प्रकार X^{\prime} दिये गए निकाय का सुसंगत हल है।
पुनः (3) से,j के कम से कम एक मान के लिए

V=\frac{\lambda_{j}}{x_{j}} \Rightarrow x_{j}=\frac{\lambda_{j}}{v} \\ \Rightarrow x_{j}-\frac{\lambda_{j}}{v}=0
अर्थात् X^{\prime} के x_{1}, x_{2}, x_{3}, \ldots, x_{k} में से कम से कम एक मान शून्य है।
अतः X^{\prime} के अधिक से अधिक (k-1) घटक शून्येत्तर हैं।
यदि नए सुसंगत हल में धनात्मक चरों से सम्बद्ध सदिश फिर भी एकघाती परतन्त्र हो तो उपर्युक्त विधि को क्रमिक रूप से तब तक दुहराते हैं जब तक कि ये सदिश एकघाती स्वतन्त्र न हो जाए।ऐसा प्राप्त सुसंगत हल दिए गए निकाय के एक आधारी सुसंगत हल हो जाएगा।
आपको यह जानकारी रोचक व ज्ञानवर्धक लगे तो अपने मित्रों के साथ इस गणित के आर्टिकल को शेयर करें।यदि आप इस वेबसाइट पर पहली बार आए हैं तो वेबसाइट को फॉलो करें और ईमेल सब्सक्रिप्शन को भी फॉलो करें।जिससे नए आर्टिकल का नोटिफिकेशन आपको मिल सके ।यदि आर्टिकल पसन्द आए तो अपने मित्रों के साथ शेयर और लाईक करें जिससे वे भी लाभ उठाए ।आपकी कोई समस्या हो या कोई सुझाव देना चाहते हैं तो कमेंट करके बताएं।इस आर्टिकल को पूरा पढ़ें।

Also Read This Article:-LPP Formulation and Graphical Solution

2.सिम्पलैक्स विधि सिद्धान्त के उदाहरण (Theory of Simplex Method Examples):

Example:1.सिद्ध कीजिए कि निम्न रैखिक समस्या का इष्टतम आधारी सुसंगत हल x_{1}=0, x_{2}=3,x_{3}=0 तथा x_{4}=3  है
(Show that x_{1}=0, x_{2}=3,x_{3}=0  and x_{4}=3 is the optimal B.F.S. to the L.P.P.)
अधिकतम (Max.) Z=3 x_{1}+5 x_{2}

प्रतिबन्ध (s.t.) x_{1}+2 x_{2}+x_{3}=6 \\ 4 x_{1}+3 x_{2}+x_{4}=12
तथा (and) x_{1}, x_{2}, x_{3}, x_{4} \geq 0
Solution:दी गई प्रोग्रामन समस्या को निम्न प्रकार लिख सकते हैं:
अधिकतम (Max.) Z=3 x_{1}+5 x_{2}+0 x_{3}+0 x_{4}
प्रतिबन्ध (s.t.) x_{1}+2 x_{2}+x_{3}+0 x_{4}=6 \\ 4 x_{1}+3 x_{2}+0 x_{3}+x_{4}=12
तथा x_{1}, x_{2}, x_{3}, x_{4} \geq 0
उपर्युक्त को मैट्रिक्स रूप में निम्न प्रकार व्यक्त कर सकते हैं:
Max.Z=CX, s.t. AX=b, X \geq 0
जहाँ A=\left[\begin{array}{llll} 1 & 2 & 1 & 0 \\ 4 & 3 & 0 & 1 \end{array}\right]=\left(\alpha_{1}, \alpha_{2}, \alpha_{3}, \alpha_{4}\right) \\ b=\left[\begin{array}{l} 6 \\ 12 \end{array}\right], X=\left[\begin{array}{l}x_{1} \\ x_{2} \\x_{3} \\x_{4}\end{array}\right] ,C=\left(\begin{array}{llll}3 & 5 & 0 & 0 \end{array}\right)
यदि X_{B} दिया हुआ आधारी हल है तो:

X_{B}=\left[\begin{array}{l}x_{B_{1}} \\x_{B_{2}}\end{array}\right]=\left[\begin{array}{l}x_{2} \\x_{4} \end{array} \right] =\left[\begin{array}{l}3 \\3\end{array}\right] \\ B=\left(\beta_{1} \quad \beta_{2}\right)=\left(\alpha_{2} \quad \alpha_{4}\right)=\left[\begin{array}{ll}2 & 0 \\3 & 1\end{array}\right] \\ C_{B}=\left(C_{B_{1}} \quad C_{B_{2}} \right)= \left(\begin{array}{ll}5 & 0\end{array}\right)
अब हम y_{1}, y_{2}, y_{3}, y_{4} के मान ज्ञात करते हैं:

y_{1}=B^{-1} \alpha_{1}=\frac{1}{2}\left[\begin{array}{ll}1 & 0 \\-3 & 2\end{array}\right]\left[\begin{array}{l}1 \\4\end{array}\right] \\ \Rightarrow y_{1}=\frac{1}{2}\left[\begin{array}{c}1+6 \\-3+8\end{array} \right] =\left[ \begin{array}{c} \frac{1}{2} \\ \frac{5}{2}\end{array}\right] \\ y_{2} =B^{-1} \alpha_{2}=\frac{1}{2}\left[\begin{array}{ll}1 & 0 \\-3 & 2\end{array}\right]\left[\begin{array}{l}2 \\3\end{array}\right] \\ \Rightarrow y_{2}=\frac{1}{2} \left[\begin{array}{c}2+0 \\-6+6\end{array}\right]=\left[\begin{array}{l}1 \\0\end{array}\right] \\ y_{3}=B^{-1} \alpha_{3}=\frac{1}{2}\left[ \begin{array}{cc}1 & 0 \\-3 & 2\end{array}\right] \left[\begin{array}{l}1 \\0\end{array}\right] \\ \Rightarrow y_{3}=\frac{1}{2}\left[\begin{array}{c}1+0 \\-3+0\end{array}\right]=\left[\begin{array}{c}\frac{1}{2} \\-\frac{3}{2}\end{array}\right] \\ y_{4} =B^{-1} \alpha_{4} \\=\frac{1}{2}\left[\begin{array}{cc}1 & 0 \\-3 & 2\end{array}\right] \left[\begin{array}{l}0 \\1\end{array}\right] \\ =\frac{1}{2}\left[\begin{array}{l}0+0 \\0+2\end{array}\right] \\ \Rightarrow y_{4}=\left[ \begin{array}{l}0 \\1\end{array}\right]
साथ ही Z_{1}-C_{1} =C_{B}-y_{1} \\ =(5 \quad 0)\left[\begin{array}{l}\frac{1}{2} \\\frac{5}{2}\end{array}\right] \\ =\frac{5}{2} \\ Z_{2}-C_{2} =C_{B}-y_{2} \\=(5 \quad 0)\left[\begin{array}{l}1 \\0\end{array}\right]=5 \\ Z_{3}-C_{3}=\left(\begin{array}{ll}5 & 0\end{array}\right)\left[\begin{array}{c}\frac{1}{2} \\-\frac{3}{2}\end{array}\right]=\frac{5}{2} \\ Z_{4}-C_{4}= \left(\begin{array}{ll}5 & 0\end{array}\right)\left[\begin{array}{l}0 \\1\end{array}\right]=0
उपर्युक्त से स्पष्ट है कि j के प्रत्येक मान के लिए Z_{j}-C_{j} \geq 0 अत: दत्त आधारी सुसंगत हल इष्टतम हल (optimal solution) है।
Example:2.यदि x_{1}=2, x_{2}=3, x_{3}=1 निम्न रैखिक प्रोग्रामन समस्या का एक सुसंगत हल है तो इसके एक आधारी सुसंगत हल ज्ञात कीजिए।
(If x_{1}=2, x_{2}=3, x_{3}=1 be a feasible solution of the following L.P.P. then find B.F.S.)
अधिकतम (Max.) Z=x_{1}+2 x_{2}+4 x_{3}
प्रतिबन्ध (s.t.) 2 x_{1}+x_{2}+4 x_{3}=11 \\ 3 x_{1}+x_{2}+5 x_{3}=14 ,x_{1}, x_{2}, x_{3} \geq 0 
Solution:दी गई समस्या को निम्न प्रकार मैट्रिक्स के रूप में व्यक्त कर सकते हैं:

\left[\begin{array}{lll}2 & 1 & 4 \\3 & 1 & 5\end{array}\right]\left[\begin{array}{c}x_{1} \\x_{2} \\x_{3}\end{array} \right]=\left[\begin{array}{c}11 \\14\end{array}\right]
या \alpha_{1} x_{1}+\alpha_{2} x_{2}+\alpha_{3} x_{3}=b \cdots(1)
जहाँ \alpha_{1}=\left[\begin{array}{l}2 \\3\end{array}\right], \alpha_{2}=\left[\begin{array}{l}1 \\1\end{array}\right], \alpha_{3}=\left[\begin{array}{l}4 \\5\end{array}\right],b=\left[\begin{array}{l}11 \\14\end{array}\right] 
तथा x_{1}, x_{2}, x_{3} \geq 0
अब चूँकि x_{1}=2, x_{2}=3, x_{1}=1 दी गई समस्या का एक सुसंगत हल है।इसलिए 2 \alpha_{1}+3 \alpha_{2}+\alpha_{3}=b \cdots(2)
हम देखते हैं कि सदिश \alpha_{1},\alpha_{2},\alpha_{3} एकघातत: परतन्त्र है,अतः किसी एक सदिश को अन्य दो सदिशों के एकघातत: संचय (L.C.) के रूप में व्यक्त किया जा सकता है।
माना \alpha_{3}=\lambda_{1} \alpha_{1}+\lambda_{2} \alpha_{2} \cdots(3)
या \left[\begin{array}{l}4 \\5\end{array}\right]=\left[\begin{array}{l}2 \lambda_{1}+\lambda_{2} \\3 \lambda_{1} +\lambda_{2}\end{array}\right] \\ \Rightarrow 2 \lambda_{1}+\lambda_{2}=4 तथा 3 \lambda_{1}+\lambda_{2}=5 \\ \Rightarrow \lambda_{1}=1, \lambda_{2}=2
\lambda_{1}, \lambda_{2} का मान (3) में रखने पर:

\alpha_{3}=\alpha_{1}+2 \alpha_{2} \Rightarrow \alpha_{1}+2 \alpha_{2}-\alpha_{3}=0 \\ \Rightarrow \sum_{j=1}^{3} \lambda_{j} \alpha_{j}=0 \cdots(4)
जहाँ \lambda_{1}=1, \lambda_{2}=2, \lambda_{3}=-1
अब हम चर x_{1},x_{2},x_{3} में से कौनसा एक चर शून्य होगा इस पर विचार करेंगे।मान लो v=अधिकतम \frac{\lambda_{j}}{x_{j}}, 1 \leq j \leq 3
=अधिकतम \left\{\frac{\lambda_{1}}{x_{1}}, \frac{\lambda_{2}}{x_{2}}, \frac{\lambda_{3}}{x_{3}}\right\}
=अधिकतम \left[\frac{1}{2}, \frac{2}{3}, \frac{-1}{1}\right] \\ =\frac{2}{3}=\frac{\lambda_{2}}{x_{2}}
[\lambda_{2} मुख्य अवयव (key element) कहलाता है]
अतः x_{2} का मान शून्य होना चाहिए तथा \alpha_{2} आधार से लुप्त होना चाहिए।
को लुप्त करने के हेतु (4) से \alpha_{2}=\frac{\alpha_{3}-\alpha_{1}}{2} का मान (2) में रखने पर:

2 \alpha_{1}+3\left(\frac{\alpha_{3}-\alpha_{1}}{2}\right)+\alpha_{3}=b
या \frac{\alpha_{1}}{2}+0 \alpha_{2}+\frac{5}{2} \alpha_{3}=b \ldots(5)
समीकरण (5) से:
x_{1}=\frac{1}{2}, x_{2}=0 तथा x_{3}=\frac{5}{2} दी गई समस्या का एक नया सुसंगत हल है।

Theory of Simplex Method

Example:3.यदि x_{1}=2, x_{2}=4, x_{3}=1 निम्न रैखिक प्रोग्रामन समस्या का एक सुसंगत हल है तो इसके लिए एक आधारी सुसंगत हल ज्ञात कीजिए।
(If x_{1}=2, x_{2}=4  and x_{3}=1 be a feasible solution of the following L.P.P. then find B.F.S.)
अधिकतम (Max.) Z=2 x_{1}+x_{2}+4 x_{3}
प्रतिबन्ध (s.t.) 2 x_{1}-x_{2}+2 x_{3}=2 \\ x_{1}+4 x_{2}=18 \\ x_{1}, x_{2}, x_{3} \geq 0
Solution:दी हुई समस्या को निम्न प्रकार मैट्रिक्स के रूप में व्यक्त कर सकते हैं’

\left[\begin{array}{lll}2 & -1 & 2 \\1 & 4 & 0\end{array}\right]\left[\begin{array}{l}x_{1} \\x_{2} \\x_{3}\end{array} \right]=\left[\begin{array}{c}2 \\18\end{array}\right]
या \alpha_{1} x_{1}+\alpha_{2} x_{2}+\alpha_{3} x_{3}=b \cdots(1)
जहाँ \alpha_{1}=\left[\begin{array}{l}2 \\1\end{array}\right], \alpha_{2}=\left[\begin{array}{c}-1 \\4\end{array} \right],\alpha_{3}=\left[\begin{array}{l}2 \\0\end{array}\right],b=\left[\begin{array}{l}2 \\18\end{array}\right]
तथा x_{1}, x_{2}, x_{3} \geq 0
अब चूँकि x_{1}=2, x_{2}=4, x_{3}=1 दी गई समस्या का एक सुसंगत हल है।
इसलिए 2 \alpha_{1}+4 \alpha_{2}+\alpha_{3}=b \cdots(2)
हम देखते हैं कि सदिश \alpha_{1},\alpha_{2},\alpha_{3} एकघातत: परतन्त्र है,अतः किसी एक सदिश को अन्य दो सदिशों के एकघातत: संचय (L.C.) के रूप में व्यक्त किया जा सकता है।
माना \alpha_{3}=\lambda_{1} \alpha_{1}+\lambda_{2} \alpha_{2} \ldots \cdots(3)
या \left[\begin{array}{l}2 \\0\end{array}\right]=\lambda_{1}\left[\begin{array}{l}2 \\1\end{array}\right]+ \lambda_{2} \left[\begin{array}{l}-1 \\4\end{array}\right] \\ \Rightarrow \left[\begin{array}{l}2 \\0\end{array}\right] =\left[ \begin{array}{l}2 \lambda_{1}-\lambda_{2} \\ \lambda_{1}+4 \lambda_{2}\end{array}\right] \\ \Rightarrow 2 \lambda_{1}-\lambda_{2}=2 तथा \lambda_{1}+4 \lambda_{2}=0 \\ \Rightarrow \lambda_{1}=\frac{8}{9}, \lambda_{2}=-\frac{2}{9}
\lambda_{1},\lambda_{2} का मान (3) में रखने पर:

\alpha_{3}=\frac{8}{9} \alpha_{1}-\frac{2}{9} \alpha_{2} \\ \Rightarrow \frac{8}{9} \alpha_{1}-\frac{2}{9} \alpha_{2}-\alpha_{3}=0 \\ \sum_{j=1}^{3} \lambda_{j} \alpha_{j}=0 \cdots(4)
जहाँ \lambda_{1}=\frac{8}{9}, \lambda_{2}=-\frac{2}{9}, \lambda_{3}=-1
अब हम चर x_{1}, x_{2}, x_{3} में से कौनसा एक चर शून्य होगा इस पर विचार करेंगे।
मानलो v=अधिकतम \frac{\lambda_{j}}{x_{j}}, 1 \leq j \leq 3
=अधिकतम \left\{\frac{\lambda_{1}}{x_{1}}, \frac{\lambda_{2}}{x_{2}}, \frac{\lambda_{3}}{x_{3}}\right\}

=अधिकतम \left\{\frac{\frac{8}{9}}{2}, \frac{-\frac{2}{9}}{4}, \frac{-1}{1}\right\} \\ =\frac{4}{9}=\frac{\lambda_{1}}{x_{1}} 
[ \lambda_{1} मुख्य अवयव (key element) कहलाता है]
अतः x_{1} का मान शून्य होना चाहिए तथा \alpha_{1} आधार से लुप्त होना चाहिए।
\alpha_{1} को लुप्त करने हेतु (4) से:
\alpha_{1}=\frac{1}{4} \alpha_{2}+\frac{9}{8} \alpha_{3} का मान (2) में रखने पर:

2\left(\frac{1}{4} \alpha_{2}+\frac{9}{8} \alpha_{3}\right)+4 \alpha_{2}+\alpha_{3}=b \\ \Rightarrow \frac{9}{2} \alpha_{2}+\frac{13}{4} \alpha_{3}=b \\ \Rightarrow 0 \cdot \alpha_{1}+\frac{9}{2} \alpha_{2}+\frac{13}{4} \alpha_{3}=b \cdots(5)
समीकरण (5) से:

x_{1}=0, x_{2}=\frac{9}{2}, x_{3}=\frac{13}{4}
समस्या का एक नया सुसंगत हल है।
उपर्युक्त उदाहरणों के द्वारा सिम्पलैक्स विधि सिद्धान्त (Theory of Simplex Method) को समझ सकते हैं।

3.सिम्पलैक्स विधि सिद्धान्त की समस्याएं (Theory of Simplex Method Problems):

(1.)निम्न रैखिक प्रोग्रामन समस्या को मैट्रिक्स रूप में व्यक्त कीजिए।
(Express the following L.P.P. in the matrices form.(
निम्नतम करिए (Mini) Z=-3 x_{1}-5 x_{2}+4 x_{3}
प्रतिबन्ध (s.t.) 2 x_{1}+3 x_{3} \leq 8  \\ 3 x_{1}+2 x_{2}+4 x_{3} \leq 15 \\ 2 x_{1}+5 x_{3}\geq 10
तथा (and) x_{1}, x_{1}, x_{3} \geq 0
(2.)निम्न रैखिक प्रोग्रामन समस्या पर विचार कीजिए
(Consider the following L.P.P.)
अधिकतम (Max.)  Z=x_{1}+x_{2}+2 x_{3}
प्रतिबन्ध (s.t.) 4 x_{1}+2 x_{2}+x_{3} \leq 4 \\ x_{1}+2 x_{2}+3 x_{3} \geq 8
तथा (and) x_{1}, x_{1}, x_{3} \geq 0
उत्तर (Answers):(1.)अधिकतम करो Z^{\prime}=CX ,प्रतिबन्ध (s.t.) AX=b,तथा X\geq 0
जहाँ C=\left(\begin{array}{llllll}3 & 5 & -4 & 0 & 0 & 0 \end{array}\right), X=\left[\begin{array}{l}x_{1} \\x_{2} \\x_{3} \\x_{4} \\x_{5} \\x_{6}\end{array}\right] \\b=\left[\begin{array}{c}8 \\15 \\10\end{array}\right] तथा A=\left[\begin{array}{llllll}2 & 0 & 3 & 1 & 0 & 0 \\3 & 2 & 4 & 0 & 1 & 0 \\0 & 2 & 5 & 0 & 0 & 1\end{array}\right]
(2.)z_{2}=\frac{16}{11}, \alpha_{2}=\frac{6}{11} \beta_{1}+\frac{4}{11} \beta_{2}
उपर्युक्त सवालों को हल करने पर सिम्पलैक्स विधि सिद्धान्त (Theory of Simplex Method) को ठीक से समझ सकते हैं।

4.मुख्य बिन्दु (HIGHLIGHTS):

Theory of Simplex Method

(1.) किसी रैखिक प्रोग्रामन समस्या को सिम्पलैक्स विधि द्वारा हल करने के लिए उसे एक विशेष रूप में लिखा जाता है जो समस्या का मानक रूप कहलाता है।मानक रूप की विशेषताएं निम्न प्रकार हैं:
(i)समस्या का उद्देश्य फलन अधिकतमीकरण (Maximization) रूप में होना चाहिए।
(ii)ऋणेत्तर प्रतिबंधों (Constraints) के अतिरिक्त सभी प्रतिबंध समीकरण के रूप में होने चाहिए।
(iii)आवश्यकता सदिश (Requirement vector) b के सभी घटक धनात्मक (positive) होने चाहिए।
(iv)सभी चर ऋणेत्तर (Non-negative) होने चाहिए।
(v)यदि उद्देश्य फलन न्यूनतमीकरण (Minimization) के रूप में हो तो उसे अधिकतमीकरण (Maximization) के रूप में बदल देना चाहिए अर्थात् उद्देश्य फलन के सभी चरों के मूल्यों का चिन्ह बदल देना चाहिए क्योंकि न्यूनतममीकरण f(x)=अधिकतमीकरण (-f(x))
(vi)इसी प्रकार किसी प्रतिबंध में b का घटक ऋणात्मक हो तो उस प्रतिबंध के दोनों पक्षों को -1 से गुणा कर धनात्मक बना लिया जाता है।
(vii)अंत में ऋणेत्तर प्रतिबंधों के अतिरिक्त निकाय में असमिकाओं को समीकरण में परिवर्तित कर लेते हैं।

Also Read This Article:-Basic Feasible Solution in LPP

5.सिम्पलैक्स विधि सिद्धान्त (Theory of Simplex Method) के सम्बन्ध में अक्सर पूछे जाने वाले प्रश्न:

 

सिम्पलैक्स विधि सिद्धान्त (Theory of Simplex Method):रैखिक प्रोग्रामन का आधारभूत प्रमेय
(Fundamental Theorem of L.P.P.):प्रमेय (Theorem):1.यदि रैखिक प्रोग्रामन समस्या
अधिकतम Z=CX जबकि