به طور کلی، هدف این درس آشنایی با مسائل برنامه‌ریزی (بهینه‌سازی) خطی¹⁾ (LP) و برنامه‌ریزی مخروطی²⁾ (CP) است. شرایط لازم و کافی برای جواب بهینه‌ی مسائل LP و CP را مطالعه خواهیم کرد. بر آن اساس الگوریتم‌هایی را برای حل مسائل LP و CP ارائه خواهیم داد. برخی چالش‌ها در پیاده‌سازی الگوریتم‌ها مورد بررسی قرار خواهند گرفت. به طور مختصر زمان اجرا و همگرایی الگوریتم‌ها را بررسی خواهیم کرد. در انتها، کاربردهایی از این رده مسائل در حوزه‌های مختلف علوم و مهندسی، مخصوصا علوم ریاضی و کامپیوتر، ارائه خواهند شد.

• آشنایی با برنامه‌ریزی خطی و تعبیرهای هندسی آن
• تکنیک‌های مدل‌سازی
• مقدمه‌ای بر آنالیز محدب و هندسه چندوجهی
• شرایط لازم و کافی بهینگی برای مساله برنامه‌ریزی خطی
• روش سیمپلکس
• چالش‌های پیاده‌سازی روش سیمپلکس
• نظریه دوگانی و شرط مکمل لَنگی
• روش‌های سیمپلکس دوگان و سیمپلکس اولیه-دوگان
• تحلیل حساسیت
• برنامه‌ریزی پارامتری
• مساله حمل و نقل و مساله تخصیص
• برنامه‌ریزی خطی مقیاس بزرگ و برنامه‌ریزی تصادفی
• روش‌های بیضوی و تحلیل پیچیدگی مساله برنامه‌ریزی خطی
• روش‌های نقطه درونی
• آشنایی با برنامه‌ریزی مخروطی و برنامه‌ریزی نیمه‌معین
• کاربردهایی از برنامه‌ریزی خطی و برنامه‌ریزی مخروطی

پیش‌نیاز اساسی و اصلی این درس، جبرخطی است.

• منابع اصلی:
  1. فصل‌های اول تا ششم، هشتم و نهم کتاب Bertsimas D, Tsitsiklis JN. Introduction to linear optimization. Belmont, MA: Athena Scientific; 1997 Jan
  2. فصل سوم کتاب Conforti M, Cornuéjols G, Zambelli G. Integer programming. Berlin: Springer; 2014 Nov 15
  3. فصل‌های اول تا چهارم کتاب Ben-Tal A, Nemirovski A. Lectures on modern convex optimization: analysis, algorithms, and engineering applications. SIAM; 2001
• منابع کمکی:
  1. Bazaraa MS, Jarvis JJ, Sherali HD. Linear programming and network flows. John Wiley & Sons; 2010 Nov 4
  2. Schrijver A. Theory of linear and integer programming. John Wiley & Sons; 1998
  3. Gärtner B, Matousek J. Approximation algorithms and semidefinite programming. Springer Science & Business Media; 2012

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

کلاس‌ها ساعت ۱۷ تا ۱۹ روز‌های شنبه و دوشنبه در کلاس مجازی مدرس درس به آدرس https://vc.sharif.edu/ch/hani.ahmadzadehs94 برگزار می‌شود.

• تمرین: 6 نمره
• میان‌ترم: 6 نمره
• پایان‌ترم: 8 نمره

تمرین‌ها در بستر درس‌افزار CW بارگذاری و تحویل گرفته خواهند شد. در ابتدای ترم، دانشجویان درس در گروه‌های (حداکثر) چهار نفره تقسیم خواهند شد. در صورت لزوم پس از میان‌ترم تقسیم‌بندی گروه‌ها می‌تواند تغییر کند. تحویل تمرین‌ها به صورت گروهی خواهد بود. پس از تحویل نسخه اولیه، راه‌حل‌ها توسط گروه‌های دیگر مورد بررسی و داوری قرار خواهند گرفت. سپس نظرات به گروه پاسخ‌دهنده ارسال شده تا بر آن اساس پاسخ‌های خود را بازنگری کنند و نسخه نهایی را تحویل دهند. لذا، هر سری تمرین شامل سه فعالیت است که توسط هر گروه باید انجام پذیرد: ۱- حل تمرین‌های اختصاص داده شده به آن گروه، ۲- داوری (تصحیح) راه‌حل‌های گروه دیگر، ۳- بازنگری راه‌حل‌ها بر اساس نظرات و تصحیح‌های ارائه شده. در صورتی که حتی یکی از این فعالیت‌ها توسط گروه انجام نگیرد، نمره آن تمرین را تمام اعضای آن گروه از دست خواهند داد. هر تمرین ۱ نمره خواهد داشت که با بررسی و تصحیح دستیاران آموزشی درس به تمام اعضای گروه اختصاص داده خواهد شد. در انتها ۶ نمره از مجموع ۷ نمره تمرین‌ها برای ارزشیابی نهایی در نظر گرفته خواهد شد.

مدت زمان آزمون‌ها بین ۳ تا ۴ ساعت خواهد بود. تلاش خواهیم کرد که سوالات آزمون‌ها به صورتی باشند که همراهی دانشجو در درس (فهم کامل مطالب ارائه شده و حل و بررسی تمرین‌ها) و توان‌مندی و استعداد دانشجو را بسنجند. آزمون‌ها در بستر CW برگزار خواهند شد.

…