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

रैखिक प्रोग्रामन, जिसे एलपी(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$ आव्यूह में एक नकारात्मक प्रविष्टि है, इसलिए, प्रक्रिया को दोहराना आवश्यक है। हमें निम्नलिखित आव्यूह मिलता है।