रैखिक प्रोग्रामिंग में समस्या को हल करने के दो चरण तरीके: पहला और दूसरा चरण

इस विधि में, समस्या को दो चरणों में हल किया गया है जैसा कि नीचे दिया गया है।

पहला चरण:

(ए) आरएचएस पर सभी शर्तें गैर नकारात्मक होनी चाहिए। यदि कुछ हैं, तो उन्हें पहले जैसा समझाया गया है, वैसा बनाया जाना चाहिए।

(b) मानक रूप में बाधाओं को व्यक्त करें।

(c) समानता बाधाओं या (>) प्रकार की बाधाओं में कृत्रिम चर जोड़ें।

(d) एक नया उद्देश्य फ़ंक्शन W बनाएँ जिसमें सभी कृत्रिम चर शामिल हैं

W = A 1 + A 2 + …………………… + A m

फंक्शन (W) को इनफैबिलिटी फॉर्म के रूप में जाना जाता है।

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

निम्नलिखित तीन मामलों में से कोई भी उत्पन्न हो सकता है:

(मैं भी शामिल। W> 0 और कम से कम एक कृत्रिम चर सकारात्मक स्तर पर कॉलम "बेसिक चर" में दिखाई देता है। ऐसे मामले में, मूल एलपीपी के लिए कोई संभव समाधान मौजूद नहीं है और प्रक्रिया बंद कर दी गई है।

(ii) न्यूनतम। W = 0 और शून्य स्तर पर कॉलम "बेसिक वेरिएबल्स" में कम से कम एक कृत्रिम चर दिखाई देता है। ऐसे मामले में, इन्फैटेबिलिटी फॉर्म का इष्टतम बुनियादी संभव समाधान दिए गए (मूल) एलपीपी के लिए एक बुनियादी संभव समाधान नहीं हो सकता है या नहीं, एक बुनियादी व्यवहार्य समाधान प्राप्त करने के लिए, हम चरण I को जारी रखते हैं और सभी कृत्रिम चर को बाहर निकालने का प्रयास करते हैं। आधार और फिर चरण II के लिए आगे बढ़ें।

(iii) मिन। W = 0 और कोई कृत्रिम चर "मूल चर" वर्तमान समाधान 'में दिखाई नहीं देता है। ऐसे मामले में मूल एलपीपी के लिए एक मूल संभव समाधान पाया गया है। द्वितीय चरण में आगे बढ़ें।

दूसरा चरण:

वह चरण I के मूल बुनियादी व्यवहार्य समाधान का उपयोग करें I मूल एलपीपी के लिए एक प्रारंभिक समाधान के रूप में सरलतम विधि का उपयोग करके इसे प्राप्त करने के लिए एक इष्टतम बुनियादी संभव समाधान तक पुनरावृत्तियां करें।

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

उदाहरण 1 (दो चरण सिंप्लेक्स विधि):

टू-फेज सिंप्लेक्स मेथड टू यूज करें

Z = -3X - 2Y - 2Z को कम से कम करें

5X + 7Y + 4Z <7 के अधीन

-4X + 7Y + 5Z> -2

3X + 4 V - 6Z> 29/7

एक्स, वाई, जेड> 0

उपाय:

पहला चरण

इसमें निम्न चरण होते हैं।

(ए) दूसरे बाधा में, आरएचएस -ve है, इसके दोनों ओर माइनस साइन के साथ गुणा करके इसे + ve बनाया जाता है।

4X - 7Y - 5Z <2

(b) बाधाओं में सुस्त चर जोड़ना

5X + 7Y + 4Z + S 1 = 7

4X - 7Y - 5Z + S 2 = 2

3X + 4Y - 6Z - एस 3 = 29/7

जहाँ X, Y, Z, S 1, S 2, S 3 > 0 है

(c) पुट एक्स = वाई = जेड = 0, हमें एस 1 = 7, एस 2 = 2, एस 3 = -29/7 मिलता है। प्रारंभिक समाधान के रूप में। लेकिन श्रृंखला S 3 is -ve है, हम कृत्रिम चर A जोड़ेंगे, अर्थात

3X + 4Y- 6Z- एस 3 + ए 1 = 29/7

(d) वस्तुनिष्ठ प्रकार्य जो कि न्यूनता प्रकार है अधिकतम बनाया जाता है

Z = 3X + 2Y + 2Z को अधिकतम करें

(ई) हम पहले चरण के लिए नए उद्देश्य समारोह डब्ल्यू = ए १ का परिचय देते हैं जिसे न्यूनतम किया जाना है।

(एफ) एक्सट्रैस्यूटिंग एक्स = वाई = जेड = एस = ० में कमी होने पर हमें एस = ing, एस = २, / ए = २ ९ / basic को प्रारंभिक मूलभूत व्यवहार्य समाधान तालिका १ के रूप में मिलता है।

सुधारित इष्टतमता परीक्षण

चूंकि Cj-Ej एक ही कॉलम (कम से कम समस्या) के तहत नकारात्मक है, इसलिए वर्तमान बुनियादी संभव समाधान में सुधार किया जा सकता है।

और अधिकतम समाधान की ओर ध्यान दें:

एक इष्टतम समाधान प्राप्त करने के लिए पुनरावृत्तियों का प्रदर्शन करना।

S 2 को X 2 से बदलें। यह नीचे दी गई तालिका में दिखाया गया है

तालिका में कुंजी पंक्ति के लिए टाई है X स्तंभ कुंजी स्तंभ है और y स्तंभ पहचान का पहला स्तंभ है। टाई ब्रेकिंग के लिए विधि के बाद हम पाते हैं कि y कॉलम टाई को तोड़ता नहीं है। पहचान के अगले कॉलम यानी S 2- कॉलम में एक पंक्ति के रूप में A -row की पैदावार होती है। इस प्रकार (1/7) प्रमुख तत्व है जिसे तालिका में एकता बनाया गया है

नीचे दिए गए तालिका में दिखाए अनुसार ए 1 को एक्स द्वारा बदलें

तालिका 5 इष्टतम समाधान दें। न्यूनतम W = 0 के बाद से और मूल चर में कोई कृत्रिम चर नहीं है अर्थात वर्तमान समाधान में, Table5 फेज-एलएल के लिए मूल व्यवहार्य समाधान देता है

दूसरा चरण:

मूल उद्देश्य समारोह है

अधिकतम करें Z = 3x + 2y + 2Z + OS, + 0S 2 + 0S 3

मूल बाधाओं का उपयोग करके इसे अधिकतम किया जाना है। चरण I के समाधान का उपयोग चरण II के लिए शुरुआती समाधान के रूप में और सरल एक्सगोरिथम का उपयोग करके गणना करने के बाद हमें तालिका 6 प्राप्त होती है

तालिका 7 में मुख्य तत्व को एकता बनाया गया है

S 2 को X 3 से बदलें।