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

द्वारा निरूपित करें एक्स (वी)एक चाप में गतिमान प्रवाह की मात्रा वी. जाहिर सी बात है

0£ x(v) £d(v) , vнV । (6. 1)

हर शिखर पर iОE\(टी, एस)आने वाले प्रवाह की मात्रा आउटगोइंग प्रवाह की मात्रा के बराबर होती है, अर्थात। निष्पक्ष समानता

(एक्स (वी .))|i V + (i))= (x(v)| iО V - (i))

(x(v)| आईएनवी + (i)) - (एक्स(वी)| आईएनवीवी - (i))=0.(6.2)

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

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

शीर्ष s . के लिए

(x(v)| में V + (i)) -(x(v)¦ i н V - (i))= Q.(6.4)

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

परिभाषित करने के लिए आवश्यक

क्यू®मैक्स(6.5)

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

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

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

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

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

वी(E1,E2,+)=(vнV(E1,E2)| h1(v)нE1तथा h2(v) нE2)

वी(ई1,ई2,-)= ( वीएनवी(ई1,ई2)|एच2(वी) нE1तथा एच1 (वी) एनई2)

कट का थ्रूपुट कहा जाएगा

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),कहाँ पे क्यू1=मिनट(डी(वी)-एक्स(वी)), न्यूनतम श्रृंखला के सभी सीधे चापों पर लिया जाता है, क्यू1 = मिनट (एक्स (वी)), न्यूनतम श्रृंखला के सभी पिछड़े चापों पर लिया जाता है।

प्रमेय 2.

प्रवाह क्यू, एक्स (वी), वीएनवी, अधिकतम अगर और केवल अगर प्रवाह को बढ़ाने का कोई तरीका नहीं है।

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

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

vertex i को स्कैन किया जाता है यदि उसके साथ के सभी कोने चिह्नित हैं।

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

नेटवर्क में अधिकतम प्रवाह की गणना के लिए एल्गोरिदम

मैं पुनरावृत्ति। चरण 2. नेटवर्क में स्वतंत्र मार्गों का चयन और उनमें प्रवाह का निर्धारण।जैसा एम 1 मार्ग ले लो ( वी और = वी 1 , वी 2 , वी 5 , वी सी \u003d वी 7) उदाहरण 1 में विचार किया गया। उसके लिए लेकिन(एम 1) = 10.

से स्वतंत्र भेद करना भी आसान है एम 1 मार्ग एम 2 = (वी और = वी 1 , वी 3 , वी 6 , वी सी \u003d वी 7)। आइए इसके लिए अधिकतम थ्रूपुट की गणना करें और आर्क्स के थ्रूपुट को समायोजित करें: लेकिन(एम 2)= मिनट{डी 13 , डी 36 , डी 67 } = मिनट{45, 40, 30} = 30. डी 13¢ =डी 13 - 30 = 15, डी 36¢ =डी 36 - 30 = 10, डी 67¢ =डी 67 - 30 = 0.

द्वितीय पुनरावृत्ति। चरण दो।एकमात्र स्वतंत्र मार्ग के रूप में, हम लेते हैं एम 3 = (वी और = वी 1 , वी 4 , वी 2 , वी 5 , वी सी \u003d वी 7)। उसके लिए:

लेकिन(एम 3)= मिनट{डी 14 , डी 42 , डी 25 , डी 57 } = मिनट{15, 10, 10, 15} = 10.

डी 14¢ =डी 14 - 10 = 5, डी 42¢ =डी 42 - 10 = 0, डी 25¢ =डी 25 - 10 = 0, डी 57¢ =डी 57 - 10 = 5.

चरण 4. नेटवर्क सुधार।अधिकतम प्रवाह लेकिन(एम 3) मार्ग के चापों से घटाना एम 13. परिणाम चित्र 1.16 ख में दिया गया है।

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

नेटवर्क योजना

काफी जटिल वस्तु के डिजाइन या निर्माण का कोई भी कार्य ( परियोजना) को कई छोटे घटक चरणों में तोड़ा जा सकता है। से सही पसंदइन चरणों का क्रम पूरी परियोजना के समय पर निर्भर करता है।

परियोजना के कार्यान्वयन के लिए कार्यों का पूरा परिसर एक सेट के रूप में प्रस्तुत किया गया है आयोजनतथा काम करता है. घटनाओं को परियोजना के व्यक्तिगत चरण कहा जाता है। नौकरियां वह प्रक्रिया है जिसके द्वारा उन्हें पूरा किया जाता है। परियोजना के कार्यान्वयन के लिए आवश्यक घटनाओं और कार्यों के पूरे परिसर को दो-ध्रुव नेटवर्क के रूप में दर्शाया जा सकता है जी =({वी मैं, वी जेड} , वी, एक्स), जिसमें:

और सभी घटनाक्रमकई शीर्षों से चिह्नित वी,उनमें से हाइलाइट किया गया प्रारंभिक घटना वी और(काम की शुरुआत) और अंतिम घटना v(पूरे प्रोजेक्ट को पूरा करना), नेटवर्क के आंतरिक कोने परिभाषित करते हैं मध्यवर्ती घटनाएं- प्रक्रिया में पालन करने के लिए कदम परियोजना कार्यान्वयन,

गेंद कामघटनाओं के जोड़े को जोड़ने वाले चापों द्वारा इंगित किए जाते हैं - शिखर।

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

एक उदाहरण के रूप में, कुछ उत्पादन के संगठन पर विचार करें। परियोजना को निम्नलिखित कार्य की आवश्यकता है:

I) विपणन अनुसंधान, II) उपकरण पर पूर्व-परियोजना अनुसंधान, III) बिक्री नेटवर्क का संगठन, IV) विज्ञापन अभियान, V) उत्पादन उपकरण के लिए तकनीकी विशिष्टताओं का विकास, VI) उत्पादन सुविधाओं और संचार के लिए तकनीकी दस्तावेज का विकास, VII ) मानक उपकरण की खरीद, VIII) गैर-मानक उपकरण का डिजाइन और निर्माण, IX) औद्योगिक परिसर का निर्माण और संचार की स्थापना, X) मानक उपकरण की स्थापना, XI) गैर-मानक उपकरण की स्थापना, XII) कमीशनिंग।

इन कार्यों को संबंधित संख्याओं के साथ आर्क द्वारा नेटवर्क आरेख में दर्शाया गया है।

इस परियोजना में निम्नलिखित कार्यक्रम होंगे:

1) काम की शुरुआत (प्रारंभिक घटना), 2) विपणन अनुसंधान पूरा करना, 3) पूर्व-परियोजना अनुसंधान पूरा करना, 4) एक वितरण नेटवर्क का संगठन, 5) एक विज्ञापन अभियान का संगठन, 6) उत्पादन के लिए तकनीकी विशिष्टताओं की तैयारी उपकरण, 7) उत्पादन परिसर और संचार के लिए तकनीकी दस्तावेज के विकास को पूरा करना, 8) मानक उपकरण की खरीद को पूरा करना, 9) गैर-मानक उपकरणों के डिजाइन और निर्माण को पूरा करना, 10) उत्पादन परिसर और स्थापना के निर्माण का पूरा होना संचार की, 11) उपकरण स्थापना और कमीशनिंग का पूरा होना,

12) परियोजना का पूरा होना (समाप्ति घटना)।

घटनाएँ संगत संख्याओं वाले शीर्षों से जुड़ी होती हैं। नेटवर्क आरेखपरियोजना कार्यान्वयन अंजीर में दिया गया है। 1.17:

चित्र 1.17। परियोजना नेटवर्क अनुसूची

नेटवर्क में प्रवाह

अधिकतम प्रवाह समस्या

मान लीजिए कि एक नेटवर्क दिया गया है, जिसमें शीर्ष E का एक सेट है और E से लिए गए कुछ क्रमित जोड़े को जोड़ने वाले चापों का एक सेट है। हम मान लेंगे कि यह एक सममित ग्राफ है, अर्थात यदि नेटवर्क में एक चाप () शामिल है, तो इसमें एक सममित चाप () भी शामिल है, हालांकि वास्तव में ऐसा चाप नहीं हो सकता है। निश्चितता के लिए, हम निम्नलिखित संख्याओं को नेटवर्क के शीर्षों पर असाइन करते हैं: . प्रत्येक शीर्ष तीव्रता की विशेषता है। जिन शीर्षों के लिए , स्रोत कहलाते हैं, वे शीर्ष जिनके लिए , सिंक होते हैं, और शेष मध्यवर्ती होते हैं। कुछ प्रवाह नेटवर्क के रास्तों के साथ भेजे जाते हैं - एक सजातीय पदार्थ (गैस, तरल) या परिवहन - स्रोतों से सिंक तक। नेटवर्क के प्रत्येक चाप () को एक संख्या सौंपी जाती है जिसे चाप की बैंडविड्थ कहा जाता है। एक चाप की क्षमता अधिकतम प्रवाह है जिसे वह प्रति इकाई समय में पारित कर सकता है। चलो , और शेष कोने के लिए, फिर - एकमात्र स्रोत, - एकमात्र सिंक, और - नेटवर्क के मध्यवर्ती नोड्स।

कार्य किसी दिए गए नेटवर्क के लिए स्रोत से सिंक तक प्रवाह का अधिकतम मूल्य निर्धारित करना है। स्रोत से सिंक तक नेटवर्क में प्रवाह के तहत, हमारा मतलब नेटवर्क के सभी चापों के साथ प्रवाह () के सेट से है, जहां चाप के साथ प्रवाह है (), , प्रति इकाई समय में इसके माध्यम से चले गए पदार्थ की मात्रा के बराबर। गणितीय रूप से, अधिकतम प्रवाह समस्या निम्नानुसार तैयार की जाती है: सभी के लिए गैर-ऋणात्मक मान खोजें, अधिकतम करना

(3.9)

प्रतिबंधों के साथ:

(3.11)

स्थिति (3.9) अधिकतम प्रवाह के मूल्य को दर्शाती है, जो स्रोत से बहने वाले या नाले में बहने वाले पदार्थ की मात्रा के बराबर है। शर्तों (3.10) का मतलब है कि प्रत्येक चाप के साथ प्रवाह गैर-ऋणात्मक होना चाहिए और इसकी क्षमता से अधिक नहीं होना चाहिए; यह शर्त (3.11) से इस प्रकार है कि किसी भी मध्यवर्ती शीर्ष में बहने वाले पदार्थ की मात्रा उसमें से निकलने वाले पदार्थ की मात्रा के बराबर होती है।

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

आइए इसे एक उदाहरण से स्पष्ट करते हैं।

एक नेटवर्क पर विचार करें जिसमें तीन स्रोत और दो सिंक हों (चित्र 3.10)। चलो, निश्चितता के लिए, यह नेटवर्कअगले कार्य का वर्णन करता है।

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

जाहिर है, मूल नेटवर्क और विस्तारित नेटवर्क दोनों में प्रवाह की मात्रा मूल नेटवर्क के आर्क्स के थ्रूपुट द्वारा निर्धारित की जाती है। इस प्रकार, स्रोतों के एक सेट से सिंक के एक सेट तक अधिकतम प्रवाह की समस्या एकल स्रोत से एकल सिंक तक अधिकतम प्रवाह की समस्या के बराबर है।

चावल। 3.10. एक काल्पनिक स्रोत और सिंक का परिचय

उदाहरण 3

आइए एक्सेल में अधिकतम प्रवाह समस्या को हल करने का एक उदाहरण दें। कुछ परिवहन नेटवर्क पर विचार करें (चित्र 3.11.)। हम यह भी मानते हैं कि यातायात प्रवाह कुछ चापों के दोनों दिशाओं में जा सकता है (जाहिर है, यह मामला एकतरफा यातायात प्रवाह के मामले की तुलना में अधिक सामान्य और हल करने में अधिक कठिन है)। आंकड़ा दोनों दिशाओं में अधिकतम थ्रूपुट दिखाता है: उदाहरण के लिए, बिंदु 3 से बिंदु 6 तक 4 इकाइयों की तीव्रता के साथ एक प्रवाह को ले जाया जा सकता है, और बिंदु 6 से बिंदु 3 तक समान प्रवाह (कुछ चापों के सिरों पर शून्य का मतलब है) इसी दिशा में परिवहन की असंभवता)। संपूर्ण रूप से नेटवर्क के अधिकतम थ्रूपुट को निर्धारित करना आवश्यक है, अर्थात। अधिकतम प्रवाह मूल्य

चावल। 3.11. नेटवर्क आरेख उदाहरण 3.

समाधान।

चूंकि यह माना जाता है कि प्रत्येक मध्यवर्ती नेटवर्क नोड के लिए कुल आवक प्रवाह कुल आउटगोइंग प्रवाह के बराबर होना चाहिए, समस्या को निम्नानुसार तैयार किया जा सकता है:

बाधाओं के तहत अधिकतम करें:

आइए अंजीर के अनुसार वर्कशीट पर डेटा दर्ज करें। 3.12.

चावल। 3.12. अधिकतम प्रवाह समस्या को हल करने के लिए डेटा

कक्षों की श्रेणी A6:Q6 को चरों के परिकलित मानों को सौंपा जाएगा। कक्ष A8:A14, साथ ही लक्ष्य कक्ष F13 में, निम्न सूत्र दर्ज करें

समाधान की खोज शुरू करने के बाद, हम निम्नलिखित प्रतिबंध लगाएंगे:

डायलॉग बॉक्स में समाधान खोजना in कक्षों की श्रेणी बदलने के लिए, A6:Q6 निर्दिष्ट करें।

समाधान के परिणामस्वरूप, हमें उत्तर मिलता है: ; चापों में प्रवाह नीचे प्रस्तुत किया गया है

यह ध्यान दिया जाना चाहिए कि इस समस्या का एक गैर-अद्वितीय इष्टतम समाधान है, अर्थात, 17 इकाइयों के अधिकतम प्रवाह के साथ, चापों पर प्रवाह का एक अलग वितरण हो सकता है।