विषयसूची

लघुतम पथ समस्या

एक अनिर्दिष्ट नेटवर्क में नोड S से नोड T तक का सबसे छोटा रास्ता खोजने के लिए एक्सेल में सॉल्वर का उपयोग करें। नेटवर्क में बिंदुओं को नोड्स (SABCDE और T) कहा जाता है। नेटवर्क में रेखाओं को आर्क्स (SA SB SC AC आदि) कहा जाता है।

मॉडल तैयार करें

हम जिस मॉडल को हल करने जा रहे हैं वह एक्सेल में इस प्रकार दिखता है।

एक्सेल में लघुतम पथ समस्या

1. इस लघुत्तम पथ समस्या को सूत्रबद्ध करने के लिए निम्नलिखित तीन प्रश्नों के उत्तर दीजिए।

एक। क्या निर्णय लिए जाने चाहिए? इस समस्या के लिए हमें एक्सेल की आवश्यकता है कि पता लगाया जाए कि चाप सबसे छोटे पथ पर है या नहीं (हाँ=1 नहीं=0)। उदाहरण के लिए यदि SB सबसे छोटे पथ का भाग है तो सेल F5 बराबर 1 है। यदि नहीं तो सेल F5 बराबर 0 है।

बी। What are the constraints on these decisions? The Net Flow (Flow Out – Flow In) of each node should be equal to Supply/Demand. Node S should only have one outgoing arc (Net Flow = 1). Node T should only have one ingoing arc (Net Flow = -1). All other nodes should have one outgoing arc and one ingoing arc if the node is on the shortest path (Net Flow = 0) or no flow (Net Flow = 0).

सी। इन निर्णयों के लिए प्रदर्शन का समग्र माप क्या है? प्रदर्शन का समग्र माप सबसे छोटे रास्ते की कुल दूरी है, इसलिए उद्देश्य इस मात्रा को न्यूनतम करना है।

2. मॉडल को समझना आसान बनाने के लिए निम्नलिखित नामित श्रेणियाँ बनाएँ।

रेंज का नाम प्रकोष्ठों
From बी4:बी21
को सी4:सी21
दूरी डी4:डी21
जाना एफ4:एफ21
शुद्ध प्रवाह I4:I10
SupplyDemand के4:के10
कुल दूरी एफ23

3. निम्नलिखित फ़ंक्शन डालें।

फ़ंक्शन सम्मिलित करें

Explanation: The SUMIF functions calculate the Net Flow of each node. For node S the SUMIF function sums the values in the Go column with an “S” in the From column. As a result only cell F4 F5 or F6 can be 1 (one outgoing arc). For node T the SUMIF function sums the values in the Go column with a “T” in the To column. As a result only cell F15 F18 or F21 can be 1 (one ingoing arc). For all other nodes Excel looks in the From and To column. Total Distance equals the sumproduct of Distance and Go.

परीक्षण त्रुटि विधि

इस सूत्रीकरण से किसी भी परीक्षण समाधान का विश्लेषण करना आसान हो जाता है।

1. उदाहरण के लिए पथ SBET की कुल दूरी 16 है।

परीक्षण समाधान

परीक्षण और त्रुटि का उपयोग करना आवश्यक नहीं है। हम आगे बताएंगे कि एक्सेल सॉल्वर का उपयोग कैसे किया जा सकता है ताकि जल्दी से इष्टतम समाधान पाया जा सके।

मॉडल हल करें

इष्टतम समाधान खोजने के लिए निम्नलिखित चरणों का पालन करें।

1. विश्लेषण समूह में डेटा टैब पर सॉल्वर पर क्लिक करें।

सॉल्वर पर क्लिक करें

Note: can’t find the Solver button? Click here to load the Solver add-in.

सॉल्वर पैरामीटर दर्ज करें (आगे पढ़ें)। परिणाम नीचे दी गई तस्वीर के अनुरूप होना चाहिए।

सॉल्वर पैरामीटर

आपके पास स्प्रेडशीट में श्रेणी नाम टाइप करने या कक्षों पर क्लिक करने का विकल्प है।

2. उद्देश्य के लिए कुल दूरी दर्ज करें।

3. न्यूनतम पर क्लिक करें.

4. बदलते चर कोशिकाओं के लिए जाओ दर्ज करें।

5. निम्नलिखित प्रतिबंध दर्ज करने के लिए जोड़ें पर क्लिक करें।

Net Flow Constraint

6. Check ‘Make Unconstrained Variables Non-Negative’ and select ‘Simplex LP’.

7. अंत में हल करें पर क्लिक करें।

परिणाम:

सॉल्वर परिणाम

इष्टतम समाधान:

लघुतम पथ समस्या परिणाम

निष्कर्ष: SADCT सबसे छोटा रास्ता है जिसकी कुल दूरी 11 है।

एक टिप्पणी छोड़ें

Excel meets AI – Boost your productivity like never before!

At Formulas HQ, we’ve harnessed the brilliance of AI to turbocharge your Spreadsheet mastery. Say goodbye to the days of grappling with complex formulas, VBA code, and scripts. We’re here to make your work smarter, not harder.

संबंधित आलेख