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

Combinatorial Optimization

شماره درس: ۴۰۷۸۵ تعداد واحد: ۳
مقطع: کارشناسی ارشد نوع درس: نظری
پیش‌نیاز: – هم‌نیاز: –

اهداف درس

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

ریز مواد

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

ارزیابی

مراجع

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