الگوریتم تقریبی برای مساله بسته بندی دو بعدی

تعداد 70 صفحه فایل word

چکیده

ما بسته بندی جعبه ها را از طریق اختلاف جایگشت ها انجام می­دهیم، ما مسأله بسته بندی جعبه دو بعدی را با چرخش و بدون چرخش مورد مطالعه قرار می­دهیم. در این جا ما مجموعه ای از جعبه های مستطیل شکل دو بعدی را ارائه می­دهیم و هدف بسته بندی این موارد به تعداد حداقل جعبه های مربع واحد است. ما در مورد بسته بندی متعامد که در آن لبه های جعبه ها، باید به موازات لبه های جعبه تراز وسط قرار داشته باشد را مورد ملاحظه قرار دادیم. نتیجه اصلی ما تقریب -1.405 برای بسته بندی جعبه دو بُعدی با چرخش و بدون چرخش است که به دلیل نظر یانسن و پرادل تقریب های اخیر 1.5 را بهبود می­بخشد است. ما همچنین نشان می­دهیم که یک کلاس گسترده ای از الگوریتم های مبتنی بر گرد کردن نمی تواند تقریب 1.5 را بهبود بخشد.

کلمات کلیدی: بسته بندی مستطیل، بسته بندی جعبه، برنامه ریزی و مسایل تخصیص منابع، الگوریتم تقریبی، بهینه سازی ترکیبی، تسهیلات برنامه ریزی خطی، نظریه ی اختلاف.

 

فهرست مطالب

فصل اول. ۱

تعاریف و مقدمات.. ۱

۱-۱-مجموعه محدب.. ۲

۱-۱-۱-مسائل محدب.. ۲

۱-۲-مفاهیم پایه ای برای گراف.. ۳

تعریف ۱-۲-۲:گراف جهت دار  را یک شبکه گوییم اگر امکان وجود جریان در امتداد یال ها باشد. ۴

تعریف ۱-۲-۳:گراف بدون جهت یک گذر T از رأس  به رأس  در گراف بدون جهت  دنباله ای از رأس ها و یال ها به صورت  است به طوری که: ۴

۱-۳-مسایل بهینه سازی ریاضی.. ۶

۱-۳-۲-مسأله بهینه سازی ترکیبی.. ۸

۱-۳-۴-۱-مسئله ی کوله پشتی بیکران. ۱۰

۱-۳-۸-اصل لانه کبوتری به انگلیسی: (Pigeonhole principle)، ۱۲

۱-۴-برنامه ریزی خطی.. ۱۲

۱-۴-۱-۱-شکاف دوگانگی (duality gap). ۱۳

۱-۴-۱-۲-رابطه ی بین مساله ی اصلی و مساله ی دوگان. ۱۴

۱-۴-۳-الگوریتم کارمارکار. ۱۶

۱-۴-۴-جایگشت… ۱۷

۱-۴-۵-مسأله بهینه سازی پیوسته. ۱۷

فصل دوم. ۱۹

۲-۱-نظریه ی اختلاف.. ۲۲

۲-۲-محدود کردن فاصله از طریق اختلاف ماتریس های یکنواخت… ۲۴

۲-۳-محدود نمودن اختلاف ماتریس های یکنواخت توسط اختلاف جایگشت ها ۲۷

۲-۴-محدود نمودن اختلاف جایگشت ها بر حسب اختلاف ماتریس های یکنواخت : ۲۸

۲-۵-کران های پایین برای الگوریتم مبتنی بر گرد کردن. ۳۱

۲-۵-۲-کران پایین  برای مورد عمومی.. ۳۶

فصل سوم. ۳۹

بهبود الگوریتم تقریبی برای بسته بندی جعبه دو بُعدی.. ۳۹

۳-۱-ترتیب LP: ۴۰

۳-۲-برگشت . ۴۲

۳-۳-الگوریتم های مبتنی گرد کردن. ۴۳

۳-۴-مربوط ساختن الگوریتم مبتنی بر ترتیب LP با اندازه جعبه گردشده ۴۵

۳-۵-R&A برای الگوریتم های مبتنی بر گرد کردن. ۴۶

۳-۶-الگوریتم تقریبی ۵/۱ که جعبه ها را به انواع   گرد    می کند. ۴۸

تکنیک… ۴۸

۳-۷-کران پایین برای الگوریتم های مبتنی بر گرد کردن. ۵۰

منابع. ۵۶

واژه نامه  فارسی به انگلیسی.. ۶۰

واژه نامه  انگلیسی به فارسی.. ۶۱

 

نقد و بررسی‌ها

هیچ دیدگاهی برای این محصول نوشته نشده است.

اولین کسی باشید که دیدگاهی می نویسد “الگوریتم تقریبی برای مساله بسته بندی دو بعدی”
قبلا حساب کاربری ایجاد کرده اید؟
گذرواژه خود را فراموش کرده اید؟
Loading...