Advanced linear programming 1

 

Syllabus

 

Chapter 1

 

*************************************   Ref: Bertsimas  *********************

Exercises 

Chapter 1

 

 

 

1, 2, 3, 4, 5, 7, 8, 9, 10, 12, 18, 19, 20

 

 

 

Chapter 2:

 

3, 5, 6, 8, 9, 10, 11, 12, 13, 14, 15, 17, 18, 19.

 

 

Chapter 3:

 

1, 2, 3, 4, 5, 6, 7, 9, 10, 12, 15, 18, 19, 20, 22, 23, 24, 25, 28, 33.

 

Chapter 4:

2, 4, 6, 8, 10, 13, 19, 20 a, 21, 26, 27, 34, 35, 40, 43, 50. 

 

Chapter 5:

3, 9, 12, 14, 13.

 

*************************** Ref:  Bazaraa  *********************************

 

 

شماره تمرینات فصل دوم کتاب بازارا 

تمرینات فصل دوم:

،48 ،47 ،46 ،45 ،44 ،42 ،40 ،39 ،38 ،34 ،32 ،29 ،25 24 ،23 ،19 ،13 ،7 ،5 ،3 ،2

.54 ،52 

 

صورت تمرینات فصل دوم کتاب بازارا

 

 

************************************  دکتر جهانشاهلوRef:****************************

 

تذکر: شماره تمرینات فقط مربوط به انتهای فصل می باشد پس تمام تمرینات داخل فصل در امتحان مشخص شده هستند.

 

فصل دوم:

54, 56, 68, 70, 72, 73, 79, 82, 86, 93, 94

 

 

فصل سوم:

 

11, 12, 14, 15, 19, 22, 25, 33.

 

 

********************************************************************************************************

 

 

Book

 

Introduction to Linear Optimization_Dimitris Bertsimas, John N. Tsitsiklis -Chapter 1-5

 

Rao-Book-ENGINEERING-OPTIMIZATION

 

Integer Programming 

 

 LOGICAL_CONSTRAINTS

 

Game Theory

 

Network Flow_Book_AMO

 

·     فایل GAMS  مثال جزوه1

 

 

نرم افزار بهینه سازی Tora

 

 

اسامى دانشجویانى که علاقه مند به گرفتن پروژه تحقیق در عملیات پیشرفته می باشند:

 

 

پروژه Robust optimization

 

 

 

 

 

درس بهینه سازی خطی 1

بسمه تعالی

 

 

 

 

نام درس: بهینه سازی خطی 1

 

 

مدرس: دکتر رعایت‌پناه

 

 

دفتر: دانشکده  ریاضی، آمار وعلوم کامپیوتر، طبقه 3، اتاق 40

 

 

ایمیل:[e-mail]

 

 

تلفن: [phone]

 

 

  پیشنیاز درس: مبانی ماتریس ها و جبر خطی، مبانی آنالیز

 

 

نوع درس: اختیاری  □            الزامی ■            مقطع:         کارشناسی ■              تعداد واحد: 3

 

 

نام انگلیسی درس:    Linear Optimization 1

 

 

توضیحات اولیه:

 

 

بهینه سازی یکی از شاخه های مهم ریاضیات کاربردی است که به ارتباط هایی بین ریاضیات، اقتصاد و صنعت منجر می شود. در این شاخه از ریاضیات، مساله اصلی ماکزیمم (مینیمم) کردن سود (هزینه) می باشد. البته می تواند هدف مینیمم کردن شاخص هایی دیگر نظیر آلودگی هوا، ترافیک و ... نیز باشد. یکی از مسایل اولیه در این شاخه از ریاضیات، بهینه سازی خطی در فضاهای متناهی البعد است که در این درس بدان پرداخته می شود.

 

 

اهداف:

 

 

-        آشنایی دانشجویان با بهینه سازی خطی در فضاهای متناهی البعد، شامل: مدل سازی و کاربردهای آن، حل مدل ها، دوگان، تفسیر های هندسی، جبری و اقتصادی.

 

 

-        درک برخی کاربردهای ابزارهای آنالیزی و جبر خطی در دیگر شاخه ها ی ریاضیات

 

 

-        درک برخی ارتباط ها بین ریاضیات، اقتصاد و صنعت

 

 

 

 

 

منابع درس:

 

 

n M. S. Bazaraa,  J.J. Jarvis, H.D. Sherali,  Linear Programming and Network Flows, Wiley; 4 edition 2009.

دانلود کتاب 

 

 

n  K. G. Murty, Linear Programming, Wiley, 1983.

 

 

n D. Bertsimas, J.N. Tsitsiklis, Introduction to Linear Optimization, Athena Scientific 1997.

 

 

 

 

 

نمرات:

 

 

·        میانترم اول   ( هفته اخر اسفند -- فصل یک و دو)

·        میانترم دوم   ( هفته اخر اردیبهشت --فصل سه و چهار)

 

 

 

·        پایان ترم( تاریخ مشخص شده توسط گروه-- فصل 5 و 6)

 

 

·        ارایه تمرینات مشخص شده( تحویل تمرینات  در انتهای هر فصل )

 

 

·        پروژه کامپیوتری

 

 

o       جزییات نمرات به صورت تقریبی:

 

 

·        میانترم (40%)، پایانترم(40%)، تمرینات و پروژه کامپیوتری(10%)

 

 

_______________________________________________________________________

·                                                        نرم افزارهای تخصصی

 

 

 

GAMS: Lingo; Lindo; AMPL

 

دانلود نرم افزار TORA

 

 

 

 

 

  ----------------------------------------------------------- 

سر فصل مطالب:

 

 

فصل اول:

 

 

مقدمه ای بر بهینه سازی

 

 

·        مقدمه ای بر بهینه سازی،   مدل سازی، اهمیت و کاربرد آنها

 

 

·   تبدیلات برنامه‌ریزی خطی،  حل هندسی مسایل بهینه سازی خطی (LP)

·     فایل GAMS  مثال جزوه

· تمرینات فصل اول کتاب بازارا

 

·چند فایل آموزشی برای نرم افزار GAMS

 

 

 

 

• نمونه تستهای کارشناسی ارشد تحقیق در عملیات
• تمرینات فصل های 2، 3 و 4، کتاب برنامه ریزی خطی بازارا
• تمرینات فصل های 5 و 6، کتاب برنامه ریزی خطی بازارا

 

 

 

 

 

فصل دوم

 

 

مروری بر جبرخطی

 

 

·        مفهوم POS (requirements space)، پوسته خطی، پوسته محدب و پوسته آفین و ارتباط آنها با LP ها

 

 

·        استقلال و وابستگی خطی و رتبه ماتریس

 

 

·        مولد و پایه

 

 

·        معادلات خطی هم‌زمان

 

 

·        مقدمه ای بر خواص مجموعه های محدب، چند وجهی ها، ابر صفحه ها، نیم فضا، اشعه (شعاع)

آنالیز محدب

 

 

·        تعریف تابع محدب و برخی خواص مقدماتی آن

 

 

·        مفهوم و خواص نقاط راسی، جواب‌های پایه‌ شدنی، قضیه هل دادن

 

 

·        تباهیدگی، زاید بودن، مجاورتی،

 

 

·        جهت های دورشونده (راسی) چند وجهی ها و نحوه بدست آوردن آنها

 

 

·        توابع محدب و مقعر

 

 

·        قضیه نمایش و کاربردهای آن

 

 

فصل سوم

 

 

الگوریتم سیمپلکس(قسمت اول)

فصل سوم قسمت دوم

فصل سوم قسمت سوم

 

 

·        شرایط لازم و کافی وجود جواب بهینه (نتایج قضیه نمایش)

 

 

·        الگوریتم سیمپلکس: معیارهای بهینگی، بیکرانگی، واردشوندگی و خارج شوندگی متغیرها

 

 

·        حل مثالهای عددی با الگوریتم سیمپلکس (به صورت دستی و برنامه نویسی)

 

 

·        وجود جواب های بهینه دگرین و نحوه بدست اوردن انها

 

 

·        همگرایی الگوریتم سیمپلکس در غیاب تباهیدگی

 

 

·        قضیه نمایش برای مجموعه جواب های بهینه دگرین

 

 

·        متغیرهای مصنوعی و استفاده از روش M-بزرگ  (روش دوفازی، در صورت وجود زمان کافی)

 

 

فصل چهارم

 

 

چند قضیه مهم

 

 

·        قضایای دگرین:  لم فارکاس و قضیه گردن

 

 

·        شرایط بهینگی KKT ( اثبات قضیه KKT و تعبیر هندسی آن)

 

 

فصل پنجم

 

 

نظریه دوگان

قسمت اول

قسمت دوم

 

 

·        مفهوم دوگان، طریقه نوشتن دوگان یک LP

 

 

·        قضایای دوگان: ضعیف، قوی، قضیه مکمل زائد ضعیف، قضیه اساسی دو آلیتی، قضیه مکمل زائد قوی

 

 

·        کاربردهای دوگان و شرایط مکمل زائد ضعیف

 

 

·        تعبیر اقتصادی دوگان و جواب های بهینه دوگان

 

 

·        روش سیمپلکس دوگان

 

 

·        محاسبه جواب های بهینه دوگان از روی جواب بهینه اولیه

 

 

·        تحلیل حساسیت

 

 

 شماره تمرینات فصل 3و 4 و 5 و 6 :

 

تمرینات فصل سوم کتاب بازارا ویرایش 2:

2 (الف و ب)،

 

‎3, 4, 8, 13, 16, 17, 18, 20, 23, 30, 32, 34, 37, 38, 46, 47, 48, 51, 

تمرینات فصل چهار کتاب بازارا ویرایش 2:

 

1, 2, 9 ,11, 17

‎

تمرینات فصل پنجم کتاب بازارا ویرایش 2:

 

 

 37, 38, 42, 44, 46, 49

 

 

 

تمرینات فصل ششم کتاب بازارا ویرایش 2:

 

 

 

 

 

1, 3, 6, 7, 8, 9, 11, 13, 14, 16, 26, 28, 30