अधिकतम नेटवर्क प्रवाह. अधिकतम प्रवाह ज्ञात करने के लिए एल्गोरिदम

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

3. स्टॉक को लेबल करने दें (जे+, ε(टी)), तब एफ(जे,टी)के साथ बदलें एफ(जे,टी)+ε(टी). यदि स्टॉक अंकित है (जे-, ε(टी)), वह एफ(जे,टी)के साथ बदलें एफ(जे,टी)-ε(टी). चलो शीर्ष पर चलते हैं जे. अगर जेएक निशान है (आई+, ε(जे)), फिर हम प्रतिस्थापित करते हैं एफ(आई,जे)पर f(i,j)+ε(t), और यदि (आई-, ε(जे)), एफ(जे,आई)के साथ बदलें एफ(जे,आई)-ε(टी). चलो शीर्ष पर चलते हैं मैं. हम इस ऑपरेशन को तब तक दोहराते हैं जब तक हम स्रोत तक नहीं पहुंच जाते एस।प्रवाह परिवर्तन रुक जाता है, सभी निशान मिट जाते हैं और चरण 2 पर चले जाते हैं

उदाहरण 3.14.

एम 4 के

काम। नेटवर्क पर उच्चतम प्रवाह ज्ञात करें

एल्गोरिदम

आइए शीर्ष को निरूपित करें एस=एक्स 0 . अन्य सभी x i हैं।

प्रथम चरण।

1. कोई भी ऐसा पथ चुनें जिसके सभी चाप संतृप्त न हों।

2. हम इस पथ पर प्रवाह की मात्रा एक तक बढ़ाते हैं जब तक कि इसमें कोई संतृप्त चाप न रह जाए।

हम प्रवाह को बढ़ाने की प्रक्रिया तब तक जारी रखते हैं जब तक कि पूर्ण प्रवाह न बन जाए, यानी। किसी भी पथ में कम से कम एक संतृप्त चाप होगा।

चरण 2.

2. यदि x i पहले से ही एक चिह्नित शीर्ष है, तो हम (+i) उन सभी असंतृप्त शीर्षों को चिह्नित करते हैं, जिन तक असंतृप्त चाप x i से जाते हैं, और सूचकांक (-i) के साथ सभी अचिह्नित शीर्षों को चिह्नित करते हैं, जहां से गैर-शून्य प्रवाह वाले चाप जाते हैं से x i.

3. यदि इस प्रक्रिया के परिणामस्वरूप एक शीर्ष अंकित हो जाता है टी, फिर बीच में एसऔर टीएक पथ है जिसके सभी शीर्ष पिछले शीर्षों की संख्या से चिह्नित हैं। यदि हम आगे बढ़ते हैं तो इस पथ के सभी चापों में प्रवाह को एक से बढ़ा देते हैं एसको टीचाप का अभिविन्यास गति की दिशा के साथ मेल खाता है, और यदि चाप का अभिविन्यास विपरीत है तो यह एक से कम हो जाता है। चलिए चरण 1 पर चलते हैं।

4. जब शीर्ष टीयह चिह्नित करना असंभव है कि प्रक्रिया समाप्त हो गई है और परिणामी प्रवाह नेटवर्क का सबसे बड़ा प्रवाह है।

टिप्पणी। आप पहला चरण पूरा किए बिना चरण 2 पर जा सकते हैं (उदाहरण 3.16 देखें)।

उदाहरण 3.15.

9

समाधान:

किसी दिए गए परिवहन नेटवर्क पर एक पूर्ण प्रवाह पाया गया है। संतृप्त चापों को हाइलाइट किया गया है

इस नेटवर्क में, आप अंतिम शीर्ष को भी चिह्नित कर सकते हैं, और अंकन का परिणाम वही होगा। प्रवाह को बदलने से, हमें एक नेटवर्क मिलता है जिसमें अंतिम शीर्ष को चिह्नित करना असंभव है, इसलिए इसमें प्रवाह सबसे बड़ा और 10 के बराबर है।

उदाहरण 3.16.

8 2 1

किसी दिए गए परिवहन नेटवर्क पर अधूरा प्रवाह पाया गया

आइए नेटवर्क को चिह्नित करें और एल्गोरिदम के अनुसार उसमें प्रवाह बढ़ाएं। हम पाते हैं

इस नेटवर्क में, आप अंतिम शीर्ष को भी चिह्नित कर सकते हैं, और अंकन का परिणाम वही होगा। प्रवाह को बदलने से, हमें एक नेटवर्क मिलता है जिसमें अंतिम शीर्ष को चिह्नित करना असंभव है, इसलिए इसमें प्रवाह सबसे बड़ा और 6 के बराबर है।

धारा IV. गतिशील प्रोग्रामिंग.

डायनेमिक प्रोग्रामिंग का उपयोग इष्टतम मल्टी-स्टेज समाधान खोजने के लिए किया जाता है। उदाहरण के लिए, उपकरण प्रतिस्थापन के लिए दीर्घकालिक योजना; कई वर्षों में उद्योग की गतिविधि। यह इष्टतमता के सिद्धांत का उपयोग करता है, जिसके अनुसार कोई भी नया आंशिक समाधान प्राप्त स्थिति के सापेक्ष इष्टतम होना चाहिए।

एक को कई बार हल करना बेहतर है सरल कार्यएक बार से अधिक जटिल.

समस्या 1. दो बिंदुओं के बीच सबसे लाभप्रद मार्ग के बारे में।

दो बिंदुओं ए और बी को जोड़ने वाला एक पथ बनाना आवश्यक है, जिनमें से दूसरा पहले के उत्तर-पूर्व में स्थित है। सरलता के लिए, मान लें कि पथ बनाने में चरणों की एक श्रृंखला होती है, और प्रत्येक चरण पर हम या तो उत्तर की ओर या पूर्व की ओर बढ़ सकते हैं। फिर कोई भी पथ एक चरणबद्ध टूटी हुई रेखा है, जिसके खंड समन्वय अक्षों में से एक के समानांतर हैं। इनमें से प्रत्येक खंड के निर्माण की लागत ज्ञात है।

उदाहरण 4.1. A से B तक न्यूनतम पथ ज्ञात कीजिए।

अंतिम चरण टी.वी. हासिल करना है। अंतिम चरण से पहले, हम उन बिंदुओं पर हो सकते हैं जहां से हम एक चरण में टी.वी. तक पहुंच सकते हैं। ऐसे दो बिंदु हैं (सिस्टम दो राज्यों में से एक में हो सकता है)। उनमें से प्रत्येक के लिए, टीवी तक पहुंचने का केवल एक ही विकल्प है: एक के लिए - पूर्व की ओर बढ़ें; दूसरे के लिए - उत्तर की ओर। आइए प्रत्येक स्थिति में लागत 4 और 3 लिखें।

4

आइए अब अंतिम चरण को अनुकूलित करें। पिछले चरण के बाद, हम तीन बिंदुओं में से एक पर समाप्त हो सकते हैं: सी 1, सी 2, सी 3।

बिंदु C 1 के लिए, केवल एक ही नियंत्रण है (आइए इसे एक तीर से चिह्नित करें) - पूर्व की ओर बढ़ें, और लागत 2 (इस चरण पर) + 4 (अगले चरण पर) = 6 होगी। इसी प्रकार, आइटम सी 3 के लिए लागत 2+3=5 होगी। टी.सी 2 के लिए दो नियंत्रण हैं: पूर्व या उत्तर की ओर जाएं। पहले मामले में, लागत 3+3=6 होगी, और दूसरे मामले में - 1+4=5. इसका मतलब यह है कि सशर्त इष्टतम नियंत्रण उत्तर की ओर जाना है। आइए इसे एक तीर से चिह्नित करें और संबंधित लागतें दर्ज करें।

उत्तर: x 1 =1; एक्स 3 =0; एक्स 3 =4; डब्ल्यू=3.5

सामान्यीकृत एल्गोरिदम

1. सिस्टम का वर्णन करें. अर्थात्, प्रत्येक चरण से पहले पता लगाएं कि कौन से पैरामीटर नियंत्रित प्रणाली की स्थिति को दर्शाते हैं। कार्य को अनावश्यक विवरणों के साथ अतिभारित किए बिना, नियंत्रित प्रणाली के विवरण को यथासंभव सरल बनाने में सक्षम होना महत्वपूर्ण है।

2. ऑपरेशन को चरणों (चरणों) में विभाजित करें। प्रबंधन पर लगाए गए सभी उचित प्रतिबंधों को यहां ध्यान में रखा जाना चाहिए। चरण इतना छोटा होना चाहिए कि चरण नियंत्रण अनुकूलन प्रक्रिया काफी सरल हो; और साथ ही, कदम बहुत छोटा नहीं होना चाहिए ताकि अनावश्यक गणना न करें जो इष्टतम समाधान खोजने की प्रक्रिया को जटिल बनाती है, लेकिन इष्टतम में महत्वपूर्ण परिवर्तन नहीं करती है उद्देश्य समारोह.

3. प्रत्येक चरण के लिए चरण नियंत्रण x i का सेट और उन पर लगाए गए प्रतिबंधों का पता लगाएं।

4. निर्धारित करें कि नियंत्रण x i i-चरण पर क्या लाभ लाता है, यदि इससे पहले सिस्टम राज्य S में था, अर्थात। भुगतान कार्यों को लिखें:

w i =f i (S, x i)

5. निर्धारित करें कि नियंत्रण x i के प्रभाव में सिस्टम की स्थिति कैसे बदलती है पहला कदम, यानी राज्य परिवर्तन फ़ंक्शन लिखें।

एस / =φ मैं (एस, एक्स मैं)

6. पहले से ज्ञात फ़ंक्शन के माध्यम से सशर्त इष्टतम लाभ को व्यक्त करते हुए मुख्य आवर्ती गतिशील प्रोग्रामिंग समीकरण लिखें

डब्ल्यू आई (एस)= अधिकतम(एफ आई (एस, एक्स आई)+डब्ल्यू आई+1 (φ आई (एस, एक्स आई)))

7. उत्पादन सशर्त अनुकूलनअंतिम चरण, इस बारे में विभिन्न धारणाएँ बनाना कि अंतिम चरण कैसे समाप्त हुआ, और इनमें से प्रत्येक धारणा के लिए अंतिम चरण पर सशर्त (इस शर्त के आधार पर चयनित कि चरण किसी चीज़ के साथ समाप्त हुआ) इष्टतम नियंत्रण खोजें।

डब्ल्यू एम (एस)= अधिकतम(एफ एम (एस, एक्स एम))

8. सशर्त अनुकूलन करें, अंतिम चरण से शुरू करके पहले चरण (वापस लौटते हुए) पर समाप्त करें।

9. उत्पादन बिना शर्त अनुकूलननियंत्रण, प्रत्येक चरण पर संबंधित अनुशंसाओं को "पढ़ना": पहले चरण में पाया गया इष्टतम नियंत्रण लेना और सिस्टम की स्थिति को बदलना, पाए गए राज्य के लिए दूसरे चरण में इष्टतम नियंत्रण ढूंढना, आदि। अंतिम चरण तक.

इष्टतमता का सिद्धांत. अगले चरण से पहले सिस्टम की स्थिति जो भी हो, इस चरण पर नियंत्रण चुनना आवश्यक है ताकि इस चरण पर लाभ और इसके बाद के सभी चरणों में इष्टतम लाभ अधिकतम हो।

गतिशील प्रोग्रामिंग के सिद्धांत का अर्थ यह नहीं है कि प्रत्येक चरण को दूसरों से स्वतंत्र रूप से अलग से अनुकूलित किया गया है। ऐसे नियंत्रण को चुनने का क्या मतलब है जिसकी प्रभावशीलता एक विशिष्ट चरण में अधिकतम है, यदि यह कदम हमें अगले चरणों में अच्छी तरह से जीतने के अवसर से वंचित कर देगा?

व्यवहार में, ऐसे मामले होते हैं जब किसी ऑपरेशन की योजना अनिश्चित काल के लिए बनानी पड़ती है। ऐसे मामले का मॉडल एक अनंत-चरणीय नियंत्रित प्रक्रिया है, जहां सभी चरण समान होते हैं। यहां जीतने वाला फ़ंक्शन और राज्य परिवर्तन फ़ंक्शन चरण संख्या पर निर्भर नहीं करता है।

खंड V. सिमुलेशन मॉडलिंग

यह मैनुअल असतत गणित और/या ग्राफ सिद्धांत में पाठ्यक्रम लेने वाले छात्रों के लिए है।

इसकी मदद से आप "नेटवर्क में अधिकतम प्रवाह और न्यूनतम कटौती" विषय पर महारत हासिल कर लेंगे।

• सीधे इस मैनुअल से, आप अपनी आईडी की गणना कर सकते हैं, भले ही आपके कंप्यूटर पर MATLAB न हो।=|यदि आपके पास MATLAB है, तो इस पृष्ठ पर जाएँ: वहाँ आपके पास गणना स्क्रिप्ट (प्रोग्राम) में हस्तक्षेप करने का अवसर है। यहां, नेटवर्क में अधिकतम प्रवाह की समस्या को एक रैखिक प्रोग्रामिंग समस्या में घटाकर हल किया जाता है।आइए निम्नलिखित संकेतन का परिचय दें:
• एन=|वी| − ग्राफ़ आकार (शीर्षों की संख्या);
• एम ई सीधे इस मैनुअल से, आप अपनी आईडी की गणना कर सकते हैं, भले ही आपके कंप्यूटर पर MATLAB न हो।× एन| − ग्राफ कार्डिनैलिटी (किनारों की संख्या); ए- आकार के नेटवर्क डिग्राफ का घटना मैट्रिक्स मैं; इसका हर तत्व एक इक=1 यदि से ए-शीर्ष बाहर आता है मैंके एक इक-मैं आर्क; ए=−1, यदि में
• एसवां शीर्ष प्रवेश करता है
• टी-मैं आर्क; और
• =0 अन्य मामलों में; ऐसे मैट्रिक्स के प्रत्येक कॉलम में बिल्कुल एक, एक घटा एक, और बाकी शून्य होते हैं;- नेटवर्क के स्रोत शीर्ष की संख्या; इस शीर्ष से केवल चाप निकलना चाहिए, और कोई भी अन्य शीर्ष स्रोत से पहुंच योग्य होना चाहिए; − एस एम - नेटवर्क के सिंक नोड की संख्या; केवल आर्क्स को इस शीर्ष में प्रवेश करना चाहिए, और एक नाली किसी अन्य शीर्ष से पहुंच योग्य होनी चाहिए;
• =0 अन्य मामलों में; ऐसे मैट्रिक्स के प्रत्येक कॉलम में बिल्कुल एक, एक घटा एक, और बाकी शून्य होते हैं;ए − टीएस एम ;
• एमइसमें केवल एक ही होना चाहिए, क्योंकि स्रोत से केवल चाप निकलना चाहिए;टी एम नेटवर्क डिग्राफ की घटना मैट्रिक्स की -वीं पंक्ति एस; टीइसमें केवल माइनस वाले होने चाहिए, क्योंकि केवल चापों को नाली में प्रवेश करना चाहिए;
• अनुसूचित जनजाति - नेटवर्क डिग्राफ की घटना मैट्रिक्स एनउन लोगों के साथ जो इससे बाहर फेंक दिए गए वें औरवें पंक्तियाँ; एक इकई
• − लंबाई का स्तंभ वेक्टर - नेटवर्क डिग्राफ की घटना मैट्रिक्स एनउन लोगों के साथ जो इससे बाहर फेंक दिए गए ; इसके प्रत्येक तत्व मेंई के एक इकप्रवाह का परिमाण होगा

वें चाप;

सी

सी के

• ≥0 थ्रूपुट सेट करता है वें औरवें चाप. वें और = ; इसके प्रत्येक तत्व मेंतब अधिकतम नेटवर्क प्रवाह समस्या को एक रैखिक प्रोग्रामिंग समस्या के रूप में तैयार किया जा सकता है:
• स्रोत (1) छोड़ने वाला कुल प्रवाह अधिकतम है। इसके अलावा, किसी भी मध्यवर्ती शीर्ष पर आने वाला प्रवाह आउटगोइंग प्रवाह (2) के बराबर है, और चाप की क्षमता सीमित है (3)।
• यदि ऐसे दो घटक हैं, तो छोड़े गए चाप न्यूनतम कटौती देते हैं;
• यदि दो से अधिक जुड़े हुए घटक दिखाई देते हैं, तो नेटवर्क डायग्राफ में कई न्यूनतम कटौती होती है (संबंधित रैखिक प्रोग्रामिंग समस्या खराब हो जाती है)।

किसी गंभीर समस्या के लिए, स्रोत के निकटतम पहला न्यूनतम कट इस पृष्ठ पर बनाया गया है।

इस पृष्ठ का सही ढंग से उपयोग करने के लिए, आपके ब्राउज़र को स्क्रिप्ट का समर्थन करना चाहिए जावा स्क्रिप्ट. उन्हें चालू करें.

नीचे इनपुट क्षेत्रों में प्रारंभिक डेटा दर्ज करें। पहले क्षेत्र में, आपको नेटवर्क का डिग्राफ खींचने के लिए शीर्षों के निर्देशांक दर्ज करने की आवश्यकता है (अधिक सटीक रूप से, आप कर सकते हैं)। इन्हें मैट्रिक्स के रूप में निर्दिष्ट किया गया है सीधे इस मैनुअल से, आप अपनी आईडी की गणना कर सकते हैं, भले ही आपके कंप्यूटर पर MATLAB न हो।×2: पहले कॉलम में - एक्सवें निर्देशांक, दूसरे में - य-इ. संख्याओं को पूर्णांक के रूप में, दशमलव बिंदु के साथ, या घातांकीय रूप में निर्दिष्ट किया जा सकता है। संख्याओं को रिक्त स्थान से अलग करें. कुल मात्राइस इनपुट क्षेत्र में रेखाएं डिग्राफ का आकार निर्धारित करती हैं सीधे इस मैनुअल से, आप अपनी आईडी की गणना कर सकते हैं, भले ही आपके कंप्यूटर पर MATLAB न हो।− शीर्षों की संख्या. ये प्रारंभिक डेटा (वर्टेक्स निर्देशांक) वैकल्पिक हैं: यदि वे निर्दिष्ट नहीं हैं, तो नेटवर्क डिग्राफ को सही के रूप में खींचा जाएगा सीधे इस मैनुअल से, आप अपनी आईडी की गणना कर सकते हैं, भले ही आपके कंप्यूटर पर MATLAB न हो।-गॉन, और शीर्षों की संख्या अगले इनपुट क्षेत्र में अधिकतम शीर्ष संख्या द्वारा निर्धारित की जाएगी।

अगले इनपुट क्षेत्र में बाईं तरफ- भरना आवश्यक है। यह नेटवर्क डिग्राफ की संरचना को परिभाषित करता है। एनडिग्राफ में प्रत्येक चाप दो शीर्षों को जोड़ता है। इन शीर्षों की संख्याएँ मैट्रिक्स के रूप में निर्दिष्ट हैं ×2 दूसरे इनपुट क्षेत्र के बाईं ओर। प्रत्येक पंक्ति पर, चाप का पहला शीर्ष (पूंछ, स्रोत) पहले निर्दिष्ट किया जाता है, और फिर, एक स्थान के माध्यम से, चाप का दूसरा शीर्ष (टिप, नाली) निर्दिष्ट किया जाता है।इन कॉलमों में शामिल होना चाहिए सीधे इस मैनुअल से, आप अपनी आईडी की गणना कर सकते हैं, भले ही आपके कंप्यूटर पर MATLAB न हो।प्राकृतिक संख्या एन 1 से

इनमें से प्रत्येक कॉलम में संख्याओं की कुल संख्या डिग्राफ की शक्ति निर्धारित करती है − चापों की संख्या. , गणना एक निर्देशित ग्राफ दिया जाएजी= जिसमें प्रत्येक चाप की दिशावीÎवी वीमतलब प्रवाह की दिशा (उदाहरण के लिए, कारों का प्रवाह), प्रत्येक चाप की क्षमता के बराबर है टीऔर एसघ(v). टीअनेक शिखरों पर एसदो शीर्षों को हाइलाइट किया गया है टी. शिखर एस .

प्रवाह का स्रोत है, - नाली। शीर्ष से पारित किया जा सकने वाला अधिकतम प्रवाह निर्धारित करना आवश्यक हैवी आइए हम इसे निरूपित करेंएक्स(वी)

एक चाप के साथ चलने वाले प्रवाह की मात्रा (6. 1)

वी . यह तो स्पष्ट है 0 £ x(v) £ d(v) , vÎV .

हर शिखर पर)iÎE\(t,s)

(x(v)| iÎV + (i)) - (x(v)| iÎV - (i))=0.(6.2)

शीर्ष के लिए टी

(x(v)| iÎV + (i)) -(x(v)¦ iÎV - (i))=-Q,(6.3)

वर्टेक्स एस के लिए

(x(v)| iO V + (i)) -(x(v)¦ i О V - (i))= Q.(6.4)

परिमाण क्यूशीर्ष से निकलने वाले प्रवाह का परिमाण है टीऔर शीर्ष पर प्रवेश करता है एस.

तय करने की जरूरत है

क्यू ® अधिकतम(6.5)

प्रतिबंधों के तहत (6.1-6.4)।

मात्रा क्यू, एक्स(वी) , वीÎवी,संतोषजनक प्रतिबंध (6.1-6.4) हम नेटवर्क में प्रवाह कहेंगे, और यदि वे मूल्य को अधिकतम करते हैं क्यू, फिर अधिकतम प्रवाह। यह देखना आसान है कि मान Q=0, x(v)=0, vÎV, नेटवर्क में एक स्ट्रीम हैं।

समस्या (6.1-6.5) एक रैखिक प्रोग्रामिंग समस्या है और इसे सिंप्लेक्स विधि एल्गोरिदम का उपयोग करके हल किया जा सकता है।

आइए शीर्ष E के समुच्चय को दो असंयुक्त भागों E1 और E2 में इस प्रकार विभाजित करें tÎE1, sÎE2. काटने से वी(ई1,ई2), पृथक करना टीऔर एसहम सेट को कॉल करेंगे वी(ई1,ई2)Ìवीऐसा कि प्रत्येक चाप के लिए v О V(E1,E2)या h1(v)OE1और h2(v)OE2, या h1(v)OE2और h2(v)OE1.

आइए सेट को विभाजित करें वी(ई1,ई2)दो भागों में वी(ई1,ई2,+),वी(ई1,ई2,-)निम्नलिखित नुसार:

V(E1,E2,+)=(vÎV(E1,E2)| h1(v)ÎE1और h2(v)OE2)

V(E1,E2,-)= ( vÎV(E1,E2)| h2(v)ÎE1और h1(v)OE2)

हम कट की थ्रूपुट क्षमता को कॉल करेंगे

Q(E1,E2) = (x(v)| vÎV(E1,E2,+))-(x(v)| vÎV(E1,E2,-))

निम्नलिखित सत्य है

प्रमेय 1. (अधिकतम प्रवाह और न्यूनतम कटौती के बारे में)।

किसी भी नेटवर्क में स्रोत से अधिकतम प्रवाह होता है एस्टॉक करना एसन्यूनतम थ्रूपुट के बराबर क्यू(ई1,ई2)तमाम कटौतियों के बीच वी(ई1,ई2), शीर्षों को अलग करना टीऔर एस.

ध्यान दें कि अधिकतम प्रवाह में

x(v)=d(v) , vÎV(E1,E2,+),

x(v)=0 , vÎV(E1,E2,-).

होने देना क्यू, एक्स(वी), वीÎवी, -कुछ नेटवर्क प्रवाह, अनुक्रम

t=i(0),v(1),i(1),v(2),i(2),...,v(k),i(k)=s,

शीर्षों को जोड़ने वाली एक शृंखला है टीऔर एस. आइए हम इस श्रृंखला पर शीर्ष से गति की दिशा निर्धारित करें टीको एस. आर्क वी(जे)इस श्रृंखला को एक सीधी रेखा कहा जाता है यदि इसकी दिशा गति की दिशा से मेल खाती है टीको एस, और अन्यथा विपरीत। इस शृंखला को हम पथ कहेंगे बढ़ता प्रवाह, यदि सीधे चापों के लिए आइए हम इसे निरूपित करेंचेन एक्स(वी)< d(v) और रिवर्स के लिए एक्स(वी) > 0. इस सर्किट से एक अतिरिक्त प्रवाह पारित किया जा सकता है क्यूसे टीको एसआकार क्यू = मिनट(क्यू1,क्यू2),कहाँ q1=मिनट (d(v) -x(v)), श्रृंखला के सभी सीधे चापों पर न्यूनतम लिया जाता है, q1=मिनट (x(v)), श्रृंखला के सभी रिवर्स आर्क पर न्यूनतम लिया जाता है।

प्रमेय 2.

प्रवाह Q, x(v) , vÎV, अधिकतम है यदि और केवल यदि प्रवाह को बढ़ाने का कोई तरीका नहीं है।

किसी नेटवर्क में अधिकतम प्रवाह की समस्या को हल करने के लिए प्रस्तावित एल्गोरिदम प्रवाह को बढ़ाने का तरीका खोजने पर आधारित है टी. शिखर एस, जो बदले में शीर्ष लेबलों को व्यवस्थित करने की प्रक्रिया पर आधारित है। चलिए ऐसा कहते हैं

शिखर मैंएक निशान के साथ चिह्नित क्यू(i)>0, और सीधा चाप चाप भी जाना जाता है वी(आई), जिससे होकर यह प्रवाह आया, या अंकित है , यदि परिमाण का कुछ अतिरिक्त प्रवाह क्यू(i)>0, और रिवर्स आर्क भी जाना जाता है वी(आई), जिससे होकर यह प्रवाह प्रविष्ट हुआ;

शीर्ष I को तब देखा जाता है जब इसके सभी पड़ोसी शीर्षों को चिह्नित किया जाता है।

यदि शीर्ष s को चिह्नित किया गया है, तो प्रवाह को परिमाण के अनुसार बढ़ाने के लिए एक पथ पाया गया है क्यू, जो इस पथ से होकर गुजरता है। एल्गोरिदम का वर्णन करने के लिए हमें एक सारणी की भी आवश्यकता है एसपीडब्ल्यू, जिसमें चिह्नित शीर्षों की संख्या उसी क्रम में होती है जिस क्रम में उन्हें चिह्नित किया गया था। सी 1- सरणी में संख्या एसपीडब्ल्यूचरम देखा, सी2- इस सरणी में अंतिम चिह्नित शीर्ष की संख्या।

इस एल्गोरिदम का विचार स्रोत से सिंक तक सकारात्मक प्रवाह के साथ अंत-से-अंत पथ ढूंढना है।

(प्रारंभिक) क्षमता वाले एक किनारे (i, j) पर विचार करें। एल्गोरिदम के निष्पादन के दौरान, इस क्षमता के कुछ हिस्सों को किसी दिए गए किनारे से गुजरने वाले प्रवाह द्वारा "छीन" लिया जाता है, परिणामस्वरूप, प्रत्येक किनारे में एक अवशिष्ट क्षमता होगी। लिखें - अवशिष्ट बैंडविड्थ. ऐसा नेटवर्क जिसमें सभी किनारों की अवशिष्ट क्षमता हो, अवशिष्ट कहा जाएगा।

नोड i से प्रवाह प्राप्त करने वाले एक मनमाना नोड j के लिए, हम एक लेबल परिभाषित करते हैं, जहां नोड j से नोड i तक प्रवाहित होने वाले प्रवाह का मान होता है। अधिकतम प्रवाह ज्ञात करने के लिए, हम निम्नलिखित चरण निष्पादित करते हैं।

सभी किनारों के लिए, हम प्रारंभिक क्षमता के बराबर अवशिष्ट क्षमता निर्धारित करते हैं, अर्थात। आइए बराबरी करें =. आइए नोड 1 को एक लेबल के साथ निर्दिष्ट करें और चिह्नित करें। हम मान लेते हैं i=1.

नोड्स j का सेट जिसमें आप सभी j के लिए सकारात्मक अवशिष्ट क्षमता >0 के साथ किनारे पर नोड I से जा सकते हैं। यदि, हम चरण 3 को पूरा करते हैं, अन्यथा हम 4 पर जाते हैं।

में हमें नोड k ऐसा मिलता है। आइए नोड k को एक लेबल से रखें और चिह्नित करें। यदि k=n, एक अंत-से-अंत पथ मिल जाता है और हम चरण 5 पर जाते हैं, अन्यथा हम i=k सेट करते हैं और चरण 2 पर लौट आते हैं।

रोलबैक. यदि i=1, कोई अंत-से-अंत पथ संभव नहीं है, और 6 पर जाएं। यदि, हम नोड i से ठीक पहले लेबल किया गया नोड r पाते हैं और इसे नोड r से सटे नोड्स के सेट से हटा देते हैं। हम i=r सेट करते हैं और चरण 2 पर लौटते हैं।

अवशिष्ट नेटवर्क की परिभाषा. आइए हम नोड्स के सेट को निरूपित करें जिसके माध्यम से स्रोत नोड (नोड 1) से सिंक नोड (नोड एन) तक एंड-टू-एंड पथ पाया जाता है, फिर इस पथ के साथ गुजरने वाला अधिकतम प्रवाह गुजरता है

अंत-से-अंत पथ बनाने वाले किनारों की अवशिष्ट क्षमता प्रवाह की दिशा में एक मात्रा से घट जाती है और विपरीत दिशा में उसी मात्रा से बढ़ जाती है।

वह। एंड-टू-एंड पथ में शामिल किनारे (i, j) के लिए, वर्तमान अवशिष्ट क्षमताएं बदल जाती हैं:

1) यदि प्रवाह नोड i से j तक जाता है,

2) यदि प्रवाह नोड j से i तक जाता है।

ए) एम एंड-टू-एंड पथ पाए जाने पर, अधिकतम प्रवाह द्वारा व्यक्त किया जाता है

बी) किनारे की प्रारंभिक और अंतिम क्षमता (i, j) के मान होने पर, हम इस किनारे के माध्यम से इष्टतम प्रवाह की गणना निम्नानुसार कर सकते हैं। चलिए डालते हैं. यदि >0, किनारे (i, j) से गुजरने वाला प्रवाह बराबर है। यदि >0, तो प्रवाह बराबर है। (वह स्थिति जब >0 और >0 दोनों असंभव हैं)।

उदाहरण 1. नेटवर्क में अधिकतम प्रवाह ज्ञात कीजिए चित्र। 1

पुनरावृत्ति 1.=

3) k=3, चूँकि। हम नोड 3 को एक लेबल के साथ निर्दिष्ट और चिह्नित करते हैं। i=3 और 2 पर लौटें)

5) k=5 और. हम नोड 5 को एक लेबल से चिह्नित करते हैं। हमें एक मार्ग मिलता है।

6) हम लेबल द्वारा अंत-से-अंत पथ निर्धारित करते हैं, नोड 5 से शुरू होकर नोड 1: पर समाप्त होते हैं। और। हम पथ के साथ अवशिष्ट क्षमताओं की गणना करते हैं:

पुनरावृत्ति 2.

1) और नोड 1 को एक लेबल से चिह्नित करें। मैं=1

2") (इसलिए नोड 5 इसमें शामिल नहीं है

3") k=4, और नोड 4 को एक लेबल से चिह्नित करें। i=4 और 2 पर लौटें)

2""") (चूंकि नोड 1 और 3 चिह्नित हैं, वे इसमें शामिल नहीं हैं)

3""") k=5 और। हम नोड 5 को एक लेबल के साथ चिह्नित करते हैं। एक एंड-टू-एंड पथ प्राप्त होता है। 5 पर जाएं)

पुनरावृत्ति 3.

1) और नोड 1 को एक लेबल से चिह्नित करें। मैं=1

3) k=2, और नोड 2 को एक लेबल से चिह्नित करें। i=2 और 2 पर लौटें)

3") k=3 और। नोड 3 को एक लेबल से चिह्नित करें। i=3 और 2 पर वापस लौटें)

2") (तब से) 4 पर जाएँ)

4) नोड 3 लेबल पिछले नोड की संख्या दिखाता है। इस पुनरावृत्ति पर, नोड 3 को भविष्य में ध्यान में नहीं रखा जाता है; और 2 पर वापस लौटें)

2""") (चूंकि नोड 3 को संभावित एंड-टू-एंड पथ से हटा दिया गया है)

3""") और। हम नोड 5 को एक लेबल के साथ चिह्नित करते हैं। एक अंत-से-अंत पथ प्राप्त होता है। 5 पर जाएं)

5) मैं. हम पथ के साथ अवशिष्ट क्षमताओं की गणना करते हैं:

पुनरावृत्ति 4. इस पुनरावृत्ति पर, पथ के साथ

पुनरावृत्ति 5. इस पुनरावृत्ति पर, पथ के साथ

पुनरावृत्ति 6: कोई नया एंड-टू-एंड पथ संभव नहीं है क्योंकि नोड 1 से निकलने वाले सभी किनारों में शून्य अवशिष्ट क्षमता है। समाधान निर्धारित करने के लिए 6) पर जाएँ

6) नेटवर्क में अधिकतम प्रवाह मात्रा इकाइयों के बराबर है।

विभिन्न किनारों के लिए प्रवाह मूल्यों की गणना प्रारंभिक क्षमता मूल्यों से नवीनतम अवशिष्ट क्षमता मूल्यों को घटाकर की जाती है।

गणना परिणाम: तालिका। 1

अधिकतम प्रवाह ज्ञात करने के लिए एल्गोरिदम का आलेखीय अनुक्रमिक निष्पादन (उदाहरण 1)

ई) एफ) कोई पार पथ नहीं है

चावल।

परिवहन प्रणाली पर प्रारंभिक डेटा, उदाहरण के लिए, इन-प्लांट, चित्र में दिखाया गया है। 2, को एक तालिका (तालिका 2) द्वारा भी निर्दिष्ट किया जा सकता है।

तालिका 2. अधिकतम प्रवाह समस्या के लिए प्रारंभिक डेटा

जाहिर है, परिवहन प्रणाली की अधिकतम क्षमता 6 से अधिक नहीं है, क्योंकि शुरुआती बिंदु 0 से 6 इकाइयों से अधिक कार्गो नहीं भेजा जा सकता है, अर्थात् 2 इकाइयों को बिंदु 1, 3 इकाइयों को बिंदु 2 और 1 इकाई को बिंदु 3 पर भेजा जा सकता है। इसके बाद, यह सुनिश्चित करना आवश्यक है कि बिंदु 0 से निकलने वाले कार्गो की सभी 6 इकाइयाँ अंतिम बिंदु 4 तक पहुँचें। जाहिर है, बिंदु 1 पर आने वाले कार्गो की 2 इकाइयों को सीधे बिंदु 4 पर भेजा जा सकता है। विभाजित करना होगा: 2 इकाइयों को तुरंत बिंदु 4 पर भेजा जाता है, और 1 इकाई को - मध्यवर्ती बिंदु 3 पर भेजा जाता है (बिंदु 2 और 4 के बीच अनुभाग की सीमित क्षमता के कारण)। निम्नलिखित कार्गो को बिंदु 3 पर पहुंचाया गया: बिंदु 0 से 1 इकाई और बिंदु 3 से 1 इकाई। हम उन्हें बिंदु 4 पर भेजते हैं। इसलिए, प्रश्न में परिवहन प्रणाली का अधिकतम थ्रूपुट 6 इकाई कार्गो है। इस मामले में, बिंदु 1 और 2 के बीच, साथ ही बिंदु 1 और 3 के बीच के आंतरिक खंड (शाखाएँ) का उपयोग नहीं किया जाता है। बिंदु 1 और 4 के बीच की शाखा पूरी तरह से लोड नहीं होती है - कार्गो की 2 इकाइयाँ इसके साथ भेजी जाती हैं 3 इकाइयों का थ्रूपुट। समाधान को तालिका के रूप में प्रस्तुत किया जा सकता है (तालिका 3)

टेबल तीन। अधिकतम प्रवाह समस्या का समाधान

प्रवाह अधिकतमीकरण के लिए रैखिक प्रोग्रामिंग समस्या।आइए हम रैखिक प्रोग्रामिंग के संदर्भ में अधिकतम प्रवाह समस्या तैयार करें। मान लीजिए X KM बिंदु K से बिंदु M तक परिवहन की मात्रा है। चित्र के अनुसार। 2 K = 0,1,2,3, M = 1,2,3,4, और परिवहन केवल अधिक संख्या वाले बिंदु तक ही संभव है। इसका मतलब यह है कि कुल 9 चर X KM हैं, अर्थात्, X 01, X 02, X 03, X 12, X 13, X 14, X 23, X 24, प्रवाह का रूप है:

एक्स 01 + एक्स 02 + एक्स 03 = एफ (0)

एक्स 01 + एक्स 12 + एक्स 13 + एक्स 14 = 0 (1)

एक्स 02 - एक्स 12 + एक्स 23 + एक्स 24 = 0 (2)

एक्स 03 - एक्स 13 - एक्स 23 + एक्स 34 = 0 (3)

एक्स 14 - एक्स 24 - एक्स 34 = - एफ (4)

एक्स किमी? 0, के, एम = 0, 1, 2, 3, 4

यहाँ F वस्तुनिष्ठ फलन है, स्थिति (0) परिवहन प्रणाली में माल के प्रवेश का वर्णन करती है। शर्तें (1) - (3) सिस्टम के नोड्स 1-3 के लिए संतुलन संबंध निर्धारित करती हैं। दूसरे शब्दों में, प्रत्येक आंतरिक नोड के लिए, माल का आने वाला प्रवाह आउटगोइंग प्रवाह के बराबर होता है, माल सिस्टम के अंदर जमा नहीं होता है और इसमें "जन्म" नहीं होता है; शर्त (4) सिस्टम से भार के "बाहर निकलने" की शर्त है। शर्त (0) के साथ, यह संपूर्ण सिस्टम के लिए एक संतुलन संबंध बनाता है ("इनपुट" "आउटपुट" के बराबर है)। निम्नलिखित नौ असमानताएँ परिवहन प्रणाली की व्यक्तिगत "शाखाओं" की क्षमता पर प्रतिबंध लगाती हैं। फिर ट्रैफ़िक की मात्रा और उद्देश्य फ़ंक्शन की गैर-नकारात्मकता का संकेत दिया जाता है। यह स्पष्ट है कि अंतिम असमानता वस्तुनिष्ठ फ़ंक्शन (संबंध (0) या (4)) के रूप और ट्रैफ़िक वॉल्यूम की गैर-नकारात्मकता से उत्पन्न होती है। हालाँकि, अंतिम असमानता कुछ लेकर आती है सामान्य जानकारी- या तो कार्गो की एक सकारात्मक मात्रा सिस्टम के माध्यम से पारित की जा सकती है, या शून्य (उदाहरण के लिए, यदि सिस्टम के भीतर एक सर्कल में गति होती है), लेकिन नकारात्मक नहीं (इसका कोई आर्थिक अर्थ नहीं है, लेकिन औपचारिक है) गणितीय मॉडलइसके बारे में "नहीं जानता")।

चाप घटना के माध्यम से प्रवाह का योग आइए हम इसे निरूपित करें, चाप घटना के माध्यम से प्रवाह के योग के बराबर है डब्ल्यू; इस योग को फ्लक्स मान कहा जाता है। हम मुख्य रूप से उन प्रवाहों में रुचि लेंगे जिनका संभावित परिमाण सबसे बड़ा है - तथाकथित अधिकतम प्रवाह। में सामान्य मामलाएक नेटवर्क में कई अलग-अलग अधिकतम प्रवाह हो सकते हैं, लेकिन उनका मान समान होना चाहिए। (4)

नेटवर्क एन = (वी, डी, ए) के माध्यम से अधिकतम प्रवाह का अध्ययन कट की अवधारणा से निकटता से संबंधित है, यानी। डिग्राफ डी के चापों का ऐसा सेट ए जिसमें किसी भी साधारण श्रृंखला की संपत्ति है आइए हम इसे निरूपित करें. शिखर ए से संबंधित चाप से होकर गुजरता है। कट की क्षमता उससे संबंधित चाप की क्षमताओं का योग है। वे कट जिनमें न्यूनतम संभव थ्रूपुट होता है, न्यूनतम कट कहलाते हैं।

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

प्रमेय (अधिकतम प्रवाह और न्यूनतम कटौती के बारे में). किसी भी नेटवर्क में, किसी भी अधिकतम प्रवाह का आकार किसी भी न्यूनतम कटौती की क्षमता के बराबर होता है।

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

स्टेप 1. सबसे पहले, आइए एक ऐसे प्रवाह का चयन करें जिसका मान शून्य न हो (यदि ऐसा कोई प्रवाह मौजूद है)। उदाहरण के लिए, यदि N चित्र में दिखाया गया नेटवर्क है। 29.3, फिर चित्र में दिखाया गया प्रवाह। 29.4. यह ध्यान देने योग्य है कि हमारे द्वारा चुने गए प्रारंभिक प्रवाह का मूल्य जितना बड़ा होगा, बाद के चरण उतने ही आसान होंगे।

चरण दो. एन के आधार पर, हम प्रवाह की दिशा को विपरीत दिशा में बदलकर एक नया नेटवर्क एन' बनाते हैं। अधिक सटीक रूप से, कोई भी चाप a जिसके लिए (a) = 0 अपनी मूल क्षमता के साथ N' में रहता है, और कोई भी चाप a जिसके लिए, क्षमता वाले चाप a और क्षमता (a) के साथ विपरीत चाप द्वारा प्रतिस्थापित किया जाता है। हमारे उदाहरण में नेटवर्क एन' चित्र में दिखाया गया है। 29.5. शिखर आइए हम इसे निरूपित करेंअब एक स्रोत नहीं, बल्कि एक सिंक है।

चरण 3. यदि नेटवर्क एन' में हम एक गैर-शून्य प्रवाह पा सकते हैं आइए हम इसे निरूपित करेंसी, तो इसे मूल प्रवाह में जोड़ा जा सकता है और एन में बड़े मूल्य का एक नया प्रवाह प्राप्त किया जा सकता है। अब आप नेटवर्क बनाते समय N' के बजाय नए थ्रेड N' का उपयोग करके चरण 2 को दोहरा सकते हैं। इस प्रक्रिया को दोहराकर, हम अंततः एक नेटवर्क एन' पर पहुंचेंगे जिसमें कोई गैर-शून्य प्रवाह नहीं होगा; तो संगत प्रवाह अधिकतम प्रवाह होगा। उदाहरण के लिए, चित्र में. 29.5 एक गैर-शून्य प्रवाह है जिसमें चापों के माध्यम से प्रवाह होता है ( वी,यू), (यू,जेड), (जेड,एक्स), (एक्स, वाई) और ( हाँ,) एक के बराबर हैं, और शेष चापों के माध्यम से फ्लक्स शून्य के बराबर हैं। इस प्रवाह को चित्र में दिखाए गए प्रवाह में जोड़ना। 29.4, हमें चित्र में दिखाया गया प्रवाह प्राप्त होता है। 29.6; चरण 2 को दोहराते हुए, यह दिखाना आसान है कि यह अधिकतम प्रवाह है।

प्रयुक्त साहित्य:

(1) http://pgap.chat.ru/zap/zap264.htm#0

(2) असानोव एम.ओ., बारांस्की वी.ए., रसिन वी.वी. असतत गणित: मैट्रोइड ग्राफ़, एल्गोरिदम

(3) बसाकर आर., साती टी. परिमित ग्राफ़ और नेटवर्क।

(4) विल्सन आर. ग्राफ सिद्धांत का परिचय