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

محورهای موضوعی : آمار

هاجر بنی خادمی ¹ ( دانشجوی دکتری، گروه ریاضی، دانشگاه آزاد اسلامی واحد کرج، کرج، ایران )
حسن صالحی فتح آبادی ² ( عضو هیأت علمی، گروه ریاضی، دانشگاه آزاد اسلامی واحد کرج، کرج، ایران )

تاریخ دریافت : 1395/03/16 تاریخ پذیرش : 1395/06/31 تاریخ انتشار : 1395/04/01

کلید واژه: Dynamic network flows, Inverse Optimization, Euclidean norms, Hamming&#x0D, &#x0D, distance,

چکیده مقاله :

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

چکیده انگلیسی:

Inverse maximum flow (IMDF), is among the most important problems in the field ofdynamic network flow, which has been considered the Euclidean norms measure in previousresearches. However, recent studies have mainly focused on the inverse problems under theHamming distance measure due to their practical and important applications. In this paper,we studies a general approach for handling the inverse maximum dynamic flow problemunder the weighted sum-type Hamming distance. We assume that a dynamic network flow,and a desired feasible dynamic flow on the network is given. We try to adjust the current arccapacity vector to maximize the dynamic flow and minimize the changes. The motivationfor this study stems from the Hamming distance that is made practically important in thesituation where we only care about the change, disregarding its magnitude. In this paper,first we prove some preliminary results, then we show that this problem (IMDF) can betransformed to a minimum dynamic cut problem. So, we proposed a combinatorialalgorithm for solving the IMDF in strongly polynomial time. Ultimately, the proposedalgorithm, is illustrated by a numerical example on a dynamic network.