Linear programming — रैखिक प्रोग्रामिंग

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

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

विषय और उद्देश्य

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

• रैखिक प्रोग्रामिंग निम्नलिखित व्यावहारिक समस्याओं को हल करने में सक्षम बनाती है:
• उत्पादन का इष्टतम नियोजन।
• परिवहन प्रवाहों का अनुकूलन (परिवहन समस्या)।
• निवेशों का इष्टतम वितरण।
• सामग्री की इष्टतम कटाई। असाइनमेंट समस्या।

LP समस्या का गणितीय सूत्रीकरण

रैखिक प्रोग्रामिंग की मानक समस्या को निम्नानुसार प्रस्तुत किया जाता है:

उन निर्णय चरों के मान ज्ञात करने की आवश्यकता होती है जो रैखिक उद्देश्य फलन को अधिकतम या न्यूनतम करें। इस स्थिति में निर्णय चरों पर रैखिक समानताओं और/या रैखिक असमानताओं की प्रणाली के रूप में प्रतिबंध लगाए जाते हैं। सामान्यतः निर्णय चरों की अऋणात्मकता की शर्त जोड़ी जाती है (उनके मान शून्य से अधिक या बराबर होने चाहिए), जो प्रायः समस्या के भौतिक या आर्थिक अर्थ से निर्धारित होती है।

गणितीय दृष्टि से इसका अर्थ है रैखिक फलनों और रैखिक समीकरणों/असमानताओं की प्रणालियों के साथ कार्य करना।

LP की मूल अवधारणाएँ

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

LP समस्याओं के समाधान की विधियाँ

रैखिक प्रोग्रामिंग समस्याओं के समाधान के लिए कई मुख्य विधियाँ हैं:

• आलेखीय विधि: दो निर्णय चरों वाली समस्याओं के लिए लागू होती है। यह समतल पर स्वीकार्य समाधान क्षेत्र और उद्देश्य फलन को दृश्य रूप में प्रस्तुत करने और स्वीकार्य समाधान क्षेत्र के शीर्षों के विश्लेषण या उद्देश्य फलन की समस्तरीय रेखा को स्थानांतरित करके इष्टतम समाधान खोजने में सहायक है।
• सिम्प्लेक्स विधि: George Dantzig द्वारा विकसित एक सार्वभौमिक पुनरावृत्तीय एल्गोरिदम। यह विधि प्रत्येक चरण में उद्देश्य फलन के मान में सुधार करते हुए, स्वीकार्य समाधान क्षेत्र के एक शीर्ष से उसके निकटवर्ती शीर्ष पर क्रमशः जाती है, जब तक इष्टतम समाधान नहीं मिल जाता। यह LP समस्याओं के समाधान की शास्त्रीय और सर्वाधिक प्रसिद्ध विधि है।
• आंतरिक बिंदु विधियाँ: एल्गोरिदम का एक वैकल्पिक वर्ग जो सिम्प्लेक्स विधि के बाद उभरा। ये सीमाओं के बजाय स्वीकार्य समाधान क्षेत्र के भीतर से इष्टतम समाधान की ओर बढ़ती हैं। ये विधियाँ अत्यधिक बड़े आयाम की LP समस्याओं को हल करने के लिए विशेष रूप से प्रभावी हैं।

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

प्रत्येक रैखिक प्रोग्रामिंग समस्या (जिसे प्रत्यक्ष कहा जाता है) के साथ एक अन्य LP समस्या को संबद्ध किया जा सकता है, जिसे द्वैत समस्या कहते हैं। प्रत्यक्ष और द्वैत समस्याएँ परस्पर घनिष्ठ रूप से जुड़ी हुई हैं:

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

LP का अनुप्रयोग

रैखिक प्रोग्रामिंग का व्यापक उपयोग निम्नलिखित क्षेत्रों में होता है:

• अर्थव्यवस्था और व्यवसाय (उत्पादन नियोजन, लॉजिस्टिक्स, वित्त, विपणन)।
• उद्योग (तकनीकी प्रक्रियाओं का अनुकूलन, स्टॉक प्रबंधन, सामग्री की कटाई)।
• परिवहन (मार्गों, समय-सारणियों का अनुकूलन)। कृषि (बुवाई क्षेत्रों, चारा राशन का अनुकूलन)।
• ऊर्जा क्षेत्र (उत्पादन क्षमताओं की लोडिंग का अनुकूलन)।

साहित्य

• Dantzig, George रैखिक प्रोग्रामिंग, इसके अनुप्रयोग और सामान्यीकरण। — मॉस्को: Progress, 1966.
• Yudin D. B., Goldstein E. G. रैखिक प्रोग्रामिंग (सिद्धांत, विधियाँ और अनुप्रयोग)। — मॉस्को: Nauka, 1969.
• Taha, Hamdy A. Operations Research: An Introduction. — Pearson. (10th ed., 2017)
• Hillier, Frederick S.; Lieberman, Gerald J. Introduction to Operations Research. — McGraw-Hill Education. (11th ed., 2021)

यह भी देखें

• संक्रिया अनुसंधान
• अनुकूलन
• उद्देश्य फलन
• प्रतिबंध
• स्वीकार्य समाधान क्षेत्र
• इष्टतम समाधान