بهینه سازی در شبکه های حداکثر جریان هرزوج گره

چکیده مقاله

شبکه های حداکثر جریان از مباحث مشهور، بنیادی و پرطرف دار در جریان های شبکه بوده و کاربردهای فراوانی در حوزه های مختلف دارند برای حل اینگونه شبکه ها، روش ها و الگوریتم های زیادی با رویکردهای متفاوت جریان دارد در این مقاله، الگوریتم دقیق جدیدی با نام مستطیل آبشاری، با رویکرد افزودن مسیر بر پایه جبرماتریسی و با پیچیدگی زمانی بدترین حالت O n 3 ارایه می شود، بطوریکه مقدار حداکثر جریان و مسیر را از هرزوج گره محاسبه می کند اساس این الگوریتم، انجام حداقل n 2 محاسبات ریاضی در قالب مستطیل هایی هستند که در یک راس مشترکند الگوریتم مستطیل های آبشاری، بجهت وابسته کردن محاسبات ماتریس مسیر به ماتریس جریان بسیار سریع و از طرفی دیگر بجهت انجام محاسبات مستطیلی بسیار جذاب است در پایان، با ارایه یک مثال نمونه الگوریتم مستطیل های آبشاری گام به گام پیاده سازی شده است

کلیدواژه‌ها

نویسندگان

اصغر عینی

دانشجوی دکتری مهندسی صنایع، دانشگاه صنعتی شریف

Kourosh Eshghi

استاد دانشکده مهندسی صنایع، دانشگاه صنعتی شریف

�ینی، اصغر و عشقی، کوروش،1396،بهینه سازی در شبکه های حداکثر جریان هرزوج گره،سومین کنفرانس بین المللی مهندسی صنایع و سیستم­ها (ICISE ۲۰۱۷)،مشهد

ارائه‌شده در

مجموعه مقالات سومین کنفرانس بین المللی مهندسی صنایع و سیستم­ها (ICISE ۲۰۱۷)22 شهریور 1396 · مشهد