حل مسئله معکوس مینیمم برش در شبکه های پویا (فایل فارسی به همراه ترجمه عالی انگلیسی آن)

چکیده:

در این مقاله مسئله معکوس مینیمم برش پویا را مورد مطالعه قرار میدهیم. این مسأله عبارت است از چگونگی تغییر بردار ظرفیت u  به طوری که برش پویای داده شده مینیمم شود و در ضمن کمترین فاصله را از ظرفیت های موجود مسئله داشته باشند. در این مقاله برای بدست آوردن این تغییرات از نرم اقلیدسی  استفاده شده است. همچنین نشان داده شده است که این مسئله را می توان با حل یک مسئله جریان ماکزیمم در شبکه توسعه یافته زمانی حل کرد. ابتدا به توضیح الگوریتم حل مسئله جریان ماکزیمم، می پردازیم. سپس به تجزیه و تحلیل ارتباط شبکه توسعه یافته زمانی، مسأله جریان ماکزیمم با مسأله مورد نظر میپردازیم. در نهایت الگوریتمی برای حل مسئله معکوس مینیمم برش پویا تدوین میگردد و روی یک مثال عددی از شبکه جریان پویا پیاده سازی میشود.