ابزار کاربر

ابزار سایت


درس:۴۰۷۸۵

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

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.
درس/۴۰۷۸۵.txt · آخرین ویرایش: 2019/12/26 01:59 (ویرایش خارجی)