Write Dual of LPP and Solve It

Q: प्रश्न:2.जब प्रतिबन्ध निकाय में तीनों चिन्ह हों तो इकाई मैट्रिक्स कैसे प्राप्त करते हैं? (How is the Unit Matrix Obtained When the Constraint System Has All Three Signs?):

उत्तर:इस स्थिति में प्रत्येक \geq चिन्ह वाले प्रतिबन्ध में एक आधिक्यपूरक चर घटायेंगे प्रत्येक \leq चिन्ह वाले प्रतिबन्ध में एक न्यूनतापूरक चर जोड़ेंगे तथा आवश्यकतानुसार कृत्रिम चरों को जोड़कर आधारी मैट्रिक्स प्राप्त करते हैं जिसके संगत हल प्रारम्भिक आधारी हल होगा।

Mathematics Satyam June 21, 2024 Linear Programming No Comments

Contents hide

1 1.रैखिक प्रोग्रामन समस्या की द्वैती लिखकर हल करें (Write Dual of LPP and Solve It),द्वैतता की सहायता से रैखिक प्रोग्रामन समस्या को हल करो (Use Duality to Solve Linear Programming Problems):

1.1 2.रैखिक प्रोग्रामन समस्या की द्वैती लिखकर हल करें के उदाहरण (Write Dual of LPP and Solve It Illustrations):

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

1.2.1 प्रश्न:1.जब सभी प्रतिबन्ध समीकरणों में हो तो इकाई मैट्रिक्स कैसे प्राप्त करते हैं? (How Do You Get Unit Matrix When All the Constraints Are in the Equations?):

1.2.2 प्रश्न:2.जब प्रतिबन्ध निकाय में तीनों चिन्ह हों तो इकाई मैट्रिक्स कैसे प्राप्त करते हैं? (How is the Unit Matrix Obtained When the Constraint System Has All Three Signs?):

1.2.3 प्रश्न:3.नवीन सारणी से इष्टतम हल प्राप्त न हो तो क्या करते हैं? (What Do You Do If the New Table Does Not Achieve the Optimum Solution?):

1.2.3.1 Write Dual of LPP and Solve It

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

2.1 Write Dual of LPP and Solve It

1.रैखिक प्रोग्रामन समस्या की द्वैती लिखकर हल करें (Write Dual of LPP and Solve It),द्वैतता की सहायता से रैखिक प्रोग्रामन समस्या को हल करो (Use Duality to Solve Linear Programming Problems):

Write Dual of LPP and Solve It

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

Also Read This Article:- Solve LPP by Writing Its Dual

2.रैखिक प्रोग्रामन समस्या की द्वैती लिखकर हल करें के उदाहरण (Write Dual of LPP and Solve It Illustrations):

निम्न रैखिक प्रोग्रामन समस्याओं को उनकी द्वैत सिद्धान्त के प्रयोग से हल कीजिए।
(Use duality to solve the following L.P.P.’s):
Illustration:15.अधिकतम करो (max.): $Z=3 x_1+4 x_2$
प्रतिबन्ध (s.t.) $x_1-x_2 \leq 1 \\ x_1+x_2 \geq 4 \\ x_1-3 x_2 \leq 3$
तथा (and) $x_1 \geq 0, x_2 \geq 0$
Solution:दी गई आद्य समस्या मानक रूप में नहीं है,इसलिए सर्वप्रथम इस आद्य समस्या को मानक रूप में निम्न प्रकार लिखते हैं:
अधिकतम करो: $Z=3x_1+4x_2$
प्रतिबन्ध $x_1-x_2 \leq 1 \\ -x_1-x_2 \leq-4 \\ x_1-3 x_2 \leq 3$
तथा $x_1, x_2 \geq 0$
अब यह समस्या अपने मानक रूप में है।इसकी द्वैती समस्या निम्न प्रकार होगी:
निम्नतम करो: $Z_D=w_1-4 w_2+3 w_3$
प्रतिबन्ध $w_1-w_2+w_3 \geq 0 \\ -w_1-w_2-w_3 \geq 4$
तथा $w_1,w_2 ,w_3 \geq 0$
इसे सिम्पलेक्स विधि से हल करने के लिए प्रतिबन्ध निकाय के समीकरणों में बदलना होगा।अतः $w_4,w_5$ दो आधिक्यपूरक चर एवं $w_6,w_7$ कृत्रिम चर के जोड़ने पर तथा उद्देश्य फलन को अधिकतम रूप में लिखने पर उपर्युक्त द्वैत समस्या निम्न प्रकार है:
अधिकतम करो: $Z^*=-w_1+4 w_2-3 w_3+0 w_4+0 w_5-M w_6-M w_7$
प्रतिबन्ध $w_1-w_2+w_3-w_4+0 w_5+w_6+0 w_7=3 \\ -w_1-w_2-w_3+0 w_4-w_5+0 w_6+w_7=4$
तथा $w_1, w_2, w_3, w_4, w_5, w_6, w_7 \geq 0$
अब प्रतिबन्ध निकाय में गुणांक मैट्रिक्स
$A=\left[\begin{array}{ccccccc} 1 & -1 & 1 & -1 & 0 & 1 & 0 \\ -1 & -1 & -1 & 0 & -1 & 0 & 1 \end{array}\right]=\left(\alpha_1 \alpha_2 \alpha_3 \alpha_4 \alpha_5 \alpha_6 \alpha_7 \right)$ (माना)
प्रारम्भिक आधार $B=\left(\alpha_6 \alpha_7 \right)=I_2$ लेने पर,प्रारम्भिक सिम्पलेक्स सारणी निम्न प्रकार है:
प्रथम सिम्पलेक्स सारणी

$\begin{array}{|ccc|c|ccccccc|} \hline & & & C_{j} \rightarrow & -1 & 4 & -3 & 0 & 0 & -M & -M \\ \hline C_{B} & B & X_B & b & y_1 & y_2 & y_3 & y_4 & y_5 & y_6 & y_7 \\ \hline -M & \alpha_6 & w_6 & 3 & 1 & -1 & 1 & -1 & 0 & 1 & 0 \\ -M & \alpha_7 & w_7 & 4 & -1 & -1 & -1 & 0 & -1 & 0 & 1 \\ \hline & & & Z^*_{j}-C_{j}\rightarrow & 1 & 2 M-4 & 3 & M & M & 0 & 0 \\ \hline \end{array}$
प्रथम सिम्पलेक्स सारणी में $Z_j^*-C_j \geq 0$ , j के सभी मानों के लिए (j=1,2,3,4,5,6,7) अतः इष्टतम हल होना चाहिए,परन्तु इसके आधार में दो कृत्रिम चर $\alpha_6$ व $\alpha_7$ विद्यमान हैं जिनका मान शून्य नहीं है।अतः आद्य समस्या का कोई भी परिमित इष्टतम हल विद्यमान नहीं है।
Illustration:16.अधिकतम (max.): $Z=40 x_1+50 x_2$
प्रतिबन्ध (s.t.) $2 x_1+3 x_2 \leq 3 \\ 8 x_1+4 x_2 \leq 5$
तथा (and) $x_1, x_2 \geq 0$
Solution:दी गई आद्य समस्या मानक रूप में है,अतः इसकी द्वैती निम्न प्रकार होगी:
निम्नतम करो: $Z_D=3 w_1+5 w_2$
प्रतिबन्ध $2 w_1+8 w_2 \geq 40 \\ 3 w_1+4 w_2 \geq 50$
तथा $w_1, w_2 \geq 0$
प्रतिबन्धों को समीकरणों में परिवर्तन करने के लिए $w_3,w_4$ न्यूनतापूरक चरों तथा $w_5,w_6$ कृत्रिम चरों का समावेश करने पर तथा उद्देश्य फलन को अधिकतम रूप में लिखने पर उपर्युक्त द्वैत समस्या निम्नांकित है:
अधिकतम करोः $Z^{*}=-3 w_1-5 w_2+0 w_3+0 w_4-M w_5-M w_6$
प्रतिबन्ध $2 w_1+8 w_2-w_3+0 w_4+w_5+0 w_5 +0w_6=40 \\ 3 w_1+4 w_2+0 w_3-w_4+0 w_5+w_6=50$
तथा $w_1, w_2, w_3, w_4, w_5, w_6 \geq 0$
उद्देश्य फलन में कृत्रिम चर $w_5$ व $w_6$ का मूल्य -M लेते हैं जहाँ M एक बहुत बड़ी धनात्मक संख्या है।
अब प्रतिबन्धों का गुणांक मैट्रिक्स
$A=\left[\begin{array}{cccccc} 2 & 8 & -1 & 0 & 1 & 0 \\ 3 & 4 & 0 & -1 & 0 & 1 \end{array}\right] =\left(\alpha_1 \alpha_2 \alpha_3 \alpha_4 \alpha_5 \alpha_6\right)$ (माना)
यहाँ प्रारम्भिक आधार $B=\left( \alpha_5 \alpha_6 \right)=I_2$ लेने पर,प्रारम्भिक सिम्पलेक्स सारणी निम्न प्रकार है:
प्रथम सिम्पलेक्स सारणी

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

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

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

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

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

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

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

$w_1=15, w_2=\frac{5}{4}$
तथा निम्नतम $Z_D=3 w_1+5 w_2 \\ =3 \times 15+5 \times \frac{5}{4} \\ =45+\frac{25}{4} \\ \Rightarrow \min Z_D =\frac{205}{4}$

तथा $x_1=z_3^*-x_3=\frac{3}{16}, x_2=z_4^*-c_4=\frac{7}{8}$
अधिकतम $Z=\frac{205}{4}$

Write Dual of LPP and Solve It

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

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

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

$\begin{array}{|ccc|c|cccc|} \hline & & & C_{j} \rightarrow & 40 & 50 & 0 & 0 \\ \hline C_{B} & B & W_B & b & y_1 & y_2 & y_3 & y_4 \\ \hline 50 & \alpha_2 & w_2 & \frac{3.5}{4} & 0 & 1 & \frac{1}{2} & -\frac{1}{4} \\ 40 & \alpha_1 & w_1 & \frac{1.5}{8} & 1 & 0 & -\frac{1}{4} & \frac{3}{8} \\ \hline & & & Z^*_{j}-C_{j}\rightarrow & 0 & 0 & 15 & \frac{5}{2} \\ \hline \end{array}$
चूँकि इस सारणी में $Z_j^*-C_j \geq 0$ ,j के सभी मानों के लिए,अतः इसका आधारी हल परिवर्तित समस्या का इष्टतम हल होगा:

$w_1=\frac{1.5}{8}, w_2=\frac{3.5}{4}$
अतः द्वैती समस्या का इष्टतम हलः

$w_1=\frac{1.5}{8}, w_2=\frac{3.5}{4}$
तथा अधिकतम $Z_D=40 w_1+50 w_2 \\ =40 \times \frac{1.5}{8}+50 \times \frac{3.5}{4} \\ \Rightarrow \max Z_D=\frac{205}{4}$
तथा $x_1=z_3-c_3=15, x_2=z_4-c_4=\frac{5}{2}$
न्यूनतम $Z=\frac{205}{4}$
Illustration:18.अधिकतम (max.): $Z=4 x_1+2 x_2$
प्रतिबन्ध (s.t.) $x_1+x_2 \geq 3 \\ x_1-x_2 \geq 2$
तथा (and) $x_1, x_2 \geq 0$
Solution:दी गई आद्य समस्या मानक रूप में नहीं है,इसलिए सर्वप्रथम इस आद्य समस्या को मानक रूप में निम्न प्रकार लिखते हैं:
अधिकतम करो: $Z=4 x_1+2 x_2$
प्रतिबन्ध $-x_1-x_2 \leq-3 \\ -x_1+x_2 \leq-2$
तथा $x_1,x_2 \geq 0$
अब यह समस्या अपने मानक रूप में है।इसकी द्वैती समस्या निम्न प्रकार होगी:
निम्नतम करो: $Z_D=-3 w_1-2 w_2$
प्रतिबन्ध $-w_1-w_2 \geq 4 \\ -w_1+w_2 \geq 2$
तथा $w_1,w_2 \geq 0$
इसे सिम्पलेक्स विधि से हल करने के लिए प्रतिबन्ध निकाय को समीकरणों में बदलना होगा।अतः $w_3,w_4$ दो आधिक्यपूरक चर एवं $w_5,w_6$ कृत्रिम चर के जोड़ने पर तथा उद्देश्य फलन को अधिकतम रूप में लिखने पर उपर्युक्त द्वैत समस्या निम्न प्रकार है:
अधिकतम करो: $Z^*=3 w_1+2 w_2+0 w_3+0 w_4-M W_5-M W_6$
प्रतिबन्ध $-w_1-w_2-w_3+0 w_4+w_5+0 w_6=4 \\ -w_1+w_2+0 w_3-w_4+0 w_5+w_6=2$
तथा $w_1, w_2, w_3, w_4, w_5, w_6 \geq 0$
उद्देश्य फलन में कृत्रिम चर $w_5,w_6$ का मूल्य -M लेते हैं जहाँ M एक बहुत बड़ी धनात्मक संख्या है।
अब प्रतिबन्ध निकाय में गुणांक मैट्रिक्स
$A=\left[\begin{array}{cccccc} -1 & -1 & -1 & 0 & 1 & 0 \\ -1 & 1 & 0 & -1 & 0 & 1 \end{array}\right]=\left(\alpha_1 \alpha_2 \alpha_3 \alpha_4 \alpha_5 \alpha_6\right)$ (माना)
यहाँ प्रारम्भिक आधार $B=\left(\alpha_5 \alpha_6\right)=I_2$ लेने पर,प्रारम्भिक सिम्पलेक्स सारणी निम्न प्रकार है:
प्रथम सिम्पलेक्स सारणी

$\begin{array}{|ccc|c|cccccc|} \hline & & & C_{j} \rightarrow & 3 & 2 & 0 & 0 & -M & -M \\ \hline C_{B} & B & X_B & b & y_1 & y_2 & y_3 & y_4 & y_5 & y_6 \\ \hline -M & \alpha_5 & w_5 & 4 & -1 & -1 & -1 & 0 & 1 & 0 \\ -M & \alpha_6 & w_6 & 2 & -1 & \fbox{1} & 0 & -1 & 0 & 1 \\ \hline & & & Z^*_{j}-C_{j} \rightarrow & 2 M-3 & -2 & M & M & 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 2}}, y_{i 2}>0\right\}=\underset{i}{\text{निम्नतम}} \left\{ \frac{2}{1} \right\} \\ =\frac{2}{1}=\frac{W_{B2}}{y_{22}}$
अतः $y_{22}$ अर्थात् 1 मुख्य अवयव (key element) तथा $\alpha_6$ अपगामी सदिश (departing vector) होगा। $\alpha_6$ कृत्रिम चर है अतः इसे नवीन सारणी में शामिल नहीं करेंगे।अब सामान्य रूपान्तरणों से नवीन सारणी निम्न प्रकार होगी:
द्वितीय सिम्पलेक्स सारणी

$\begin{array}{|ccc|c|ccccc|} \hline & & & C_{j} \rightarrow & 3 & 2 & 0 & 0 & -M \\ \hline C_{B} & B & W_B & b & y_1 & y_2 & y_3 & y_4 & y_5 \\ \hline -M & \alpha_5 & w_5 & 6 & -2 & 0 & -1 & -1 & 1 \\ 2 & \alpha_2 & w_2 & 2 & -1 & 1 & 0 & -1 & 0 \\ \hline & & & Z^*_{j}-C_{j}\rightarrow & 2 M-5 & 0 & M & M-2 & 0 \\ \hline \end{array}$
द्वितीय सिम्पलेक्स सारणी $Z_j^*-C_j \geq 0$ ,j के सभी मानों के लिए (j=1,2,3,4,5) अतः इष्टतम हल होना चाहिए,परन्तु इसके आधार में कृत्रिम चर $\alpha_5$ विद्यमान हैं जिसका मान शून्य नहीं है।अतः आद्य समस्या का कोई भी परिमित इष्टतम हल विद्यमान नहीं है।
Illustration:19.अधिकतम (max.): $Z=3 x-2 x_2$
प्रतिबन्ध (s.t.) $x_1+x_2 \leq 5 \\ x_1 \leq 4 \\ 1 \leq x_2 \leq 6$
तथा (and) $x_1, x_2 \geq 0$
Solution:दी गई आद्य समस्या मानक रूप में नहीं है,इसलिए सर्वप्रथम इस आद्य समस्या को मानक रूप में निम्न प्रकार लिखते हैं:
अधिकतम करो: $Z=3 x_1-2 x_2$
प्रतिबन्ध $x_1+x_2 \leq 5 \\ x_1 \leq 4 \\ x_2 \leq 6 \\ -x_2 \leq-1$
तथा $x_1, x_2 \geq 0$
अब यह समस्या अपने मानक रूप में है।इसकी द्वैती समस्या निम्न प्रकार होगी:
निम्नतम करो: $Z_D=5 w_1+ 4 w_2+6 w_3-w_4$
प्रतिबन्ध $w_1+w_2 \geq 3 \\ w_1+w_3-w_4 \geq -2 \\ \Rightarrow -w_1-w_3+w_4 \leq 2$
तथा $w_1, w_2, w_3, w_4>0$
इसे सिम्पलेक्स विधि से हल करने के लिए प्रतिबन्ध निकाय को समीकरणों में बदलना होगा।अतः $w_5$ आधिक्यपूरक चर घटाने तथा $w_6$ न्यूनतापूरक चर जोड़ने तथा उद्देश्य फलन को अधिकतम रूप में लिखने पर उपर्युक्त द्वैत समस्या निम्न प्रकार है:
अधिकतम करो: $Z*=-5 w_1-4 w_2-6 w_3+w_4+0w_5+0 w_6$
प्रतिबन्ध $w_1+w_2+0 w_3+0 w_4-w_5+0 w_6=3 \\ -w_1+0 w_2-w_3+w_4+0 w_5+w_6=2$
तथा $w_1, w_2, w_3, w_4, w_5, w_6 \geq 0$
अब प्रतिबन्ध निकाय में गुणांक मैट्रिक्स
$A=\left[\begin{array}{rrrrrr}1 & 1 & 0 & 0 & -1 & 0 \\-1 & 0 & -1 & 1 & 0 & 1 \end{array}\right] =\left(\alpha_1 \alpha_2 \alpha_3 \alpha_4 \alpha_5 \alpha_6\right)$ (माना)
यहाँ प्रारम्भिक आधार $B=\left(\alpha_2 \alpha_6\right)=I_2$ लेने पर,प्रारम्भिक सिम्पलेक्स सारणी निम्न प्रकार है:
प्रथम सिम्पलेक्स सारणी

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

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

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

$w_1=0, w_2=3, w_3=0, w_4=2$
तथा निम्नतम $Z_D=5 w_1+4 w_2+6 w_3-w_4 \\ =5 \times 0+4 \times 3+6 \times 0-2 \\ \min Z_D=10$
तथा $x_1=z_5-c_5=4, x_2=z_6-c_6=1$
तथा $\max. Z=10$
उपर्युक्त उदाहरणों के द्वारा रैखिक प्रोग्रामन समस्या की द्वैती लिखकर हल करें (Write Dual of LPP and Solve It),द्वैतता की सहायता से रैखिक प्रोग्रामन समस्या को हल करो (Use Duality to Solve Linear Programming Problems) को समझ सकते हैं।

Write Dual of LPP and Solve It

Also Read This Article:- Solve Dual of LPP

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

प्रश्न:1.जब सभी प्रतिबन्ध समीकरणों में हो तो इकाई मैट्रिक्स कैसे प्राप्त करते हैं? (How Do You Get Unit Matrix When All the Constraints Are in the Equations?):

उत्तर:यदि मैट्रिक्स A के सदिशों से इकाई सदिश विद्यमान हो तो उसे आधार मानकर प्रारम्भिक हल निकाल सकते हैं।यदि A के सदिशों से इकाई मैट्रिक्स का कोई एक सदिश $e_i$ प्राप्त न हो तो उस समीकरण में एक कृत्रिम चर जोड़कर इसे प्राप्त करेंगे।इसी प्रकार यदि एक से अधिक इकाई सदिशों की कमी हो तो उन्हीं के संगत कृत्रिम चर जोड़कर दूर करते हैं।

प्रश्न:2.जब प्रतिबन्ध निकाय में तीनों चिन्ह हों तो इकाई मैट्रिक्स कैसे प्राप्त करते हैं? (How is the Unit Matrix Obtained When the Constraint System Has All Three Signs?):

उत्तर:इस स्थिति में प्रत्येक $\geq$ चिन्ह वाले प्रतिबन्ध में एक आधिक्यपूरक चर घटायेंगे प्रत्येक $\leq$ चिन्ह वाले प्रतिबन्ध में एक न्यूनतापूरक चर जोड़ेंगे तथा आवश्यकतानुसार कृत्रिम चरों को जोड़कर आधारी मैट्रिक्स प्राप्त करते हैं जिसके संगत हल प्रारम्भिक आधारी हल होगा।

प्रश्न:3.नवीन सारणी से इष्टतम हल प्राप्त न हो तो क्या करते हैं? (What Do You Do If the New Table Does Not Achieve the Optimum Solution?):

उत्तर:नवीन सिम्पलेक्स सारणी तैयार होने के पश्चात इष्टतम हल की जाँच करते हैं।यदि आधारी हल इष्टतम न हो तो पुनः नवीन सारणी (आगामी) तैयार करते हैं,इस प्रकार इष्टतम हल प्राप्त किया जा सकता है।
यदि निम्नतम मान अद्वितीय नहीं हो तो तब अगली सिम्पलेक्स सारणी से एक से अधिक चरों का मान शून्य (vanish) हो जायेगा।इसके फलस्वरूप अगली सारणी से प्राप्त हल अपभ्रष्ट आधारी सुसंगत हल (degenerate B.F.S.) होगी।ऐसी स्थिति में अपगामी सदिश के चयन की अलग विधि है।
उपर्युक्त प्रश्नों के उत्तर द्वारा रैखिक प्रोग्रामन समस्या की द्वैती लिखकर हल करें (Write Dual of LPP and Solve It),द्वैतता की सहायता से रैखिक प्रोग्रामन समस्या को हल करो (Use Duality to Solve Linear Programming Problems) के बारे में ओर अधिक जानकारी प्राप्त कर सकते हैं।

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

Write Dual of LPP and Solve It

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

Write Dual of LPP and Solve It

रैखिक प्रोग्रामन समस्या की द्वैती लिखकर हल करें (Write Dual of LPP and Solve It),
के इस आर्टिकल में आद्य समस्या की द्वैती लिखकर समस्या को हल करने का प्रयास करेंगे।

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.