اجازه دهید یک نمودار جهت دار داده شود G= , که جهت هر قوس vOVبه معنای جهت جریان (مثلاً جریان اتومبیل ها)، توان عملیاتی هر قوس برابر است با d (v).در بسیاری از قله ها Eدو راس انتخاب شد تیو س. راس تیمنبع جریان است، س- موجودی. تعیین حداکثر جریان قابل عبور از بالا الزامی است تیکه در س .

با نشان دادن x(v)مقدار جریانی که در یک قوس حرکت می کند v. بدیهی است که

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

در هر اوج iOE\(t,s)حجم جریان ورودی برابر با حجم جریان خروجی است، یعنی. برابری عادلانه

(x(v)|i О V + (i))= (x(v)| iО V - (i))

(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)

برای راس s

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

ارزش سمقدار جریانی است که از راس خارج می شود تیو به سمت بالا می رود س.

برای تعریف لازم است

Q®max(6.5)

تحت محدودیت (6.1-6.4).

مقادیر Q، x(v)، vnV،ارضای قیود (6.1-6.4) جریان شبکه نامیده می شود و اگر مقدار را به حداکثر برسانند س، سپس حداکثر جریان. به راحتی می توان متوجه شد که ارزش ها Q=0، x(v)=0، vnV، یک جریان در شبکه هستند.

مسئله (6.1-6.5) یک مسئله برنامه ریزی خطی است و با الگوریتم های روش سیمپلکس قابل حل است.

مجموعه راس E را به دو قسمت غیر متقاطع E1 و E2 تقسیم می کنیم به این ترتیب که tОE1، sОE2. قطع كردن V(E1,E2)جدا کردن تیو سما مجموعه را صدا خواهیم کرد V(E1,E2)ÌVبه طوری که برای هر قوس v О V(E1,E2)یا h1(v)нE1و h2(v)нE2، یا h1(v)нE2و h2(v)нE1.

بیایید مجموعه را تقسیم کنیم V(E1,E2)به دو بخش V(E1،E2،+)،V(E1،E2،-)به روش زیر:

V(E1,E2,+)=(vнV(E1,E2)| h1(v)нE1و h2(v)нE2)

V(E1,E2,-)= ( vнV(E1,E2)| h2(v)нE1و h1(v)нE2)

توان عملیاتی برش نامیده می شود

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

به شرح زیر

قضیه 1. (درباره حداکثر دبی و حداقل برش).

در هر شبکه، مقدار حداکثر جریان از منبع تیانبار کردن سبرابر با حداقل توان عملیاتی است Q(E1,E2)در میان همه برش ها V(E1,E2)رگه ها تیو س.

توجه داشته باشید که در حداکثر جریان

x(v)=d(v)، vнV(E1،E2،+)،

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

اجازه دهید Q، x(v)، vOV، -مقداری جریان در شبکه، توالی

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

زنجیره ای است که رئوس را به هم متصل می کند تیو س. اجازه دهید جهت حرکت را از بالا روی این زنجیره تنظیم کنیم تیبه س. قوس v(j)از این زنجیره اگر جهت آن با جهت حرکت از منطبق باشد خط مستقیم نامیده می شود تیبه س، و در غیر این صورت معکوس. ما این مدار را یک مسیر می نامیم. افزایش جریان، اگر برای قوس های مستقیم vزنجیر x(v)< d(v) و برای معکوس x(v) > 0. جریان اضافی را می توان از این مدار عبور داد qاز جانب تیبه ساندازه q = min(q1,q2)جایی که q1=min(d(v)-x(v))، حداقل در تمام قوس های مستقیم زنجیره گرفته می شود، q1=min(x(v))، حداقل روی تمام قوس های عقب زنجیره گرفته می شود.

قضیه 2.

جریان Q، x(v)، vнV، حداکثر اگر و تنها در صورتی که راهی برای افزایش جریان وجود نداشته باشد.

الگوریتم پیشنهادی برای حل مشکل حداکثر جریان در شبکه مبتنی بر یافتن راهی برای افزایش جریان از تیکه در س، که به نوبه خود بر اساس فرآیند برچسب گذاری رئوس است. این را خواهیم گفت

راس منبا علامت مشخص شده است q(i)>0، و همچنین قوس مستقیم قوس شناخته شده است v(i)، که از طریق آن این جریان آمده است یا با علامت مشخص شده است ، اگر مقداری جریان اضافی با قدر باشد q(i)>0، و قوس عقب نیز شناخته شده است v(i)، که از طریق آن این جریان وارد شد;

راس i در صورتی اسکن می شود که تمام رئوس مجاور آن علامت گذاری شده باشند.

اگر راس s برچسب گذاری شده باشد، راهی برای افزایش جریان یافت می شود q، که در این مسیر پرش می شود. برای توصیف الگوریتم به یک آرایه نیز نیاز داریم SPW، که شامل تعداد رئوس برچسب گذاری شده به ترتیب برچسب گذاری شده است. C1- عدد در آرایه SPWاوج مشاهده شده، C2- شماره آخرین راس برچسب گذاری شده در این آرایه.

الگوریتم محاسبه حداکثر جریان در شبکه ها

من تکرار. مرحله 2. انتخاب مسیرهای مستقل در شبکه و تعیین جریان در آنها.مانند م 1 مسیر را انتخاب کنید( v و =V 1 ، V 2 ، V 5 , v c \u003d V 7) در نظر گرفته شده در مثال 1. برای او ولی(م 1) = 10.

همچنین تشخیص مستقل از آن آسان است م 1 مسیر م 2 = (v و =V 1 ، V 3 ، V 6 , v c \u003d V 7). بیایید حداکثر توان را برای آن محاسبه کنیم و توان کمان ها را تنظیم کنیم: ولی(م 2)= دقیقه{د 13 ، د 36 ، د 67 } = دقیقه{45, 40, 30} = 30. د 13¢ =د 13 - 30 = 15، د 36¢ =د 36 - 30 = 10، د 67¢ =د 67 - 30 = 0.

تکرار دوم. گام 2.ما به عنوان تنها مسیر مستقل در پیش می گیریم م 3 = (v و =V 1 ، V 4 ، V 2 ، V 5 , v c \u003d V 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 ب آورده شده است.

اگر چندین منبع در شبکه مشخص شده باشد، با معرفی یک منبع مشترک جدید که توسط کمان هایی با پهنای باند نامحدود به منابع اصلی متصل می شود، تکمیل می شود. سپس مشکل طبق الگوریتم معمول حل می شود. جریان های مورد نظر از طریق منابع اصلی، جریان هایی هستند که در امتداد کمان های جدید اضافه شده از یک منبع مشترک جدید وارد آنها می شوند. در صورتی که چندین پریز در شبکه وجود داشته باشد همین امر صدق می کند.

برنامه ریزی شبکه

هر کار طراحی یا ساخت یک شی نسبتاً پیچیده ( پروژه) را می توان به چند مرحله جزء کوچکتر تقسیم کرد. از جانب انتخاب صحیحتوالی این مراحل به زمان بندی کل پروژه بستگی دارد.

کل مجموعه اقدامات برای اجرای پروژه در قالب یک مجموعه ارائه شده است مناسبت هاو آثار. رویدادها مراحل تکی پروژه نامیده می شوند. مشاغل فرآیندی هستند که طی آن تکمیل می شوند. کل مجموعه رویدادها و کارهای لازم برای اجرای پروژه را می توان به صورت یک شبکه دو قطبی نشان داد G =({v i، v z} ، V، X)، که در آن:

و همه تحولاتبا رئوس زیاد مشخص شده است V،در میان آنها برجسته شده است رویداد اولیه v و(شروع کار) و رویداد نهایی 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). اجازه دهید، برای قطعیت، این شبکهکار بعدی را شرح می دهد.

سایت های تولید نفت در موقعیت های جغرافیایی قرار دارند. نفت از محل های تولید از طریق برخی نقاط میانی به پالایشگاه ها منتقل می شود. مجموعه ای از نقاط با مسیرهای حمل و نقل که آنها را به هم متصل می کند به صورت یک شبکه در شکل 1 نشان داده شده است. 3.10، قوس ها مربوط به بزرگراه ها، و رئوس مربوط به نقاط منفرد (محل های معدن، کارخانه ها، ایستگاه های پمپاژ یا ایستگاه های راه آهن) است. توان عملیاتی بزرگراه های حمل و نقل به قوس های شبکه اختصاص داده می شود. برای تعیین حداکثر مقدار نفت قابل حمل از محل های تولید به پالایشگاه ها، باید با افزودن یک منبع ساختگی و یک سینک ساختگی، شبکه را گسترش داد (قوس های ساختگی در شکل با خطوط بریده ترسیم شده اند).

بدیهی است که میزان جریان هم در شبکه اصلی و هم در شبکه توسعه یافته توسط توان عملیاتی قوس های شبکه اصلی تعیین می شود. بنابراین، مشکل حداکثر جریان از یک منبع به یک مجموعه از سینک ها معادل مشکل حداکثر جریان از یک منبع به یک سینک است.

برنج. 3.10. معرفی منبع و سینک ساختگی

مثال 3

بیایید مثالی از حل مشکل حداکثر جریان در اکسل ارائه دهیم. برخی از شبکه های حمل و نقل را در نظر بگیرید (شکل 3.11.). ما همچنین فرض می‌کنیم که جریان‌های ترافیکی می‌توانند در هر دو جهت برخی از کمان‌ها حرکت کنند (بدیهی است که حل این مورد عمومی‌تر و دشوارتر از مورد جریان‌های ترافیکی یک طرفه است). شکل حداکثر توان عبوری را در هر دو جهت نشان می دهد: به عنوان مثال، از نقطه 3 به نقطه 6 می توان جریانی با شدت 4 واحد را انتقال داد و همان جریان را از نقطه 6 به نقطه 3 (صفر در انتهای برخی از کمان ها به معنی عدم امکان حمل و نقل در جهت مربوطه). لازم است حداکثر توان عملیاتی شبکه به عنوان یک کل تعیین شود، یعنی. حداکثر مقدار جریان

برنج. 3.11. نمودار شبکه مثال 3.

راه حل.

از آنجایی که فرض می شود برای هر گره شبکه میانی، کل جریان ورودی باید برابر با کل جریان خروجی باشد، مشکل را می توان به صورت زیر فرموله کرد:

به حداکثر رساندن تحت محدودیت ها:

بیایید داده ها را مطابق شکل بر روی کاربرگ وارد کنیم. 3.12.

برنج. 3.12. داده ها برای حل مسئله حداکثر جریان

محدوده سلول های A6:Q6 به مقادیر محاسبه شده متغیرها اختصاص داده می شود. در سلول های A8:A14 و همچنین در سلول هدف F13 فرمول های زیر را وارد کنید

پس از شروع جستجوی راه حل، محدودیت های زیر را معرفی می کنیم:

در پنجره محاوره ای یافتن راه حل برای تغییر محدوده سلول ها، A6:Q6 را مشخص کنید.

در نتیجه حل به جواب می رسیم: ; جریان در کمان در زیر ارائه شده است

لازم به ذکر است که این مشکل دارای یک راه حل بهینه غیر منحصر به فرد است، یعنی با حداکثر دبی 17 واحد ممکن است توزیع متفاوتی از جریان ها بر روی قوس ها وجود داشته باشد.