پایان نامه > کتابخانه مرکزی دانشگاه صنعتی شاهرود > علوم ریاضی > مقطع دکتری > سال 1400
پدیدآورندگان:
شاهده امیدی نورابادی [پدیدآور اصلی]، جعفر فتحعلی[استاد راهنما]، مهرداد غزنوی[استاد مشاور]
چکیده: چکیده
در این رساله مسائل مکانیابی معکوس و مکانیابی متعادل را با هم ترکیب کردهایم. در یک مدل، مسئله مکانیابی متعادل معکوس با طول یالهای متغیر با کمترین هزینه و بودجه محدود روی درخت در نظر گرفتهایم. هدف مسئله در حالت با کمترین هزینه، اصلاح طول یالها با کمترین هزینه، به گونهای است که اختلاف بین ماکزیمم و مینیمم وزن مشتریهای تخصیص یافته به دو سرویسدهنده(میانه)، مینیمم شود. حالت دیگر این مسئله را با بودجه محدود در نظر گرفتیم. این بودجه را برای اصلاح طول یالها طوری که اختلاف بین ماکزیمم و مینیمم وزن مشتریهای تخصیص یافته به دو سرویسدهنده تا حد امکان کاهش یابد در نظر گرفتهایم. برای هر دو حالت دو
الگوریتم با پیچیدگی زمانی O(nlogn) ارائه کردهایم.
علاوه براین مدل، مسئله مکانیابی تک سرویسدهنده متعادل معکوس را روی درخت معرفی کردیم و قصد داریم طول یالها را با کمترین هزینه تغییر دهیم به طوری که اختلاف فاصله بین دورترین و نزدیکترین مشتری از میانه مینیمم شود. دو حالت را برای این مسئله در نظر گرفتیم حالتی که طول یالها نامحدود و حالتی که طول یالها محدود باشد. در حالت نامحدود نشان دادیم که مسئله میتواند برای حل به یک مسئله روی گراف ستارهای کاهش یابد. سپس یک الگوریتم با پیچیدگی زمانی O(nlogn) برای پیدا کردن جواب بهینه ارائه شد. برای حالت طول یالهای محدود یک الگوریتم با پیچیدگی زمانی O(n^2) ارائه شد.
کلید واژه ها (نمایه ها):
#کلمات کلیدی: مسئله مکانیابی #مکانیابی معکوس #مکانیابی متعادل #مسئله میانه.
محل نگهداری: کتابخانه مرکزی دانشگاه صنعتی شاهرود
یادداشت: حقوق مادی و معنوی متعلق به دانشگاه صنعتی شاهرود می باشد.
تعداد بازدید کننده: