نمونه ای از یافتن حداکثر جریان با استفاده از روش فورد-فولکرسون. روشی برای یافتن حداکثر جریان

این راهنما برای دانش آموزانی است که درس ریاضیات گسسته و (یا) نظریه گراف را مطالعه می کنند. با آن به مبحث "حداکثر جریان و حداقل برش در شبکه" مسلط خواهید شد. درست از این راهنما، می توانید IPD خود را محاسبه کنید، حتی اگر MATLAB روی رایانه خود ندارید. اگر متلب دارید، به این صفحه بروید: در آنجا این فرصت را دارید که در اسکریپت محاسبه (برنامه) دخالت کنید. در اینجا، مشکل حداکثر جریان در شبکه با کاهش آن به یک مسئله برنامه ریزی خطی حل می شود.

بیایید نماد را معرفی کنیم:

• n=|V| - اندازه گراف (تعداد رئوس)؛
• متر=|E| - کاردینالیته نمودار (تعداد لبه ها)؛
• آ - ماتریس بروز دیگراف شبکه اندازه n× متر; هر عنصر آن aik=1 اگر از منراس -ام بیرون می آید کقوس -ام؛ aik=-1 اگر در منراس -ام گنجانده شده است کقوس -ام؛ و aik=0 در موارد دیگر. در هر ستون چنین ماتریسی دقیقاً یک، یک منهای یک و بقیه صفر وجود دارد.
• س- شماره گره منبع شبکه؛ فقط قوس ها باید از این راس خارج شوند و هر راس دیگری باید از منبع قابل دسترسی باشد.
• تی- تعداد گره سینک شبکه؛ فقط کمان ها باید وارد این راس شوند و یک سینک باید از هر راس دیگری قابل دسترسی باشد.
• آس − س آ ; باید فقط شامل واحدها باشد، زیرا فقط قوس ها باید از منبع خارج شوند.
• آتی − تی-مین ردیف از ماتریس بروز دیگراف شبکه آ ; باید فقط دارای یک های منفی باشد، زیرا قوس ها فقط باید وارد زهکشی شوند.
• آخیابان- ماتریس بروز دیگراف شبکه آ با کسانی که از آن پرتاب شده اند س-ام و تیخطوط -ام؛
• ه - بردار ستون طول متر; در هر عنصر e kمقدار جریان در خواهد بود کقوس -ام؛
• ج - بردار ستون طول متر; در هر عنصر c k≥0 توان عملیاتی است کقوس هفتم

سپس مشکل حداکثر جریان در شبکه را می توان به عنوان یک مسئله برنامه ریزی خطی فرموله کرد:

جریان کل از منبع (1) به حداکثر می رسد. در عین حال، در هر راس میانی، جریان ورودی برابر با جریان خروجی (2) است و ظرفیت کمان ها محدود است (3).

مشکل دوگانه به حداکثر جریان، مشکل برش حداقل است. برای ساختن برش حداقل می توان از قضایای دوگانگی استفاده کرد. نیاز داشتن:

• تمام خالی را از دیگراف شبکه حذف کنید ( e k= 0) و اشباع شده ( e k = c k) کمان ها؛
• اجزای متصل گراف باقیمانده را پیدا کنید.
• اگر دو جزء از این قبیل وجود داشته باشد، قوس های دور ریخته شده حداقل برش را دارند.
• اگر بیش از دو جزء متصل ظاهر شود، دیگراف شبکه چندین برش حداقلی دارد (مسئله برنامه ریزی خطی مربوطه منحط است).

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

برای عملکرد صحیحبا این صفحه مرورگر شما باید از اسکریپت پشتیبانی کند جاوا اسکریپت. آنها را روشن کنید.

داده های اولیه را در فیلدهای ورودی زیر وارد کنید. در ناحیه اول باید (به طور دقیق تر، می توانید) مختصات رئوس را برای رسم دیگراف شبکه وارد کنید. آنها در قالب یک ماتریس آورده شده اند n×2: در ستون اول − ایکس-ام مختصات، در دوم − y-e. اعداد را می توان به صورت اعداد صحیح، با اعشار یا به صورت نمایی وارد کرد. اعداد را با فاصله جدا کنید. تعداد کل خطوط در این ناحیه ورودی اندازه دیگراف را تعیین می کند n- تعداد رئوس. این داده های اولیه (مختصات رأس) اختیاری هستند: اگر مشخص نشده باشند، نمودار شبکه به صورت منظم رسم می شود. n-gon، و تعداد رئوس با حداکثر عدد راس در ناحیه ورودی بعدی تعیین می شود.

در قسمت ورودی بعدی، قسمت سمت چپ اجباری است. ساختار دیگراف شبکه را تعریف می کند. هر کمان در یک دیگراف دو راس را به هم متصل می کند. اعداد این رئوس در قالب یک ماتریس آورده شده است متر× 2 در سمت چپ ناحیه ورودی دوم. در هر خط ابتدا راس 1 (دم، منبع) کمان مشخص می شود و سپس راس 2 (نوک، سینک) کمان با فاصله از هم جدا می شود. این ستون ها باید باشند اعداد صحیحاز 1 تا nشامل. اعداد را با فاصله جدا کنید. در سمت راست، ظرفیت کمان ها آورده شده است - اعداد واقعی مثبت. اگر این ستون تنظیم نشده باشد، همه پهنای باند یکسان در نظر گرفته می شوند (تک). تعداد کل اعداد در هر یک از این ستون ها، کاردینالیته دیگراف را تعیین می کند متر- تعداد کمان ها.

جریان در شبکه ها

مشکل حداکثر جریان

اجازه دهید یک شبکه داده شود، متشکل از مجموعه ای از رئوس 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 واحد ممکن است توزیع متفاوتی از جریان ها بر روی قوس ها وجود داشته باشد.