Network model (operations research) — नेटवर्क मॉडल

From Systems analysis Wiki
Jump to navigation Jump to search

नेटवर्क मॉडल (संक्रिया अनुसंधान में; अंग्रेज़ी Network models) — यह गणितीय मॉडलों का एक वर्ग है, जो किसी समस्या को ग्राफ (नेटवर्क) के रूप में प्रस्तुत करता है, जिसमें शीर्ष (नोड) वस्तुओं या अवस्थाओं को दर्शाते हैं, तथा किनारे (चाप) उनके बीच के संबंधों या प्रक्रियाओं को[1]। अनुकूलन के संदर्भ में नेटवर्क से प्रायः एक निर्देशित ग्राफ अभिप्रेत होता है, जिसे संक्रिया विश्लेषण में सीधे «नेटवर्क» कहा जाता है; ऐसे नेटवर्क के शीर्षों को नोड और किनारों को चाप कहते हैं[2]।

नेटवर्क मॉडल लॉजिस्टिक्स, दूरसंचार, परियोजना प्रबंधन और वित्त जैसे क्षेत्रों में जटिल प्रणालियों के विश्लेषण और अनुकूलन के लिए एक शक्तिशाली उपकरण हैं। इनकी शक्ति अमूर्तन के उच्च स्तर में निहित है: एक नोड किसी शहर, कंप्यूटर राउटर या परियोजना के चरण को दर्शा सकता है, और एक चाप किसी सड़क, संचार चैनल या तकनीकी संक्रिया को।

परिभाषा और शब्दावली

नेटवर्क मॉडलों का आधार ग्राफ सिद्धांत है। प्रमुख अवधारणाएँ निम्नलिखित हैं:

  • प्रवाह नेटवर्क (अंग्रेज़ी flow network): एक निर्देशित ग्राफ जिसमें प्रत्येक किनारे की क्षमता (capacity) और प्रवाह (flow) होती है। ग्राफ में दो विशेष शीर्ष होते हैं: स्रोत (source), जहाँ से प्रवाह उत्पन्न होता है, और सिंक (sink), जहाँ वह प्रवेश करता है[1]।
  • प्रवाह संरक्षण का नियम: किसी भी ऐसे शीर्ष के लिए जो स्रोत या सिंक नहीं है, कुल आने वाला प्रवाह कुल जाने वाले प्रवाह के बराबर होना चाहिए। यह शर्त भौतिक संरक्षण नियमों का असांतत्य (discrete) समतुल्य है[3]।
  • नेटवर्क नियोजन: एक मॉडल जो किसी परियोजना को परस्पर संबद्ध संक्रियाओं (चापों) और घटनाओं (नोडों) के समुच्चय के रूप में प्रस्तुत करता है। ऐसे नेटवर्क निर्देशित चक्रहीन ग्राफ होते हैं, जो कार्यों के निष्पादन क्रम को प्रतिबिंबित करते हैं[4]।

मुख्य गुण और प्रमेय

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

  • समाधानों की पूर्णांकता: नेटवर्क अनुकूलन की कई समस्याएँ (जैसे अधिकतम प्रवाह या न्यूनतम पथ) प्रतिबंध मैट्रिक्स की पूर्ण unimodularity का गुण रखती हैं। इसके कारण, यदि समस्या के पैरामीटर (क्षमताएँ, लंबाइयाँ) पूर्णांक हों, तो रैखिक प्रोग्रामिंग विधियों द्वारा प्राप्त इष्टतम समाधान भी बिना अतिरिक्त प्रतिबंध लगाए पूर्णांक होगा[5][6]।
  • अधिकतम प्रवाह और न्यूनतम कट प्रमेय: प्रवाह सिद्धांत का केंद्रीय परिणाम। यह प्रतिपादित करता है कि स्रोत से सिंक तक अधिकतम प्रवाह की मात्रा, स्रोत और सिंक को अलग करने वाले सभी कटों में न्यूनतम क्षमता के बराबर होती है। यह प्रमेय प्रवाह के लिए इष्टतमता का मानदंड स्थापित करता है और अनेक एल्गोरिदम का आधार है[6][7]।
  • न्यूनतम पथ के लिए इष्टतमता का सिद्धांत: यदि बिंदु A से बिंदु C तक का पथ न्यूनतम है, तो उसका कोई भी खंड (जैसे मध्यवर्ती बिंदु B से C तक) संबंधित शीर्षों के बीच न्यूनतम पथ होगा। गतिशील प्रोग्रामिंग का आधार यही गुण है, जो Dijkstra जैसे एल्गोरिदम की शुद्धता को सुनिश्चित करता है[8]।
  • न्यूनतम आच्छादी वृक्ष (Minimum Spanning Tree) के गुण:
  • कट गुण: ग्राफ के किसी भी कट के लिए, कट को पार करने वाला न्यूनतम भार का किनारा कम से कम एक न्यूनतम आच्छादी वृक्ष में शामिल होता है।
  • चक्र गुण: ग्राफ के किसी भी चक्र में, अधिकतम भार वाला किनारा किसी भी न्यूनतम आच्छादी वृक्ष में शामिल नहीं होता।

इन्हीं गुणों पर Prim और Kruskal के «लालची» एल्गोरिदम की शुद्धता आधारित है[9]।

नेटवर्क अनुकूलन की मुख्य समस्याएँ

  • न्यूनतम पथ की समस्या: दो दिए गए नोडों के बीच न्यूनतम कुल लंबाई (भार) वाला पथ ज्ञात करना। इसे Dijkstra एल्गोरिदम (अऋणात्मक भारों के लिए) या Bellman-Ford एल्गोरिदम (स्वेच्छ भारों के लिए) द्वारा हल किया जाता है[8]।
  • अधिकतम प्रवाह की समस्या: चापों की दी गई क्षमताओं पर स्रोत से सिंक तक अधिकतम संभव प्रवाह निर्धारित करना। इसका क्लासिक समाधान Ford–Fulkerson एल्गोरिदम है[6]।
  • न्यूनतम आच्छादी वृक्ष की समस्या: ऐसा उपग्राफ ज्ञात करना जो नेटवर्क के सभी शीर्षों को जोड़े और किनारों की कुल लागत न्यूनतम हो।
  • क्रिटिकल पाथ विधि (CPM): नियोजन के नेटवर्क मॉडलों में कार्यों के सबसे लंबे अनुक्रम की पहचान करना, जो पूरी परियोजना की न्यूनतम संभव समय-सीमा निर्धारित करता है। इस पथ पर स्थित कार्यों का समय-आरक्षण शून्य होता है[10]।

उदाहरण

  • न्यूनतम पथ: किसी शहर के मानचित्र पर दो बिंदुओं के बीच नेविगेशन प्रणाली द्वारा इष्टतम मार्ग ढूँढना, जहाँ शहर नोड हैं और सड़कें चाप हैं जिनका भार लंबाई या यात्रा समय के बराबर है।
  • अधिकतम प्रवाह: पाइपलाइन नेटवर्क की अधिकतम क्षमता निर्धारित करना, जहाँ पंपिंग स्टेशन नोड हैं और सीमित क्षमता वाले पाइप चाप हैं।
  • न्यूनतम आच्छादी वृक्ष: कई शहरों को न्यूनतम कुल केबल लंबाई के साथ जोड़ने के लिए संचार नेटवर्क (जैसे ऑप्टिकल फाइबर केबल बिछाना) का अभिकल्पन।
  • क्रिटिकल पाथ: किसी घर निर्माण परियोजना में, जहाँ कार्यों (नींव डालना, दीवारें खड़ी करना, छत लगाना) की निर्धारित अवधि और तकनीकी निर्भरताएँ हों, क्रिटिकल पाथ निर्माण के न्यूनतम समापन समय को निर्धारित करता है। इस पथ पर किसी भी कार्य में विलंब पूरी परियोजना में विलंब का कारण बनेगा[10]।

यह भी देखें

  • संक्रिया अनुसंधान
  • ग्राफ सिद्धांत
  • परिवहन समस्या
  • क्रिटिकल पाथ विधि
  • PERT

टिप्पणियाँ

  1. ↑ 1.0 1.1 "Flow network". Wikipedia. [१]
  2. ↑ "Тема 10: Сетевые модели". Учебное пособие. Гомель: БелГУТ. [२]
  3. ↑ "Транспортная сеть". Википедия. [३]
  4. ↑ "Сетевое планирование". Википедия. [४]
  5. ↑ Bradley S. P., Hax A. C., Magnanti T. L. (1977). Applied Mathematical Programming. Addison-Wesley. Ch.8: Network Models. [५]
  6. ↑ 6.0 6.1 6.2 "Задача о максимальном потоке". Википедия. [६]
  7. ↑ Goldberg A. V., Tardos É., Tarjan R. E. (1990). "Network Flow Algorithms". In: Paths, Flows, and VLSI-Layout. Springer. [७]
  8. ↑ 8.0 8.1 "Задача о кратчайшем пути". Википедия. [८]
  9. ↑ "Минимальное остовное дерево". Википедия.
  10. ↑ 10.0 10.1 "Метод критического пути". Википедия. [९]
Retrieved from "https://systems-analysis.info/int/index.php?title=Network_model_(operations_research)_—_नेटवर्क_मॉडल&oldid=4868"