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

Combinatorial Optimization

مقطع: تحصیلات تکمیلی گرایش: الگوریتم‌ها و محاسبات
نوع درس: نظری تعداد واحد: ۳
پیش‌نیاز: – هم‌نیاز: –

هدف کلی

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

سرفصل‌ها

  1. مسائل بهینه‌سازی
  2. مجموعه‌ها و توابع محدب
  3. هندسه‌ی برنامه‌ریزی خطی
  4. دوگان برنامه‌ریزی خطی
  5. الگوریتم سیمپلکس
  6. دوگان الگوریتم سیمپلکس
  7. الگوریتم‌های اولیه-دوگان
  8. الگوریتم‌های شبکه‌های شار
  9. مسائل تطابق و کوتاه‌ترین مسیر
  10. برنامه‌ریزی خطی صحیح
  11. کاربرد در الگوریتم‌های تقریبی

ارزیابی پیشنهادی

منابع پیشنهادی

  1. C. H. Papadimitriou and K. Steiglitz. Combinatorial Optimization: Algorithms and Complexity. Dover Publications, 1998.