कक्षा 12 → रैखिक प्रोग्रामिंग → सिंप्लेक्स विधि ↓
सिंप्लेक्स विधि का उपयोग करके रैखिक प्रोग्रामिंग समस्याओं का समाधान
रैखिक प्रोग्रामिंग एक गणितीय मॉडल में सर्वोत्तम परिणाम प्राप्त करने का तरीका है। इस मॉडल को रैखिक संबंधों द्वारा निरूपित किया जाता है। रैखिक प्रोग्रामिंग का उद्देश्य एक विशेष मात्रा के अधिकतम या न्यूनतम मान को खोजना होता है, जिसे विशिष्ट सीमाओं में एक समीकरण के रूप में व्यक्त किया जा सकता है। सिंप्लेक्स विधि एक लोकप्रिय एल्गोरिथ्म है जो रैखिक प्रोग्रामिंग समस्याओं को हल करने के लिए उपयोग की जाती है।
सिंप्लेक्स विधि क्या है?
सिंप्लेक्स विधि रैखिक प्रोग्रामिंग समस्याओं को हल करने की एक चरण-दर-चरण प्रक्रिया है। यह दो से अधिक चर और अधिक जटिल सीमाओं वाली समीकरणों को संभालने के लिए डिज़ाइन की गई है। सिंप्लेक्स विधि की खूबसूरती यह है कि यह समस्या को एक सुनियोजित प्रक्रिया में बदल देती है जिसका उपयोग एक सारणी के रूप में किया जाता है जिसे सिंप्लेक्स टेबलौ कहा जाता है।
रैखिक प्रोग्रामिंग समस्या
सिंप्लेक्स विधि में और आगे बढ़ने से पहले, आइए समझते हैं कि एक रैखिक प्रोग्रामिंग समस्या कैसी दिखती है। एक सामान्य रैखिक प्रोग्रामिंग समस्या में निम्न शामिल होंगे:
- एक उद्दिष्ट फलन जिसे अधिकतम या न्यूनतम करना है।
- लक्षण रैखिक असमानताओं के रूप में।
- अधिनियामक चर।
उदाहरण के लिए:
अधिकतम करें: Z = 3x + 2y शर्ते: 2x + y ≤ 18 2x + 3y ≤ 42 3x + y ≤ 24 x, y ≥ 0
यहां, Z वह उद्दिष्ट फलन है जिसे आप अधिकतम करना चाहते हैं। सीमाएं असमानताओं द्वारा प्रस्तुत की जाती हैं। दोनों x और y चर शून्य या उससे अधिक होना चाहिए।
सिंप्लेक्स विधि के चरण
सिंप्लेक्स विधि में कई प्रमुख चरण शामिल हैं:
चरण 1: असमानताओं को समीकरणों में परिवर्तित करें
स्लैक चरों को जोड़कर असमानताओं को समतुल्यता में बदलें। स्लैक चर असमानता के बाएं और दाएँ पक्षों के बीच का अंतर दर्शाता है।
लक्षण पर विचार करें:
2x + y ≤ 18 2x + 3y ≤ 42 3x + y ≤ 24
स्लैक चर s1, s2 और s3 जोड़कर उन्हें बदलें:
2x + y + s1 = 18 2x + 3y + s2 = 42 3x + y + s3 = 24
अब, रैखिक समीकरणों में स्लैक चर हैं जो प्रारंभ में शून्य के बराबर होते हैं।
चरण 2: सिंप्लेक्स टेबलौ सेट अप करें
आपके द्वारा परिवर्तित किए गए समीकरणों से एक प्रारंभिक सिंप्लेक्स टेबल बनाएं। तालिका कुछ इस तरह दिखती है:
| x | y | s1 | s2 | s3 | समाधान | , 2 | 1 | 1 | 0 | 0 | 18 | , 2 | 3 | 0 | 1 | 0 | 42 | , 3 | 1 | 0 | 0 | 1 | 24 | , -3 | -2 | 0 | 0 | 0 | 0 |
नोट: नीचे की पंक्ति उद्दिष्ट फलन गुणांक को घटाकर बनाई गई है। यह पंक्ति अनुकूलन निर्धारित करने में मदद करती है।
चरण 3: धुरी तत्व की पहचान करें
एक धुरी तत्व का चयन किया जाता है ताकि समाधान को इस तरह से बदला जा सके कि यह इष्टतम समाधान की दिशा में नए आयाम ले। इस प्रक्रिया में मुख्य बिंदु शामिल हैं:
- तालिका की नीचे की पंक्ति में सबसे नकारात्मक संख्या का चयन करें। यह धुरी स्तंभ होगा।
- समाधान मान की अनुपात की गणना करें जो धुरी स्तंभ में गुणांक के होते हैं (शून्य और नकारात्मक गुणांक को छोड़कर)। सबसे छोटी सकारात्मक अनुपात धुरी पंक्ति को निर्धारित करेगा।
उदाहरण के लिए:
अनुपात: (18/2) = 9, (42/2) = 21, (24/3) = 8
सबसे छोटी अनुपात 8 है, जो धुरी पंक्ति के अनुरूप है। और इस उदाहरण के लिए, चूंकि -3 नीचे की पंक्ति में सबसे नकारात्मक है, धुरी स्तंभ वह होगा जो 3 के साथ है।
चरण 4: पंक्ति संचालन करें
धुरी तत्व को 1 में बदलने के लिए प्राथमिक पंक्ति संचालन का उपयोग करें और स्तम्भ में अन्य तत्वों को 0 में समायोजित करें। यह चरण इष्टतम समाधान की ओर संगम सुनिश्चित करता है।
चरण 5: पुनरावृत्ति
चरण 3 और 4 तब तक दोहराएँ जब तक नीचे की पंक्ति में कोई नकारात्मक संख्या न बचें। जब यह बिंदु आ जाता है, मूल लागू समाधान इष्टतम पाया जाता है।
सिंप्लेक्स विधि का उपयोग करके एक व्यावहारिक उदाहरण
समस्या
उद्दिष्ट फलन Z = 5x + 4y को अधिकतम करें, शर्तों के साथ:
y + 2x ≤ 20 2x + 3y ≤ 30 2x + y ≤ 15 x, y ≥ 0
चरण 1: स्लैक चर के साथ समीकरण में परिवर्तित करें
x + 2y + s1 = 20 2x + 3y + s2 = 30 2x + y + s3 = 15
चरण 2: सिंप्लेक्स टेबलौ सेट अप करें
| x | y | s1 | s2 | s3 | समाधान | , 1 | 2 | 1 | 0 | 0 | 20 | , 2 | 3 | 0 | 1 | 0 | 30 | , 2 | 1 | 0 | 0 | 1 | 15 | | -5|-4 | 0 | 0 | 0 | 0 |
चरण 3: धुरी तत्व की पहचान करें
-5 के साथ तत्व धुरी स्तंभ है। तीसरे स्तंभ के लिए अनुपात की गणना:
अनुपात: (20/1) = 20, (30/2) = 15, (15/2) = 7.5
सबसे छोटी सकारात्मक मान 7.5 है। तत्व (पंक्ति 3, स्तंभ 1) धुरी होगा।
चरण 4: पंक्ति संचालन करें
धुरी तत्व को 1 के बराबर करें:
| x | y | s1 | s2 | s3 | समाधान | , 1 | 2 | 1 | 0 | 0 | 20 | | 1 | 1.5| 0 | 0.5| 0 | 7.5 | <- धुरी पंक्ति (धुरी तत्व 1 बनाया गया) , 2 | 1 | 0 | 0 | 1 | 15 | | -5|-4 | 0 | 0 | 0 | 0 |
अन्य स्तम्भ तत्वों को शून्य करने और नीचे पंक्ति में कोई नकारात्मक संख्या न रहने तक प्रक्रिया को दोहराते रहें।
चरण 5: इष्टतम समाधान
अंततः लगातार पुनरावृत्तियों के माध्यम से:
| x | y | s1 | s2 | s3 | समाधान | , 1 | 0 | 1 | 1 | 0 | 5 | | 0 | 1 | 0 | 1.5| 0 | 12.5 | , 0 | 0 | -1 |-1.5| 1 | -7.5 | | 0 | 0 | 0 |0.5 | 0 | 35 |
मान x = 5 और y = 12.5 उद्दिष्ट फलन Z को 35 तक अधिकतम करते हैं।
निष्कर्ष
सिंप्लेक्स विधि रैखिक प्रोग्रामिंग के लिए एक शक्तिशाली अनुकूलन उपकरण है। यह कई चरों का प्रभावी ढंग से प्रबंधन कर सकता है, सीमाओं द्वारा परिसीमित एक इष्टतम बिंदु की ओर मार्गदर्शन करता है। प्रक्रिया की प्रकृति सीमित संसाधनों वाले व्यावहारिक परिदृश्यों का गहन विश्लेषण करने की अनुमति देती है, जिससे इष्टतम उपयोग सुनिश्चित होता है।
टिप्पणियाँ