بهینه‌سازی گسسته
Discrete Optimization
| نام درس: | بهینه‌سازی گسسته | مقطع: | کارشناسی |
|---|---|---|---|
| پیش‌نیاز: | طراحی و تحلیل الگوریتم‌ها | گروه درس: | تخصصی الزامی |
| هم‌نیاز: | ندارد | نوع درس: | نظری |
| تعداد واحد: | 3 | تعداد ساعت: | 48 |
| حل تمرین: | ندارد |
سرفصل درس:
مروری بر مدل سازی ریاضی. روشهای شمارشی و شاخه و کران برای مسایل بهینه‌سازی. معرفی الگوریتم فراابتکاری برای حل مسایل بهینه‌سازی گسسته. مدلسازی مسایل واقعی به کمک گراف و شبکه. الگوریتمهای تطابق. بررسی کاربردهای مسایل شبکه در حمل و نقل، بهینه‌سازی شبکه و طراحی شبکه. الگوریتمهای مسائل شبکه (جریان بیشینه، برش کمینه)، مسئله پستچی چینی (تور اویلری و حل آن)، مسئله کوله‌پشتی و الگوریتم تقریبی برای آن، برخی مسائل پوشش در گراف و حل آنها، مسئله تخصیص و ارتباط آن با مسئله تطابق بیشینه و روش حل آن، مسئله فروشنده دوره‌گرد با معرفی 2-opt ، 3-opt و NN، مسئله افرازبندی گراف، مسائل مکان‌یابی. اجرای پروژه کاربردی.
منابع:
-
حمدی طه، (۱۳۸۷) آشنایی با تحقیق در عملیات: برنامه‌ریزی خطی پویا و با اعداد صحیح، (م. بازرگان، مترجم). تهران: مرکز نشر دانشگاهی.
-
مهدی قطعی، (1395). تحقیق در عملیات و بهینه‌سازی ترکیبیاتی. تهران: انتشارات ناقوس.
-
Lee, J. (2004). A First Course in Combinatorial Optimization. Cambridge University Press.
-
Cormen, T.H., Leiserson, C.E., Rivest, R.L., & Stein, C. (2009). Introduction to Algorithms (3rd Ed.). The MIT Press.
-
Papadimitriou, C.H., & Steiglitz, R. (1982). Combinatorial Optimization Algorithms and Complexity. Prentice-Hall.
-
Balakrishnan, V. (1995). Network Optimization. Chapman and Hall/CRC.
-
Ahuja, R.K., Magnanti, T.L., & Orlin, J.B. (1993). Network Flows: Theory, Algorithms, and Applications. Prentice-Hall.