1.उन्नत आधारी सुसंगत हल (Improved Basic Feasible Solution),उन्नत आधारी सुसंगत हल ज्ञात करना (To Determine Improved Basic Feasible Solution):

Improved Basic Feasible Solution

उन्नत आधारी सुसंगत हल (Improved Basic Feasible Solution) ज्ञात के लिए एक महत्त्वपूर्ण प्रमेय को सिद्ध करेंगे जो कि हमें एक रैखिक प्रोग्रामन समस्या का आधारी सुसंगत हल से एक उन्नत आधारी सुसंगत हल प्राप्त करने में सहायक होती है।
प्रमेय (Theorem):3.माना कि एक रैखिक प्रोग्रामन समस्या का X_{B}=B^{-1} b आधारी सुसंगत है जिसके लिए उद्देश्य फलन का Z=C_{B} X_{B} है।किसी मैट्रिक्स A के स्तम्भ \alpha_{j} के लिए जो कि मैट्रिक्स B का स्तम्भ नहीं है, प्रतिबन्ध C_{j}-Z_{j}>0 या Z_{j}-C_{j}<0 सत्य है।यदि कम से कम एक y_{i j}>0,i=1,2,3,.......,m तब मैट्रिक्स B के एक स्तम्भ को \alpha_{j} से प्रतिस्थापित करने पर एक नये आधारी सुसंगत हल (B.F.S.) ज्ञात करना सम्भव है और यदि उद्देश्य फलन का नया मान Z’ है तब Z^{\prime} \geq Z तथा यदि दिया हुआ आधारी सुसंगत हल अनपभ्रष्ट है तब Z’>Z.
(Let X_{B}=B^{-1} b be a B.F.S. of a L.P.P. with Z=C_{B} X_{B} as the value of objective function.If for any columns \alpha_{j} in A, but not in B, the condition C_{j}-Z_{j}>0 or Z_{j}-C_{j}<0 holds and if at least one y_{i j}>0,i=1,2,3,.......,m then it is possible to obtain a new B.F.S. by replacing one of the column in B by \alpha_{j} and if the new value of the objective function is Z^{\prime} \geq Z if the given B.F.S. is non-degenerate then Z’>Z.)
उपपत्ति (Proof):माना कि निम्न दिए गए रैखिक प्रोग्रामन समस्या का आधारी सुसंगत हल X_{B}=\left[ x_{B_{1}}, x_{B_{2}}, x_{B_{3}}, \cdots, x_{B_{m}}\right] है।
Max.Z=CX
प्रतिबन्ध (s.t.) A X=b, X \geq 0
जहाँ A=\left(\alpha_{1}, \alpha_{2}, \alpha_{3}, \cdots, \alpha_{n}\right)
तथा आधारी मैट्रिक्स (Basis Matrix)

B=\left(\beta_{1}, \beta_{2}, \beta_{3}, \cdots, \beta_{m}\right) \\ \therefore B X_{B}=b \cdots(1)
अब माना कि \alpha_{j} \in A परन्तु \alpha_{j} \notin B तथा \alpha_{j} \neq \beta_{i}(i=1,2,3,\cdots,m)
चूँकि मैट्रिक्स के आधार \beta_{1}, \beta_{2} ,\beta_{3} , \cdots ,\beta_{m} बनाते हैं; इसलिए \alpha_{j} को \beta_{1}, \beta_{2} ,\beta_{3} , \cdots ,\beta_{m} के एकघात संचय में व्यक्त किया जा सकता है अर्थात्

\alpha_{j}=\sum_{i=1}^{k} \beta_{i} y_{i j}=\beta_{i} y_{1 j}+\beta_{2} y_{2j}+\beta_{3} y_{3j}+\cdots+\beta_{m} y_{m j} \ldots(2)
यदि y_{r j} \neq 0 तब हम \beta_{r} \in B को \alpha_{j} से प्रतिस्थापित कर सकते हैं तथा तब भी B आधारी मैट्रिक्स रहेगी।
मानलो कि y_{r j} \neq 0, तब (2) से:

\beta_{r}=\frac{1}{y_{rj}} \alpha_{j}-\frac{y_{1j}}{y_{rj}} \beta_{1}-\frac{y_{2j} }{y_{rj}} \beta_{2}- \cdots \cdot \frac{y_{(r-1)j}}{y_{rj}} \beta_{r+1}-\frac{y_{m i}}{y_{r j}} \beta_{m} \\ \Rightarrow B_{r}=\frac{1}{y_{rj}} \alpha_{j}-\sum_{i=1 \atop i \neq r}^{m}\left(\frac{y_{ij}}{y_{r j}}\right) \beta_{i} \cdots(3)
साथ ही B X_{B}=b \\ \Rightarrow \sum_{i=1}^{m} \beta_{i} X_{Bi} =b
पुनः (1) से

\left(\beta_{1}, \beta_{2}, \beta_{3}, \ldots \beta_{r},\ldots,\beta_{m}\right) \left[x_{B_{1}},x_{B_{2}},x_{B_{3}} \ldots x_{B_{m}}\right]=b \\ \Rightarrow \beta_{1} x_{B_{1}}+\beta_{2} x_{B_{2}}+\ldots+\beta_{r} x_{B_{r}}+\ldots+\beta_{m}x_{B_{m}}=b \\ \Rightarrow \sum_{i=1 \atop i \neq r} \beta_{i} x_{B_{i}}+ \beta_{r}x_{B_{r}}=b \ldots(4)
का मान (3) से (4) में प्रतिस्थापित करने पर:

\sum_{i=1 \atop i \neq 1}^{m} \beta_{i} x_{B_{i}}+x_{B_{r}}\left[\frac{1}{y_{r j}} \alpha_{j}-\sum_{i=1 \atop i \neq r}^{m} \frac{y_{ij}}{y_{r j}}\right] \beta_{i}=b \\ \sum_{i=1 \atop i \neq r }^{m}\left(x_{B_{i}}-x_{B_{r}} \frac{y_{ij}}{y_{r j}}\right) \beta_{i}+\frac{x_{B_{r}}}{y_{rj}} \alpha_{j}=b \cdots(5)
(5) को (4) से तुलना करने पर AX=b का नया आधारी हल निम्न होगा:

x_{B}^{\prime}=\left[x_{B_{1}}^{\prime}, x^{\prime}_{B_{2}}, x^{\prime}_{B_{3}}, \ldots x^{\prime}_{B_{m}}\right]
जहाँ x_{B_{i}}^{\prime}=x_{B_{i}}-x_{B_{r}} \frac{y_{i j}}{y_{rj}}, i=1,2,3,\ldots, m ; i \neq r
तथा x_{B_{r}}^{\prime}=\frac{y_{B_{r}}}{y_{rj}} ; i=r के लिए …….(6)
आधारी सुसंगत हल होंगे यदि

x_{B_{i}}-x_{B_{r}} \quad \frac{y_{ij}}{y_{r j}} \geq 0,(i=1,2,3,\cdots m,i \neq r) \cdots(7)
तथा \frac{x_{B_{r}}}{y_{r j}} \geq 0,i=r के लिए   ……..(8)
चूँकि X_{B}, रैखिक प्रोग्रामन समस्या का आधारी सुसंगत हल है,इसलिए x_{B_{i}} \geq 0, i=1,2,3 \ldots m
फलतः (7) तथा (8) सन्तुष्ट केवल तभी होंगे जबकि यदि y_{r j}>0 तथा y_{ij} \leq 0(i \neq r,i=1,2,3,.....,m)
यदि y_{r j}>0 तथा y_{ij}>0 तब (7) व (8) सन्तुष्ट केवल तभी होंगे यदि

\frac{x_{B_{i}}}{y_{i j}}-\frac{x_{B_{r}}}{y_{rj} } \geq 0\\ \Rightarrow \frac{x_{B_{r}}}{y_{r j}} \leq \frac{x_{B_{i}}}{y_{i j}} \\ \Rightarrow \frac{x_{B_{r}}}{y_{r j}}=\min _{i}\left[\frac{x_{B_{i}}}{y_{ij}}, y_{i j}>0 \right]
फलतः यदि हम r को इस प्रकार चुने कि

\frac{x_{B_{r}}}{y_{rj}}=\min_{i} \left[\frac{x_{B_{i}}}{y_{i j}}, y_{i j}>0\right]=v \cdots(9)
तब आधारी मैट्रिक्स B का स्तम्भ \beta_{r} हट जायेगा तथा इसके स्थान पर \alpha_{j} प्रतिस्थापित हो जायेगा,अतः नया आधारी हल सुसंगत होगा।
समीकरण (9) के अनुसार यदि r=0 जो कि सम्भव तभी होगा यदि x_{B_{r}}=0 इस स्थिति में आधारी सुसंगत हल अपभ्रष्ट आधारी हल होगा।
Z^{\prime} \geq Z सिद्ध करना
मूल आधारी सुसंगत हल के लिए उद्देश्य फलन का मान

Z=C_{B} X_{B}=\left(C_{B_{1}}, C_{B_{2}}, C_{B_{3}}, \ldots, C_{B_{m}}\right)\left[x_{B_{1}},x_{B_{2}}, x_{B_{3}}, \ldots, x_{B_{m}}\right] \\ \Rightarrow Z=\sum_{i=1}^{m} C_{B_{i}} x_{B_{i}}
तब उद्देश्य फलन का नया मान

Z^{\prime}=\sum_{i=1}^{m} C^{\prime}_{B_{i}} x^{\prime}_{B_{i}} \\ =\sum_{i=1 \atop i \neq r}^{m} C^{\prime}_{B_{i}} x_{B_{i}}^{\prime}+C_{B_{r}}^{\prime} x_{B_{r}}
यह स्पष्ट है कि
C^{\prime}_{B_{i}}=C_{B_{i}}(i \neq r) तथा C^{\prime}_{B_{r}}=C_{j} \\ Z^{\prime}=\sum_{i=1 \atop i \neq r }^{m} C_{B_{i}}^{\prime}\left(x^{\prime}_{B_{i}}-\frac{y_{i j}}{y_{rj}} x_{B_{r}}\right)+C^{\prime}_{B_{r}} \frac{y_{i j}}{y_{r j}}[(6) से]

=\sum_{i=1 \atop i \neq r}^{m} C_{B_{i}}^{\prime}\left(x_{B_{i}}-\frac{y_{i j}}{y_{r j}} x_{B_{r}}\right) +c_{j} \frac{x_{B_{r}}}{y_{rj}}\\  =\sum_{i=1}^{m} C_{B_{i}}\left(x_{B_{i}}-\frac{y_{ij}}{y_{rj}} x_{B_{r}}\right)+c_{j} \frac{x_{B_{r}}}{y_{rj}}
[चूँकि C_{B_{i}}\left(x_{B_{i}}-\frac{y_{ij}}{y_{rj}} x_{B_{r}}\right)=0 जब i=r]

=\sum_{i=1}^{m} C_{B_{i}} x_{B_{i}}-\frac{x_{B_{r}}}{y_{rj}} \sum_{i=1}^{m} C_{B_{i}} y_{i j}+\frac{x_{B_{r}}}{y_{rj}} C_{j} \\ =Z-\frac{x_{B_{r}}}{y_{rj}} \sum_{i=1}^{m} C_{B_{i}} y_{i j}+\frac{x_{B_{r}}}{y_{rj}} C_{j} \\ =Z+\frac{x_{B_{r}}}{y_{r j}}\left(C_{j}-Z_{j}\right) जहाँ Z_{j}=\sum_{i=1}^{m} C_{B_{i}} y_{i j}=C_{B} y_{1}
[Z_{j} मूल B.F.S. के संगत है]
\Rightarrow Z^{\prime}=Z+v\left(C_{j}-Z_{j}\right) जहाँ v=\frac{x_{B_{r}}}{y_{rj}}
अतः उद्देश्य फलन का नवीन मान=उद्देश्य फलन का प्रारम्भिक मान+v\left(C_{j}-Z_{j}\right)
अब Z^{\prime} \geq Z  यदि v\left(C_{j}-Z_{j}\right) \geq 0
चूँकि v \geq 0
Z^{\prime} \geq Z केवल यदि \left(C_{j}-Z_{j}\right)>0 या \left(Z_{j}-C_{j}\right)<0
अतः यदि \left(C_{j}-Z_{j}\right)<0 तथा कम से कम एक y_{ij}>0

तो हमें एक नया आधारी हल प्राप्त होता है जिसके लिए Z^{\prime} \geq Z
यदि प्रारम्भिक आधारी सुसंगत हल अनपभ्रष्ट था तो v>0 तथा इस स्थिति में Z’>Z अतः प्रमेय सिद्ध हो गई।
(2.)इष्टतम की कसौटी (Optimality Criterion):
प्रमेय (Theorem):4.यदि रैखिक प्रोग्रामन के किसी आधारी सुसंगत हल X_{B} अर्थात् सिम्पलैक्स फलन के किसी पुनरावृत्ति,पर मैट्रिक्स A के आधारीतर सदिशों के लिए \left(Z_{j}-C_{j}\right)>0 तब X_{B} एक इष्टतम हल होता है।
(If for any basic feasible solution X_{B} of a L.P.P. i.e. at any iteration of simplex algorithm \left(Z_{j}-C_{j}\right)>0 of A,then X_{B}  an optimal solution.)
उपपत्ति (Proof):माना सिम्पलैक्स कलन के लिए किसी पुनरावृत्ति (iteration) रैखिक प्रोग्रामन समस्या का X_{B} एक आधारी सुसंगत हल है तथा B इसके संगत आधारी मैट्रिक्स है तब
B X_{B}=b \cdots(1) \\ \Rightarrow X_{B}=B^{-1} b तथा B=\left(\beta_{1}, \beta_{2},\ldots, \beta_{m}\right)
जहाँ X_{B}=\left(x_{B_{1}}, x_{B_{2}},x_{B_{3}},\ldots, x_{B_{m}}\right)
तथा उद्देश्य फलन इस हल के लिए माना Z^{*} है तब

Z^{*}=C_{B} X_{B}=\sum_{i=1}^{m} C_{B_{i}} x_{B_{i}} \cdots(2)
माना कि उद्देश्य फलन किसी दत्त समस्या का सुसंगत हल X^{\prime}=\left(x_{1}^{\prime},x_{2}^{\prime},\cdots,x_{n}^{\prime}\right) के लिए Z^{\prime}=C X^{\prime}=\sum_{i=1}^{n+m} C_{i} x_{i}^{\prime} \cdots(3)
तथा A X^{\prime}=b, X^{\prime} \geq 0 \cdots(4)
अब हम सिद्ध करेंगे Z^{*} \geq Z^{\prime}
(1) तथा (3) से:

X_{B}=B^{-1} b=B^{-1}\left(A X^{\prime}\right)=\left(B^{-1} A\right) X^{\prime}=Y X^{\prime}
जहाँ y=\left(y_{1}, y_{2}, y_{3}, \ldots, y_{m+n}\right) \\ X_{B}=Y X^{\prime}=\left(y_{1}, y_{2}, y_{3}, \ldots,y_{m+n} \right) \left(x_{1}^{\prime}, x_{2}^{\prime},\ldots,x_{m}^{\prime}\right) \\ \Rightarrow \left[\begin{array}{c} x_{B_{1}} \\ x_{B_{2}} \\ x_{B_{3}} \\ \cdot \\ \cdot \\ x_{B_{m}} \end{array}\right] = \begin{bmatrix} y_{11} & y_{12} & y_{13} & \ldots & y_{1j} & \ldots & y_{1,m+n}\\ y_{21} & y_{22} & y_{23} & \ldots & y_{2j} & \ldots & y_{2,m+n}\\ y_{31} & y_{32} & y_{33} & \ldots & y_{3j} & \ldots & y_{3,m+n} \\ \ldots & \ldots & \ldots & \ldots & \ldots & \ldots & \ldots \\ \ldots & \ldots & \ldots & \ldots & \ldots & \ldots & \ldots \\ y_{m1} & y_{m2} & y_{m3} & \ldots & y_{mj} & \ldots & y_{m,m+n} \end{bmatrix} \left[\begin{array}{c} x_{1}^{\prime} \\ x_{2}^{\prime} \\ x_{3}^{\prime} \\ \cdot \\ \cdot \\ x_{m+n}^{\prime} \end{array}\right] \\ \Rightarrow \left[\begin{array}{c} x_{B_{1}} \\ x_{B_{2}} \\ x_{B_{3}} \\ \cdot \\ \cdot \\ x_{B_{m}} \end{array}\right]=\begin{bmatrix} y_{11}x^{\prime}_{1}+y_{12}x^{\prime}_{2}+ y_{1,m+n} x^{\prime}_{m+n} \\ y_{21}x^{\prime}_{1}+y_{22}x^{\prime}_{2}+y_{2,m+n}x^{\prime}_{m+n}\\ y_{31}x^{\prime}_{1} + y_{32}x^{\prime}_{2} +  y_{3,m+n}x^{\prime}_{m+n} \\ \ldots \ldots \ldots \ldots \ldots \ldots \ldots \ldots \\ \ldots \ldots \ldots \ldots \ldots \ldots \ldots \ldots \\ y_{m1}x^{\prime}_{1}+ y_{m2}x^{\prime}_{2}+ y_{m,m+n}x^{\prime}_{m+n} \end{bmatrix}
दोनों पक्षों के i वें घटकों को बराबर रखने पर:

x_{B_{i}}=\sum_{j=1}^{n+m} y_{i j} x_{j}^{\prime}
परन्तु यह दिया हुआ है कि प्रत्येक j के लिए \alpha_{j} \in A, \alpha_{j} \notin B के लिए Z_{j}-C_{j} \geq 0
अब यदि \alpha_{j}=\beta_{j} तथा \alpha_{j} \in \beta प्रत्येक j के लिए
\alpha_{j}=\beta_{i}=0 \cdot \beta_{1}+0 \cdot \beta_{2}+\cdots+0 \cdot \beta_{i-1}+1 \cdot \beta_{i}+0 \cdot \beta_{i+1}+\cdots+0 \cdot \beta_{m} \\ =\left(\beta_{1}, \beta_{2}, \beta_{3} \ldots, \beta_{i}, \ldots \beta_{m}\right)[0,0,0, \ldots 1, \ldots 0] \\ =B_{e_{i}} [जहाँ e_{i} एक एकक मैट्रिक्स है जिसका iवां अवयव है]
चूँकि C_{j}=\beta_{i} \Rightarrow C_{j}=C_{B_{i}}
अर्थात् Z_{j}-C_{j}=C_{B} y_{j}-C_{j} \\ =C_{B_{e_{i}}} -C_{j}=C_{B_{e_{i}}}-C_{j}=C_{B_{i}}-C_{j}=0\left[C_{B_{i}}=C_{j}\right]
अतः उन j के लिए जिनके लिए \alpha_{j} \in B भी है Z_{j}-C_{j}=0
प्रत्येक j जिनके लिए \alpha_{j} \in A के लिए हम Z_{j}-C_{j}\geq 0 ले सकते हैं।

\Rightarrow Z_{j} \geq C_{j} \quad \forall_{j}, \alpha_{j} \in A
दोनों पक्षों को x_{j}^{\prime} से गुणा करने पर

Z_{j}x_{j}^{\prime} \geq C_{j}x_{j}^{\prime} \left[\because x_{j} \geq 0 \forall_{j} \right] \\ \sum_{j=1}^{m+n} Z_{j} x_{j}^{\prime} \geq \sum_{j=1}^{m+n} C_{j} x_{j}^{\prime} \\ \Rightarrow \sum_{j=1}^{m+n} x_{j}^{\prime} \left(\sum_{i=1}^{m} C_{B_{i}} y_{ij} \right) \geq Z^{\prime} \\ \Rightarrow \sum_{i=1}^{m} \mathrm{C}_{B _{i}} \left(\sum_{j=1}^{m+n} x^{\prime}_{j} y_{i j}\right) \geq Z^{\prime} \\ \Rightarrow \sum_{j=1}^{m} C_{B_{i}} x_{B_{i}} \geq Z^{\prime} \\ \Rightarrow Z^{*} \geq Z^{\prime}
जिससे यह प्रदर्शित होता है कि उद्देश्य फलन का अधिकतम मान Z^{*} है।जिससे प्रमेय सिद्ध हो जाता है।
(3.)अपरिबद्ध हल (Unbounded Solution):
प्रमेय (Theorem):5.यदि सिम्पलैक्स कलन में किसी पुनरावृत्ति पर कम से कम एक j के मान के लिए Z_{j}-C_{j}<0 प्राप्त होता है तथा साथ ही इस j के मान के लिए y_{ij} \leq 0 \quad \forall i=1,2,3,\cdots ,m तब उद्देश्य फलन को अधिकतम करना है तो समस्या का हल अपरिबद्ध होता है।
(If at any iteration of the simple algorithm, we get Z_{j}-C_{j}<0 for at least one j and for this j, y_{ij} \leq 0 \quad \forall i=1,2,3,\cdots ,m then if objective function is to be maximized the problem problem has an unbounded solution.)
उपपत्ति (Proof):माना कि सिम्पलैक्स कलन के लिए किसी पुनरावृत्ति (iteration) पर रैखिक प्रोग्रामन समस्या (L.P.P.) का x_{B}=\left[x_{B_{1}}, x_{B_{2}}, x_{B_{3}},\cdots,x_{B_{m}}\right] एक आधारी सुसंगत हल निम्न दत्त समस्या का है।
अधिकतम Z=CX प्रतिबन्ध AX=b, X \geq 0
जहाँ A=\left(\alpha_{1}, \alpha_{2}, \alpha_{3}, \ldots, \alpha_{m+n}\right) तथा साथ में आधार मैट्रिक्स B=\left(\beta_{1}, \beta_{2}, \beta_{3}, \ldots, \beta_{m}\right) के लिए B X_{B}=b या \sum_{j=1}^{m} X_{B_{i}} \cdot \beta_{i}=b \cdots(1)
तब उद्देश्य फलन का मान इस आधारी सुसंगत हल (B.F.S.) के लिए

Z=C_{B} X_{B}=\sum_{j=1}^{m} C_{B_{i}} X_{B_{i}} \cdots(2)
माना कि हम स्तम्भ \alpha_{j} को B में प्रवेश कराते हैं जहाँ \alpha_{j},A में हैं परन्तु B में नही तथा Z_{j}-C_{j}<0 तथा y_{ij} \leq 0, \forall i=1,2,\ldots ,m
माना \lambda एक अदिश है, यदि हम (1) में \lambda \alpha_{j} जोड़ें तथा घटाएं तब

\sum_{j=1}^{m} x_{B_{i}} \beta_{i}-\lambda \alpha_{j}+\lambda \alpha_{j}=b \ldots (3)
चूँकि A के आधार \beta_{1}, \beta_{2},\beta_{3},\ldots,\beta_{m} है इसलिए \alpha_{j} को इन सदिशों के एकघातत:संचय में व्यक्त किया जा सकता है।अर्थात्

\alpha_{j}=\sum_{i=1}^{m} \beta_{i} y_{i j} \\ \Rightarrow -\lambda \alpha_{j}=-\lambda \sum_{j=1}^{m} \beta_{i} y_{i j}
अब -\lambda \alpha_{j} का मान (3) में रखने पर:

\sum_{i=1}^{m} x_{B_{i}} \beta_{i}-\lambda \sum_{i=1}^{m} \beta_{i} y_{i j}+\lambda \alpha_{j}=b \\ \sum_{i=1}^{m} \left(x_{B_{i}}-\lambda y_{ij} \right) \beta_{i}+\lambda \alpha_{j}=b \cdots(4)
जब \lambda>0 तब x_{B i}-\lambda y_{i j} \geq 0 \\ [\because y_{ij} \leq 0, i=1,2,3, \cdots,m]
अतः समीकरण (4) दत्त समस्या का नवीन हल है जिसके चरों को x_{B_{i}}^{\prime} से व्यक्त करते हैं
\left.\begin{matrix} \text{ जहाँ } x_{B_{i}}^{\prime}=x_{B_{i}}-y_{i j}, i=1,2,3, \cdots, m \\ \text{ तथा } x^{\prime}_{m+1}=\lambda \end{matrix}\right\} \cdots(5)
चूँकि समस्त y_{ij} \leq 0 तब \lambda>0 x_{B_{i}}-\lambda y_{i j} \geq 0 इसलिए (5) एक सुसंगत हल है जिसमें धनात्मक चरों की संख्या \leq m+1 यह संख्या (m+1) से कम हो सकती है चूँकि i के किसी मान के लिए x_{B_{i}}-\lambda y_{i j} शून्य हो सकता है।यदि धनात्मक चरों की संख्या  इस हल x_{B_{i}} में m+1 के बराबर है जो कि m से अधिक है तब यह आधारोतर सुसंगत हल (Non Basis Solution) है
अब यदि इस नवीन हल के लिए उद्देश्य फलन का नवीन मान Z’ है तब

Z^{\prime}=\sum_{i=1}^{m} C_{B_{i}}\left(x_{B_{i}}-\lambda y_{ij}\right)+\lambda C_{j} \\ =\sum_{j=1}^{m} C_{B_{i}} x_{B_{i}}+\lambda\left(C_{j}-\sum_{i=1}^{m}C_{B_{i}} y_{i j}\right) \\ =Z+\lambda \left ( C_{j}-Z_{j} \right ) \\=Z-\lambda \left ( Z_{j}-C_{j} \right )
चूँकि Z_{j}-C_{j}<0 ,\lambda को पर्याप्त बड़े से बड़ा मान देकर हम Z’ के मान को जितना चाहें बड़ा बना सकते हैं।
अतः समस्या के उद्देश्य फलन का स्वेच्छा से अधिकतम किया जा सकता है इसलिए दत्त समस्या का हल अपरिबद्ध है।
आपको यह जानकारी रोचक व ज्ञानवर्धक लगे तो अपने मित्रों के साथ इस गणित के आर्टिकल को शेयर करें।यदि आप इस वेबसाइट पर पहली बार आए हैं तो वेबसाइट को फॉलो करें और ईमेल सब्सक्रिप्शन को भी फॉलो करें।जिससे नए आर्टिकल का नोटिफिकेशन आपको मिल सके ।यदि आर्टिकल पसन्द आए तो अपने मित्रों के साथ शेयर और लाईक करें जिससे वे भी लाभ उठाए ।आपकी कोई समस्या हो या कोई सुझाव देना चाहते हैं तो कमेंट करके बताएं।इस आर्टिकल को पूरा पढ़ें।

Also Read This Article:-Theory of Simplex Method

2.उन्नत आधारी सुसंगत हल के उदाहरण (Improved Basic Feasible Solution Examples):

Example:1.सिद्ध कीजिए कि निम्न निकाय के लिए सुसंगत हल x_{1}=1, x_{2}=0, x_{3}=1,Z=6 पर आधारी हल नहीं है
(Show that the feasible solution x_{1}=1, x_{2}=0, x_{3}=1,Z=6 to the following system is not basic):
न्यूनतम (Min.) Z=2x_{1}+3 x_{2}+4 x_{3}
प्रतिबन्ध (s.t.) x_{1}+x_{2}+x_{3}=2 \\ x_{1}-x_{2}+x_{3}=2 \\ x_{i} \geq 0, i=1,2,3
Solution:दिए गए निकाय को निम्न प्रकार लिख सकते हैं:

x_{1}+x_{2}+x_{3}+0 \cdot Z=2 \\ x_{1}-x_{2}+x_{3}+0 \cdot Z=2 \\ 2 x_{1}+3 x_{2}+4 x_{3}-1 Z=0
इस निकाय को मैट्रिक्स रूप में निम्न प्रकार भी लिख सकते हैं:

\begin{bmatrix}\alpha_{1} & \alpha_{2} & \alpha_{3} & \alpha_{4} \end{bmatrix}\left[ \begin{array}{l} x_{1} \\ x_{2} \\ x_{3} \\ x_{4} \end{array}\right]=\left[\begin{array}{l}2 \\ 2 \\0\end{array}\right]
या AX=b
जहाँ \alpha_{1}=\left[\begin{array}{c}1 \\1 \\2\end{array}\right],\alpha_{2}=\left[\begin{array}{c}1 \\-1 \\3\end{array} \right], \alpha_{3}=\left[\begin{array}{l}1 \\1 \\4\end{array}\right], \alpha_{4}= \left[\begin{array}{c}0 \\0 \\-1\end{array}\right]
तथा b=\left[\begin{array}{lll} 2 & 2 & 0\end{array}\right]
दिए हुए सुसंगत हल हैं:

x_{1}=1, x_{2}=0,x_{3}=1, Z=6
यहाँ n=4,m=3,n-m=1
यहाँ तीन चरों के मान अशून्य है,अतः यह आधारी सुसंगत हल होगा यदि शून्येत्तर चरों के सदिश अर्थात् \alpha_{1}, \alpha_{3}, \alpha_{4} एकघातत: स्वतन्त्र (L.I.) हो।माना \lambda_{1},\lambda_{2},\lambda_{3} ऐसी संख्याएँ विद्यमान हैं कि

\lambda_{1} \alpha_{1}+\lambda_{2} \alpha_{3}+\lambda_{3} \alpha_{4}=0 \\ \Rightarrow \lambda_{1} \left[\begin{array}{l} 1 \\1 \\2 \end{array}\right]+\lambda_{2}\left[\begin{array}{l}1 \\1 \\4\end{array}\right]+ \lambda_{3} \left[\begin{array}{c}0 \\0 \\-1\end{array}\right]=\left[\begin{array}{l}0 \\0 \\0\end{array}\right] \\ \Rightarrow\left[\begin{array}{l} \lambda_{1} +\lambda_{2} \\ \lambda_{1}+\lambda_{2} \\ 2 \lambda_{1}+4 \lambda_{2}-\lambda_{3} \end{array}\right]= \left[\begin{array}{l}0 \\0 \\0\end{array}\right] \\ \Rightarrow \lambda_{1}+\lambda_{2} =0 , \lambda_{1} +\lambda_{2}=0,2 \lambda_{1}+4 \lambda_{2}-\lambda_{3}=0 \\ \Rightarrow \frac{\lambda_{1}}{1}=\frac{\lambda_{2}}{-1}=\frac{\lambda_{3}}{-2}
माना \lambda_{1}=k तब \lambda_{2}=-k तथा \lambda_{3}=-2k
k को वास्तविक संख्या मानने पर हम अनन्त \lambda_{1},\lambda_{2}, \lambda_{3} ज्ञात कर सकते हैं यदि हम k=1 लें तब
\lambda_{1}=1, \lambda_{2}=-1, \lambda_{3}=-2 अर्थात् सदिश \lambda_{1}, \lambda_{3}, \lambda_{4} एकघातत: परतन्त्र हैं अतः दिया हुआ सुसंगत हल आधारी नहीं है।
Example:2.यदि निम्न रैखिक प्रोग्रामन समस्या का x_{1}=0, x_{2}=0, x_{3}=6, x_{4}=12 एक आधारी सुसंगत हल हो तो इसका उन्नत आधारी हल ज्ञात कीजिए।
(If x_{1}=0, x_{2}=0, x_{3}=6, x_{4}=12 is a B.F.S. of the L.P.P. find the new improved B.F.S. for
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 \\ 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
इसको L.P.P. के निम्न मानक रूप में व्यक्त कर सकते हैं।
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)(माना)

X=\left[\begin{array}{l}x_{1} \\x_{2} \\x_{3} \\x_{4}\end{array}\right], b=\left[\begin{array}{l}6 \\12\end{array}\right] , C=\left(\begin{array}{llll} 3 & 5 & 0 & 0\end{array}\right)
यदि X_{B} दिए हुए हल को व्यक्त करे तो

B X_{B}=b
जहाँ X_{B}=\left[\begin{array}{r}x_{3} \\x_{4}\end{array}\right]=\left[\begin{array}{l}6 \\12\end{array}\right]
तथा B=\left[\begin{array}{ll}1 & 0 \\0 & 1 \end{array}\right]=\left(\alpha_{3} \alpha_{4}\right)
तथा इसके उद्देश्य फलन का मान
Z=3(0)+5(0)=0
उन्नत आधारी हल हेतु \alpha_{1} तथा \alpha_{2},A में है परन्तु B में नहीं है।हमें \alpha_{1} तथा \alpha_{2} में से किसी एक सदिश का चयन करना है जिसके लिए हमें प्रारम्भ में y_{1} तथा y_{2} सदिश ऐसे ज्ञात करने होंगे जिनके लिए Z_{1}-C_{1} तथा Z_{2}-C_{2} मान ज्ञात किया जा सके,

y_{1} =B^{-1} \alpha_{1}=\left[\begin{array}{ll}1 & 0 \\0 & 1\end{array}\right]\left[\begin{array}{l}1 \\4\end{array} \right] =\left[\begin{array}{l}1 \\4\end{array}\right] \\ \Rightarrow y_{1} =\left[\begin{array}{l} y_{11} \\ y_{21}\end{array} \right] = \left[\begin{array}{l}1 \\4\end{array}\right] \\ y_{2}=B^{-1} \alpha_{2}=\left[\begin{array}{ll}1 & 0 \\0 & 1\end{array} \right] \left[\begin{array}{l} 2 \\3\end{array}\right]=\left[\begin{array}{l}2 \\3\end{array}\right] \\ \Rightarrow y_{2}= \left[\begin{array}{l} y_{12} \\y_{22}\end{array}\right]=\left[\begin{array}{l}2 \\3\end{array}\right]
चूँकि y_{11}>0 तथा y_{21}>0 इसलिए \alpha_{1} को B में निविष्ट (insert) कर सकते हैं तथा इसी प्रकार \alpha_{2} को B में निविष्ट कर सकते हैं।
अब Z_{1}-C_{1}=C_{B} y_{1}-C_{1} \\ \Rightarrow Z_{1}-C_{1}=(0 \quad 0)\left[\begin{array}{l}1 \\4\end{array} \right] -3=(0 \times 1+0 \times 4)-3=-3 \\ Z_{2}-C_{2}=C_{B} y_{2}-C_{2}=(0 \quad 0)\left[\begin{array}{l}2 \\3\end{array} \right]-5=(0 \times 2+0 \times 3)-5=-5
निम्नतम \left\{\left(Z_{1}-C_{1}\right),\left(Z_{2}-C_{2}\right)\right\}=निम्नतम {-3,-5}=-5
अतः j=2 के लिए Z_{j}-C_{j} निम्नतम है अतः \alpha_{2} प्रवेशी सदिश होगा।अपगामी सदिश ज्ञात करने हेतु
निम्नतम \left\{\frac{x_{B_{i}}}{y_{i 2}}, y_{i 2}>0\right\}=निम्नतम \left\{\frac{x_{B_{1}}}{y_{12}}, \frac{x_{B_{2}}}{y_{22}}\right\} \\ =\min \left\{\frac{6}{2}, \frac{12}{3}\right\} \\ =\min \{3,4\} \\ =3
i=1 के लिए अनुपात निम्नतम है।अतः B_{1} अपगामी सदिश (Departing Vector) है तो मुख्य अवयव (Key Element) y_{12} होगा और नवीन आधारी मैट्रिक्स तथा इसके संगत आधारी सुसंगत हल निम्न है

B=\left(\alpha_{2} \quad \alpha_{4}\right)=\left[\begin{array}{ll}2 & 0 \\3 & 1\end{array}\right] \\ X_{B}^{\prime} =B^{\prime^{-1}} b \\ \Rightarrow \left[\begin{array}{l}x_{2} \\x_{4}\end{array} \right]=\frac{1}{2}\left[\begin{array}{ll}1 & 0 \\-3 & 2\end{array}\right] \begin{bmatrix}6\\ 12\end{bmatrix}\\ =\frac{1}{2}\begin{bmatrix} 6+0\\ -18+24 \end{bmatrix} \\ \Rightarrow \left[\begin{array}{l}x_{2} \\x_{4}\end{array}\right]= \begin{bmatrix} 3 \\ 3 \end{bmatrix}
जो कि अपभ्रष्ट (degenerate) हल तथा इसके उद्देश्य फलन का मान
Z=3×3+5×3
Z=9+15=24
जिससे स्पष्ट है कि यह मान उद्देश्य फलन के पूर्व मान से अधिक है।
अतः x_{1}=0, x_{2}=3, x_{3}=0, x_{4}=3 नवीन उन्नत आधारी सुसंगत हल है।

Improved Basic Feasible Solution

Example:3.सिद्ध कीजिए कि निम्न रैखिक समस्या का इष्टतम आधारी सुसंगत हल x_{1}=0, x_{2}=3, x_{3}= 0 तथा x_{4}=3  नहीं है।
(Show that x_{1}=0, x_{2}=3, x_{3}=0,x_{4}=3 is not the optimal B.F.S. to 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.) 1 x_{1}+2 x_{2}+x_{3}+0 x_{4}=6 \\ 4 x_{1}+3 x_{2}+0 x_{3}+x_{4}=12

तथा (and) x_{1}, x_{2}, x_{3}, x_{4} \geq 0 
Solution: उपर्युक्त को मैट्रिक्स रूप में निम्न प्रकार लिख सकते हैं:
Max. Z=CX,s.t. AX=b, X \geq 0
जहाँ A=\left[\begin{array}{llll}1 & 2 & 3 & 0 \\4 & 3 & 0 & 1\end{array}\right]=\left(\alpha_{1} \quad \alpha_{2} \quad \alpha_{3} \quad \alpha_{4}\right) \\ b=\left[\begin{array}{l}6 \\12\end{array}\right], \quad X=\left[\begin{array}{l}x_{1} \\x_{2} \\x_{3} \\x_{3}\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(B_{1} \quad B_{2}\right)=\left(\alpha_{2} \quad \alpha_{4} \right)= \left[\begin{array}{ll}2 & 0 \\3 & 1\end{array}\right] \\ \Rightarrow B^{-1}=\frac{1}{2}\left[\begin{array}{rr}1 & 0 \\-3 & 2\end{array}\right] \\ C_{B}=(C_{B_{1}}, C_{B_{2}})=(5,0)
अब हम y_{1}, y_{2}, y_{3}, y_{4} के मान ज्ञात करते हैं:

y_{1}=B^{-1} \alpha_{1}=\frac{1}{2}\left[\begin{array}{cc}1 & 0 \\-3 & 2\end{array}\right]\left[\begin{array}{l}1 \\4\end{array} \right] \\=\frac{1}{2}\left[\begin{array}{c}1+0 \\-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}{cc}1 & 0 \\-3 & 2\end{array} \right]\left[\begin{array}{l}2 \\3\end{array}\right] \\=\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}{ll}1 & 0 \\-3 & 2\end{array}\right]\left[\begin{array}{l}3 \\0\end{array}\right] \\=\frac{1}{2}\left[\begin{array}{l}3+0 \\9+0\end{array} \right] =\left[\begin{array}{l}\frac{3}{2} \\\frac{9}{2}\end{array}\right] \\ y_{4}=B^{-1} \alpha_{4}=\frac{1}{2} \left[\begin{array}{ll}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]=\left[\begin{array}{l}0 \\1\end{array}\right] 
साथ ही Z_{1}-C_{1}=C_{B} y_{1}-C_{1}=(5 \quad 0)\left[\begin{array}{c} \frac{1}{2} \\ \frac{5}{2} \end{array}\right] -3=\frac{5}{2}-3 \\ \Rightarrow Z_{1}-C_{1}=-\frac{1}{2}\\ Z_{2}-C_{2}=C_{B} y_{2}-C_{2}=(5 \quad 0) \begin{bmatrix} 1\\0 \end{bmatrix}-5=(5 \times 1-0 \times 0)-5=0\\ Z_{3}-C_{3}=C_{B} y_{3}-C_{3}=(5 \quad 0)\left[\begin{array}{c}\frac{3}{2} \\\frac{9}{2}\end{array}\right]-0=\frac{15}{2}\\ Z_{4}-C_{4}=C_{B} y_{4}-C_{4}=(5 \quad 0)\left(\begin{array}{l}0 \\1\end{array}\right)-0=0

उपर्युक्त से स्पष्ट है कि j के Z_{j}-C_{j} \ngeqslant 0 है अतः सुसंगत हल इष्टतम हल(optional Solution) नहीं है।
उपर्युक्त उदाहरणों के द्वारा उन्नत आधारी सुसंगत हल (Improved Basic Feasible Solution) को समझ सकते हैं।

3.उन्नत आधारी सुसंगत हल के सवाल (Improved Basic Feasible Solution Questions):

Improved Basic Feasible Solution

(1.)रैखिक प्रोग्रामन समस्या
अधिकतम (Max.) Z=x_{1}+2 x_{2}
प्रतिबन्ध (s.t.) x_{1}+2 x_{2}+x_{3}=4\\ x_{1}+4 x_{2}+x_{4}=8
तथा x_{1}, x_{2}, x_{3}, x_{4} \geq 0
का आधारी सुसंगत हल x_{1}=x_{2}=0, x_{3}=4 तथा x_{4}=8 हो तो एक नवीन उन्नत आधारी हल ज्ञात कीजिए।
(Given the B.F.S. x_{1}=x_{2}=0, x_{3}=4,x_{4}=8 of the following L.P.P.

Max. Z=x_{1}+2 x_{2}  

s.t. x_{1}+2 x_{2}+x_{3}=4\\x_{1}+4x_{2}+x_{4}=8  and x_{1}, x_{2}, x_{3}, x_{4} \geq 0

obtain the new improved basic feasible solution.
(2.)सिद्ध कीजिए कि x_{1}=4, x_{2}=0, x_{3}=0 तथा x_{4}=4 निम्न रैखिक प्रोग्रामन समस्या का इष्टतम हल है
(Show that x_{1}=4, x_{2}=0, x_{3}=0, x_{4}=4 is the optimal B.F.S. to the L.P.P.)
उपर्युक्त सवालों को हल करने पर उन्नत आधारी सुसंगत हल (Improved Basic Feasible Solution) को ठीक से समझ सकते हैं।

Also Read This Article:-Basic Feasible Solution in LPP

4.उन्नत आधारी सुसंगत हल (Improved Basic Feasible Solution),उन्नत आधारी सुसंगत हल ज्ञात करना (To Determine Improved Basic Feasible Solution) के सम्बन्ध में अक्सर पूछे जाने वाले प्रश्न:

उन्नत आधारी सुसंगत हल (Improved Basic Feasible Solution) ज्ञात के लिए एक महत्त्वपूर्ण प्रमेय को
सिद्ध करेंगे जो कि हमें एक रैखिक प्रोग्रामन समस्या का आधारी सुसंगत हल से एक उन्नत आधारी सुसंगत
हल प्राप्त करने में सहायक होती है।