فهرست مندرجات

{تحقیق در عملیات 1} - نیم‌سال {1} {1401}

مدرس ایمیل
{الهام منیفی} elham.monifi@sharif.edu

توضیحات درس

توصیف درس

درین درس با کلیات و مباحث پایه‌ای بهینه‌سازی خطی آشنا می‌شویم.

سرفصل‌های تقریبی

پیش‌نیازها

درس آشنایی با جبر خطی یا درس جبر خطی 1

منابع درس

1. Introduction to Linear Optimization, Dimitris Bertsimas and Tsitsiklis

2. Linear Programming and Network Flows, Bazaraa

نحوه ارزش‌یابی

جدول زمانی و توضیحات آزمون‌ها

آزمون تاریخ برگزاری مباحث مربوطه
میان‌ترم پنج شنبه ۳ آذر ساعت ۹:۰۰ مباحث میان‌ترم
پایان‌ترم یکشنبه ۲۵ دی ساعت ۹:۰۰ مباحث کل ترم

دستیاران آموزشی درس (به ترتیب الفبا)

نام دستیاران ایمیل
محمدجواد بهمنی mj.bahmani2000@gmail.com
محمدسعید حقی m.s.haghi2013@gmail.com
حسین رحمانی horatalonema79@yahoo.com
فرزاد رویین‌تن farzad.r.a.1380@gmail.com
مازیار شمسی‌پور maziar56bnd@gmail.com
غزل فراهانی farahaniqazal@gmail.com
هادی هادوی hadihadavi7@gmail.com

کلاس حل تمرین

برای تمرین و تسلط بیشتر بر مطالب درسی تمرینات کتاب Bertsimas را حل کنید. تمرین تحویلی نداریم ولی دو کلاس حل تمرین در هفته خواهیم داشت که دانشجویان عزیز میتوانند جهت رفع اشکال یا حل تمرینات کتاب درین کلاس‌ها شرکت کنند.

زمان کلاسهای حل تمرین : شنبه و سه شنبه ۱۲:۳۰ تا ۱۳:۳۰. مکان و سایر موارد بعدا اعلام خواهد شد.

سرفصلهای مطالب گفته شده در کلاس

جلسه 1 - مقدمه

مدلسازی مسایل مختلف نظیر مساله زنجیره تولید،‌رژیم غذایی،‌جریان شبکه،‌برازش داده ،‌کلاسیفایر خطی

جلسه 2 - فرم‌های مختلف نمایش مساله بهینه‌سازی خطی و انواع حالت‌ها

فرم کلی،‌ نمایش استاندارد،‌ نمایش کانونی،‌ بررسی انواع حالت‌های یک مساله بهینه‌سازی خطی (مساله شدنی،‌ مساله نشدنی، مساله بیکران)،‌ بررسی انواع حالت‌های مساله بهینه‌سازی خطی از نظر شکل ناحیه شدنی و تعداد جوابها( مساله با ناحیه شدنی کراندار و جواب منحصر بفرد،‌ مساله با ناحیه شدنی کراندار و بینهایت جواب،‌ مساله با ناحیه شدنی بیکران و جواب منحصر بفرد،‌ مساله با ناحیه شدنی بیکران و بدون جواب،‌ مساله با ناحیه شدنی بیکران و بینهایت جواب بهینه)

مطالب مربوط به جبر خطی که لازم است مرور شود در اینجا قرار گرفته است.

linear_algebra_review_1.pdf

جلسه 3 - بررسی چندوجهی‌ها از لحاظ هندسی

بخش‌های 2.1 و 2.2 از کتاب Bertsimas کامل شد: تعریف مجموعه محدب،‌ ترکیب محدب،‌ پوسته محدب،‌ چندوجهی،‌ نقطه گوشه‌ای،‌ گره،‌ قید اکتیو،‌ جواب پایه‌ای،‌ جواب پایه‌ای شدنی، … و قضایای مربوط به آنها.

جلسه 4 - بررسی چندوجهی‌ها از لحاظ هندسی

بخش‌های 2.3 و 2.4 و 2.5 از کتاب Bertsimas کامل شد: شرط لازم و کافی برای جوابهای پایه ای در نمایش استاندارد،‌الگوریتم پیدا کردن جوابهای پایه ای در فرم استاندارد،‌ تباهیدگی،‌ شرط لازم و کافی برای جواب پایه ای تباهیده، تعریف چند وجهی دربرگیرنده خط، شرط لازم و کافی برای وجود نقاط گوشه ای

جلسه 5 - بررسی چندوجهی‌ها از لحاظ هندسی

بخش‌ 2.6 از کتاب Bertsimas کامل شد: شرط لازم برای بهینگی وقتی که میدانیم جواب بهینه وجود دارد،‌ شرط لازم برای بهینگی وقتی که میدانیم تابع هدف همیشه کران پایین دارد.

جلسه 6 - بررسی چندوجهی‌ها از لحاظ هندسی

بخش‌‌های 2.7 و 2.8 از کتاب Bertsimas کامل شد: نمایش چند وجهی‌های کراندار بصورت پوسته محدب نقاط گوشه‌ای،‌ تصویرسازی چند وجهی‌ها

همچنین بخش 2.4 تا 2.7 از کتاب بازارا گفته شد: جهت‌های دورشونده،‌ جهت دورشونده گوشه‌ای، مخروط محدب،‌ ترکیب مخروطی،‌ قضیه نمایش چندوجهی‌های بیکران بصورت پوسته محدب نقاط گوشه‌ای باضافه ترکیب مخروطی جهت‌های گوشه‌ای.

جلسه 7 - روش سیمپلکس

بخش 3.1 و نیمی از بخش 3.2 تدریس شد.

جلسه 8 - روش سیمپلکس

بخش 3.2 کامل و نیمی از بخش 3.3 تدریس شد.

جلسات ۹ و ۱۰ - روش سیمپلکس

فصل سوم کتاب تمام شد.

جزوه مربوط به فصل دوم و سوم کتاب را اینجا ببینید:

chapters_2_and_3.pdf

جلسه 11 - فصل چهارم دوگانی

بخشهای 4.1 و 4.2 و 4.3 تدریس شد. جزوه کلاس را در اینجا ببینید:

4_1_and_4_2_and_4_3.pdf

جلسه 12 - فصل چهارم دوگانی

بخشهای 4.4 و 4.5 و 4.6 تدریس شد. جزوه کلاس را در اینجا ببینید:

4_4_and_4_5_and_4_6.pdf

همچنین بحث جهت‌های دورشونده و چند وجهی‌های بیکران قبلا در انتهای فصل دوم گفته شد که در بخشهای 4.8 و 4.9 کتاب Bertsimas به آنها پرداخته شده است. جزوه مربوط به این مباحث هم اینجاست:

recession_direction.pdf

به این ترتیب فصل دوگانی تمام است. یکشنبه 27 آذر کوییز کلاسی از مباحث فصل 4 خواهیم داشت. تمرین تحویلی هم داریم که شماره هایش را از cw ببینید.

جلسه 13 - فصل پنجم آنالیز حساسیت

بخش 5.1 و 5.2 گفته شد.

جلسه 14 و 15 و 16 - فصل پنجم و ششم

فصل پنجم و ششم تمام شده است. جزوه را اینجا ببینید:

chapter_5_and_6.pdf

کوییزها

تمرین‌ها

میان‌ترم

پایان‌ترم