Solve Dual of LPP

Q: प्रश्न:1.द्वैती समस्या को हल करने में सर्वप्रथम क्या करते हैं? (What is the First Thing You Do in Solving the Duality Problem?):

उत्तर:किसी रैखिक प्रोग्रामन समस्या की द्वैती समस्या के संरूपण के लिए सर्वप्रथम समस्या को मानक रूप में व्यक्त करते हैं इसके पश्चात ही द्वैती समस्या का संरूपण करते हैं।

Q: प्रश्न:2.किसी आद्य समस्या का मैट्रिक्स रूप लिखो। (Write a Matrix Form of a Primal Problem):

उत्तर:यदि समस्या अधिकतमीकरण की है तो उसका मैट्रिक्स रूप निम्न प्रकार लिखा जा सकता है: अधिकतम करो: Z_p=\left(c_1 \quad c_2 \ldots \ldots \ldots c_n\right)\left[\begin{array}{l} x_1 \\ x_2 \\ \vdots \\ x_n \end{array}\right] प्रतिबन्ध \left[\begin{array}{cccc} a_{11} & a_{12} & \cdots & a_{1 n} \\ a_{21} & a_{22} & \cdots & a_{2 n} \\ \vdots & \vdots & \vdots \\ a_{m 1} & a_{n 2} & \cdots & a_{m n} \end{array}\right]\left[\begin{array}{c} x_1 \\ x_2 \\ \vdots \\ x_n \end{array}\right] \leq\left[\begin{array}{c} b_1 \\ b_2 \\ \vdots \\ b_n \end{array}\right] तथा x_1, x_2, \ldots, x_n \geq 0 इस समस्या को संक्षिप्त रूप में निम्न प्रकार से व्यक्त कर सकते हैं: अधिकतम करो: Z_p=C X प्रतिबन्ध A X \leq b \\ X \geq 0

Mathematics Satyam May 19, 2024 Linear Programming No Comments

Contents hide

1 1.रैखिक प्रोग्रामन समस्या की द्वैती समस्या को हल करो (Solve Dual of LPP),रैखिक प्रोग्रामन समस्याओं को द्वैत सिद्धान्त के प्रयोग से हल कीजिए (Use Duality to Solve LPP):

1.1 2.रैखिक प्रोग्रामन समस्या की द्वैती समस्या को हल करो पर आधारित उदाहरण (Examples Based on Solve Dual of LPP):

1.1.1 3.रैखिक प्रोग्रामन समस्या की द्वैती समस्या को हल करो (Frequently Asked Questions Related to Solve Dual of LPP),रैखिक प्रोग्रामन समस्याओं को द्वैत सिद्धान्त के प्रयोग से हल कीजिए (Use Duality to Solve LPP) से सम्बन्धित अक्सर पूछे जाने वाले प्रश्न:

1.1.2 प्रश्न:1.द्वैती समस्या को हल करने में सर्वप्रथम क्या करते हैं? (What is the First Thing You Do in Solving the Duality Problem?):

1.1.3 प्रश्न:2.किसी आद्य समस्या का मैट्रिक्स रूप लिखो। (Write a Matrix Form of a Primal Problem):

1.1.4 प्रश्न:3.सिद्ध करो कि किसी आद्य समस्या का हल अपरिबद्ध हो तो उसकी द्वैती समस्या का हल या तो अपरिबद्ध होगा अथवा कोई हल नहीं होगा। (Prove that if the primal problem has unbounded solution then dual has either no solution or an unbounded solution):

1.1.4.1 Solve Dual of LPP

2 रैखिक प्रोग्रामन समस्या की द्वैती समस्या को हल करो (Solve Dual of LPP)

2.1 Solve Dual of LPP

1.रैखिक प्रोग्रामन समस्या की द्वैती समस्या को हल करो (Solve Dual of LPP),रैखिक प्रोग्रामन समस्याओं को द्वैत सिद्धान्त के प्रयोग से हल कीजिए (Use Duality to Solve LPP):

Solve Dual of LPP

रैखिक प्रोग्रामन समस्या की द्वैती समस्या को हल करो (Solve Dual of LPP) के इस आर्टिकल में रैखिक प्रोग्रामन समस्याओं को द्वैत सिद्धान्त से कुछ सवालों को हल करके समझने का प्रयास करेंगे।
आपको यह जानकारी रोचक व ज्ञानवर्धक लगे तो अपने मित्रों के साथ इस गणित के आर्टिकल को शेयर करें।यदि आप इस वेबसाइट पर पहली बार आए हैं तो वेबसाइट को फॉलो करें और ईमेल सब्सक्रिप्शन को भी फॉलो करें।जिससे नए आर्टिकल का नोटिफिकेशन आपको मिल सके।यदि आर्टिकल पसन्द आए तो अपने मित्रों के साथ शेयर और लाईक करें जिससे वे भी लाभ उठाए।आपकी कोई समस्या हो या कोई सुझाव देना चाहते हैं तो कमेंट करके बताएं।इस आर्टिकल को पूरा पढ़ें।

Also Read This Article:- How to Use Duality to Solve LPP?

2.रैखिक प्रोग्रामन समस्या की द्वैती समस्या को हल करो पर आधारित उदाहरण (Examples Based on Solve Dual of LPP):

निम्न रैखिक प्रोग्रामन समस्याओं को उनकी द्वैत सिद्धान्त के प्रयोग से हल कीजिए:
(Use duality to solve the following LPP’s)
Example:7.निम्नतम करो (min.): $Z=10x_1+6x_2+2x_3$
प्रतिबन्ध (s.t.) $-x_1+x_2+x_3 \geq 1 \\ 3 x_1+x_2-x_3 \geq 2$
तथा (and) $x_1, x_2, x_3 \geq 0$
Solution:दी गई आद्य समस्या मानक रूप में है,अतः इसकी द्वैती निम्न प्रकार होगी:
अधिकतम करो: $Z_D=w_1+2 w_2$
प्रतिबन्ध $-w_1+3 w_2 \leq 10 \\ w_1+w_2 \leq 6 \\ w_1-w_2 \leq 2$
तथा $w_1, w_2 \geq 0$
प्रतिबन्ध को समीकरणों में परिवर्तन करने हेतु न्यूनतापूरक चरों $w_3,w_4,w_5$ का समावेश करने पर उपर्युक्त द्वैत समस्या निम्नांकित है:
अधिकतम करोः $Z_D=w_1+2 w_2+0 w_3+0 w_4+0 w_5$
प्रतिबन्ध $-w_1+3 w_2+w_3+0 w_4+0 w_5=10 \\ w_1+w_2+0 w_3+w_4+0 w_5=6 \\ w_1-w_2+0 w_3+0 w_4+w_5=2$
तथा $w_1, w_2, w_3, w_4, w_5 \geq 0$
अतः प्रतिबन्ध निकाय में गुणांक मैट्रिक्स
$A=\left[\begin{array}{ccccc} -1 & 3 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 \\ 1 & -1 & 0 & 0 & 1 \end{array}\right]= \left(\alpha_1 \alpha_2 \alpha_3 \alpha_4 \alpha_5\right)$ (माना)
प्रारम्भिक आधार $B=\left( \alpha_3 \alpha_4 \alpha_5\right)=I_3$ लेने पर,प्रारम्भिक सिम्पलेक्स सारणी निम्न प्रकार है:
प्रथम सिम्पलेक्स सारणी

$\begin{array}{|ccc|c|ccccc|} \hline & & & C_{i} \rightarrow & 1 & 2 & 0 & 0 & 0 \\ \hline C_{B} & B & X_B & b & y_1 & y_2 & y_3 & y_4 & y_5 \\ \hline 0 & \alpha_3 & w_3 & 10 & -1 & \fbox{3} & 1 & 0 & 0 \\ 0 & \alpha_4 & w_4 & 6 & 1 & 1 & 0 & 1 & 0 \\ 0 & \alpha_5 & w_5 & 2 & 1 & -1 & 0 & 0 & 1 \\ \hline & & & Z_{j}-C_{j}\rightarrow & -1 & -2 & 0 & 0 & 0 \\ \hline & & & & & \uparrow & \downarrow & & \end{array}$
अतः प्रथम सिम्पलेक्स सारणी से स्पष्ट है कि प्रारम्भिक आधार इष्टतम हल नहीं है,क्योंकि $Z_j-C_j$ के मान ऋणात्मक हैं i.e. $Z_2-C_2=-2$ जो कि न्यूनतम राशि है तथा यह मान द्वितीय स्तम्भ में है,इसलिए $\alpha_2$ प्रवेशी सदिश है।
पुनः $\underset{i}{\text{निम्नतम}}\left\{\frac{w_{B i}}{y_{i 1}}, y_{i 1}>0\right\}=\underset{i}{\text{निम्नतम}}\left\{\frac{10}{3},\frac{6}{7} \right\} \\ =\frac{10}{3} =\frac{W_{B1}}{y_{12}}$

अतः $y_{12}$ अर्थात् 3 मुख्य अवयव (key element) तथा $\alpha_3$ अपगामी सदिश (departing vector) होगा।अब सामान्य रूपान्तरणों से नवीन सारणी निम्न प्रकार होगी:
प्रथम पंक्ति (मुख्य अवयव वाली पंक्ति) (working rule):
प्रथम पंक्ति मुख्य अवयव वाली पंक्ति है।अतः इसे तैयार करने हेतु प्रथम सारणी की प्रथम पंक्ति के प्रत्येक अवयव में मुख्य अवयव 3 का भाग देने पर द्वितीय सारणी की प्रथम पंक्ति तैयार होगी:

$\frac{10}{3},-\frac{1}{3}, \frac{3}{3}=1, \frac{1}{3}, \frac{0}{3}=0, \frac{0}{3}=0$
द्वितीय पंक्ति:द्वितीय सारणी की द्वितीय पंक्ति को तैयार करने के लिए प्रथम सारणी की द्वितीय पंक्ति के प्रत्येक अवयव में से मुख्य अवयव वाली पंक्ति के अवयवों अर्थात् उपर्युक्त अवयवों को मुख्य अवयव के संगत अवयव 1 से गुणा करके घटा देंगे:
$6-\frac{10}{3} \times 1=\frac{8}{3}, 1-\left(-\frac{1}{3}\right) \times 1=\frac{4}{3}, 1-1 \times 1=0,0-\frac{1}{3} \times 1=-\frac{1}{3}, 1-0 \times 1=1,0-0 \times 1=0$
तृतीय पंक्ति:द्वितीय सारणी की तृतीय पंक्ति को तैयार करने के लिए प्रथम सारणी की तृतीय पंक्ति के प्रत्येक अवयव में से मुख्य अवयव वाली पंक्ति के अवयवों को मुख्य अवयव के संगत अवयव -1 से गुणा करके घटा देंगे:
$2-\frac{10}{3} \times -1=\frac{16}{3}, 1-\left(-\frac{1}{3}\right) \times -1=\frac{2}{3},-1-1 \times -1=0 ,0-\frac{1}{3}(-1)=\frac{1}{3}, 0-0 \times-1=0,1-0 \times-1=1$
द्वितीय सिम्पलेक्स सारणी

$\begin{array}{|ccc|c|ccccc|} \hline & & & C_{i} \rightarrow & 1 & 2 & 0 & 0 & 0 \\ \hline C_{B} & B & X_B & b & y_1 & y_2 & y_3 & y_4 & y_5 \\ \hline 2 & \alpha_2 & w_2 & \frac{10}{3} & -\frac{1}{3} & 1 & \frac{1}{3} & 0 & 0 \\ 0 & \alpha_4 & w_4 & \frac{8}{3} & \frac{\fbox{4}}{\fbox{3}} & 0 & -\frac{1}{3} & 1 & 0\\ 0 & \alpha_5 & w_5 & \frac{16}{3} & \frac{2}{3} & 0 & \frac{1}{3} & 0 & 1 \\ \hline & & & Z_{j}-C_{j}\rightarrow & -\frac{5}{3} & 0 & \frac{2}{3} & 0 & 0\\ \hline & & & & \uparrow & & & \downarrow & \end{array}$
अतः द्वितीय सिम्पलेक्स सारणी से स्पष्ट है कि प्रारम्भिक आधार इष्टतम हल नहीं है,क्योंकि $Z_j-C_j$ के मान ऋणात्मक है i.e. $Z_1-C_1=-\frac{5}{3}$ जो कि न्यूनतम राशि है तथा यह मान प्रथम स्तम्भ में है,इसलिए $\alpha_1$ प्रवेशी सदिश है।
पुनः $\underset{i}{\text{निम्नतम}}\left\{\frac{w_{B i}}{y_{i 1}}, y_{i 1}>0\right\}=\underset{i}{\text{निम्नतम}}\left\{ \frac{\frac{8}{3}}{\frac{4}{3}},\frac{\frac{16}{3}}{\frac{2}{3}} \right\} \\ =\frac{\frac{8}{3}}{\frac{4}{3}} =\frac{W_{B2}}{y_{21}}$
अतः $y_{21}$ अर्थात् $\frac{4}{3}$ मुख्य अवयव (key element) तथा $\alpha_4$ अपगामी सदिश (departing vector) होगा।अब सामान्य रूपान्तरणों से नवीन सारणी निम्न प्रकार होगी:
द्वितीय पंक्ति (मुख्य अवयव वाली पंक्ति) (working rule):
द्वितीय सारणी की द्वितीय पंक्ति मुख्य अवयव वाली पंक्ति है।अतः तृतीय सारणी की द्वितीय पंक्ति तैयार करने हेतु द्वितीय सारणी की द्वितीय पंक्ति के प्रत्येक अवयव में मुख्य अवयव $\frac{4}{3}$ का भाग देंगे।

$\frac{\frac{8}{3}}{\frac{4}{3}}=2, \frac{\frac{4}{3}}{\frac{4}{3}}=1, \frac{0}{\frac{4}{3}}=0, \frac{-\frac{1}{3}}{\frac{4}{3}}=-\frac{1}{4}, \frac{1}{\frac{4}{3}}=\frac{3}{4}, \frac{0}{\frac{4}{3}}=0$
प्रथम पंक्ति:तृतीय सारणी के लिए प्रथम पंक्ति तैयार करने हेतु द्वितीय सारणी की प्रथम पंक्ति के अवयवों में से मुख्य अवयव वाली पंक्ति के प्रत्येक अवयव अर्थात् उपर्युक्त अवयवों को मुख्य अवयव के संगत अवयव $-\frac{1}{3}$ से गुणा करके घटा देंगे।

$\frac{10}{3}-2 \times\left(-\frac{1}{3}\right)=4,-\frac{1}{3}-1 \times\left(-\frac{1}{3}\right)=0, 1-0 \times\left(-\frac{1}{3}\right)=1, \frac{1}{3}-\left(-\frac{1}{4}\right)\left(-\frac{1}{3}\right)=\frac{1}{4}, 0-\frac{3}{4} x-\frac{1}{3}=\frac{1}{4}, 0-0 \times-\frac{1}{3}=0$
तृतीय पंक्ति:तृतीय सारणी के लिए तृतीय पंक्ति तैयार करने हेतु द्वितीय सारणी की तृतीय पंक्ति के अवयवों में से मुख्य अवयव वाली पंक्ति के प्रत्येक अवयव को मुख्य अवयव के संगत अवयव $\frac{2}{3}$ से गुणा करके घटा देंगे।

$\frac{16}{3}-2 \times \frac{2}{3}=4, \frac{2}{3}-1 \times \frac{2}{3}=0,0-0 \times \frac{2}{3}=0,\frac{1}{3}-\left(-\frac{1}{4}\right) \times \frac{2}{3}=\frac{1}{2}, 0-\frac{3}{4} \times \frac{2}{3}=\frac{-1}{2}, 1-0 \times \frac{2}{3}=1$
तृतीय सिम्पलेक्स सारणी

$\begin{array}{|ccc|c|ccccc|} \hline & & & C_{i} \rightarrow & 1 & 2 & 0 & 0 & 0 \\ \hline C_{B} & B & X_B & b & y_1 & y_2 & y_3 & y_4 & y_5 \\ \hline 2 & \alpha_2 & w_2 & 4 & 0 & 1 & \frac{1}{4} & \frac{1}{4} & 0 \\ 1 & \alpha_1 & w_1 & 2 & 1 & 0 & -\frac{1}{4} & \frac{3}{4} & 0 \\ 0 & \alpha_5 & w_5 & 4 & 0 & 0 & \frac{1}{2} & -\frac{1}{2} & 1 \\ \hline & & & Z_{j}-C_{j}\rightarrow & 0 & 0 & \frac{1}{4} & \frac{5}{4} & 0\\ \hline \end{array}$
चूँकि इस सारणी में $Z_j-C_j \geq 0$ ,j के सभी मानों के लिए,अतः इसका आधारी हल परिवर्तित समस्या का इष्टतम हल होगा:

$w_1=2, w_2=4$
अतः द्वैती समस्या का इष्टतम हलः

$w_1=2, w_2=4$
तथा अधिकतम $Z_D=w_1+2 w_2=2+2 \times 4=10 \\ \Rightarrow \max. Z_D=10$
तथा $x_1=z_3-c_3=\frac{1}{4}, x_2=z_4-c_4=\frac{5}{4} ,x_3=z_5-c_5=0$
न्यूनतम Z=10
Example:8.निम्नतम करो (mini.) $Z=2 x_1+2 x_2+4 x_3$
प्रतिबन्ध (s.t.) $2 x_1+3 x_2+5 x_3 \geq 2 \\ 3 x_1+x_2+7 x_3 \leq 3 \\ x_1+4 x_2+6 x_3 \leq 5$
तथा (and) $x_1, x_2, x_3 \geq 0$
Solution:आद्य समस्या मानक रूप में नहीं है,इसलिए सर्वप्रथम इस आद्य समस्या को मानक रूप में निम्न प्रकार लिखते हैं:
निम्नतम करो: $Z=2 x_1+2 x_2+4 x_3$
प्रतिबन्ध $2 x_1+3 x_2+5 x_3 \geq 2 \\ -3 x_1-x_2-7 x_3 \geq -3 \\ -x_1-4 x_2-6 x_3 \geq -5$
तथा $x_1, x_2, x_3 \geq 0$
अब यह समस्या अपने मानक रूप में है।इसकी द्वैती समस्या निम्न प्रकार होगी:
अधिकतम करो: $Z_D=2 w_1-3 w_2-5 w_3$
प्रतिबन्ध $2 w_1-3 w_2-w_3 \leq 2 \\ 3 w_1-w_2-4 w_3 \leq 2 \\ 5 w_1-7 w_2-6 w_3 \leq 4$
तथा $w_1, w_2, w_3 \geq 0$
इसे सिम्पलेक्स विधि से हल करने के लिए प्रतिबन्ध निकाय को समीकरणों में बदलना होगा।अतः $w_4,w_5$ तथा $w_6$ न्यूनतापूरक चर सम्मिलित करते हुए उपर्युक्त द्वैत समस्या निम्न प्रकार है:
अधिकतम करो: $Z_D=2 w_1-3 w_2-5 w_3+0 w_4+0 w_5+0 w_6$
प्रतिबन्ध $2 w_1-3 w_2-w_3+w_4+0 w_5+0 w_6=2 \\ 3 w_1-w_2-4 w_3+0 w_1+w_5+0 w_6=2 \\ 5 w_1-7 w_2-6 w_3+0 w_4+0 w_5+w_6=4$
तथा $w_1, w_2, w_3, w_4, w_5, w_6 \geq 0$
अब प्रतिबन्ध निकाय में गुणांक मैट्रिक्स
$A=\left[\begin{array}{cccccc} 2 & -3 & -1 & 1 & 0 & 0 \\ 3 & -1 & -4 & 0 & 1 & 0 \\ 5 & -7 & -6 & 0 & 0 & 1 \end{array}\right]= \left(\alpha_1 \alpha_2 \alpha_3 \alpha_4 \alpha_5 \alpha_6\right)$ (माना)
प्रारम्भिक आधार $B=\left( \alpha_4 \alpha_5 \alpha_6\right)=I_3$ लेने पर,प्रारम्भिक सिम्पलेक्स सारणी निम्न प्रकार है:
प्रथम सिम्पलेक्स सारणी

$\begin{array}{|ccc|c|cccccc|} \hline & & & C_{i} \rightarrow & 2 & -3 & -5 & 0 & 0 & 0 \\ \hline C_{B} & B & X_B & b & y_1 & y_2 & y_3 & y_4 & y_5 & y_6 \\ \hline 0 & \alpha_4 & w_4 & 2 & 2 & -3 & -1 & 1 & 0 & 0 \\ 0 & \alpha_5 & w_5 & 2 & \fbox{3} & -1 & -4 & 0 & 1 & 0 \\ 0 & \alpha_6 & w_6 & 4 & 5 & -7 & -6 & 0 & 0 & 1 \\ \hline & & & Z_{j}-C_{j}\rightarrow & -2 & 3 & 5 & 0 & 0 & 0 \\ \hline & & & & \uparrow & & & & \downarrow & \end{array}$
अतः प्रथम सिम्पलेक्स सारणी से स्पष्ट है कि प्रारम्भिक आधार इष्टतम हल नहीं है,क्योंकि $Z_j-C_j$ के मान ऋणात्मक है i.e. $Z_1-C_1=-2$ जो कि न्यूनतम राशि है तथा यह मान प्रथम स्तम्भ में है इसलिए $\alpha_1$ प्रवेशी सदिश है।
पुनः $\underset{i}{\text{निम्नतम}}\left\{\frac{w_{B i}}{y_{i 1}}, y_{i 1}>0\right\}=\underset{i}{\text{निम्नतम}}\left\{ \frac{2}{2},\frac{2}{3},\frac{4}{5} \right\} \\ =\frac{2}{3} =\frac{W_{B2}}{y_{21}}$
अतः $y_{21}$ अर्थात् 3 मुख्य अवयव (key element) तथा $\alpha_5$ अपगामी सदिश (departing vector) होगा।अब सामान्य रूपान्तरणों से नवीन सारणी निम्न प्रकार होगी:
द्वितीय सिम्पलेक्स सारणी

$\begin{array}{|ccc|c|cccccc|} \hline & & & C_{i} \rightarrow & 2 & -3 & -5 & 0 & 0 & 0 \\ \hline C_{B} & B & X_B & b & y_1 & y_2 & y_3 & y_4 & y_5 & y_6 \\ \hline 0 & \alpha_4 & w_4 & \frac{2}{3} & 0 & -\frac{7}{3} & \frac{5}{3} & 1 & \frac{2}{3} & 0 \\ 2 & \alpha_1 & w_1 & \frac{2}{3} & 1 & -\frac{1}{3} & -\frac{4}{3} & 0 & \frac{1}{3} & 0 \\ 0 & \alpha_6 & w_6 & \frac{2}{3} & 0 & -\frac{16}{3} & \frac{2}{3} & 0 & -\frac{5}{3} & 1 \\ \hline & & & Z_{j}-C_{j}\rightarrow & 0 & \frac{7}{3} & \frac{7}{3} & 0 & \frac{2}{3} & 0 \\ \hline \end{array}$
चूँकि इस सारणी में $Z_j-C_j \geq 0$ ,j के सभी मानों के लिए,अतः इसका आधारी हल परिवर्तित समस्या का इष्टतम हल होगा:

$w_1=\frac{2}{3},w_2=0,w_3=0$
अतः द्वैती समस्या का इष्टतम हलः

$w_1=\frac{2}{3},w_2=0,w_3=0$
तथा अधिकतम $Z_D=2 w_1-3 w_2-5 w_3 \\ \Rightarrow \max. Z_D=2 \times \frac{2}{3} -3 \times 0-5 \times 0$
तथा $x_1=z_4-c_4=0, x_2=z_5-c_5=\frac{2}{3},x_3=z_6-c_6=0$
न्यूनतम $Z=\frac{4}{3}$

Solve Dual of LPP

Example:9.निम्नतम करो (min.): $Z=2 x_1+x_2$
प्रतिबन्ध (s.t.) $3 x_1+x_2 \geq 3 \\ 4 x_1+3 x_2 \geq 6 \\ x_1+2 x_2 \geq 2$
तथा (and) $x_1, x_2 \geq 0$
Solution:दी गई आद्य समस्या मानक रूप में है,अतः इसकी द्वैती निम्न प्रकार होगी:
अधिकतम करो: $Z_D=3 w_1+6 w_2+2 w_3$
प्रतिबन्ध $3 w_1+4 w_2+w_3 \leq 2 \\ w_1+3 w_2+2 w_3 \leq 1$
तथा $w_1, w_2, w_3 \geq 0$
प्रतिबन्ध को समीकरणों में परिवर्तन करने हेतु $w_4,w_5$ न्यूनतापूरक चरों का समावेश करने पर उपर्युक्त द्वैत समस्या निम्नांकित है:
अधिकतम करोः $Z_D=3 w_1+6 w_2+2 w_3+0 w_4+0 w_5$
प्रतिबन्ध $3 w_1+4 w_2+w_3+w_4+0 w_5=2 \\ w_1+3 w_2+2 w_3+0 w_4+w_5=1$
तथा $w_1, w_2, w_3, w_4, w_5 \geq 0$
अतः प्रतिबन्ध निकाय में गुणांक मैट्रिक्स
$A=\left[\begin{array}{lllll} 3 & 4 & 1 & 1 & 0 \\ 1 & 3 & 2 & 0 & 1 \end{array}\right]=\left(\alpha_1 \alpha_2 \alpha_3 \alpha_4 \alpha_5\right)$ (माना)
प्रारम्भिक आधार $B=\left(\alpha_4, \alpha_5\right)=I_2$ लेने पर,प्रारम्भिक सिम्पलेक्स सारणी निम्न प्रकार है:
प्रथम सिम्पलेक्स सारणी

$\begin{array}{|ccc|c|ccccc|} \hline & & & C_{i} \rightarrow & 3 & 6 & 2 & 0 & 0 \\ \hline C_{B} & B & X_B & b & y_1 & y_2 & y_3 & y_4 & y_5 \\ \hline 0 & \alpha_4 & w_4 & 2 & 3 & 4 & 1 & 1 & 0 \\ 0 & \alpha_5 & w_5 & 1 & 1 & \fbox{3} & 2 & 0 & 1 \\ \hline & & & Z_{j}-C_{j}\rightarrow & -3 & -6 & -2 & 0 & 0 \\ \hline & & & & & \uparrow & & & \downarrow \end{array}$
अतः प्रथम सिम्पलेक्स सारणी से स्पष्ट है कि प्रारम्भिक आधार इष्टतम हल नहीं है,क्योंकि $Z_j-C_j$ के मान ऋणात्मक हैं i.e. $Z_2-C_2=-6$ जो कि न्यूनतम राशि है तथा यह मान द्वितीय स्तम्भ में है,इसलिए $\alpha_2$ प्रवेशी सदिश है।
पुनः $\underset{i}{\text{निम्नतम}}\left\{\frac{w_{B i}}{y_{i 2}}, y_{i 2}>0\right\}=\underset{i}{\text{निम्नतम}} \left\{\frac{2}{4},\frac{1}{3} \right\} \\ =\frac{1}{3} =\frac{W_{B2}}{y_{22}}$
अतः $y_{22}$ अर्थात् 3 मुख्य अवयव (key element) तथा $\alpha_5$ अपगामी सदिश (departing vector) होगा।अब सामान्य रूपान्तरणों से नवीन सारणी निम्न प्रकार होगी:
द्वितीय सिम्पलेक्स सारणी

$\begin{array}{|ccc|c|ccccc|} \hline & & & C_{i} \rightarrow & 3 & 6 & 2 & 0 & 0 \\ \hline C_{B} & B & X_B & b & y_1 & y_2 & y_3 & y_4 & y_5 \\ \hline 0 & \alpha_4 & w_4 & \frac{2}{3} & \frac{\fbox{5}}{\fbox{3}} & 0 & -\frac{5}{3} & 1 & \frac{-4}{3} \\ 6 & \alpha_2 & w_2 & \frac{1}{3} & \frac{1}{3} & 1 & \frac{2}{3} & 0 & \frac{1}{3} \\ \hline & & & Z_{j}-C_{j}\rightarrow & -1 & 0 & 2 & 0 & 2 \\ \hline & & & & \uparrow & & & \downarrow & \end{array}$
अतः द्वितीय सिम्पलेक्स सारणी से स्पष्ट है कि प्रारम्भिक आधार इष्टतम हल नहीं है,क्योंकि $Z_j-C_j$ के मान ऋणात्मक हैं i.e. $Z_1-C_1=-1$ जो कि न्यूनतम राशि है तथा यह मान प्रथम स्तम्भ में है,इसलिए $\alpha_1$ प्रवेशी सदिश है।
पुनः $\underset{i}{\text{निम्नतम}}\left\{\frac{w_{B i}}{y_{i 1}}, y_{i 1}>0\right\}=\underset{i}{\text{निम्नतम}} \left\{ \frac{\frac{2}{3}}{\frac{5}{3}},\frac{\frac{1}{3}}{\frac{1}{3}} \right\} \\ =\frac{\frac{2}{3}}{\frac{5}{3}} =\frac{W_{B1}}{y_{11}}$
अतः $y_{11}$ अर्थात् $\frac{5}{3}$ मुख्य अवयव (key element) तथा $\alpha_4$ अपगामी सदिश (departing vector) होगा।अब सामान्य रूपान्तरणों से नवीन सारणी निम्न प्रकार होगी:
तृतीय सिम्पलेक्स सारणी

$\begin{array}{|ccc|c|ccccc|} \hline & & & C_{i} \rightarrow & 3 & 6 & 2 & 0 & 0 \\ \hline C_{B} & B & X_B & b & y_1 & y_2 & y_3 & y_4 & y_5 \\ \hline 3 & \alpha_1 & w_1 & \frac{2}{5} & 1 & 0 & -1 & \frac{3}{5} & \frac{-4}{5} \\ 6 & \alpha_2 & w_2 & \frac{1}{5} & 0 & 1 & 1 & -\frac{1}{5} & \frac{3}{5} \\ \hline & & & Z_{j}-C_{j}\rightarrow & 0 & 0 & 1 & \frac{3}{5} & \frac{6}{5} \\ \hline \end{array}$
चूँकि इस सारणी में $Z_j-C_j \geq 0$ ,j के सभी मानों के लिए,अतः इसका आधारी हल परिवर्तित समस्या का इष्टतम हल होगा:

$w_1=\frac{2}{5}, w_2=\frac{1}{5}, w_3=0$
अतः द्वैती समस्या का इष्टतम हलः

$w_1=\frac{2}{5}, w_2=\frac{1}{5}, w_3=0$
तथा अधिकतम $Z_D=3 w_1+6 w_2+2 w_3 \\ \Rightarrow \max. Z_D=3 \times \frac{2}{5}+6 \times \frac{1}{5}+2 \times 0=\frac{12}{5}$
तथा $x_1=z_4-c_4=\frac{3}{5}, x_2=z_5-c_5=\frac{6}{5}$
न्यूनतम $Z=\frac{12}{5}$
Example:10.निम्नतम करो (min.): $Z=8 x_1+2 x_2-4 x_3$
प्रतिबन्ध (s.t.) $x_1-4 x_2-2 x_3 \geq 2 \\ x_1+x_2-3 x_3 \geq -1 \\ -3 x_1-x_2+x_3 \geq 1$
तथा (and) $x_1, x_2, x_3 \geq 0$
Solution:दी गई आद्य समस्या मानक रूप में है,अतः इसकी द्वैती निम्न प्रकार होगी:
अधिकतम करो: $Z_D=2 w_1-w_2+w_3$
प्रतिबन्ध $w_1+w_2-3 w_3 \leq 8 \\ -4 w_1+w_2-w_3 \leq 2 \\ -2 w_1-3 w_2+w_3 \leq-4 \Rightarrow 2 w_1+3 w_2-w_3 \geq 4$
तथा $w_1, w_2, w_3 \geq 0$
इस द्वैती समस्या को सिम्पलेक्स विधि से हल करने के लिए हमें प्रतिबन्ध निकाय को समीकरणों में परिवर्तित करना होगा। $w_4$ और $w_5$ दो न्यूनतापूरक चर, $w_6$ एक आधिक्यपूरक चर एवं $w_7$ एक कृत्रिम चर सम्मिलित करने पर समस्या का परिवर्तित मानक रूप निम्न प्रकार है:
अधिकतम करो: $Z_D=2 w_1-w_2+w_3+0 w_4+0 w_5+0 w_6-M w_7$
प्रतिबन्ध $w_1+w_2-3 w_3+w_4+0 w_5+w_6+0 w_7=8 \\ -4 w_1+w_2-w_3+0 w_4+w_5+0 w_6+0 w_7=2 \\ 2 w_1+3 w_2-w_3+0 w_4+0 w_5-w_6+w_7=4$
तथा $w_1, w_2, w_3, w_4, w_5, w_6, w_7 \geq 0$
उद्देश्य फलन में कृत्रिम चर $w_7$ का मूल्य -M लेते हैं जहाँ M एक बहुत बड़ी धनात्मक संख्या है।
प्रतिबन्धों का गुणांक मैट्रिक्स
$A=\left[\begin{array}{ccccccc} 1 & 1 & -3 & 1 & 0 & 0 & 0 \\ -4 & 1 & -1 & 0 & 1 & 0 & 0 \\ 2 & 3 & -1 & 0 & 0 & -1 & 1 \end{array}\right]=\left(\alpha_1 \alpha_2 \alpha_3 \alpha_4 \alpha_5 \alpha_6 \alpha_7\right)$ (माना)
यहाँ प्रारम्भिक आधार मैट्रिक्स $B=\left( \alpha_4 \alpha_5 \alpha_7 \right)=I_3$ अतः प्रथम सिम्पलेक्स सारणी निम्न प्रकार है:
प्रथम सिम्पलेक्स सारणी

$\begin{array}{|ccc|c|ccccccc|} \hline & & & C_{i} \rightarrow & 2 & -1 & 1 & 0 & 0 & 0 & -M \\ \hline C_{B} & B & X_B & b & y_1 & y_2 & y_3 & y_4 & y_5 & y_6 & y_7 \\ \hline 0 & \alpha_4 & w_4 & 8 & 1 & 1 & -3 & 1 & 0 & 0 & 0 \\ 0 & \alpha_5 & w_5 & 2 & -4 & 1 & -1 & 0 & 1 & 0 & 0 \\ -M & \alpha_7 & w_7 & 4 & 2 & \fbox{3} & -1 & 0 & 0 & -1 & 1 \\ \hline & & & Z_{j}-C_{j}\rightarrow & -2 M-2 & -3 M+1 & M-1 & 0 & 0 & M & 0 \\ \hline & & & & & \uparrow & & & & & \downarrow \end{array}$
अतः प्रथम सिम्पलेक्स सारणी से स्पष्ट है कि प्रारम्भिक आधार इष्टतम हल नहीं है,क्योंकि $Z_j-C_j$ के मान ऋणात्मक हैं i.e. $Z_2-C_2=-3M+1$ जो कि न्यूनतम राशि है तथा यह मान द्वितीय स्तम्भ में है,इसलिए $\alpha_2$ प्रवेशी सदिश है।
पुनः $\underset{i}{\text{निम्नतम}}\left\{\frac{w_{B i}}{y_{i 2}}, y_{i 2}>0\right\}=\underset{i}{\text{निम्नतम}}\left\{ \frac{8}{1},\frac{2}{1},\frac{4}{3} \right\} \\ =\frac{4}{3} =\frac{W_{B3}}{y_{23}}$
अतः $y_{23}$ अर्थात् 3 मुख्य अवयव (key element) तथा $\alpha_7$ अपगामी सदिश (departing vector) होगा। $\alpha_7$ कृत्रिम चर है अतः इसे नवीन सारणी में शामिल नहीं करेंगे।अब सामान्य रूपान्तरणों से नवीन सारणी निम्न प्रकार होगी:
द्वितीय सिम्पलेक्स सारणी

$\begin{array}{|ccc|c|cccccc|} \hline & & & C_{i} \rightarrow & 2 & -1 & 1 & 0 & 0 & 0 \\ \hline C_{B} & B & X_B & b & y_1 & y_2 & y_3 & y_4 & y_5 & y_6 \\ \hline 0 & \alpha_4 & w_4 & \frac{20}{3} & \frac{1}{3} & 0 & -\frac{8}{3} & 1 & 0 & \frac{1}{3} \\ 0 & \alpha_5 & w_5 & \frac{2}{3} & -\frac{14}{3} & 0 & -\frac{2}{3} & 0 & 1 & \frac{1}{3} \\ -M & \alpha_7 & w_7 & \frac{4}{3} & \frac{\fbox{2}}{\fbox{3}} & 1 & -\frac{1}{3} & 0 & 0 & -\frac{1}{3} \\ \hline & & & Z_{j}-C_{j}\rightarrow & -\frac{8}{3} & 0 & \frac{4}{3} & 0 & 0 & \frac{1}{3} \\ \hline & & & & \uparrow & \downarrow & & & & \end{array}$
अतः द्वितीय सिम्पलेक्स सारणी से स्पष्ट है कि प्रारम्भिक आधार इष्टतम हल नहीं है,क्योंकि $Z_j-C_j$ के मान ऋणात्मक हैं i.e $Z_1-C_1=-\frac{8}{3}$ . जो कि न्यूनतम राशि है तथा यह मान प्रथम स्तम्भ में है,इसलिए $\alpha_1$ प्रवेशी सदिश है।
पुनः $\underset{i}{\text{निम्नतम}}\left\{\frac{w_{B i}}{y_{i 1}}, y_{i 1}>0\right\}=\underset{i}{\text{निम्नतम}}\left\{ \frac{\frac{20}{3}}{\frac{1}{3}}, \frac{\frac{4}{3}}{\frac{2}{3}} \right\} \\ =\frac{\frac{4}{3}}{\frac{2}{3}} =\frac{W_{B3}}{y_{31}}$
अतः $y_{31}$ अर्थात् $\frac{2}{3}$ मुख्य अवयव (key element) तथा $\alpha_2$ अपगामी सदिश (departing vector) होगा।अब सामान्य रूपान्तरणों से नवीन सारणी निम्न प्रकार होगी:
तृतीय सिम्पलेक्स सारणी

$\begin{array}{|ccc|c|cccccc|} \hline & & & C_{i} \rightarrow & 2 & -1 & 1 & 0 & 0 & 0 \\ \hline C_{B} & B & X_B & b & y_1 & y_2 & y_3 & y_4 & y_5 & y_6 \\ \hline 0 & \alpha_4 & w_4 & 6 & 0 & -\frac{1}{2} & -\frac{5}{2} & 1 & 0 & \frac{\fbox{1}}{\fbox{2}} \\ 0 & \alpha_5 & w_5 & 10 & 0 & 7 & -3 & 0 & 1 & -2 \\ -M & \alpha_7 & w_7 & 2 & 1 & \frac{3}{2} & -\frac{1}{2} & 0 & 0 & -\frac{1}{2} \\ \hline & & & Z_{j}-C_{j}\rightarrow & 0 & 4 & 0 & 0 & 0 & -1 \\ \hline & & & & & & & \downarrow & & \uparrow \end{array}$
अतः तृतीय सिम्पलेक्स सारणी से स्पष्ट है कि प्रारम्भिक आधार इष्टतम हल नहीं है,क्योंकि $Z_j-C_j$ के मान ऋणात्मक हैं i.e. $Z_6-C_6=-1$ जो कि न्यूनतम राशि है तथा यह मान षष्ठम स्तम्भ में है,इसलिए $\alpha_6$ प्रवेशी सदिश है।
पुनः $\underset{i}{\text{निम्नतम}}\left\{\frac{w_{B i}}{y_{i 6}}, y_{i 6}>0\right\}=\underset{i}{\text{निम्नतम}}\left\{ \frac{6}{\frac{1}{2}}\right\} \\ = \frac{6}{\frac{1}{2}}=\frac{W_{B1}}{y_{16}}$
अतः $y_{16}$ अर्थात् $\frac{1}{2}$ मुख्य अवयव (key element) तथा $\alpha_4$ अपगामी सदिश (departing vector) होगा।अब सामान्य रूपान्तरणों से नवीन सारणी निम्न प्रकार होगी:
चतुर्थ सिम्पलेक्स सारणी

$\begin{array}{|ccc|c|cccccc|} \hline & & & C_{i} \rightarrow & 2 & -1 & 1 & 0 & 0 & 0 \\ \hline C_{B} & B & X_B & b & y_1 & y_2 & y_3 & y_4 & y_5 & y_6 \\ \hline 0 & \alpha_6 & w_6 & 12 & 0 & -1 & -5 & 2 & 0 & 1 \\ 0 & \alpha_5 & w_5 & 34 & 0 & 5 & -13 & 4 & 1 & 0 \\ 2 & \alpha_1 & w_1 & 8 & 1 & 1 & -3 & 1 & 0 & 0 \\ \hline & & & Z_{j}-C_{j}\rightarrow & 0 & 3 & -7 & 2 & 0 & 0 \\ \hline \end{array}$
चतुर्थ सारणी में $\alpha_3$ एक ऐसा सदिश है जो आधार B में नहीं है तथा $Z_3-C_3=-7<0$ एवं $y_{i3}$ के सभी घटक ऋणात्मक हैं अतः द्वैतता के मूल प्रमेय के अनुसार दी गई आद्य समस्या का भी परिमित इष्टतम हल विद्यमान नहीं है।
उपर्युक्त उदाहरणों के द्वारा रैखिक प्रोग्रामन समस्या की द्वैती समस्या को हल करो (Solve Dual of LPP),रैखिक प्रोग्रामन समस्याओं को द्वैत सिद्धान्त के प्रयोग से हल कीजिए (Use Duality to Solve LPP) को समझ सकते हैं।

Solve Dual of LPP

Also Read This Article:- Use Duality to Solve LPP

3.रैखिक प्रोग्रामन समस्या की द्वैती समस्या को हल करो (Frequently Asked Questions Related to Solve Dual of LPP),रैखिक प्रोग्रामन समस्याओं को द्वैत सिद्धान्त के प्रयोग से हल कीजिए (Use Duality to Solve LPP) से सम्बन्धित अक्सर पूछे जाने वाले प्रश्न:

प्रश्न:1.द्वैती समस्या को हल करने में सर्वप्रथम क्या करते हैं? (What is the First Thing You Do in Solving the Duality Problem?):

उत्तर:किसी रैखिक प्रोग्रामन समस्या की द्वैती समस्या के संरूपण के लिए सर्वप्रथम समस्या को मानक रूप में व्यक्त करते हैं इसके पश्चात ही द्वैती समस्या का संरूपण करते हैं।

प्रश्न:2.किसी आद्य समस्या का मैट्रिक्स रूप लिखो। (Write a Matrix Form of a Primal Problem):

उत्तर:यदि समस्या अधिकतमीकरण की है तो उसका मैट्रिक्स रूप निम्न प्रकार लिखा जा सकता है:
अधिकतम करो: $Z_p=\left(c_1 \quad c_2 \ldots \ldots \ldots c_n\right)\left[\begin{array}{l} x_1 \\ x_2 \\ \vdots \\ x_n \end{array}\right]$
प्रतिबन्ध $\left[\begin{array}{cccc} a_{11} & a_{12} & \cdots & a_{1 n} \\ a_{21} & a_{22} & \cdots & a_{2 n} \\ \vdots & \vdots & \vdots \\ a_{m 1} & a_{n 2} & \cdots & a_{m n} \end{array}\right]\left[\begin{array}{c} x_1 \\ x_2 \\ \vdots \\ x_n \end{array}\right] \leq\left[\begin{array}{c} b_1 \\ b_2 \\ \vdots \\ b_n \end{array}\right]$
तथा $x_1, x_2, \ldots, x_n \geq 0$
इस समस्या को संक्षिप्त रूप में निम्न प्रकार से व्यक्त कर सकते हैं:
अधिकतम करो: $Z_p=C X$
प्रतिबन्ध $A X \leq b \\ X \geq 0$

प्रश्न:3.सिद्ध करो कि किसी आद्य समस्या का हल अपरिबद्ध हो तो उसकी द्वैती समस्या का हल या तो अपरिबद्ध होगा अथवा कोई हल नहीं होगा। (Prove that if the primal problem has unbounded solution then dual has either no solution or an unbounded solution):

उत्तर:हम इस प्रमेय को ‘विरोधाभास विधि’ (contradiction) से सिद्ध करते हैं।सम्भव हो तो माना कि आद्य समस्या का हल अपरिबद्ध तथा इसकी द्वैती समस्या का हल परिमित एवं इष्टतम है,परन्तु हम जानते हैं कि (i)द्वैती की द्वैती आद्य समस्या होती है तथा (ii)यदि आद्य समस्या का परिमित इष्टतम हल है तो इसकी द्वैती समस्या का हल भी परिमित इष्टतम विद्यमान होगा।
हमारी कल्पना अनुसार द्वैती का हल परिमित इष्टतम है।इस द्वैती को आद्य मानते हुए इसकी द्वैती का हल भी परिमित इष्टतम होगा [(ii) के अनुसार]।परन्तु (i) के अनुसार द्वैती की द्वैती आद्य समस्या होती है।अतः आद्य समस्या का हल परिमित इष्टतम होगा जो हमारी आद्य समस्या के लिए की गई कल्पना का विरोध करती है।अतः द्वैती का हल परिमित इष्टतम नहीं होगा तथा यदि हल होगा तो वह अपरिमित होगा।
उपर्युक्त प्रश्नों के उत्तर द्वारा रैखिक प्रोग्रामन समस्या की द्वैती समस्या को हल करो (Solve Dual of LPP),रैखिक प्रोग्रामन समस्याओं को द्वैत सिद्धान्त के प्रयोग से हल कीजिए (Use Duality to Solve LPP) के बारे में ओर अधिक जानकारी प्राप्त कर सकते हैं।

No.	Social Media	Url
1.	Facebook	click here
2.	you tube	click here
3.	Instagram	click here
4.	Linkedin	click here
5.	Facebook Page	click here
6.	Twitter	click here

Solve Dual of LPP

रैखिक प्रोग्रामन समस्या की
द्वैती समस्या को हल करो
(Solve Dual of LPP)

Solve Dual of LPP

About Author

Satyam

About my self I am owner of Mathematics Satyam website.I am satya narain kumawat from manoharpur district-jaipur (Rajasthan) India pin code-303104.My qualification -B.SC. B.ed. I have read about m.sc. books,psychology,philosophy,spiritual, vedic,religious,yoga,health and different many knowledgeable books.I have about 15 years teaching experience upto M.sc. ,M.com.,English and science.