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

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

Keywords:

مسایل ممانعت شبکه , طراحی شبکه , برش کمینه , جستجوی دودویی