مساله ممانعت از st برش کمینه

سال انتشار: 1398
نوع سند: مقاله کنفرانسی
زبان: فارسی
مشاهده: 940

فایل این مقاله در 5 صفحه با فرمت PDF قابل دریافت می باشد

استخراج به نرم افزارهای پژوهشی:

لینک ثابت به این مقاله:

شناسه ملی سند علمی:

ICIORS12_268

تاریخ نمایه سازی: 24 شهریور 1398

چکیده مقاله:

شبکه V,A,u,r با دو راس مشخص s به عنوان راس مبدا و t به عنوان راس مقصد داده شده است. در این شبکه هر یال I,j دارای ظرفیت u(ij) و هزینه r(ij) برای افزایش یک واحد ظرفیت است. مساله ممانعت از برش کمینه در پی آن است تا با در دست داشتن بودجه محدود R اقدام به افزایش ظرفیت یال ها کند به طوری که ظرفیت برش کمینه تا حد ممکن افزایش یابد. در این مقاله این مساله مدل سازی شده و یک الگوریتم برای حل آن ارایه میشود. الگوریتم پیشنهادی برای پیدا کردن جواب بهینه از جستجوی دودوییاستفاده می کند و در هر تکرار یک مساله کمترین هزینه جریان را حل می کند

نویسندگان

مسعود امان

هیات علمی گروه ریاضی، دانشکده علوم، دانشگاه بیرجند

جواد طیبی

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

ابوالفضل عبدالله زاده

دانشجوی دکتری ریاضی، دانشکده علوم، دانشگاه بیرجند