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

الموضوعات :

هاجر بنی خادمی ¹ , حسن صالحی فتح آبادی ²

1 - دانشجوی دکتری، گروه ریاضی، دانشگاه آزاد اسلامی واحد کرج، کرج، ایران
2 - عضو هیأت علمی، گروه ریاضی، دانشگاه آزاد اسلامی واحد کرج، کرج، ایران

تاريخ الإرسال : 29 الأحد , شعبان, 1437 تاريخ التأكيد : 20 الأربعاء , ذو الحجة, 1437 تاريخ الإصدار : 16 الثلاثاء , رمضان, 1437

الکلمات المفتاحية: Dynamic network flows, Inverse Optimization, Euclidean norms, Hamming&#x0D, &#x0D, distance,

ملخص المقالة :

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