Leila Aboosaeidi - کارشناسی ارشد دانشگاه علوم و تحقیقات کرمان
Abdolahad NooriZehmakan - کارشناسی ارشد دانشگاه صنعتی شریف، تهران

بسیاری از مسایل پرکاربرد و مهم بهینه سازی در حوزه های مختلف علم وصنعت از مرتبه ی زمانی بالایی برخوردارند و اصولا در گروه مسایل NP-Hard دسته بندی می شوند. از این رو در سال های اخیر گرایش به سمت الگوریتم های تقریبی که در زمان چند جمله ای و با یک ضریب خطا به حل این مسایل می پردازند، افزایش یافته است. در این مقاله یک الگوریتم تقریبی با ضریب تقریب 3 با استفاده از متدهای برنامه ریزی خطی دوگانه و اولیه برای مساله مکان یابی تسهیلات در حالت K لایه ای با توزیع تصادفی ارائه می شود.

الگوریتم های تقریبی(approximation algorithms)، مساله مکان یابی تسهیلات Problem Facility Location ، ضریب تقریبی (approximation ratio) ، بهینه سازی (optimization)، برنامه ریزی خطی و دوگانه linear programing primal and dual ، تصادفی (Stochastic)