रेखिक प्रोग्रामिंग और अनुकूलन में सिम्प्लेक्स विधि को समझना

रेखिक प्रोग्रामिंग का परिचय

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

लक्ष्य कार्य और बाधाएँ

रेखिक प्रोग्रामिंग में हमारा लक्ष्य एक रेखिक लक्ष्य कार्य अधिकतम या न्यूनतम करना होता है। एक सामान्य रेखिक प्रोग्रामिंग समस्या को निम्नलिखित रूप में व्यक्त किया जा सकता है:

अधिकतम या न्यूनतम: Z = c 1 x 1 + c 2 x 2 + ... + c n x n
इसके अधीन:
a 11 x 1 + a 12 x 2 + ... + a 1n x n ≤ b 1
a 21 x 1 + a 22 x 2 + ... + a 2n x n ≤ b 2
,
a m1 x 1 + a m2 x 2 + ... + a mn x n ≤ b m
x 1 , x 2 , ..., x n ≥ 0

यहां, x 1 , x 2 , ..., x n चर हैं, c 1 , c 2 , ..., c n लक्ष्य कार्य के गुणांक हैं, a ij बाधाओं के गुणांक हैं, और b i बाधा समीकरणों में स्थिरांक हैं।

सिम्प्लेक्स विधि: एक अवलोकन

सिम्प्लेक्स विधि एक लोकप्रिय अल्गोरिदम है जो रेखिक प्रोग्रामिंग समस्याओं को हल करने के लिए उपयोग की जाती है। इसे 1947 में जॉर्ज डेन्त्ज़िग द्वारा विकसित किया गया था। इस विधि में निम्नलिखित मुख्य कदम शामिल हैं:

• रेखिक प्रोग्रामिंग समस्या को मानक रूप में परिवर्तित करना।
• प्रारंभिक व्यवहार्य समाधान खोजना।
• लक्ष्य कार्य को तब तक सुधारते रहना जब तक गतिशील समाधान तक न पहुँचा जाए।

मानक रूप में परिवर्तित करना

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

मान लें कि हमारे पास एक बाधा है जैसे:
a 11 x 1 + a 12 x 2 ≤ b 1

इसे समानता में बदलने के लिए, हम एक शिथिल चर s 1 जोड़ते हैं:

a 11 x 1 + a 12 x 2 + s 1 = b 1

प्रारंभिक व्यवहार्य समाधान खोजना

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

पुनरावृत्त प्रक्रिया

सिम्प्लेक्स विधि का मूल उद्देश्य व्यवहार्य समाधानों के माध्यम से लक्ष्य कार्य के मूल्य को सुधारना है ताकि गतिशील समाधान की पहचान की जा सके। इसे पिवोटिंग द्वारा पूरा किया जाता है।

उदाहरण

चलो रेखिक प्रोग्रामिंग समस्या के एक दृश्य उदाहरण को देखते हैं। मान लें कि हमारे पास निम्नलिखित समस्या है:

अधिकतम: Z = 3x 1 + 5x 2
इसके अधीन:
x 1 + 2x 2 ≤ 8
3x 1 + 2x 2 ≤ 12
x 1 , x 2 ≥ 0

| x 1 | x 2 | s 1 | s 2 | दाएँ हाथ की तरफ | 
,
, 1 | 2 | 1 | 0 | 8 |
, 3 | 2 | 0 | 1 | 12 |
,
, -3 | -5 | 0 | 0 | 0 |

8/2 = 4 (पहली पंक्ति के लिए)
12/2 = 6 (दूसरी पंक्ति के लिए)
न्यूनतम अनुपात 4 है, जो इंगित करता है कि पहली पंक्ति प्रस्थान करेगी।

टिप्पणियाँ