Solve LPP by Writing Its Dual

Q: प्रश्न:1.निम्नतमीकरण की रैखिक प्रोग्रामन समस्याओं को द्वैती समस्या में कैसे परिवर्तित करते हैं? (How Do Linear Programming Problems of Minimization Turn into Dual Problem?):

उत्तर:निम्नतम करो: Z=\left(c_1 c_2 \ldots \ldots c_n\right)\left[\begin{array}{l} x_1 \\ x_2 \\ \vdots \\ x_n \end{array}\right] प्रतिबन्ध \left[\begin{array}{ccc} a_{11} & a_{12} & a_{1 n} \\ a_{21} & a_{22} & a_{2 n} \\ \vdots & \vdots & \vdots \\ a_{m 1} & a_{m 2} & a_{m n} \end{array}\right] \left[\begin{array}{c} x_1 \\ x_2 \\ \vdots \\ x_n \end{array}\right] \geq \left[\begin{array}{c} b_1 \\ b_2 \\ \vdots \\ b_n \end{array}\right] तथा x_{1}, x_2 \ldots x_n \geq 0 इस आद्य समस्या को संक्षिप्त रूप में निम्न प्रकार से व्यक्त कर सकते हैं: निम्नतम करो:Z=CX प्रतिबन्ध A X \geq b \\ X \geq 0 आद्य रैखिक प्रोग्रामन समस्या की द्वैती समस्या निम्न प्रकार परिभाषित करते हैं: अधिकतम करो: Z_D=\left(b_1 b_2,\ldots , b_m\right)\left[\begin{array}{l}w_1 \\ w_2 \\ \vdots \\ w_n \end{array}\right] प्रतिबन्ध \left[\begin{array}{cccc}a_{11} & a_{21} & \ldots & a_{m 1} \\ a_{12} & a_{22} & \ldots & a_{m 2} \\ \vdots & \vdots & \vdots & \vdots \\ a_{1 n} & a_{2n} & \ldots & a_{mn}\end{array}\right]\left[\begin{array}{c}w_1 \\ w_2 \\ \vdots \\ w_m \end{array}\right] \leq\left[\begin{array}{c}C_1 \\ C_2 \\ \vdots \\ C_m \end{array}\right] तथा w_1, w_2 \ldots w_n \geq 0 अथवा अधिकतम करो: Z_b=b^{T} w प्रतिबन्ध A^T W \leq C^T \\ W \geq 0

Q: प्रश्न:3.कब और क्यों कृत्रिम चर का उपयोग करते हैं? (When and Why artificial variable is used?):

उत्तर:यदि इकाई मैट्रिक्स I_m=\left(e_1 e_2 \ldots e_m\right) का कोई सदिश पहिले से ही विद्यमान हो तो उस समीकरण में कृत्रिम चर नहीं जोड़ते।कृत्रिम चरों को केवल इकाई सदिश e_1, e_2, \ldots, e_m प्राप्त करने के लिए जोड़ते हैं,जिन्हें एक-एक करके निकाय में से बाहर निकालते हैं।अतः रैखिक प्रोग्रामन समस्या के उद्देश्य फलन में इन चरों के संगत मूल्य -M लिये जाते हैं,जहाँ M एक बहुत बड़ी धनात्मक संख्या होती है।इस विधि को चार्नस बड़ा M-विधि (Charnes Big M-method) भी कहते हैं। उपर्युक्त प्रश्नों के उत्तर द्वारा रैखिक प्रोग्रामन समस्या की द्वैती लिखकर उसे हल करें (Solve LPP by Writing Its Dual),द्वैतता की सहायता से रैखिक प्रोग्रामन समस्या को हल करो (Use Duality to Solve LPP) के बारे में ओर अधिक जानकारी प्राप्त कर सकते हैं।

Mathematics Satyam June 4, 2024 Linear Programming No Comments

Contents hide

1 1.रैखिक प्रोग्रामन समस्या की द्वैती लिखकर उसे हल करें (Solve LPP by Writing Its Dual),द्वैतता की सहायता से रैखिक प्रोग्रामन समस्या को हल करो (Use Duality to Solve LPP):

1.1 2.रैखिक प्रोग्रामन समस्या की द्वैती लिखकर उसे हल करें के उदाहरण (Solve LPP by Writing Its Dual Examples):

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

1.2.1 प्रश्न:1.निम्नतमीकरण की रैखिक प्रोग्रामन समस्याओं को द्वैती समस्या में कैसे परिवर्तित करते हैं? (How Do Linear Programming Problems of Minimization Turn into Dual Problem?):

1.2.2 प्रश्न:2.कृत्रिम चर को परिभाषित कीजिए। (Define artificial variable):

1.2.3 प्रश्न:3.कब और क्यों कृत्रिम चर का उपयोग करते हैं? (When and Why artificial variable is used?):

1.2.3.1 Solve LPP by Writing Its Dual

2 रैखिक प्रोग्रामन समस्या की द्वैती लिखकर उसे हल करें (Solve LPP by Writing Its Dual)

2.1 Solve LPP by Writing Its Dual

1.रैखिक प्रोग्रामन समस्या की द्वैती लिखकर उसे हल करें (Solve LPP by Writing Its Dual),द्वैतता की सहायता से रैखिक प्रोग्रामन समस्या को हल करो (Use Duality to Solve LPP):

Solve LPP by Writing Its Dual

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

Also Read This Article:- Solve Dual of LPP

2.रैखिक प्रोग्रामन समस्या की द्वैती लिखकर उसे हल करें के उदाहरण (Solve LPP by Writing Its Dual Examples):

निम्न रैखिक प्रोग्रामन समस्याओं को उनकी द्वैत सिद्धान्त के प्रयोग से हल कीजिए:
(Use duality to solve the following L. P. P.’s):
Example:11.निम्नतम करो (min.) $\min Z=3 x_1-2 x_2+4 x_3$
प्रतिबन्ध (s.t.) $3 x_1+5 x_2+4 x_3 \geq 7 \\ 6 x_1+x_2+3 x_3 \geq 4 \\ 4 x_1-2 x_2-x_3 \leq 10 \\ x_1-2 x_2+5 x_3 \geq 3 \\ 4 x_1+7 x_2-2 x_3 \geq 2$
तथा (and) $x_1, x_2, x_3 \geq 0$
Solution:आद्य समस्या मानक रूप में नहीं है,इसलिए सर्वप्रथम इस आद्य समस्या को मानक रूप में निम्न प्रकार लिखते हैं:
निम्नतम करो: $Z=3 x_1-2 x_2+4 x_3$
प्रतिबन्ध $3 x_1+5 x_2+3 x_3 \geq 7 \\ 6 x_1+x_2+3 x_3 \geq 4 \\ -7 x_1+2 x_2+x_3 \geq-10 \\ x_1-2 x_2+5 x_3 \geq 3 \\ 4 x_1+7 x_2-2 x_3 \geq 2$
तथा (and) $x_1, x_2, x_3 \geq 0$
अब यह समस्या अपने मानक रूप में है।इसकी द्वैती समस्या निम्न प्रकार होगी:
अधिकतम करो: $Z_D=7w_1+4 w_2-10 w_3+3w_4+2 w_5$
प्रतिबन्ध $3 w_1+6 w_2-7 w_3+w_4+4 w_5 \leq 3 \\ 5 w_1+ w_2+2 w_3-2 w_4+7w_5 \leq-2 \Rightarrow-5 w_1-w_2-2 w_3+2 w_4-7w_{5} \geq 2 \\ 3 w_1+3w_2 +w_3+5 w_4-2 w_5 \leq 4$
तथा $w_1, w_2, w_3, w_4, w_5 \geq 0$
इस द्वैती समस्या को सिम्पलेक्स विधि से हल करने के लिए हमें प्रतिबन्ध निकाय को समीकरणों में परिवर्तित करना होगा।और $w_6,w_8$ दो न्यूनतापूरक चर, $w_7$ एक आधिक्यपूरक चर एवं $w_9$ एक कृत्रिम चर सम्मिलित करने पर समस्या का परिवर्तित मानक रूप निम्न प्रकार है:

अधिकतम करो: $Z_D=7w_1+4 w_2-10 w_3+3 w_4+2 w_5 +0 w_6+0 w_7+0 w_8-M w_9$
प्रतिबन्ध $3 w_1+6 w_2-7 w_3+w_4+4 w_5+ w_6+0 w_7+0 w_8+0 w_9=3 \\ -5w_1-w_2-2 w_3+2 w_4-7 w_5+0 w_6-w_7+0 w_8+w_9=2 \\ 4 w_1+3 w_2+w_3+5 w_4-2 w_5+0 w_6+0 w_7+ w_8+0 w_9=4$
तथा $w_1, w_2, w_3, w_4, w_5, w_6, w_7, w_8, w_9 \geq 0$
उद्देश्य फलन में कृत्रिम चर $w_9$ का मूल्य -M लेते हैं जहाँ M एक बहुत बड़ी धनात्मक संख्या है।
अब प्रतिबन्धों निकाय में गुणांक मैट्रिक्स
$A= \left[\begin{array}{ccccccccc} 3 & 6 & -7 & 1 & 4 & 1 & 0 & 0 & 0 \\ -5 & -1 & -2 & 2 & -7 & 0 & -1 & 0 & 1 \\ 4 & 3 & 1 & 5 & -2 & 0 & 0 & 1 & 0\end{array}\right]=\left( \alpha_1 \alpha_2 \alpha_3 \alpha_4 \alpha_5 \alpha_6 \alpha_7 \alpha_8 \alpha_9 \right)$ (माना)
यहाँ प्रारम्भिक आधार मैट्रिक्स $B=\left(\alpha_6 \alpha_9 \alpha_8 \right)=I_3$ लेने पर,प्रारम्भिक सिम्पलेक्स सारणी निम्न प्रकार है:
प्रथम सिम्पलेक्स सारणी

$\begin{array}{|ccc|c|ccccccccc|} \hline & & & C_{i} \rightarrow & 7 & 4 & -10 & 3 & 2 & 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 & y_8 & y_9 \\ \hline 0 & \alpha_6 & w_6 & 3 & 3 & 6 & -7 & 1 & 4 & 1 & 0 & 0 & 0 \\ 0 & \alpha_9 & w_9 & 2 & -5 & -1 & -2 & 2 & -7 & 0 & -1 & 0 & 1 \\ 0 & \alpha_8 & w_8 & 4 & 4 & 3 & 1 & \fbox{5} & 2 & 0 & 0 & 1 & 0 \\ \hline & & & Z_{j}-C_{j}\rightarrow & -5M-7 & M-4 & 2M+10 & -2M-3 & 7M-2 & 0 & M & 0 & 0 \\ \hline & & & & & & & \uparrow & & & & \downarrow & \end{array}$
अतः प्रथम सिम्पलेक्स सारणी से स्पष्ट है कि प्रारम्भिक आधार इष्टतम हल नहीं है,क्योंकि $Z_j-C_j$ के मान ऋणात्मक है i.e. $Z_4-C_4=-2M-3$ जो कि न्यूनतम राशि है तथा यह मान चतुर्थ स्तम्भ में है,इसलिए $\alpha_4$ प्रवेशी सदिश है।
पुनः $\underset{i}{\text{निम्नतम}}\left\{\frac{w_{B i}}{y_{i 4}}, y_{i 4}>0\right\}= \underset{i}{\text{निम्नतम}}\left\{\frac{3}{1},\frac{2}{2},\frac{4}{5} \right\} \\ =\frac{4}{5} =\frac{W_{B3}}{y_{34}}$
अतः $y_{34}$ अर्थात् 5 मुख्य अवयव (key element) तथा $\alpha_8$ अपगामी सदिश (departing vector) होगा।अब सामान्य रूपान्तरणों से नवीन सारणी निम्न प्रकार होगी:
तृतीय पंक्ति (मुख्य अवयव वाली पंक्ति) (working rule):
तृतीय पंक्ति मुख्य अवयव वाली पंक्ति है।अतः इसे तैयार करने हेतु प्रथम सारणी की तृतीय पंक्ति के प्रत्येक अवयव में मुख्य अवयव 5 का भाग देने पर द्वितीय सारणी की तृतीय पंक्ति तैयार होगी:

$\frac{4}{5}, \frac{4}{5}, \frac{3}{5}, \frac{1}{5}, \frac{5}{5}=1, \frac{2}{5}, \frac{0}{5}=0, \frac{0}{5}=0, \frac{1}{5}=\frac{0}{5}=0$
प्रथम पंक्ति:द्वितीय सारणी की प्रथम पंक्ति को तैयार करने के लिए प्रथम सारणी की प्रथम पंक्ति के प्रत्येक अवयव में से मुख्य अवयव वाली पंक्ति के अवयवों अर्थात् उपर्युक्त अवयवों को मुख्य अवयव के संगत अवयव 1 से गुणा करके घटा देंगे:
$3-\frac{4}{5} \times 1=\frac{11}{5}, 3-\frac{4}{5} \times 1=\frac{11}{5}, 6-\frac{3}{5} \times 1=\frac{27}{5},-7-\frac{1}{5} \times 1=\frac{-36}{5}, 1-1 \times 1=0,4-\left(-\frac{2}{5}\right) \times 1=\frac{22}{5}, 1-0 \times 1=1,0-0 \times 1=0,0-\frac{1}{5} \times 1=-\frac{1}{5} ,0-0 \times 1=0$
द्वितीय पंक्ति:द्वितीय सारणी की द्वितीय पंक्ति को तैयार करने के लिए प्रथम सारणी की द्वितीय पंक्ति के प्रत्येक अवयव में से मुख्य अवयव वाली पंक्ति के अवयवों को मुख्य अवयव के संगत अवयव 2 से गुणा करके घटा देंगे:
$2-\frac{4}{5} \times 2=\frac{2}{5},-5-\frac{4}{5} \times 2=-\frac{33}{5},-1 - \frac{3}{5} \times 2 =-\frac{11}{5},-2 -\frac{1}{5} \times 2=-\frac{12}{5},2-1 \times 2=0,7-\left(-\frac{2}{5}\right) \times 2=-\frac{31}{5}, 0-0 \times 2=0,-1-0 \times 2=-1, 0-\frac{1}{5} \times 2=-\frac{2}{5}, 1-0 \times 2=1$
द्वितीय सिम्पलेक्स सारणी

$\begin{array}{|ccc|c|ccccccccc|} \hline & & & C_{i} \rightarrow & 7 & 4 & -10 & 3 & 2 & 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 & y_8 & y_9 \\ \hline 0 & \alpha_6 & w_6 & \frac{11}{5} & \frac{11}{5} & \frac{27}{5} & \frac{-36}{5} & 0 & \frac{22}{5} & 1 & 0 & -\frac{1}{5} & 0 \\ -M & \alpha_9 & w_9 & \frac{2}{5} &-\frac{33}{5} & -\frac{11}{5} &-\frac{12}{5} & 0 & -\frac{31}{5} & 0 &-1 & -\frac{2}{5} & 1 \\ 3 & \alpha_4 & w_4 & \frac{4}{5} & \frac{4}{5} & \frac{3}{5} & \frac{1}{5} & 1 & -\frac{2}{5} & 0 & 0 & \frac{1}{5} & 0 \\ \hline & & & Z_{j}-C_{j}\rightarrow & \frac{33}{5}M-\frac{23}{5} & \frac{11}{5}M-\frac{11}{5} & \frac{12}{5}M+\frac{53}{5} & 0 & \frac{31}{5}M-\frac{16}{5} & 0 & M & \frac{2}{5}M+\frac{3}{5} & 0 \\ \hline \end{array}$
चूँकि इस सारणी में $Z_j-C_j \geq 0$ ,j के सभी मानों के लिए (j=1,2,3,……,9),अतः हल इष्टतम होना चाहिए,परन्तु इसके आधारी हल में एक कृत्रिम चर $\alpha_9$ है जिसका मान शून्य नहीं है।इसलिए इस समस्या का कोई सुसंगत हल नहीं है।अतः आद्य समस्या का कोई भी परिमित इष्टतम हल नहीं होगा।

Solve LPP by Writing Its Dual

Example:12.निम्नतम करो (min.): $Z=3 x_1+2 x_2 +x_3+4 x_4$
प्रतिबन्ध (s.t.) $2 x_1+4 x_2+5 x_3+x_4 \geq 10 \\ 3 x_1+x_2+7 x_3-2 x_4 \geq 2 \\ 5 x_1+2 x_2+x_3+6 x_4 \geq 15$
तथा (and) $x_1, x_2, x_3, x_4 \geq 0$
Solution:दी गई आद्य समस्या मानक रूप में है,अतः इसकी द्वैती निम्न प्रकार होगी:
अधिकतम करो: $Z_D=10 w_1+2 w_2+15 w_3$
प्रतिबन्ध $2 w_1+3 w_2+5 w_3 \leq 3 \\ 4 w_1+w_2+2 w_3 \leq 2 \\ 5 w_1+7 w_2+w_3 \leq 1 \\ w_1-2 w_2+6 w_3 \leq 4$
तथा $w_1, w_2, w_3 \geq 0$
प्रतिबन्ध को समीकरणों में परिवर्तन करने हेतु $w_4, w_5,w_6$ तथा $w_7$ न्यूनतापूरक चरों का समावेश करने पर उपर्युक्त द्वैत समस्या निम्नांकित है:
अधिकतम करोः $Z_D=10 w_1+2 w_2+15 w_3+0 w_4+0 w_5+0 w_6+0 w_7$
प्रतिबन्ध $2 w_1+3 w_2+5 w_3+w_4+0 w_5+0 w_6+0 w_7=3 \\ 4 w_1+w_2+2 w_3+0 w_4+w_5+0 w_6+0 w_7=2 \\ 5 w_1+7 w_2+w_3+0 w_4+0 w_5+w_6+0 w_7=1 \\ w_1-2 w_2+6 w_3+0 w_4+0 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} 2 & 3 & 5 & 1 & 0 & 0 & 0 \\ 4 & 1 & 2 & 0 & 1 & 0 & 0 \\ 5 & 7 & 1 & 0 & 0 & 1 & 0 \\ 1 & -2 & 6 & 0 & 0 & 0 & 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_6 \alpha_7 \right)=I_4$ लेने पर,प्रारम्भिक सिम्पलेक्स सारणी निम्न प्रकार है:
प्रथम सिम्पलेक्स सारणी

$\begin{array}{|ccc|c|ccccccc|} \hline & & & C_{i} \rightarrow & 10 & 2 & 15 & 0 & 0 & 0 & 0 \\ \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 & 3 & 2 & 3 & \fbox{5} & 1 & 0 & 0 & 0 \\ 0 & \alpha_5 & w_5 & 2 & 4 & 1 & 2 & 0 & 1 & 0 & 0 \\ 0 & \alpha_6 & w_6 & 1 & 5 & 7 & 1 & 0 & 0 & 1 & 0 \\ 0 & \alpha_7 & w_7 & 4 & 1 & -2 & 6 & 0 & 0 & 0 & 1 \\ \hline & & & Z_{j}-C_{j}\rightarrow & -10 & -2 & -15 & 0 & 0 & 0 & 0 \\ \hline \end{array}$
अतः प्रथम सिम्पलेक्स सारणी से स्पष्ट है कि प्रारम्भिक आधार इष्टतम हल नहीं है,क्योंकि $Z_j-C_j$ के मान ऋणात्मक हैं i.e. $Z_3-C_3=-15$ जो कि न्यूनतम राशि है तथा यह मान तृतीय स्तम्भ में है,इसलिए $\alpha_3$ प्रवेशी सदिश है।
पुनः $\underset{i}{\text{निम्नतम}}\left\{\frac{w_{B i}}{y_{i3}}, y_{i3}>0\right\}=\underset{i}{\text{निम्नतम}} \left\{\frac{3}{5},\frac{2}{2},\frac{1}{1},\frac{4}{6} \right\} \\ =\frac{3}{5} =\frac{W_{B1}}{y_{13}}$
अतः $y_{13}$ अर्थात् 5 मुख्य अवयव (key element) तथा $\alpha_4$ अपगामी सदिश (departing vector) होगा।अब सामान्य रूपान्तरणों से नवीन सारणी निम्न प्रकार होगी:
द्वितीय सिम्पलेक्स सारणी

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

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

$w_1=\frac{2}{23}, w_2=0, w_3=\frac{13}{23}$
तथा अधिकतम $Z_D=10 w_1+2 w_1+15 w_3 \\ =10 \times \frac{2}{23}+2 \times 0+15 \times 13 \\ =\frac{20}{23}+\frac{195}{23} \\ \Rightarrow \max Z_D =\frac{215}{23}$
तथा $x_1=z_4-c_4=\frac{65}{23}, x_2=z_5-c_5=0 ,x_3=z_6-c_6=\frac{20}{23}, x_4=z_7-c_7=0$
न्यूनतम $Z=\frac{215}{23}$
Example:13.निम्नतम करो (min.): $\min Z=6 x_1+12 x_2$
प्रतिबन्ध (s.t.) $x_1+4 x_2 \geq 7 \\ 2 x_1+3 x_2 \geq 5$
तथा (and) $x_1, x_2 \geq 0$
Solution:दी गई आद्य समस्या मानक रूप में है,अतः इसकी द्वैती निम्न प्रकार होगी:
अधिकतम करो: $Z_D=7 w_1+5 w_2$
प्रतिबन्ध $w_1+2 w_2 \leq 6 \\ 4 w_1+3 w_2 \leq 12$
तथा $w_1,w_2 \geq 0$
प्रतिबन्ध को समीकरणों में परिवर्तन करने हेतु $w_3$ तथा $w_4$ न्यूनतापूरक चरों का समावेश करने पर उपर्युक्त द्वैत समस्या निम्नांकित है:
अधिकतम करोः $Z_D=7 w_1+5 w_2+0 w_3+0 w_4$
प्रतिबन्ध $w_1+2 w_2+w_3+0 w_4 =6 \\ 4 w_1+3 w_2+0 w_3+w_4=12$
तथा $w_1, w_2, w_3, w_4 \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(\alpha_3 \alpha_4\right)=I_2$ लेने पर,प्रारम्भिक सिम्पलेक्स सारणी निम्न प्रकार है:
प्रथम सिम्पलेक्स सारणी

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

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

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

$w_1=3, w_2=0$
तथा अधिकतम $Z_D=7 w_1+5 w_2 \\ =7 \times 3+5 \times 0 \\ \Rightarrow \max Z_D=21$
तथा $x_1=z_3-c_3=0, x_2=z_4-c_4=\frac{7}{4}$
न्यूनतम Z=21
Example:14.निम्नतम करो (min.): $Z=50 x_1-80 x_2-140 x_3$
प्रतिबन्ध (s.t.) $x_1-x_2-3 x_3 \geq 4 \\ x_1-2 x_2-2 x_3 \geq 3$
तथा (and) $x_1, x_2, x_3 \geq 0$
Solution:दी गई आद्य समस्या मानक रूप में है,अतः इसकी द्वैती निम्न प्रकार होगी:
अधिकतम करो: $Z_D=4 w_1+3 w_2$
प्रतिबन्ध $w_1+w_2 \leq 50 \\ -w_1-2 w_2 \leq-80 \Rightarrow w_1+2 w_2 \geq 80 \\ -3 w_1-2 w_2 \leq-140 \Rightarrow 3 w_1+2 w_2 \geq 140$
तथा $w_1, w_2 \geq 0$
इस द्वैती समस्या को सिम्पलेक्स विधि से हल करने के लिए हमें प्रतिबन्ध निकाय को समीकरणों में परिवर्तित करना होगा। $w_3$ न्यूनतापूरक चर, $w_4$ तथा $w_5$ दो आधिक्यपूरक चर एवं $w_6$ तथा $w_7$ दो कृत्रिम चर सम्मिलित करने पर समस्या का परिवर्तित मानक रूप निम्न प्रकार है:
अधिकतम करो: $Z_D=4 w_1+3 w_2+0 w_3+0 w_4+0 w_5-M w_6-M w_7$
प्रतिबन्ध $w_1+w_2+w_3+0 w_4+0 w_5+0 w_6+0 w_7=50 \\ w_1+2 w_2+u w_3-w_4+0 w_5+w_6+0 w_7=80 \\ 3 w_1+2 w_2+u w_3+0 w_4-w_5+0 w_6+w_7=140$
तथा $w_1, w_2, w_3, w_4, w_5, w_6, w_7 \geq 0$
उद्देश्य फलन में कृत्रिम चर $w_6$ व $w_7$ का मूल्य -M लेते हैं जहाँ M एक बहुत बड़ी धनात्मक संख्या है।
प्रतिबन्धों का गुणांक मैट्रिक्स
$A=\left[\begin{array}{ccccccc} 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 2 & 0 & -1 & 0 & 1 & 0 \\ 3 & 2 & 0 & 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_3 \alpha_6 \alpha_7\right)=I_3$ अतः प्रथम सिम्पलेक्स सारणी निम्न प्रकार है:
प्रथम सिम्पलेक्स सारणी

$\begin{array}{|ccc|c|ccccccc|} \hline & & & C_{i} \rightarrow & 4 & 3 & 0 & 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 0 & \alpha_3 & w_3 & 50 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ -M & \alpha_6 & w_6 & 80 & 1 & 2 & 0 & -1 & 0 & 1 & 0 \\ -M & \alpha_7 & w_7 & 140 & \fbox{3} & 2 & 0 & 0 & -1 & 0 & 1 \\ \hline & & & Z_{j}-C_{j}\rightarrow & -4M-4 & -4M-3 & 0 & M & M & 0 & 0 \\ \hline & & & & \uparrow & & & & & & \downarrow \end{array}$
अतः प्रथम सिम्पलेक्स सारणी से स्पष्ट है कि प्रारम्भिक आधार इष्टतम हल नहीं है,क्योंकि $Z_j-C_j$ के मान ऋणात्मक हैं i.e. $Z_1-C_1=-4M-4$ जो कि न्यूनतम राशि है तथा यह मान प्रथम स्तम्भ में है,इसलिए $\alpha_1$ प्रवेशी सदिश है।
पुनः $\underset{i}{\text{निम्नतम}}\left\{\frac{w_{B i}}{y_{i 1}}, y_{i 1}>0\right\}=\underset{i}{\text{निम्नतम}} \left\{ \frac{50}{2},\frac{80}{1},\frac{140}{3} \right\} \\ =\frac{140}{3}=\frac{W_{B3}}{y_{31}}$
अतः $y_{31}$ अर्थात् 3 मुख्य अवयव (key element) तथा $\alpha_7$ अपगामी सदिश (departing vector) होगा। $\alpha_7$ कृत्रिम चर है अतः इसे नवीन सारणी में शामिल नहीं करेंगे।अब सामान्य रूपान्तरणों से नवीन सारणी निम्न प्रकार होगी:
द्वितीय सिम्पलेक्स सारणी

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

$\begin{array}{|ccc|c|cccccc|} \hline & & & C_{i} \rightarrow & 4 & 3 & 0 & 0 & 0 & -M \\ \hline C_{B} & B & X_B & b & y_1 & y_2 & y_3 & y_4 & y_5 & y_6 \\ \hline 3 & \alpha_2 & w_2 & 10 & 0 & 1 & 3 & 0 & 1 & 0 \\ -M & \alpha_6 & w_6 & 20 & 0 & 0 & -4 & -1 & -1 & 1 \\ 4 & \alpha_1 & w_1 & 40 & 1 & 0 & -2 & 0 & -1 & 0 \\ \hline & & & Z_{j}-C_{j}\rightarrow & 0 & 0 & 4 M+1 & M & M-1 & 0 \\ \hline \end{array}$
चूँकि इस सारणी में $Z_j-C_j \geq 0$ ,j के सभी मानों के लिए (j=1,2,3,……,6),अतः हल इष्टतम होना चाहिए,परन्तु इसके आधारी हल में एक कृत्रिम चर $\alpha_6$ है जिसका मान शून्य नहीं है।इसलिए इस समस्या का कोई सुसंगत हल नहीं है।अतः आद्य समस्या का कोई भी परिमित इष्टतम हल नहीं होगा।
उपर्युक्त उदाहरणों के द्वारा रैखिक प्रोग्रामन समस्या की द्वैती लिखकर उसे हल करें (Solve LPP by Writing Its Dual),द्वैतता की सहायता से रैखिक प्रोग्रामन समस्या को हल करो (Use Duality to Solve LPP) को समझ सकते हैं।

Solve LPP by Writing Its Dual

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

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

प्रश्न:1.निम्नतमीकरण की रैखिक प्रोग्रामन समस्याओं को द्वैती समस्या में कैसे परिवर्तित करते हैं? (How Do Linear Programming Problems of Minimization Turn into Dual Problem?):

उत्तर:निम्नतम करो: $Z=\left(c_1 c_2 \ldots \ldots c_n\right)\left[\begin{array}{l} x_1 \\ x_2 \\ \vdots \\ x_n \end{array}\right]$
प्रतिबन्ध $\left[\begin{array}{ccc} a_{11} & a_{12} & a_{1 n} \\ a_{21} & a_{22} & a_{2 n} \\ \vdots & \vdots & \vdots \\ a_{m 1} & a_{m 2} & a_{m n} \end{array}\right] \left[\begin{array}{c} x_1 \\ x_2 \\ \vdots \\ x_n \end{array}\right] \geq \left[\begin{array}{c} b_1 \\ b_2 \\ \vdots \\ b_n \end{array}\right]$
तथा $x_{1}, x_2 \ldots x_n \geq 0$
इस आद्य समस्या को संक्षिप्त रूप में निम्न प्रकार से व्यक्त कर सकते हैं:
निम्नतम करो:Z=CX
प्रतिबन्ध $A X \geq b \\ X \geq 0$
आद्य रैखिक प्रोग्रामन समस्या की द्वैती समस्या निम्न प्रकार परिभाषित करते हैं:
अधिकतम करो: $Z_D=\left(b_1 b_2,\ldots , b_m\right)\left[\begin{array}{l}w_1 \\ w_2 \\ \vdots \\ w_n \end{array}\right]$
प्रतिबन्ध $\left[\begin{array}{cccc}a_{11} & a_{21} & \ldots & a_{m 1} \\ a_{12} & a_{22} & \ldots & a_{m 2} \\ \vdots & \vdots & \vdots & \vdots \\ a_{1 n} & a_{2n} & \ldots & a_{mn}\end{array}\right]\left[\begin{array}{c}w_1 \\ w_2 \\ \vdots \\ w_m \end{array}\right] \leq\left[\begin{array}{c}C_1 \\ C_2 \\ \vdots \\ C_m \end{array}\right]$
तथा $w_1, w_2 \ldots w_n \geq 0$
अथवा
अधिकतम करो: $Z_b=b^{T} w$
प्रतिबन्ध $A^T W \leq C^T \\ W \geq 0$

प्रश्न:2.कृत्रिम चर को परिभाषित कीजिए। (Define artificial variable):

उत्तर:सरलतम आधार प्राप्त करने हेतु हम प्रत्येक प्रतिबन्ध समीकरण में एक चर जिसे कृत्रिम चर कहते हैं,जोड़ते हैं।

प्रश्न:3.कब और क्यों कृत्रिम चर का उपयोग करते हैं? (When and Why artificial variable is used?):

उत्तर:यदि इकाई मैट्रिक्स $I_m=\left(e_1 e_2 \ldots e_m\right)$ का कोई सदिश पहिले से ही विद्यमान हो तो उस समीकरण में कृत्रिम चर नहीं जोड़ते।कृत्रिम चरों को केवल इकाई सदिश $e_1, e_2, \ldots, e_m$ प्राप्त करने के लिए जोड़ते हैं,जिन्हें एक-एक करके निकाय में से बाहर निकालते हैं।अतः रैखिक प्रोग्रामन समस्या के उद्देश्य फलन में इन चरों के संगत मूल्य -M लिये जाते हैं,जहाँ M एक बहुत बड़ी धनात्मक संख्या होती है।इस विधि को चार्नस बड़ा M-विधि (Charnes Big M-method) भी कहते हैं।
उपर्युक्त प्रश्नों के उत्तर द्वारा रैखिक प्रोग्रामन समस्या की द्वैती लिखकर उसे हल करें (Solve LPP by Writing Its Dual),द्वैतता की सहायता से रैखिक प्रोग्रामन समस्या को हल करो (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 LPP by Writing Its Dual

रैखिक प्रोग्रामन समस्या की द्वैती
लिखकर उसे हल करें
(Solve LPP by Writing Its Dual)

Solve LPP by Writing Its Dual

रैखिक प्रोग्रामन समस्या की द्वैती लिखकर उसे हल करें (Solve LPP by Writing Its Dual),के
इस आर्टिकल में द्वैतता के सिद्धान्त के आधार पर सवालों को हल करके समझने का प्रयास करेंगे।

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.