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

در این مقاله مسئله یافتن یک شبکه ارتباطی۱ با حداقل هزینه در نظر گرفته می شود که در آن اولا شبکه چندکالایی۲ و بدون جهت۳ و ثانیا هزینه کمانها توابعی خطی قطعه بندی شده و مقعر۴ از جریانها هستند. چند روش برای حل مسئله بررسی می شوند: روش جستجوی تصادفی ترمودینامیکی، یک رو ش ابداعی بر پایه روش ارائه شده توسط مینوکس و یک روش ساده سازی لاگرانژی برای به دست آوردن حد پایینی همچنین نتایج محاسباتی سه روش بالا ارائه می شوند.

Keywords:

Network flow , Piecewise linear concave function , link-path model , random search methods , lagrangian relaxation method , subgradient method , جریان در شبکه , تابع خطی قطعه بندی شده مقعر , مدل یال- مسیر , روشهای جستجوی تصادفی , روش ساده سازی لاگرانژی , روش زیرگرادیان.