रैखिक प्रोग्रामन समस्याओं के भिन्न प्रकार

रैखिक प्रोग्रामन, जिसे एलपी(LP) के रूप में भी संक्षिप्त किया जाता है, एक सरल विधि है जिसका उपयोग रैखिक फलन का उपयोग करके जटिल वास्तविक दुनिया के संबंधों को दर्शाने के लिए किया जाता है। इस प्रकार प्राप्त गणितीय प्रतिरूप में तत्वों का एक दूसरे के साथ रैखिक संबंध होता है। रैखिक प्रोग्रामन का उपयोग रैखिक अनुकूलन करने के लिए किया जाता है ताकि सर्वोत्तम परिणाम प्राप्त किया जा सके।

रैखिक प्रोग्रामन एक ऐसी प्रक्रिया है जिसका उपयोग रैखिक फलन के सर्वोत्तम परिणाम को निर्धारित करने के लिए किया जाता है। यह कुछ सरल धारणाएँ बनाकर रैखिक अनुकूलन करने का सबसे अच्छा उपाय है। रैखिक फलन को उद्देश्य फलन के रूप में जाना जाता है। वास्तविक दुनिया के संबंध बेहद जटिल हो सकते हैं। हालाँकि, रैखिक प्रोग्रामन का उपयोग ऐसे संबंधों को दर्शाने के लिए किया जा सकता है, जिससे उनका विश्लेषण करना आसान हो जाता है।

रैखिक प्रोग्रामन का उपयोग ऊर्जा, दूरसंचार, परिवहन और विनिर्माण जैसे कई उद्योगों में किया जाता है। यह लेख रैखिक प्रोग्रामन के विभिन्न पहलुओं जैसे परिभाषा, और इस तकनीक का उपयोग करके समस्याओं को हल करने के तरीके और संबंधित रैखिक प्रोग्रामन उदाहरणों पर प्रकाश डालता है।

रैखिक प्रोग्रामन परिभाषा

रैखिक प्रोग्रामन को एक ऐसी तकनीक के रूप में परिभाषित किया जा सकता है जिसका उपयोग किसी रैखिक फलन को अनुकूलित करने के लिए किया जाता है ताकि सर्वोत्तम परिणाम प्राप्त किया जा सके। इस रैखिक फलन या उद्देश्य फलन में रैखिक समानता और असमानता प्रतिबंध उपस्थित हैं। हम उद्देश्य फलन को न्यूनतम या अधिकतम करके सर्वोत्तम परिणाम प्राप्त करते हैं।

रैखिक प्रोग्रामन समस्याओं का हल

रैखिक प्रोग्रामन समस्या को हल करने का सबसे महत्वपूर्ण भाग पहले दिए गए आकड़ों का उपयोग करके समस्या को तैयार करना है। रैखिक प्रोग्रामन समस्याओं को हल करने के चरण नीचे दिए गए हैं:

• चरण 1: निर्णय चर की पहचान करें।
• चरण 2: उद्देश्य फलन व्यवस्थित करें। जाँच करें कि फलन को न्यूनतम या अधिकतम करने की आवश्यकता है या नहीं।
• चरण 3: प्रतिबंधों को लिखें।
• चरण 4: सुनिश्चित करें कि निर्णय चर $0$ से अधिक या बराबर हैं। (गैर-नकारात्मक प्रतिबंध)
• चरण 5: संकेतन या आलेखीय विधि का उपयोग करके रैखिक प्रोग्रामन समस्या को हल करें।

आइए हम निम्नलिखित अनुभागों में इन विधियों के बारे में विस्तार से अध्ययन करें।

रैखिक प्रोग्रामन विधियाँ

रैखिक प्रोग्रामन समस्या को हल करने के लिए दो मुख्य विधियाँ उपलब्ध हैं। ये हैं संकेतन विधि और आलेखीय विधि। नीचे दोनों विधियों का उपयोग करके रैखिक प्रोग्रामन समस्या को हल करने के चरण दिए गए हैं।

संकेतन(सिंप्लेक्स) विधि द्वारा रैखिक प्रोग्रामन

रैखिक प्रोग्रामन में संकेतन विधि को दो या अधिक निर्णय चर वाली समस्याओं पर लागू किया जा सकता है। मान लीजिए कि उद्देश्य फलन $Z=40x_{1}+30x_{2}$ को अधिकतम करने की आवश्यकता है और प्रतिबंध इस प्रकार दिए गए हैं:

$x_{1}+x_{2}\leq 12$

$2x_{1}+x_{2}\leq 16$

$x_{1}\geq 0,x_{2}\geq 0$

चरण 1: असमानताओं को समीकरणों में बदलने के लिए एक और चर जोड़ें, जिसे स्लैक चर के रूप में जाना जाता है। इसके अलावा, उद्देश्य फलन को समीकरण के रूप में फिर से लिखें।

$-40x_{1}-30x_{2}+Z=0$

$x_{1}+x_{2}+y_{1}=12$

$2x_{1}+x_{2}+y_{2}=16$

$y_{1}$ और $y_{2}$ स्लैक चर हैं।

चरण 2: प्रारंभिक संकेतन आव्यूह का निर्माण निम्नानुसार करें:

${\begin{bmatrix}x_{1}&x_{2}&y_{1}&y_{2}&Z\\1&1&1&0&0&12\\2&1&0&1&0&16\\-40&-30&0&0&1&0\end{bmatrix}}$

चरण 3: सबसे अधिक नकारात्मक प्रविष्टि वाले स्तम्भ की पहचान करें। इसे केन्द्र बिन्दु(पिवट) स्तम्भ कहा जाता है। चूँकि $-40$ सबसे अधिक नकारात्मक प्रविष्टि है, इसलिए स्तम्भ 1 केन्द्र बिन्दु स्तम्भ होगा।

चरण 4: सबसे दाएँ स्तम्भ की प्रविष्टियों को केन्द्र बिन्दु स्तम्भ की प्रविष्टियों से विभाजित करें। हम सबसे नीचे वाली पंक्ति की प्रविष्टियों को बाहर कर देते हैं।

$12/1=12$

$16/2=8$

केन्द्र बिन्दु पंक्ति प्राप्त करने के लिए सबसे छोटे भागफल वाली पंक्ति की पहचान की जाती है। चूँकि $8,12$ की तुलना में छोटा भागफल है, इसलिए पंक्ति 2 केन्द्र बिन्दु पंक्ति बन जाती है। केन्द्र बिन्दु पंक्ति और केन्द्र बिन्दु स्तम्भ का प्रतिच्छेदन केन्द्र बिन्दु तत्व देता है।

इस प्रकार, केन्द्र बिन्दु तत्व $=2$

चरण 5: केन्द्र बिन्दु तत्व की सहायता से आव्यूह गुणों का उपयोग करके पिवटिंग करें, ताकि केन्द्र बिन्दु स्तम्भ में अन्य सभी प्रविष्टियाँ $0$ हो जाएँ।

प्राथमिक संचालन का उपयोग करके पंक्ति 2 को 2 से विभाजित करें $(R_{2}/2)$

${\begin{bmatrix}x_{1}&x_{2}&y_{1}&y_{2}&Z\\1&1&1&0&0&12\\1&1/2&0&1/2&0&8\\-40&-30&0&0&1&0\end{bmatrix}}$

अब $R_{1}=R_{1}-R_{2}$ लागू करें

${\begin{bmatrix}x_{1}&x_{2}&y_{1}&y_{2}&Z\\0&1/2&1&-1/2&0&4\\1&1/2&0&1/2&0&8\\-40&-30&0&0&1&0\end{bmatrix}}$

अंत में $R_{3}=R_{3}+40R_{2}$ आवश्यक आव्यूह प्राप्त करने के लिए।

${\begin{bmatrix}x_{1}&x_{2}&y_{1}&y_{2}&Z\\0&1/2&1&-1/2&0&4\\1&1/2&0&1/2&0&8\\0&-10&0&20&1&320\end{bmatrix}}$चरण 6: जाँच करें कि क्या सबसे नीचे वाली पंक्ति में नकारात्मक प्रविष्टियाँ हैं। यदि नहीं, तो इष्टतम समाधान निर्धारित किया गया है। यदि हाँ, तो चरण 3 पर वापस जाएँ और प्रक्रिया को दोहराएँ। $-10$ आव्यूह में एक नकारात्मक प्रविष्टि है, इसलिए, प्रक्रिया को दोहराना आवश्यक है। हमें निम्नलिखित आव्यूह मिलता है।

${\begin{bmatrix}x_{1}&x_{2}&y_{1}&y_{2}&Z\\0&1&2&-1&0&8\\1&0&-1&1&0&4\\0&0&20&10&1&400\end{bmatrix}}$

नीचे की पंक्ति को समीकरण के रूप में लिखने पर हमें $Z=400-20$

$y_{1}-10y_{2}$ मिलता है। इस प्रकार, $400$ वह उच्चतम मान है जिसे $Z$ तब प्राप्त कर सकता है जब $y_{1}$और $y_{2}$ दोनों $0$ हों।

साथ ही, जब $x_{1}=4$ और $x_{2}=8$ हो तो $Z$ का मान $=400$

इस प्रकार, $x_{1}=4$ और $x_{2}=8$ इष्टतम बिंदु हैं और हमारी रैखिक प्रोग्रामन समस्या का समाधान है।

आलेखीय विधि द्वारा रैखिक प्रोग्रामन

यदि किसी रैखिक प्रोग्रामन समस्या में दो निर्णय चर हैं, तो ऐसी समस्या को हल करने के लिए आलेखीय विधि का उपयोग आसानी से किया जा सकता है।

मान लीजिए हमें $Z=2x+5y$ को अधिकतम करना है।

$x+4y\leq 24,3x+y\leq 21$ और $x+y\leq 9$ प्रतिबंध हैं।

जहाँ, $x\geq 0$ और $y\geq 0$

इस समस्या को आलेखीय विधि का उपयोग करके हल करने के लिए निम्नलिखित चरण हैं।

चरण 1: सभी असमानता प्रतिबंधों को समीकरणों के रूप में लिखें।

$x+4y=24$

$3x+y=21$

$x+y=9$

चरण 2: परीक्षण बिंदुओं की पहचान करके इन रेखाओं को ग्राफ पर अंकित करें।

$x+4y=24$ एक रेखा है जो $(0,6)$ और $(24,0)$ से होकर गुजरती है। [$x=0$ प्रतिस्थापित करने पर बिंदु $(0,6)$ प्राप्त होता है। इसी प्रकार, जब $y=0$ होता है तो बिंदु $(24,0)$ निर्धारित होता है।]

$3x+y=21$ , $(0,21)$ और $(7,0)$ से होकर गुजरता है।

$x+y=9$, $(9,0)$ और $(0,9)$ से होकर गुजरता है।

चरण 3: सुसंगत क्षेत्र की पहचान करें। सुसंगत क्षेत्र को उस क्षेत्र के रूप में परिभाषित किया जा सकता है जो निर्देशांकों के एक समूह से घिरा होता है जो असमानताओं की कुछ विशेष प्रणाली को संतुष्ट कर सकता है।

कोई भी बिंदु जो रेखा $x+4y=24$ पर या उसके नीचे स्थित है, वह $x+4y\leq 24$की बाध्यता को संतुष्ट करेगा।

इसी तरह, $3x+y=21$ पर या उसके नीचे स्थित एक बिंदु $3x+y\leq 21$ को संतुष्ट करता है।

साथ ही, रेखा $x+y=9$ पर या उसके नीचे स्थित एक बिंदु $x+y\leq 9$ को संतुष्ट करता है।

सुसंगत क्षेत्र को $OABCD$ द्वारा दर्शाया जाता है क्योंकि यह उपर्युक्त तीनों प्रतिबंधों को संतुष्ट करता है।

आलेखीय विधि द्वारा रैखिक प्रोग्रामन

चरण 4: कोने के बिंदुओं के निर्देशांक निर्धारित करें। कोने के बिंदु संभव क्षेत्र के शीर्ष हैं।

$O=(0,0)$

$A=(7,0)$

$B=(6,3)$ ; $B$ दो रेखाओं $3x+y=21$ और $x+y=9$ का प्रतिच्छेद बिंदु है। इस प्रकार,$3x+y=21$ में $y=9-x$ प्रतिस्थापित करके हम प्रतिच्छेद बिंदु निर्धारित कर सकते हैं।

$C=(4,5)x+4y=24$और $x+y=9$ के प्रतिच्छेद द्वारा गठित

$D=(0,6)$

चरण 5: उद्देश्य फलन में प्रत्येक कोने बिंदु को प्रतिस्थापित करें। वह बिंदु जो उद्देश्य फलन का सबसे बड़ा (अधिकतम) या सबसे छोटा (न्यूनतम) मान देता है, वह इष्टतम बिंदु होगा।

कोने बिंदु	$Z=2x+5y$
O = (0, 0)	0
A = (7, 0)	14
B = (6, 3)	27
C = (4, 5)	33
D = (0, 6)	30

$33,Z$ का अधिकतम मान है और यह $C$ पर होता है। इस प्रकार, हल $x=4$ और $y=5$ है।