مجله تحقیق در عملیات در کاربردهای آن ( ریاضی کاربردی سابق )

در این مقاله دو مساله پوشش هاب تک تخصیصی با ساختار ستاره‌ای که شامل دو مساله ماکزیمم پوشش p-هاب و پوشش هاب با در نظر گرفتن هزینه انتقال جریان است، مورد بررسی قرار می­گیرد. ساختار ستاره‌ای شبکه به گونه‌ای ‌است که یک هاب مرکزی با مکان مشخص وجود دارد و سایر هاب‌ها به طور مستقیم به هاب مرکزی متصل می‌شوند. در مساله اول هدف انتخاب مکان p  هاب و تخصیص هر مشتری به حداکثر یک هاب است به طوری که کل تقاضای انتقال یافته بین مشتریان ماکزیمم شود. هدف مساله دوم حداقل‌سازی مجموع هزینه ثابت احداث هاب‌ها و هزینه انتقال جریان بین گره‌های شبکه است به طوری که پوشش کامل در شبکه ایجاد شود. در هر دو مساله اتصال مشتریان به مراکز هاب و هاب‌ها به هاب مرکزی به گونه‌ای خواهد بود که فاصله مبادی تا مقاصد با در نظر گرفتن فاکتور تخفیف برای اتصال بین هاب و هاب مرکزی از مقدار از پیش تعیین شده کمتر یا مساوی است. در هر دو مساله پس از ارائه مدل ریاضی، به خطی‌سازی آن‌ها و سپس استفاده از آزادسازی لاگرانژ به منظور یافتن کران‌های مناسبی پرداخته شده است. علاوه بر این، در مساله دوم نامساوی‌های معتبری معادل دو محدودیت مساله ارائه شده است. در نهایت، نتایج حاصل از حل مدل‌های خطی، غیرخطی و بکارگیری آزادسازی لاگرانژ بررسی و مقایسه شده است. بررسی این نتایج بر روی مجموعه داده‌های CAB بیانگر آن است که مدل‌های خطی هم از لحاظ مقدار بهینه تابع هدف و هم زمان اجرا بسیار مطلوبتر از مدل‌های غیرخطی است. همچنین با توجه به نتایج، کران‌های بدست آمده از الگوریتم آزادسازی لاگرانژ فاصله کمی با جواب بهینه مسائل دارد.