حل مسئله معکوس مینیمم برش در شبکه های پویا

9 صفحه فایل ورد فارسی به همراه فایل ورد ترجمه عالی آن به زبان انگلیسی

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

A Solution to the Inverse Minimum Cut Problem in Dynamic Networks

Abstract: This paper studies the problem of inverse minimum dynamic cut (IMDC). This problem is to change a capacity vector u in such a way that the dynamic cut is minimized with the minimum distance from the existing capacities. This paper uses the Euclidean norm l₁ to obtain the changes. In addition, it is shown that the problem can be solved by solving a maximum dynamic flow problem in a time-expanded network. Having explained the solution algorithm to the maximum dynamic flow problem, the relationship between the time-expanded network, the maximum flow problem and the problem of interest is analyzed. Finally, an algorithm is developed and implemented on a numerical sample of a dynamic flow network to solve the inverse minimum dynamic cut problem.