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

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

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

1. Introduction to Linear Optimization, Dimitris Bertsimas and Tsitsiklis

2. Linear Programming and Network Flows, Bazaraa

• آزمونک: 10 نمره (حداکثر دو کوییز)
• میان‌ترم: 40 نمره
• پایان‌ترم: 50 نمره

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

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

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

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

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

linear_algebra_review_1.pdf

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

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

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

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

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

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

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

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

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

chapters_2_and_3.pdf

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

4_1_and_4_2_and_4_3.pdf

بخشهای 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 ببینید.

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

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

chapter_5_and_6.pdf