بهینه‌سازی ترکیبیاتی

هدف این درس آشنایی دانشجو با بهینه‌سازی ترکیبیاتی از طریق بررسی مسائل بهینه‌سازی و الگوریتم‌های خاص این حوزه از جمله الگوریتم‌های Simplex و Prime-Dual، دوگانی و برنامه‌ریزی خطی صحیح است.

1. مسئله‌های بهینه‌سازی
   • معرفی، همسایگی، بهینه‌سازی محلی و سراسری، مجموعه و توابع محدب، مسئله‌های برنامه‌ریزی محدب
2. الگوریتم Simplex
   • فرم‌های مسئله‌ی برنامه‌ریزی خطی، راه‌حل امکان‌پذیر، هندسه‌ی برنامه‌ریزی خطی، الگوریتم و پیچیدگی سیمپلکس، جنبه‌های هندسی انتخاب محور
3. دوگانی
   • دوگان برنامه‌ریزی خطی در حالت کلی، Slackness، مسئله‌ی کوتاه‌ترین مسیر ودوگان آن، مسئله‌ی شبکه‌ی شاره، دوگان الگوریتم سیمپلکس، جنبه‌های محاسباتی الگوریتم سیمپلکس
4. الگوریتم Primal-Dual
   • الگوریتم و کاربرد آن در شبکه‌ی شاره و مسئله‌های کوتاه‌ترین مسیر دایکسترا، الگوریتم‌های کارا برای مسئله‌های شبکه‌ی شاره، تطابق (عادی و وزن‌دار)، درخت‌های پوشای کمینه
5. برنامه‌ریزی خطی صحیح
   • ان‌پی-تمام بودن مسئله و راه‌های تقریبی، استفاده از بهینه‌سازی در حل تقریبی مسئله‌های ان‌پی-سخت

• تمرین‌های نظری: ۳ نمره
• آزمون‌های میان‌ترم و پایانی: ۱۵ نمره
• گزارش پژوهشی: ۲ نمره