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

مساله کمترین st-برش یکی از مشهورترین مسایل بهینه سازی است که فصل مشترک دسته مسایل برنامه ریزی خطی، بهینه سازی شبکه و بهینه سازی ترکیبیاتی است. جدا از این که این مساله، دوگان مساله معروف بیشترین جریان بوده و از لحاظ نظری اهمیت دارد، از منظر کاربرد نیز بسیار مورد توجه محققین قرار گرفته است. در این مقاله یک توسیع از این مساله را در قالب نظریه بازیها بررسی می کنیم. مساله مورد نظر را ممانعت از کمترین st-برش می نامیم. مساله دارای دو بازیکن مهاجم و مدافع است. مهاجم سعی در انفصال خطوط مواصلاتی بین دو نقطه را با انتخاب کمترین برش داشته و مدافع با استحکام بخشی این خطوط می خواهد جلوی عملکرد مهاجم را تا حد ممکن بگیرد. در این مقاله، یک الگوریتم زمان چندجمله ای برای حل مساله پیشنهاد می شود. این الگوریتم از روش ریشه یابی نیوتن-کاتس استفاده کرده و در تعداد متناهی تکرار جواب دقیق مساله را می یابد.

Keywords:

مساله ممانعت , برش کمینه , الگوریتم نیوتن , ریشه یابی , توابع قطعه قطعه خطی.