गणना एल्गोरिथ्म अधिकतम प्रवाहनेटवर्क में
चरण 1. प्रारंभिक कार्य।वर्तमान मूल्य परनेटवर्क में अधिकतम प्रवाह को मान 0 दिया गया है। चरण 2. नेटवर्क में स्वतंत्र मार्गों का चयन करना और उनमें प्रवाह का निर्धारण करना।स्रोत से सिंक तक नेटवर्क में संभावित मार्गों के पूरे सेट से, हम स्वतंत्र मार्गों का चयन करते हैं एम 1 , … , एम के, नहीं हो रहे सामान्य शीर्ष, प्रारंभिक को छोड़कर (स्रोत वी और) और अंतिम (ड्रेन) वी के साथ). प्रत्येक चयनित मार्ग के लिए एम मैं(1£ मैं£ क) अधिकतम प्रवाह निर्धारित करें ए(एम मैं).चरण 3. नेटवर्क में अधिकतम प्रवाह के वर्तमान मूल्य का सुधार।हम उन लोगों को जोड़ते हैं जो यहां पाए गए हैं चरण दोस्वतंत्र मार्गों में अधिकतम प्रवाह का मान एम 1 , … , एम केवर्तमान कुल अधिकतम नेटवर्क प्रवाह के लिए: पर:= ए टी + ए(एम 1)+ ए(एम 2)+…+ ए(एम के)चरण 4. नेटवर्क सुधार।पर पाया गया चरण दोअधिकतम प्रवाह ए(एम 1), … , ए(एम के) संबंधित नेटवर्क आर्क की क्षमता से घटाया गया। शून्य अवशिष्ट क्षमता वाले आर्क हटा दिए जाते हैं। चरण 5. एल्गोरिथम के पूरा होने की जाँच करना।यदि सुधार के बाद नेटवर्क में स्रोत से कोई मार्ग नहीं बचा है वी औरसंग्रहण करना वी के साथ, तो नेटवर्क में आवश्यक अधिकतम प्रवाह पाए गए करंट के बराबर है ए:= ए टी, एल्गोरिथम समाप्त हो जाता है क्योंकि सभी नेटवर्क क्षमता समाप्त हो गई है। यदि समायोजित नेटवर्क में स्रोत से मार्ग हैं वी औरसंग्रहण करना वी के साथ, फिर जाएं चरण दोऔर एल्गोरिथम निष्पादन की निरंतरता . उदाहरण 2.इस एल्गोरिथम का उपयोग करके चित्र 1.15 में नेटवर्क में अधिकतम प्रवाह ज्ञात करें। समाधान.चरण 1. प्रारंभिक कार्य. पर: = 0.मैं पुनरावृत्ति. चरण 2. नेटवर्क में स्वतंत्र मार्गों का चयन करना और उनमें प्रवाह का निर्धारण करना।जैसा एम 1 मार्ग लें( वी और = वी 1 , वी 2 , वी 5 , वी एस =वी 7), उदाहरण 1 में माना गया। उसके लिए ए(एम 1) = 10.
स्वतंत्र को अलग करना भी आसान है एम 1 मार्ग एम 2 = (वी और = वी 1 , वी 3 , वी 6 , वी एस =वी 7). आइए इसके लिए अधिकतम थ्रूपुट की गणना करें और आर्क्स के थ्रूपुट को समायोजित करें: ए(एम 2)=मिनट{डी 13 ,डी 36 ,डी 67 } =मिनट{45, 40, 30} = 30. डी 13¢ =डी 13 - 30 = 15,डी 36¢ =डी 36 - 30 = 10,डी 67¢ =डी 67 - 30 = 0.
चरण 3. नेटवर्क में अधिकतम प्रवाह के वर्तमान मूल्य का सुधार। पर:= ए टी + ए(एम 1)+ ए(एम 2) = 0 + 10+ 30 = 40.चरण 4. नेटवर्क सुधार।पर पाया गया चरण दोअधिकतम प्रवाह ए(एम 1), ए(एम 2) मार्गों में एम 1 , एमउनके चापों की धारिता से 2 घटाया जाता है। शून्य अवशिष्ट क्षमता वाले आर्क हटा दिए जाते हैं। परिणाम चित्र 1.16 ए में दिया गया है। ए) बी) चित्र 1.16। पुनरावृत्तियों के बाद नेटवर्क सुधार का परिणाम मैंऔर IISTEP 5. एल्गोरिथम के पूरा होने की जाँच करना।समायोजित नेटवर्क (चित्र 1.16 ए) में स्रोत से मार्ग हैं वी औरसंग्रहण करना वी के साथ, उदाहरण के लिए एम 3 = (वी और = वी 1 , वी 4 , वी 2 , वी 5 , वी एस =वी 7). एल्गोरिथम का निष्पादन जारी रखना .द्वितीय पुनरावृत्ति. चरण दो।एकमात्र स्वतंत्र मार्ग के रूप में हम अपनाते हैं एम 3 = (वी और = वी 1 , वी 4 , वी 2 , वी 5 , वी एस =वी 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.
चरण 3. एक टी:= ए टी + ए(एम 3) = 40 + 10= 50.चरण 4. नेटवर्क सुधार।अधिकतम प्रवाह ए(एम 3) मार्ग के चापों से घटाएँ एम 13 . परिणाम चित्र 1.16 बी में दिया गया है।
चरण 5.समायोजित नेटवर्क में कोई सोर्स-टू-सिंक मार्ग नहीं बचा है। ए:= ए टी:= 50, एल्गोरिथम का पूरा होना। उत्तर:चित्र 1.15 में नेटवर्क में अधिकतम प्रवाह 50 है।यदि नेटवर्क में कई स्रोत निर्दिष्ट हैं, तो यह एक नया सामान्य स्रोत शुरू करके पूरा किया जाता है, जो असीमित क्षमता वाले आर्क द्वारा मूल स्रोतों से जुड़ा होता है। तब जाकर समस्या का समाधान होता है सामान्य एल्गोरिथम के अनुसार. मूल स्रोतों के माध्यम से आवश्यक प्रवाह नए सामान्य स्रोत से प्रवेश करने वाले नए जोड़े गए चापों के साथ प्रवाहित होंगे। यदि नेटवर्क में कई नालियां हैं तो भी ऐसा ही करें।
नेटवर्क योजना
किसी काफी जटिल वस्तु के डिजाइन या निर्माण का कोई भी कार्य ( परियोजना) को कई छोटे घटक चरणों में विभाजित किया जा सकता है। से सही चुनावइन चरणों का क्रम पूरे प्रोजेक्ट के समय पर निर्भर करता है।
परियोजना को लागू करने के लिए कार्रवाइयों की पूरी श्रृंखला एक सेट के रूप में प्रस्तुत की गई है आयोजनऔर काम करता है. घटनाओं को किसी परियोजना के व्यक्तिगत चरण कहा जाता है। कार्य उसे पूरा करने की प्रक्रिया है। परियोजना को पूरा करने के लिए आवश्यक घटनाओं और कार्यों के पूरे परिसर को दो-पोल नेटवर्क के रूप में दर्शाया जा सकता है जी =({वी और, वी जेड} , वी, एक्स), जिसमें:
और सभी आयोजनशीर्षों के एक सेट द्वारा चिह्नित वी,उनके बीच प्रकाश डाला गया प्रारंभिक घटना वी और(काम की शुरुआत) और अंतिम घटना v z(संपूर्ण परियोजना का समापन), नेटवर्क के आंतरिक शीर्ष परिभाषित करते हैं मध्यवर्ती घटनाएँ- वे चरण जिन्हें प्रक्रिया में पूरा करने की आवश्यकता है परियोजना कार्यान्वयन,
बी) सब कुछ कामघटनाओं के युग्मों - शीर्षों को जोड़ने वाले चाप द्वारा इंगित किए जाते हैं।
इस नेटवर्क का ग्राफ़िकल प्रतिनिधित्व कहलाता है नेटवर्क आरेख।क्रियाओं के क्रम को इंगित करने के लिए नेटवर्क आरेख भी दर्ज करें काल्पनिक कार्य, जो किसी भी कार्य को करने से संबंधित नहीं हैं। संबंधित कार्यों को धराशायी चाप द्वारा दर्शाया गया है।
उदाहरण के तौर पर, कुछ उत्पादन के संगठन पर विचार करें। परियोजना के लिए निम्नलिखित कार्य की आवश्यकता है:
I) विपणन अनुसंधान, II) उपकरण पर पूर्व-डिज़ाइन अनुसंधान, III) बिक्री नेटवर्क का आयोजन, IV) संचालन करना प्रचार अभियान, वी) उत्पादन उपकरण के लिए तकनीकी विशिष्टताओं का विकास, VI) विकास तकनीकी दस्तावेजउत्पादन परिसर और संचार के लिए, VII) मानक उपकरणों की खरीद, VIII) गैर-मानक उपकरणों का डिजाइन और निर्माण, IX) उत्पादन सुविधाओं का निर्माण और संचार की स्थापना, X) मानक उपकरणों की स्थापना, XI) गैर-मानक उपकरणों की स्थापना , XII) कमीशनिंग।
हम इन कार्यों को नेटवर्क आरेख में संगत संख्याओं वाले चापों द्वारा निरूपित करेंगे।
इस परियोजना में घटनाएँ निम्नलिखित होंगी:
1) कार्य का प्रारंभ (प्रारंभिक घटना), 2) समापन विपणन अनुसंधान, 3) प्री-डिज़ाइन अध्ययन पूरा करना, 4) बिक्री नेटवर्क का संगठन, 5) एक विज्ञापन अभियान का संगठन, 6) उत्पादन उपकरण के लिए तकनीकी विशिष्टताओं की तैयारी, 7) उत्पादन परिसर और संचार के लिए तकनीकी दस्तावेज़ीकरण का विकास पूरा करना , 8) मानक उपकरणों की खरीद को पूरा करना, 9) गैर-मानक उपकरणों के डिजाइन और निर्माण को पूरा करना, 10) उत्पादन सुविधाओं का निर्माण और संचार की स्थापना को पूरा करना, 11) उपकरणों की स्थापना और कमीशनिंग कार्य को पूरा करना,
12) परियोजना का पूरा होना (अंतिम घटना)।
हम शीर्षों को संगत संख्याओं के साथ घटनाओं से जोड़ते हैं। नेटवर्क आरेखपरियोजना का कार्यान्वयन चित्र में दिखाया गया है। 1.17:
चित्र.1.17. परियोजना कार्यान्वयन नेटवर्क अनुसूची
हैमिल्टनियन चक्र
ग्राफ़ एक मैट्रिक्स के रूप में दिया गया है, जहां कोशिकाएं बिंदुओं के बीच आंदोलन की लागत निर्दिष्ट करती हैं। प्रतीक ∞ को अपने अंदर के अर्थहीन पथ को समाप्त करने के लिए मुख्य विकर्ण पर रखा गया है।
क्योंकि यदि परिणामी मैट्रिक्स में शून्य तत्वों के बिना एक कॉलम है, तो हम इसमें न्यूनतम तत्व ढूंढेंगे और इसे इस कॉलम के सभी तत्वों से घटा देंगे।
| ए | बी | सी | डी | |
| ए | ∞ | |||
| बी | ∞ | |||
| सी | ∞ | |||
| डी | ∞ |
आइए सभी घटाए गए तत्वों को जोड़ें और चक्र की निचली सीमा प्राप्त करें में= 2+2+3+2+1=10
1.2. आइए मैट्रिक्स के सभी शून्य तत्वों का मूल्यांकन करें।
शून्य का अनुमान एक तालिका में प्रस्तुत करना सुविधाजनक है।
| ए | बी | सी | डी | |
| ए | ||||
| बी | ||||
| सी | ||||
| डी |
θ=अधिकतम γ=γ ए सी =2
1.3. आइए पथों के सेट को दो उपसमूहों में विभाजित करें: Q एसी।- चाप (एसी) और क्यू युक्त पथ एसी।- वे पथ जिनमें चाप (एसी) नहीं है। दूसरे उपसमुच्चय के लिए निचली सीमा होगी: में / = में + θ =10+2=12.
पहले उपसमुच्चय के लिए सीमा की गणना करने के लिए, हम ए-पंक्ति और सी-कॉलम को पार करते हुए, परिमाण के एक क्रम से नीचे मैट्रिक्स की ओर बढ़ते हैं। नए मैट्रिक्स में रिवर्स पाथ (सीए) को खत्म करने के लिए, हम संबंधित सेल में ∞ का चिह्न लगाते हैं।
आइए परिणामी मैट्रिक्स 2+0=2 की सीमा की गणना करें
और इसे लूप के निचले बॉर्डर पर जोड़ें। यह राशि में //=10+2=12 और पहले उपसमुच्चय के लिए सीमा होगी।
1.4. आइए सभी लटके हुए शीर्षों की सीमाओं की तुलना करें और सबसे छोटी सीमा वाले शीर्ष का चयन करें। यदि इनमें से दो शीर्ष हैं, तो उनमें से कोई एक चुनें। यह Q का शीर्ष है एसी।, जिसकी निचली सीमा =12.
आइए अनुमानों में से अधिकतम चुनें θ=अधिकतम γ=γ BD =3
में /=12+3=15.
1.6. हम बाद के सभी बिंदुओं को पिछले वाले की तरह ही निष्पादित करते हैं।
आइए अनुमानों में से अधिकतम चुनें θ=अधिकतम γ=γ C B =∞
in / =in+ θ=∞
| ए | |
| डी |
इस मैट्रिक्स की सभी पंक्तियों और स्तंभों में शून्य हैं। अत: सीमा 12 के बराबर रहती है।
काम। परिवहन नेटवर्क पर अधिकतम प्रवाह का मान ज्ञात कीजिए।
समस्या का निरूपण.
नेटवर्क पर परिवहन समस्या पर विचार करें ( आई,डी,जी) दी गई चाप क्षमताओं के साथ सी(आई,जे).
आइए दो निश्चित शीर्षों का चयन करें: एस- स्रोत और टी- नाली। नेटवर्क पर स्ट्रीम करें एस→टी आइए संख्यात्मक फ़ंक्शन को कॉल करें एफ, चापों के एक सेट पर परिभाषित और निम्नलिखित को संतुष्ट करता है रेखीय समीकरणऔर असमानताएँ:
0≤ f(i,j) ≤c(i,j)किसी के लिए (आई,जे)
किसी वैरिएबल को अधिकतम करने के लिए आवश्यक है एक्स
कट एलशीर्षों को अलग करने वाले नेटवर्क में अनुसूचित जनजाति
चापों का समुच्चय कहलाता है 
फिर भी एस→टी इसमें कम से कम एक कट आर्क शामिल है।
इष्टतमता मानदंड: एक वास्तविक नेटवर्क पर, एक मनमाना प्रवाह का मूल्य कट के थ्रूपुट से अधिक नहीं होता है, और अधिकतम प्रवाह का मूल्य कट के न्यूनतम थ्रूपुट के बराबर होता है।
उदाहरण 3.12.
एम 9 के
एम 8 के
उदाहरण 3.13.
एम 2 के
समाधान :
आउटगोइंग आर्क (टी,बी) की क्षमता संबंधित शीर्ष में प्रवेश करने वाले आर्क की कुल क्षमता से अधिक है। नेटवर्क को वास्तविक बनाने के लिए, हम c(T,B)=5 को प्रतिस्थापित करते हैं।
आइए सभी कटों की थ्रूपुट क्षमताओं का मूल्य खोजें और गणना करें। (के,वी) - (टी,वी) न्यूनतम थ्रूपुट =6 के साथ काटा जाता है। अत: अधिकतम प्रवाह =6.
कई स्रोतों और सिंक वाले नेटवर्क को एक स्रोत और सिंक वाले नेटवर्क में घटाया जा सकता है।
उदाहरण। मान लीजिए कि कई स्रोत S और सिंक T हैं ( परिवहन समस्या). आइए दो नोड्स s*, t* और सभी आर्क (s*, S) , (T,t*) जोड़कर नेटवर्क का विस्तार करें। आइए सेटिंग द्वारा क्षमता फ़ंक्शन को परिभाषित करें
अंक लगाने की विधि.
1. प्रारंभिक प्रवाह एफ(आई,जे) = 0.
आइए हम इस नेटवर्क के शीर्षों पर लेबल निर्दिष्ट करें, जिसका स्वरूप होगा (आई+, ε)या
(मैं - , ε).आइए स्रोत को चिह्नित करें (-, ∞),
वे . ε(s)= ∞.
2. किसी भी चिह्नित शीर्ष के लिए मैं
सभी लेबल रहित शीर्षों का चयन करें जे
जिसके लिए एफ(आई,जे)
हम इस ऑपरेशन को तब तक दोहराते हैं जब तक कि नाली चिह्नित न हो जाए। यदि प्रवाह लेबल रहित रहता है, तो पाया गया प्रवाह अधिकतम होता है, और चिह्नित शीर्षों को अचिह्नित शीर्षों से जोड़ने वाले चापों का सेट न्यूनतम कट बनाता है।
3. स्टॉक को लेबल करने दें (जे+, ε(टी)), तब एफ(जे,टी)के साथ बदलें एफ(जे,टी)+ε(टी). यदि स्टॉक अंकित है (जे-, ε(टी)), वह एफ(जे,टी)के साथ बदलें एफ(जे,टी)-ε(टी). चलो शीर्ष पर चलते हैं जे. अगर जेएक निशान है (आई+, ε(जे)), फिर हम प्रतिस्थापित करते हैं एफ(आई,जे)पर f(i,j)+ε(t), और अगर (आई-, ε(जे)), एफ(जे,आई)के साथ बदलें एफ(जे,आई)-ε(टी). चलो शीर्ष पर चलते हैं मैं. हम इस ऑपरेशन को तब तक दोहराते हैं जब तक हम स्रोत तक नहीं पहुंच जाते एस।प्रवाह परिवर्तन रुक जाता है, सभी निशान मिट जाते हैं और चरण 2 पर चले जाते हैं
उदाहरण 3.14.
एम 4 के
| 1 कदम | ए → (-, ∞) एम → (ए+,8) पी → (ए+,3) के → (पी+,3) टी → (पी+,3) बी → (टी+,3) | f(T,B)=3 f(P,T)=3 f(A,P)=3 f(P,K)=0 f(A,M)=0 f(M,P)=0 f(M,K)=0 f(M,T)=0 f(K,T)=0 f( के,वी)=0 |
| चरण दो | ए → (-, ∞) एम → (ए+,8) पी → (एम+,1) के → (एम+,4) टी → (एम+,2) | f(K,B)=3 f(M,K)=3 f(A,M)=3 f(T,B)=3 f(P,T)=3 f(A,P)=3 f(P,K)=0 f(M,T)=0 f(M,P)=0 f(K,T)=0 |
| चरण 3 | ए → (-, ∞) एम → (ए+,5) पी → (एम+,1) के → (एम+,1) टी → (एम+,2) बी → (टी+,2) | f(T,B)=5 f(M,T)=2 f(A,M)=5 f(K,B)=3 f(M,K)=3 f(P,T)=3 f(A,P)=3 f(P,K)=0 f(M,P)=0 f(K,T)=0 |
| चरण 4 | ए → (-, ∞) एम → (ए+,3) पी → (एम+,1) के → (एम+,1) टी → (पी+,1) बी → (टी+,1) | f(A,M)=6 f(T,B)=6 f(P,T)=4 f(M,P)=1 f(M,T)=2 f(K,B)=3 f(M,K)=3 f(A,P)=3 f(P,K)=0 f(K,T)=0 |
| चरण 5 | ए → (-, ∞) एम → (ए+,2) पी → (एम-,1) के → (एम+,1) टी → (के+,1) बी → (टी+,1) | f(A,M)=7 f(M,K)=4 f(K,T)=1 f(T,B)=7 f(P,T)=4 f(M,P)=1 f( एम,टी)=2 f(K,B)=3 f(A,P)=3 f(P,K)=0 |
| चरण 6 | ए → (-, ∞) एम → (ए+,1) | प्रवाह इष्टतम f=10 है न्यूनतम कटौती: एम→टी-एम→आर-एम→को |
काम। नेटवर्क पर उच्चतम प्रवाह ज्ञात करें
कलन विधि
आइए शीर्ष को निरूपित करें एस=एक्स 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. इसका मतलब यह है कि सशर्त इष्टतम नियंत्रण उत्तर की ओर जाना है। आइए इसे एक तीर से चिह्नित करें और संबंधित लागत दर्ज करें।
| |
| |
| |
| कार्य 2. कार लोड करने के बारे में (बैकपैक के बारे में)। एन आइटम हैं. ज्ञात वजन एक मैं और मूल्य φi प्रत्येक आइटम। ≤ वजन धारण करने में सक्षम बैकपैक भरने के लिए आवश्यक है आर , वस्तुओं का ऐसा समूह जिसका मूल्य सबसे अधिक होगा।
बैकपैक लोड करने की प्रक्रिया को एन चरणों में विभाजित किया जा सकता है। प्रत्येक चरण में हम यह प्रश्न तय करते हैं: इस वस्तु को लेना है या नहीं लेना है? प्रत्येक चरण में केवल 2 नियंत्रण होते हैं: नियंत्रण =1, यदि हम यह आइटम लेते हैं; और 0 - यदि हम इसे नहीं लेते हैं। अगले चरण से पहले सिस्टम की स्थिति को वजन एस द्वारा दर्शाया जाता है, जो पिछले चरणों के पूरा होने के बाद पूर्ण लोडिंग के अंत तक अभी भी हमारे निपटान में रहता है (कुछ आइटम पहले ही लोड हो चुके हैं), यानी। बैकपैक में खाली जगह की मात्रा। कलन विधि। 1. चलिए आखिरी चरण से शुरू करते हैं। आइए बैकपैक में खाली जगह के बारे में विभिन्न धारणाएँ बनाएं: S=0.1,…R। आइए आखिरी वस्तु को बैकपैक में रखें यदि उसमें पर्याप्त भंडारण स्थान है। 2. प्रत्येक पिछले चरण में, सभी संभावित अवस्थाओं S के लिए, हम 2 विकल्पों पर विचार करते हैं: वस्तु लें या न लें। आइए प्रत्येक मामले में वर्तमान चरण और अगले पहले से ही अनुकूलित चरण पर लाभ के योग के रूप में लाभ ज्ञात करें। हम परिणामों को सहायक तालिका में दर्ज करेंगे। 3. पहले चरण में, हम केवल एकमात्र संभावित स्थिति S=R पर विचार करते हैं। 4. आइए "पीछे की ओर बढ़ते हुए" अर्थात, समाधान खोजें। पहले चरण में इष्टतम नियंत्रण लेते हुए, हम दूसरे चरण में सिस्टम की स्थिति बदलते हैं: S=R– एक्स 1 ए 1और इस स्थिति के लिए इष्टतम नियंत्रण x 2 चुनें। वगैरह। उदाहरण 4.2. आरंभिक डेटा
मुख्य टेबल
सहायक मेज.
उत्तर: x 4 =0; एक्स 3 =1; एक्स 2 =0; एक्स 1 =1; डब्ल्यू=15 कार्य 3. संसाधनों के वितरण पर। एन उद्यम पी 1, पी 2,… पी एन हैं, जिनमें से प्रत्येक आय φ के (एक्स) उत्पन्न करता है यदि इसे एक्स की मात्रा में संसाधन आवंटित किया जाता है। मात्रा A में उपलब्ध संसाधन को वस्तुओं के बीच वितरित करना आवश्यक है ताकि कुल आय अधिकतम हो। मान लीजिए कि x k, kवें उद्यम को आवंटित संसाधन की मात्रा है। तब विचाराधीन समस्या सामान्य समस्या बनकर रह जाती है रैखिक प्रोग्रामिंग.
आइए हम समस्या को एक गतिशील प्रोग्रामिंग समस्या के रूप में तैयार करें। पहले चरण के लिए हम उद्यम पी 1 में धन का निवेश लेंगे, दूसरे के लिए - पी 2 में, आदि। में प्रबंधित प्रणाली इस मामले में- धनराशि जो वितरित की जाती है। प्रत्येक चरण से पहले सिस्टम की स्थिति को एक पैरामीटर द्वारा दर्शाया जाता है - धन का उपलब्ध स्टॉक जो अभी तक निवेश नहीं किया गया है। इस समस्या में, चरण नियंत्रण उद्यमों को आवंटित धनराशि है। इष्टतम नियंत्रण (x 1, x 2,...x N) खोजना आवश्यक है, जिस पर कुल आय अधिकतम है: | 1,1 0,5 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| एस=3 | 0,1 0,5 | 1,1 1,5 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| एस=4 | 0,1 0,5 | 2,1 1,5 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| एस=5 | 0,1 0,5 2,5 | 3,1 2,5 2,5 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| मैं=1 एस=5 | 0,5 1,5 | 3,1 1,1 | 3,1 3,5 2,1 2,6 |
उत्तर: 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. सिमुलेशन मॉडलिंग
इस एल्गोरिदम का विचार स्रोत से सिंक तक सकारात्मक प्रवाह के साथ अंत-से-अंत पथ ढूंढना है।
(प्रारंभिक) क्षमता वाले एक किनारे (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
|
प्रवाह राशि |
दिशा |
||
|
(20,0) - (0,20)=(20, - 20) |
|||
|
(30,0) - (0,30)=(30, - 30) |
|||
|
(10,0) - (0,10)=(10, - 10) |
|||
|
(40,0) - (40,0)=(0,0) |
|||
|
(30,0) - (10,20)=(20, - 20) |
|||
|
(10,5) - (0,15)=(10, - 10) |
|||
|
(20,0) - (0,20)=(20, - 20) |
|||
|
(20,0) - (0,20)=(20, - 20) |
अधिकतम प्रवाह ज्ञात करने के लिए एल्गोरिदम का ग्राफ़िकल अनुक्रमिक निष्पादन (उदाहरण 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)
टेबल तीन। अधिकतम प्रवाह समस्या का समाधान
|
प्रस्थान बिंदु |
गंतव्य |
परिवहन योजना |
बैंडविड्थ |
प्रवाह अधिकतमीकरण के लिए रैखिक प्रोग्रामिंग समस्या।आइए हम रैखिक प्रोग्रामिंग के संदर्भ में अधिकतम प्रवाह समस्या तैयार करें। माना कि बिंदु K से बिंदु M तक परिवहन की मात्रा X KM है। चित्र के अनुसार। 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, X 34। रैखिक प्रोग्रामिंग समस्या का उद्देश्य प्रवाह का रूप है:
एक्स 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.21) पर विचार करें, जिसमें बिंदु 0 (प्रवेश द्वार, उदाहरण के लिए, तैयार उत्पादों का निर्माता का गोदाम) और पी (निकास, वितरण केंद्र, थोक और खुदरा संगठनों के गोदाम, उपभोक्ता) और प्रत्येक चाप (खंड) कनेक्टिंग पॉइंट मैं और जे, संख्या dij > 0 संबद्ध है, कहलाती है THROUGHPUT चाप. थ्रूपुट मान अधिकतम को दर्शाता है अनुमेय मात्रासामग्री प्रवाह जो समय की प्रति इकाई संबंधित चाप के साथ गुजर सकता है।
चावल। 4.21.
एक चाप के साथ गुजरने वाले उत्पादों की मात्रा मैं पहले जे , हम इसे एक चाप के अनुदिश प्रवाह कहेंगे ( मैं ,जे ) तथा द्वारा निरूपित किया जाता है। यह तो स्पष्ट है
यदि हम इस बात को ध्यान में रखते हैं कि नेटवर्क के मध्यवर्ती बिंदु में प्रवेश करने वाला संपूर्ण सामग्री प्रवाह पूरी तरह से इससे बाहर निकलना चाहिए, तो हम प्राप्त करते हैं
हमारे पास इनपुट और आउटपुट पर प्रवाह की समानता की प्राकृतिक आवश्यकता है
हम Z के मान को नेटवर्क में प्रवाह का मान कहेंगे और उपरोक्त शर्तों के अधीन Z को अधिकतम करने की समस्या प्रस्तुत करेंगे।
अधिकतम प्रवाह का पता लगाना न्यूनतम कट के थ्रूपुट को खोजने के लिए नीचे आता है।
आइए मैट्रिक्स रूप में एक सार्वभौमिक खोज एल्गोरिदम पर विचार करें।
एल्गोरिथम के प्रारंभिक चरण में एक मैट्रिक्स का निर्माण होता है डी 0, जिसमें थ्रूपुट मान दर्ज किए जाते हैं (एक असम्बद्ध चाप के लिए हम मैट्रिक्स तत्वों के सममित मान लेते हैं)।
एल्गोरिथम के मुख्य चरण एक निश्चित पथ ढूंढना और इस पथ पर प्रवाह को सही करना है।
पथ ढूँढ़ते समय, हम अंकन प्रक्रिया का उपयोग करते हैं। हम मैट्रिक्स (नेटवर्क इनपुट) की शून्य पंक्ति और स्तंभ को प्रतीक * से चिह्नित करते हैं। 0वीं पंक्ति में हम खोजते हैं, संबंधित कॉलमों को सूचकांकों से चिह्नित करें
और कॉलम लेबल को पंक्तियों में ले जाएँ। फिर हम ith चिह्नित पंक्ति लेते हैं, उसमें एक अचिह्नित कॉलम की तलाश करते हैं, जिससे हम इंडेक्स लेबल से मेल खाते हैं
हम कॉलम लेबल को पंक्तियों में स्थानांतरित करते हैं, और इस प्रक्रिया को तब तक जारी रखते हैं जब तक कि nवां कॉलम चिह्नित न हो जाए।
तब " उलटे हुए"सूचकांकों का उपयोग करके, हम उस पथ का पता लगाते हैं जो η-वें शीर्ष तक ले जाता है, पथ के चापों (मैट्रिक्स तत्वों) की क्षमता को कम करता है वी n और सममित तत्वों को समान मात्रा में बढ़ाएँ।
यह प्रक्रिया चिन्हांकन तक जारी रहती है एन -शीर्ष असंभव नहीं हो जाएगा.
अधिकतम फ्लक्स मूल मैट्रिक्स से घटाकर पाया जा सकता है डी 0, क्षमता मैट्रिक्स के उपरोक्त सुधार के बाद प्राप्त:
उदाहरण 4.4
उत्पादन मास्को में स्थित है. उत्पादों को वितरित करने के लिए, कंपनी बिचौलियों को आकर्षित करती है जो विभिन्न स्तरों पर वितरण केंद्रों के माध्यम से कंपनी के साथ काम करते हैं। रूस के यूरोपीय भाग में एक थोक उद्यम 1 है, जो एक केंद्रीय वितरण केंद्र द्वारा सेवा प्रदान करता है। थोक उद्यम 2 निकट विदेश (यूक्रेन, बेलारूस) में संचालित होता है और एक क्षेत्रीय वितरण केंद्र द्वारा सेवा प्रदान की जाती है। स्थानीय बाजार (मॉस्को और मॉस्को क्षेत्र) में कंपनी के अपने ग्राहक हैं - खुदरा विक्रेता जो शहर वितरण केंद्र से उत्पाद प्राप्त करते हैं। क्षेत्रीय और शहरी वितरण केंद्रों को केंद्रीय वितरण केंद्र से पुनः भंडारित किया जाता है।
आइए वितरण नेटवर्क के एक अंश पर प्रकाश डालें:
- एक विनिर्माण उद्यम के तैयार उत्पादों का गोदाम;
- केंद्रीय वितरण केंद्र;
- क्षेत्रीय वितरण केंद्र;
- शहरी वितरण केंद्र;
- दो थोक उद्यम;
- कंपनी के स्वामित्व वाला खुदरा आउटलेट;
- उपभोक्ता.
चावल। 4.22.
आइए वितरण नेटवर्क के प्रत्येक लिंक को एक संख्या से नामित करें, और क्षमता को आर्क्स के ऊपर रखें। थ्रूपुट क्षमता, लिंक के प्रकार के आधार पर, उत्पादन क्षमता की मात्रा, उपभोक्ताओं की योजनाबद्ध आवश्यकता (मांग) और बाजार क्षमता के संदर्भ में व्यक्त की जा सकती है।
उत्पाद वितरण नेटवर्क ग्राफ़ चित्र में दिखाया गया है। 4.23. आइए एक मैट्रिक्स बनाएं डी 0, जिसमें हम वितरण नेटवर्क लिंक की थ्रूपुट क्षमताओं के मान दर्ज करते हैं (चित्र 4.24)।
चावल। 4.23.
चावल। 4.24.
शून्य पंक्ति से हम शीर्षों (पंक्तियों-स्तंभों) 1, 2 और 3 को सूचकांक μ = 0 के साथ चिह्नित करते हैं और वी, 30.10 और 10 के बराबर.
चिह्नित पंक्ति 1 से, शीर्ष 4 और 5 को सूचकांक μ = 1 और V4 = मिनट (30,15) = 15, V5 = मिनट (30,10) = 10 के साथ चिह्नित करें।
पंक्ति 3 से हम शीर्ष 6 को चिह्नित करते हैं और अंत में, पंक्ति 4 से - शीर्ष 7 को चिह्नित करते हैं (चित्र 4.25)।
चावल। 4.25.
μ के अनुदिश वापस जाने पर हमें पथ मिलता है: शीर्ष 7 से 4 तक, शीर्ष 4 से 1 तक, शीर्ष 1 से 0 तक; तत्वों का समायोजन डी 0 प्रति प्रवाह मान V7 = 15.
अगला चरण प्रवाह 5 के साथ एक पथ देता है (चित्र 4.26)।
चावल। 4.26.
अगला चरण चित्र में दिखाया गया परिणाम देता है। 4.27.
चावल। 4.27.
आगे कोई अंकन संभव नहीं है. यहां से हमें अधिकतम प्रवाह मैट्रिक्स प्राप्त होता है (चित्र 4.28)।
चावल। 4.28.
नेटवर्क में अधिकतम प्रवाह खोजने के लिए एल्गोरिदम लागू करने के परिणामस्वरूप, परिणाम चित्र में प्रस्तुत किए गए हैं। 4.29. ग्राफ़ के आर्क पर दिखाए गए कोष्ठक में संख्याओं के जोड़े आर्क के अधिकतम थ्रूपुट और नेटवर्क को आपूर्ति की गई वस्तुओं की अनुशंसित मात्रा को दर्शाते हैं।
चाप घटना के माध्यम से प्रवाह का योग वी, चाप घटना के माध्यम से प्रवाह के योग के बराबर है डब्ल्यू; इस योग को फ्लक्स मान कहा जाता है। हम मुख्य रूप से उन प्रवाहों में रुचि लेंगे जिनका संभावित मूल्य सबसे बड़ा है - तथाकथित अधिकतम प्रवाह। में सामान्य मामलाएक नेटवर्क में कई अलग-अलग अधिकतम प्रवाह हो सकते हैं, लेकिन उनका मान समान होना चाहिए। (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) विल्सन आर. ग्राफ सिद्धांत का परिचय
