بهینه‌سازی ترکیبیاتی
Combinatorial Optimization
| شماره درس: ۴۰۷۸۵ | تعداد واحد: ۳ |
| مقطع: کارشناسی ارشد | نوع درس: نظری |
| پیش‌نیاز: – | هم‌نیاز: – |
اهداف درس
هدف این درس آشنایی دانشجو با بهینه‌سازی ترکیبیاتی از طریق بررسی مسائل بهینه‌سازی و الگوریتم‌های خاص این حوزه از جمله الگوریتم‌های Simplex و Prime-Dual، دوگانی و برنامه‌ریزی خطی صحیح است.
ریز مواد
- مسئله‌های بهینه‌سازی
- معرفی، همسایگی، بهینه‌سازی محلی و سراسری، مجموعه و توابع محدب، مسئله‌های برنامه‌ریزی محدب
- الگوریتم Simplex
- فرم‌های مسئله‌ی برنامه‌ریزی خطی، راه‌حل امکان‌پذیر، هندسه‌ی برنامه‌ریزی خطی، الگوریتم و پیچیدگی سیمپلکس، جنبه‌های هندسی انتخاب محور
- دوگانی
- دوگان برنامه‌ریزی خطی در حالت کلی، Slackness، مسئله‌ی کوتاه‌ترین مسیر ودوگان آن، مسئله‌ی شبکه‌ی شاره، دوگان الگوریتم سیمپلکس، جنبه‌های محاسباتی الگوریتم سیمپلکس
- الگوریتم Primal-Dual
- الگوریتم و کاربرد آن در شبکه‌ی شاره و مسئله‌های کوتاه‌ترین مسیر دایکسترا، الگوریتم‌های کارا برای مسئله‌های شبکه‌ی شاره، تطابق (عادی و وزن‌دار)، درخت‌های پوشای کمینه
- برنامه‌ریزی خطی صحیح
- ان‌پی-تمام بودن مسئله و راه‌های تقریبی، استفاده از بهینه‌سازی در حل تقریبی مسئله‌های ان‌پی-سخت
ارزیابی
- تمرین‌های نظری: ۳ نمره
- آزمون‌های میان‌ترم و پایانی: ۱۵ نمره
- گزارش پژوهشی: ۲ نمره
مراجع
- C.H. Papadimitriou and K. Steiglitz. Combinatorial Optimization: Algorithms and Complexity. Dover Publications, 1998.