रैखिक प्रोग्रामिंग सॉल्वर

रैखिक प्रोग्रामिंग क्या है?

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

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

लक्ष्य फलन और बाधाएं

2-चर LP समस्या में, हम Z = c₁x₁ + c₂x₂ को अनुकूलित करने के लिए x₁ और x₂ के मान चुनते हैं, जहाँ c₁ और c₂ लक्ष्य गुणांक हैं जो प्रति इकाई लाभ, प्रति इकाई लागत, या अंशदान मार्जिन दर्शाते हैं। बाधाएं a₁x₁ + b₁x₂ ≤ (या ≥ या =) RHS के रूप में होती हैं, जो व्यवहार्य विकल्पों को प्रतिबंधित करती हैं।

अऋणात्मकता बाधाएं (x₁ ≥ 0, x₂ ≥ 0) आमतौर पर मानी जाती हैं क्योंकि उत्पादन मात्रा, काम किए गए घंटे, या भेजी गई इकाइयाँ जैसे निर्णय चर नकारात्मक नहीं हो सकते। ये बाधाएं हल को निर्देशांक तल के पहले चतुर्भाग तक सीमित करती हैं।

व्यवहार्य क्षेत्र

व्यवहार्य क्षेत्र सभी बिंदुओं (x₁, x₂) का समुच्चय है जो समस्या की हर बाधा को एक साथ संतुष्ट करते हैं। आलेखीय रूप से, प्रत्येक रैखिक असमानता एक अर्ध-तल परिभाषित करती है, और व्यवहार्य क्षेत्र सभी अर्ध-तलों का प्रतिच्छेदन है। यदि अऋणात्मकता बाधाएं शामिल हैं, तो व्यवहार्य क्षेत्र पहले चतुर्भाग में होता है।

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

कोने बिंदु (शीर्ष) प्रमेय

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

यह प्रमेय अनुकूलन समस्या को व्यवहार्य बिंदुओं के अनंत समुच्चय की खोज से कम करके सीमित संख्या में कोने बिंदुओं पर लक्ष्य फलन का मूल्यांकन करने तक सीमित कर देता है—जिससे LP गणनात्मक रूप से व्यवहार्य बन जाता है। कोने बिंदु सीमा समीकरणों के जोड़े को एक साथ हल करके, फिर व्यवहार्यता की जाँच करके पाए जाते हैं।

कोने बिंदुओं की पहचान

कोने बिंदु बाधा सीमा रेखाओं के आपस में और अक्षों के साथ प्रतिच्छेदन से उत्पन्न होते हैं। n बाधाओं और अऋणात्मकता वाली समस्या के लिए, आप सभी युगल सीमा रेखाओं के सभी प्रतिच्छेदन बिंदु गणना करते हैं, फिर जो एक या अधिक बाधाओं का उल्लंघन करते हैं उन्हें हटा देते हैं। शेष बचे व्यवहार्य प्रतिच्छेदन बिंदु व्यवहार्य बहुभुज के शीर्ष हैं।

आलेखीय विधि बनाम सिंप्लेक्स विधि

आलेखीय विधि सहज और दृश्य है, 2-चर LP समस्याओं के लिए उपयुक्त है। यह आपको व्यवहार्य क्षेत्र, कोने बिंदु और लक्ष्य फलन आइसो-रेखाएं व्यवहार्य समुच्चय पर कैसे चलती हैं यह देखने देती है। हालांकि, यह सख्ती से दो चरों तक सीमित है।

सिंप्लेक्स एल्गोरिथ्म, 1947 में जॉर्ज डैंट्ज़िग द्वारा विकसित, कोने-बिंदु विचार को बीजगणितीय रूप से सामान्यीकृत करता है। यह एक आधारभूत व्यवहार्य हल (एक शीर्ष) से शुरू होता है और एक आसन्न बेहतर शीर्ष की ओर एक किनारे के साथ आगे बढ़ता है, जब तक कोई सुधार संभव नहीं होता। यह हजारों चरों और बाधाओं को कुशलतापूर्वक संभालता है।

LP में विशेष मामले

• अव्यवहार्य LP: बाधाएं विरोधाभासी हैं—कोई बिंदु एक साथ सभी को संतुष्ट नहीं करता। उदाहरण: x + y ≤ 4 और x + y ≥ 6 एक साथ सत्य नहीं हो सकते।
• असीमित LP: व्यवहार्य क्षेत्र अनंत तक फैला है और लक्ष्य को बिना सीमा के सुधारा जा सकता है। अधिकतमीकरण के लिए, इसका अर्थ है कि आप हमेशा अधिक लक्ष्य मान वाला व्यवहार्य बिंदु खोज सकते हैं। महत्वपूर्ण बाधाएं संभवतः गायब हैं।
• एकाधिक इष्टतम हल: लक्ष्य फलन आइसो-रेखा एक बाधा सीमा के समानांतर है, इसलिए व्यवहार्य बहुभुज का एक पूरा किनारा समान इष्टतम Z मान प्राप्त करता है। उस किनारे पर कोई भी बिंदु समान रूप से इष्टतम है।
• पतित हल: एक कोने बिंदु पर दो से अधिक बाधाएं सक्रिय (बंधनकारी) हैं। यह सिंप्लेक्स विधि को धीमा कर सकता है लेकिन शुद्धता को प्रभावित नहीं करता।

रैखिक प्रोग्रामिंग के वास्तविक-विश्व अनुप्रयोग

• उत्पादन योजना: एक निर्माता सीमित मशीन घंटों, कच्चे माल और श्रम के साथ लाभ अधिकतम करने के लिए प्रत्येक उत्पाद की उत्पादन मात्रा तय करता है।
• आहार और पोषण: पोषण विशेषज्ञ न्यूनतम लागत वाली भोजन योजना खोजते हैं जो कैलोरी, प्रोटीन, विटामिन और खनिजों की दैनिक आवश्यकताओं को पूरा करे।
• परिवहन और लॉजिस्टिक्स: शिपिंग कंपनियां कई गोदामों से कई ग्राहकों तक माल की इष्टतम रूटिंग करके परिवहन लागत न्यूनतम करती हैं।
• पोर्टफोलियो अनुकूलन: निवेशक जोखिम बाधाओं और परिसंपत्ति आवंटन पर बजट सीमाओं के अधीन अपेक्षित रिटर्न अधिकतम करते हैं।
• नेटवर्क प्रवाह: दूरसंचार और उपयोगिता कंपनियां नेटवर्क में क्षमता आवंटन अनुकूलित करती हैं, थ्रूपुट अधिकतम करती हैं या लागत न्यूनतम करती हैं।
• एयरलाइन शेड्यूलिंग: एयरलाइंस लागत न्यूनतम करते हुए कवरेज, आराम नियमों और मांग बाधाओं को संतुष्ट करने के लिए मार्गों पर क्रू और विमान नियुक्त करती हैं।

रैखिक प्रोग्रामिंग में द्वैतता

प्रत्येक LP समस्या (प्राथमिक) के पास एक संगत द्वैत LP समस्या होती है। यदि प्राथमिक Z = c·x का अधिकतमीकरण करती है Ax ≤ b, x ≥ 0 के अधीन, तो द्वैत W = b·y का न्यूनतमीकरण करती है Aᵀy ≥ c, y ≥ 0 के अधीन। प्रबल द्वैतता प्रमेय कहता है कि यदि दोनों व्यवहार्य हैं, तो उनके इष्टतम मान बराबर हैं। द्वैत चर (छाया कीमतें) प्रत्येक बाधा को एक इकाई ढीला करने के सीमांत मूल्य को प्रकट करते हैं—संवेदनशीलता विश्लेषण और संसाधन मूल्यांकन के लिए एक शक्तिशाली उपकरण।