آموزش متلب

بهینه سازی با متلب

بهینه سازی چیست ؟

بهینه سازی یا ) optimization ( شاخه ایی از ریاضیات است که هدف آن موثر کردن هر چه بیشتر و بهتر یک سیستم میباشد این سیستم بر اساس مدل سازی از یک پدیده که ما با آن سر و کار داریم ایجاد میشود به زبانی ساده تر ما با یک سوال یا در حالت کلی تر تعداد بیشتری سوال روبه رو میشویم که میخواهیم ازیک حالت ابتدایی که در آن قرار دارد به حالت مطلوبمان برسد ، که این حالت مطلوب  میتواند ماکسیمم کردن سود یا استفاده ی کامل و درست از تمامی فرصت ها یا مینیمم کردن هزینه ها باشد . برای این امرما از مدل سازی استفاده کرده و تمامی خواسته ها و داشته های خود را به صورت یک سیستم ریاضیاتی در می آوریم. بعد یک معادله  نهایی از آن تولید میکنیم که در علم بهینه سازی به این معادله ، تابع هدف یاobjective function )   (میگوییم این تابع هدف در واقع همان پایه ی اصلی سیستم ماست که قرار است بیشینه یا کمینه شود ، سپس ما داشته ها و خواسته های مساله را نیز به صورت یک سری معادلات یا نامعادلات  (constraints)در می آوریم این داشته ها و خواسته ها در اصل منابع ، هزینه ها و… هستند در واقع مشخصص کننده ی دامنه ی اختیارات ما و بهره وریی که بر اساس آن ها میتوانیم داشته باشیم ، است . و خواسته ی اصلی ما این است که بر اساس آنها در سیستم مورد بحث مان تغیری بدهیم .

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

 

C1X1 + C2X2 + …. + CnXn                                                              

 

در این معادله ی هدف Ci   ها ضریب تغیرات  Xi  هستند یعنی نشان دهنده ی تاثیر گذاری Xi  میباشند . خود Xi   ها که متغیرات تصمیم نامیده میشوند همان متغیرات مساله ی ما هستند مثل تعداد کارگرهایمان یا هزینه ی هرواحد ازمواد اولیه یا …

گام بعدی نوشتن قسمت محدودیت ها ( constraints ) یا همان دامنه ی فعالیت مان است . مثلا ما بیشتر از w کارگر نمیتوانیم داشته باشیم یا در طول روز بیشتر از h ساعت نمیتوانیم از منابع مان استفاده کنیم یا نهایت هزینه ای که میتوانیم داشته باشیم برای مثال y تومان است. این ها تشکیل یک سری معادلات و نامعادلات را میدهد که برای مساله ی فرضی ما به شکل زیر است :

 

a11X1 + a12X2 + … + a1nXn    ≥  b1

a21X1 + a22X2 + … + a2nXn    ≥  b2

am1X1 + am2X2 + … + amnXn    ≥  bm

    

هدف ما ماکسیمم یا مینیمم کردن تابع هدف با دانستن شرایط محدودیتمان یعنی همین constraint ها است . برای این کار با استفاده از محدودیت ها و اشتراک آنها با هم یک محدوده ی جواب های شدنی به دست می آوریم و از بین آنها بهترین را که میتواند مینیمم یا ماکسیمم باشد انتخاب میکنیم ومساله ی خود را حل میکنیم . در حل این مسائل اگر استفاده از نرم افزارها را در نظر نگیریم باید با استفاده از جبر خطی یا کمک از تکنیک های خاص بهینه سازی یک سری عملیات ریاضی انجام دهیم و در نهایت به جواب خود برسیم اما نرم افزار ها کار را برای ما ساده کرده اند به گونه ایی که با گرفتن ضرایب متغیرهای تصمیم ( Xi ) و دریافت constraint ها جواب مساله را به ما میدهند .این بیان ، یکی از ساده ترین و در عین حال کاربردی ترین مسائل موجود در بهینه سازی بود یک تیپ کلی . اما همان طور که بیان شد یکی از تیپ های کلی میباشد ودرکنار این تیپ و نوع ما انواع گوناگون دیگری از مسائل بهینه سازی داریم مثلا در این صورت کلی همه ی متغییرها ازدرجه ی واحد بودند یعنی ما با یک سوال خطی رو به رو بودیم اما مسائل دنیای اطراف ما فقط در مسائل خطی خلاصه نمیشوند و بیشتر آنها مسائل غیر خطی هستند یعنی ما در تابع هدفمان که همان  CiXi∑ ( با محدوده ی قابل تعریف و مشخصi ) خیلی اوقات ضرایب درجه دو یا بالاتر هم داریم یا دربه همین منوال در قید هایمان . این گوناگونی ها به مسائل بهینه سازی تایپ های مشخصی میدهد که هر کدام داری یک فرم کلی میباشند و همین طور یک روش حل مخصوص به خود وقطعا یک شکل مشخص در نرم افزارها که در این گزارش به اختصار به چندی از آنها خواهیم پرداخت .

 

متلب (MATLAB   (به صورت اجمالی  :

 

متلب یک زبان سطح بالا  با UI جذاب میباشد که در ابتدا بر اساس زبان برنامه نویسی C توسعه داده شد. MATLAB  از ترکیب دو واژه ی MATrix  و LABoratory  گرفته شده است حضور نام ماتریس در متلب به دلیل رویکرد ماتریس محور این زبان برنامه نویسی میباشد ، به گونه ایی که تقریبا همه ی داده ها در متلب به صورت ماتریس در نظر گرفته میشوند و کار کردن با آنها هم در متلب بسیار ساده است. حتی اعداد اسکالر هم به صورت ماتریس های ۱*۱  درنظر گرفته میشوند ، رشته ها هم به صورت یک ماتریس سطری با ستون هایی به تعداد کاراکترهای رشته  ذخیره میشوند حتی فایل های صوتی به صورت بردارهای ستونی و تصویرها به صورت یک ماتریس ۳*۳ که بعد اول و دوم برای تعیین مختصات و بعد سوم برای تعیین رنگ نقاط استفاده میشوند. کاربردهای زبان برنامه نویسی مطلب بسیار وسیع است در زمینه های تجزیه تحلیل مالی و اقتصادی ، طراحی کنترلرها ، پردازش تصویری و… علاوه بر این کاربردهای کلی ، قابلیت اضافه کردن Toolbox  های خاص و استفاده های جزیی تر و تخصصی تر را نیز دارد. همان طور که در قسمت های بالاتر گفتیم هسته ی متلب بر اساس زبان برنامه نویسی C نوشته شده است اما رابط گرافیکی آن به زبان java پیاده سازی شده است . جز مهم ترین ویژگی های متلب میتوانیم به منعطف بودن آن و راحتی کار با آن اشاره کنیم علاوه بر این این قابلیت در آن وجود دارد که هر ساله شرکت سازنده ی آن و یا گاها دانشگاه ها و لابراتورهای برتر Toolbox های خاص و کاربردی را به آن اضافه میکنند که باعث افزایش کارایی و محبوبیت آن میشود.

 

تولباکس بهینه سازی متلب :

 

همین طور که از نام این تولباکس مشخص است به ما کمک میکند که به حل مسائل بهینه سازی بپردازیم و محاسبات لازم را برای ما انجام میدهد.

(ورژنی از متلب که این گزارش براساس آن انجام شده است R2012a میباشد. تغییرات جزیی بر اساس تغیِر ورژن وجود دارد اما خیلی جزیی هستند ، مثل جابه جایی تولباکس ها از قسمت start  به قسمت apps  اما این تغییرات شامل هیچ گونه مسائل کلی نمیباشند )

در ابتدا ما با یک سوال بهینه سازی ( خطی یا غیر خطی و انواع مشخص آن ) رو به رو میشویم .

 

دسته بندی مسائل بهینه سازی :

 

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

 

 

دسته بندي برحسب خطي، درجه دوم و يا غيرخطي بودن توابع هدف و قيود :

 

تابع f   یا همان تابع هدف را ، f : Rn →R  را یک تابع خطی  گوییم، هرگاه به فرم زیر باشد :

mat1

 

اﮔﺮ در ﯾﮏ ﻣﺴﺎﻟﻪ ﺑﻬﯿﻨﻪ ﺳﺎزی ﺗﺎﺑﻊ ﻫﺪف و ﺗﺎﺑﻊ ﻣﺘﻨﺎﻇﺮ ﺑﺎ ﻗﯿﻮد ﺗﺴﺎوی و  ﻣﺴﺎوی ﺟﻤﻠﮕﯽ ﺧﻄﯽ ﺑﺎﺷﻨﺪ، آن ﮔﺎه ﻣﺴﺎﻟﻪ ﺑﻪ ﯾﮏ ﻣﺴﺎﻟﻪ  ﺑﺮﻧﺎﻣﻪ ﺳﺎزی ﺧﻄﯽ ﯾﺎ ﻣﺴﺎﻟﻪ  بهینه سازی ﺧﻄﯽ ﻣﻮﺳﻮم ﺑﺎﺷﺪ  وﻟﯽ اﮔﺮ ﺣﺪاﻗﻞ ﯾﮏ ﻗﯿﺪ ﯾﺎ ﺗﺎﺑﻊ ﻫﺪف ﺧﻄﯽ ﻧﺒﺎﺷﺪ، آن ﮔﺎه ﻣﺴﺎﻟﻪ را ﯾﮏ ﻣﺴﺎﻟﻪ برنامه  رﯾﺰی ﻏﯿﺮﺧﻄﯽ می ﻧﺎﻣﻨﺪ.

فرم کلی یک مساله خطی به شکل زیر است :

mat2

 

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

تابع q  را یک تابع درجه دو مینامند هرگاه به فرم زیر باشد :

mat3

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

mat4.jpg

 

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

  • مسایل برنامه ریزی خطی (LP)
  • مسایل درجه دوم (QP)
  • مسایل درجه دوم با قیود درجه دوم(QPQC)
  • مسایل برنامه ریزی غیرخطی (NLP)

دسته  بندي بر مبناي پيوسته يا گسسته بودن متغيرهاي تصميم  (Xi ها ) :

در مسائل بهینه سازی اگر دامنه ی همه ی متغیر های تصمیم مجموعه هایی پیوسته باشند ؛ انگاه مساله را یک مساله ی بهینه سازی پیوسته میگوییم منظور از پیوسته بودن دامنه این است که متغییر مربوطه میتواند هر مقداری را در یک بازه ی مشخص  برای مثال (a,b) اخذ کند. اما اگر دامنه ی متغییر ها برابر با مجموعه اعداد صحیح یا مجموعه ی دو دویی {۰,۱}  یا هر مجموعه با تعداد متناهی عضو باشد آنگاه مساله رو یک مساله ی گسسته میگوییم . در حالتی که دامنه برابر با Z (مجموعه اعداد صحیح ) باشد آنگاه مساله را یک مساله ی برنامه ریزی دودویی یا به اختصار IP مینامند و در حالتی که متغیرها ۰ یا ۱ باشند آنگاه مساله ی برنامه ریزی دودویی یا به اختصار BP میباشد .

همچنین ممکن است ناحیه شدنی بهصورت ترکیبی باشد. یعنی برخی از متغیرهای تصمیم  پیوسته و برخی دیگر گسسته باشند. در این حالت مساله را یک مساله بهینه سازی مخلوط مینامیم.

دسته بندي برمبناي وجود يا عدم وجود قيود :

در یک مساله بهینه سازی پیوسته اگر قیود تساوی و نامساوی موجود نباشند و همچنین دامنه ی متغیر های تصمیم برابر با Rn باشد آنگاه مساله به مساله ی بهینه سازی نامقید موسوم میباشد .

در صورتی که حداقل یک قید تساوی یا نامساوی وجود داشته باشد آنگاه مساله را یک مساله بهینه سازی مقید مینامیم. لذا در مسایل بهینه سازی مقید سه نوع قید تساوی، نامساوی وکرانهای میتواند موجود باشد.

 

دسته بندي بر مبناي محدب بودن توابع هدف و قيود مساله :

مجموعه S را یک مجموعه محدب گوییم هرگاه به ازای هر x و y در S داشته باشیم که λ x  + (۱-λ) y ∈ S

تابع f  را یک تابع محدب مینامیم هرگاه به ازای هر λ ∈ [۰,۱]   داشته باشیم :

(f (λ x  + (۱-λ)y) ≤ λf(x) +(1-λ) f(y)

یک مساله برنامه ریزی را یک مساله محدب مینامیم، هرگاه :

  • تابع هدف یک تابع محدب باشد.
  • مجموعه دامنه متغیرها یک مجموعه محدب باشد.
  • توابع متناظر با قیود نامساوی، جملگی محدب باشند.
  • توابع متناظر با قیود تساوی، جملگی خطی یا آفینی باشند.

بنابراین، مسایل بهینه سازی به دو دسته محدب و غیرمحدب دسته بندی میشوند. دسته بندی محدب و غیرمحدب به نظر بی مسمی به نظر میرسد. اما این دسته بندی یکی از مهمترین دسته بندیها میباشد. چرا که مسایل محدب دارای خواص بسیار مناسبی میباشند که آنها را در میان مسایل بهینه سازی بسیار جذاب کرده است. به عنوان یک خاصیت نمونه در مسایل محدب، مینیمم موضعی یک مینیمم سراسری میباشد.

 

دسته بندي برمبناي طبيعت متغيرهاي تصميم :

بسته به طبیعت متغیرهای تصمیم، مسایل بهینه سازی به دو دسته

  • مسایل بهینه سازی پارامتری یا مسایل بهینه سازی ایستا
  • مسایل بهینه سازی تراجکتوری و یا مسایل بهینه سازی پویا

تقسیم میشوند. در دسته اول متغیرهای تصمیم پارامترهای ثابت میباشند. اما در دسته دوم متغیرهای تصمیم توابعی پیوسته یا گسسته از یک یا چند پارامتر میباشند. به عبارت دیگر در مسایل پویا، مجهولات تابع میباشند.

 

 

دسته بندي برمبناي تصادفي يا قطعي بودن متغيرهاي تصادفي :

مسایل بهینه سازی به دو دسته  :

  • مسایل بهینه سازی قطعی
  • مسایل بهینه سازی تصادفی

در مسایل بهینه سازی تصادفی برخی از متغیرهای تصمیم و یا برخی پارامترهای ظاهر شده در مساله تصادفی میباشند.

 

دسته بندي براساس تعداد توابع هدف :

بسته به تعداد توابع هدف موجود، یک مساله بهینه سازی به دو دسته زیر تقسیم میشوند :

  • مسایل بهینه سازی تک هدفه
  • مسایل بهینه سازی چند هدفه

دسته بندي بر مبناي جدايي پذير بودن توابع هدف و قيود :

تابع f  را یک تابع جدایی پذیر میگوییم اگر بتوان f را به صورت مجموع n  تابع یک متغییره نوشت به عبارت دیگر ، f1,f2,…fn موجود باشند که  : f(x) = ∑ fi(Xi)

حال اگر تابع هدف و قیود یک مساله بهینه سازی توابعی جدایی پذیر باشند، آنگاه مساله بهینه سازی را جدایی پذیر مینامیم.

 

دسته بندي بر مبناي به فرم بسته بودن تابع هدف و توابع قيود مساله :

مسایل بهینه سازی را بر مبنای به فرم بسته بودن داده های مساله به دو دسته زیر تقسیم میشوند :

  • مسایل به فرم بسته یا تحلیلی
  • مسایل دارای داده های جعبه سیاه یا اوراکل

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

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

مسايل بهينه سازي هموار و ناهموار :

اگر تابع هدف یا حداقل تابع منتاظر با یک قید مشتق پذیر نباشد، آنگاه مساله بهینه سازی را یک مساله ی بهینه سازی ناهموار  مینامند. اما اگر کلیه توابع هدف و قیود مشتق پذیر باشند، آنگاه  مساله را هموار مینامند. به عنوان مثال میدانیم که تابع قدرمطلق یک تابع ناهموار است، لذا وجود تابع قدرمطلق در تابع هدف و یا قیود یک مساله، نشانه ناهموار بودن مساله است.

 

مسايل كمترين مربعات :

در مسایل برنامه ریزیکمترین مربعات تابع هدف به شکل زیر است :

mat5

از مشخصه های این نوع توابع هدف این استکه میتوان آنها را با نرم دو نیز توصیف کرد . مسایل کمترین مربعات در مدل کردن بسیاری از مسایل اقتصادی و مهندسی ظاهر میگردند. در بین مسایل غیرخطی ظاهر شده در کاربردها بیشترین آنها از نوع مسایل بهینه سازی کمترین مربعات میباشد. بهعنوان نمونه برازش منحنی که ابزاری پر استفاده در علوم مهندسی است در نهایت به یک مساله بهینه سازی کمترین مربعات تبدیل میشود. مسایل کمترین مربعات در حالت کلی یک مساله غیرخطی است که تابع هدف آن دارای ساختار خاصی میباشد.

نامگذاري مسايل بهينه سازي برمبناي نوع آنها :

دیدیم که هر مساله بهینه  سازی از دیدگاههای متفاوتی دسته بندی میشوند. به عنوان مثال یک مساله از یک دیدگاه ممکن است خطی باشد و از دیدگاه دیگر یک مساله گسسته اعداد صحیح باشد. در این راستا این مساله را مساله اعداد صحیح خطی نامگذاری میکنیم. در جدول زیر برخی از این نامگذاریها به همراه واژه خلاصه آنها ارایه شده است :

mat6

 

mat7

روش های حل مسائل بهینه سازی :

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

–  روشهای تصویری

– روشهای تحلیلی یا روشهای کلاسیک

– روشهای خاص

– روشهای عددی

– روشهای برنامه ریزی دینامیکی

 

روشهاي تصويري :

روشهای تصویری با کمک رسم ناحیه شدنی و تابع هدف، جوابهای مساله بهینه سازی را می یابند. این روشها برای مسایل با دو تصمیم کاربرد دارد. چرا که تابع هدف و ناحیه شدنی مسایل با بیشتر از دو متغیر تصمیم قابل رسم و تجسم نمیباشد. روشهای تصویری به ندرت در عمل استفاده میشوند و معمولا از این روشها برای آموزش مباحث و مفاهیم بهینه سازی استفاده میشود.

 

روشهاي تحليلي يا كلاسيك :

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

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

روشهاي خاص :

روشهای خاص روشهایی هستند که برای حل یک مساله بهینه سازی خاص طراحی شده اند. به عنوان نمونه میتوان به روش سیمپلکس اشاره کرد که یک الگوریتم برای حل مسایل برنامه ریزی خطی میباشد.

 

روشهاي عددي :

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

 

حال که به اختصارفرم کلی مسائل بهینه سازی را بیان کردیم به سراغ پیاده سازی این ها در نرم افزار متلب و حل آنها میرویم .

تولباکس بهینه سازی در متلب از دو طریق زیر قابل درسترسی میباشد :

  • از منوی start در قسمت پایین سمت چپ برنامه و بعد toolboxes ، optimization  وبعد

Optimization tool

  • در پنجره ی command با تایپ عبارت :  optimtool

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

mat8

این پنجره از سه قسمت اصلی تشکیل شده است :

  • problem setup and results
  • options
  • quick references

دو قسمت اول نقش کلیدی داشته و قسمت سوم در نقش help  نزدیک و خلاصه ایی برای این تولباکس است . بر اساس نوع مساله ی بهینه سازی از قسمت solver  ، تابع مربوط را انتخاب میکنیم ، برای مثال اگر مساله ی ما بهینه سازی خطی باشد ما linprog-Linear programming را انتخاب میکنیم . بنا بر solver  مربوطه قسمت algorithm  برای ما ممکن است فعال شود در این قسمت هم الگوریتمی که مد نظرمان هست را انتخاب میکنیم که در این مثال ما سه گزینه ی medium scale-simplex ,

Large scale, medium scale-active set  را داریم ، سیمپلکس را انتخاب میکنیم .  در قسمت problem  ، تابع هدفمان را وارد میکنیم .  در قسمت constraints ، قیدهایمان را وارد میکنیم در

همین نقطه ما میتوانیم start  را زده وحل سوال را ببنیم اما ممکن است ما بخواهیم مساله ی مان را در حالت خاص تری نیز حل کنیم در این جا وارد قسمت  options  میشویم :

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

مثالی از چندsolver  و سینتکس های آنها :

Bintprog : Solve a binary integer programming problem.

x = bintprog(f)

x = bintprog(f,A,b)

x = bintprog(f,A,b,Aeq,beq)

x = bintprog(f,A,b,Aeq,beq,x0)

x = bintprog(f,A,b,Aeq,Beq,x0,options)

x = bintprog(problem)

[x,fval] = bintprog(…)

[x,fval,exitflag] = bintprog(…)

[x,fval,exitflag,output] = bintprog(…)

Linprog : Solve linear programming problems .

x = linprog(f,A,b)

x = linprog(f,A,b,Aeq,beq)

x = linprog(f,A,b,Aeq,beq,lb,ub)

x = linprog(f,A,b,Aeq,beq,lb,ub,x0)

x = linprog(f,A,b,Aeq,beq,lb,ub,x0,options)

x = linprog(problem)

[x,fval] = linprog(…)

[x,fval,exitflag] = linprog(…)

[x,fval,exitflag,output] = linprog(…)

[x,fval,exitflag,output,lambda] = linprog(…)

Fminimax : Solve minimax constraint problem

x = fminimax(fun,x0)

x = fminimax(fun,x0,A,b)

x = fminimax(fun,x,A,b,Aeq,beq)

x = fminimax(fun,x,A,b,Aeq,beq,lb,ub)

x = fminimax(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon)

x = fminimax(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon,options)

x = fminimax(problem)

[x,fval] = fminimax(…)

[x,fval,maxfval] = fminimax(…)

[x,fval,maxfval,exitflag] = fminimax(…)

[x,fval,maxfval,exitflag,output] = fminimax(…)

[x,fval,maxfval,exitflag,output,lambda] = fminimax(…)

لیست توابع :

برای دسترسی به توابع موجود در این تولباکس در قسمت help  وارد تولباکس بهینه سازی میشویم گزینه ی functions  را انتخاب میکنیم  توابع در این قسمت به چهار دسته ی کلی تقسیم شده اند :

  • Minimization 13 تابع
  • Equation Solving 2 تابع
  • Least Squares 4 تابع
  • GUI 1 تابع
  • Utilities 5 تابع

توابع موجود در سه قسمت اول که با توضیحات کامل موجود در help  از قبیل مثال ، سینتکس کلی تابع توضیح برای قسمت های اضافه موجود در options  وغیره میباشد تنها تابع موجود در قسمت GUI  ، همان دسترسی از طریق cmd  به پنجره ی تولباکس است ؛ یعنی optimtool  است دسترسی دیگری که میتوانیم به توابع داشته باشیم از طریق پنجره ی تولباکس در قسمت solvers  بر اساس انتخاب هر یک از solvers  درقسمت references توضیح مختصری راجب تابع ، تیپ کلی آن سینتکس اش ، مثال از فرم کلی ، گزینه های مربوط به قسمت options و موارد دیگری آورده شده است و همین طور اگر این اطلاعات کافی نباشد از قسمت more info  وارد help  کلی متلب میشویم و به صورت کامل مسائل مربوط به تابع کاملا اورده شده است .

بررسی یک سوال بهینه سازی خطی و کد آن :

F(x) = –۵×۱ – ۴×۲ –۶×۳   تابع هدف

s.t  :  قید ها

      x1 – x2 + x3  ≤ ۲۰

      ۳×۱ +۲×۲ + ۴×۳ ≤  ۴۲

      ۳×۱ +۲×۲ ≤  ۳۰

     ۰ ≤ x1,x2,x3

نوشتن ماتریس های مربوطه در محیط ادیتور :

f = [-5; -4; -6];

A =  [ ۱ -۱  ۱

         ۳  ۲  ۴

         ۳  ۲  ۰];

b = [20; 42; 30];

lb = zeros(3,1)

فراخوانی تابع :

[x,fval,exitflag,output,lambda] = linprog(f,A,b,[],[],lb);

ران کردن برنامه و گرفتن خروجی ها

x =

     ۰٫۰۰۰۰

    ۱۵٫۰۰۰۰

     ۳٫۰۰۰۰

ans =

     ۰٫۰۰۰۰

     ۱٫۵۰۰۰

     ۰٫۵۰۰۰

ans =

     ۱٫۰۰۰۰

     ۰٫۰۰۰۰

     ۰٫۰۰۰۰

 

توضیحات سینتکس :

Problem f :   Linear objective function vector f

Aineq:   Matrix for linear inequality constraints

bineq :  Vector for linear inequality constraints

Aeq:   Matrix for linear equality constraints

beq :   Vector for linear equality constraintslbVector of lower boundsubVector of upper bounds

x0 : Initial point for x, active set algorithm only

solver:  ‘linprog’

توضیحات کلی برای استفاده از تولباکس بهینه سازی :

 

معرفی solver های تولباکس بهینه سازی :

ما چهار نوع کلی solver های بهینه سازی را داریم :

Minimizers :

این گروه از solver ها به دنبال پیدا کردن یک local مینیمم از تابع هدفند در نزدیکی نقطه ی x0  (نقطه ی ابتدایی که در صورت سوال به ما داده میشود ) وشامل مسائل زیر میشوند :

unconstrained optimization, linear programming, quadratic programming, general nonlinear programming

Multiobjective minimizers :

این گروه از solver ها به دنبال ۱) مینیمم کردن ، ماکسیمم مقدار یک مجموعه از توابعند (fminimax)

۲) یا به دنبال محلی که یک مجموعه از توابع زیر یک مقدار مشخص از پیش تعیین شده هستند یعنی مقدارشان کمتر از یک مقدار مشخص و فیکس است .( fgoalattain)

 

Equation solvers:

این گروه از solver ها به دنبال پیدا کردن راه حل برای یک معادله ی غیر خطی با مقادیر اسکالر یا برداری f(x) = 0, در نزدیکی نقطه ی شروع (x0) میباشد . equation solversرا میتوانیم بعنوان یکی از solver های بهینه سازی در نظر بگیریم زیرا این سوال معادل با پیدا کردن مینیمم نُرم f(x) در نزدیکی نقطه ی شروع است .

Least-Squares (curve-fitting) solvers :

این گروه ازsolver  ها به دنبال مینیمم کردن جمع مربعات هستند این نوع از مسائل اخیرا برای بهتر مدل کردن یک مساله به data  ایجاد شده است و شامل انواع زیر میشود :

nonnegative solutions, bounded or linearly constrained solutions, and fitting parameterized nonlinear models to data .

 

حال بر اساس انواع مسائل بهینه سازی و همین طور انواع solver  ها که تا اینجا با آنها آشنا شدیم یک جدول تصمیم گیری خواهیم داشت که براساس نوع مساله solver  های مناسب را به ما پیشنهاد میدهد البته این جدول یک فرم کلی است و ممکن است دربرخی از قسمت ها دارای استثناهایی باشد . مسائل ما یکی از پنج مدل زیر خواهد بود :

۱) Linear

۲) Quadratic

۳) Sum-of-squares (Least squares)

۴) Smooth nonlinear

۵) Nonsmooth

و معادلات یا نامعادلات قیدها یا همان constraints یکی ازپنج حالت زیر خواهد بود :

۱) None (unconstrained)

۲) Bound

۳) Linear (including bound)

۴) General smooth

۵) Discrete (integer)

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

mat9

الگوریتم های solver ها :

هرکدام از Solver ها الگوریتم های مشخصی نیز دارند که میتوانیم از آنها استفاده کنیم و حتی میتوانیم در قسمت cmd  (کامند ، کنسول ) الگوریتم خاصی را on کنیم تا حتما از آن الگوریتم مشخص استفاده کند چون با استفاده از الگوریتم های خاص مجموعه قسمت های شدنی که جواب های مساله است تغییر میکنند  الگوریتم های هر کدام از solver  ها در پنجره ی بهینه سازی بعد از انتخاب solver  درخواستی مشخص میشوند .

ما در اینجا به صورت خلاصه توضیحی کلی راجب الگوریتم های Linear Programming  میدهیم:

LP  دارای سه الگوریتم : Large-scale interior-point و Medium-scale active set و Medium-scale Simplex  است . در قسمت cmd  با استفاده از optimset اگر ما large-scale  را on  (‘LargeScale’ = ‘on’) بگذاریم از Large-scale interior-point  استفاده میکند که الگوریتم دیفالت LP هم هست در در صورت off  بودن از بین دو الگوریتم دیگرانتخاب میکند.

در این قسمت مسائلی که با توابع بهینه سازی مدل شده و حل میشوند براساس نوع کلی آنها در چند جدول دسته بندی شده اند :

Minimization Problems :

mat10

۲) Multiobjective Problems

11mat

۳) Equation Solving Problems

mat12

۴)Least-Squares (Model-Fitting) Problems

mat13

بر اساس نوع سوال و فرم کلی تابع هدف و همین طور قید های مساله solver  مناسب را طبق جدول های بالا انتخاب کرده و به حل سوال میپردازیم .

نوشتن تابع هدف :

mat15

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

نوشتن تابع هدف اسکالر :

یک فایل تابع هدف اسکالر فقط یک input  دارد و یک خروجی نیز بازمیگرداند ؛ input  دراین مرحله میتواند “یک ” اسکالر ، بردار یا ماتریس باشد . برای مثال تابع هدف زیر را در نظر بگیرید :

  F(x) =3*(x – y)4 + 4*(x + z)2 / (1 + x2 + y2 + z2) + cosh(x – ۱) + tanh(y + z)

این تابع را در فایل تابع هدف به صورت زیر مینویسیم به طوری که بردار   xin=[x,y,z] ورودی آن بوده و مقدار f را باز میگرداند :

function f = myObjective(xin)

f = 3*(xin(1)-xin(2))^4 + 4*(xin(1)+xin(3))^2/(1+norm(xin)^2)…

+ cosh(xin(1)-1) + tanh(xin(2)+xin(3));

بعد این فایل را با نام myObjective.m  سیو میکنیم بعد درقسمت cmd وردی مناسب را داده و تابع را با ان ورودی فراخوانی میکنیم :

myObjective([1;2;3])

ans =

    ۹٫۲۶۶۶

نوشتن قید ها :

Solver های تولباکس بهینه سازی روش های مشخصی نیز برای نوشتن فایل قید ها دارند :

Bound Constraints :

حد بالایی (UB) و حد پایین (LB) برای هر یک از xi ها به صورت مجزا :

x ≥ l and x ≤ u

Linear Inequality Constraints:

A·x ≤ b ؛ یک ماتریس m*n برای m  قید ویک بردارn  بعدی x .

Linear Equality Constraints:

Aeq·x = beq ؛ فرم مساوی قیدها به همان فرم نامساوی  میباشد .

Nonlinear Constraints:

 ؛ c(x) ≤ ۰ و ceq(x) = 0

که هم c و ceq اسکالر ها یا بردارهایی که نمایش دهنده ی قید ها هستند میباشد .

بعد از نوشتن فایل تابع هدف و قید ها و انتخاب solver  مناسب و ران شدن برنامه ممکن است که solver  ما fail  شود حال به بررسی دلایل آن میپردازیم :

Solver منتخب ما ممکن است که قبل از حل مساله stop  شود این اتفاق ممکن است به دلیل زیاد شدن iterations (تعداد دفعاتی که الگوریتم اجرا میشود )  باشد برای ادامه ی حل باید یکی از روش های زیر را انجام دهیم :

۱) Enable Iterative Display

۲) Relax Tolerances

۳) Start the Solver From Different Points

۴) Check Objective and Constraint Function Definition

۵) Center and Scale Your Problem

۶) Provide Gradient or Jacobian

۷) Provide Hessian

۱- در این قسمت ما با استفاده از فرمان زیر در cmd

options = optimset(‘Display’,’iter’);

نتیجه ی iteration ها را مشخص میکنیم در اینجا مثلا اگر مقدار تابع هدف در حال کاهش باشد این کاهش نشان دهنده ی ادامه ی فرایند مینیمم سازی و ادامه ی برنامه است .

۲- اگر تلورانس x یا تلورانس تابع هدف ناچیز باشد ممکن است solver نقطه ی مینیمم را تشخیص ندهد وبازstop شود، پس با به اصطلاح ریلکس کردن تلورانس آنها یعنی افزایش دامنه ی آنها از این اتفاق جلوگیری میکنیم .

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

۴- چک کردن اینکه یک نقطه ی نشدنی باعث ایجاد خطا در روند برنامه نمیشود بر اساس تعریف تابع هدف و قیود .

No Feasible Point :

دلیل بعدی که ممکن است solver  ما stop شود نبودن یک نقطه ی شدنی است یعنی اینکه هیچ نقطه ایی وجود نداشته باشد که تمامی قید ها را به اصطلاح satisfy کند . در این صورت باید قید ها را دوباره چک کنیم . برای این کار اگر قید های ما همگی خطی باشند از راه زیر اقدام میکنیم :

یک LP ویک تابع هدف تعریف میکنیم که همواره برابر صفر است :

f = zeros(size(x0));

فرض میکنیم که x0 یک نقطه ی ابتدایی است

LP را حل میکنیم تا ببینم که ایا یک جواب شدنی دارد یا خیر

xnew = linprog(f,A,b,Aeq,beq,lb,ub);

اگر یک نقطه ی شدنی وجود داشت از xnew بعنوان نقطه ی شدنی مساله ی اولیه استفاده میکنیم و به مساله ی اولیه برمیگردیم . در غیر این صورت مساله ی اولیه ما به صورت درست فرم بندی نشده است و باید باند ها و قیود آن دوباره بررسی شوند .

problem Unbounded :

lim f(xi)

= ∞-

باید دوباره مساله را چک کنیم که ایا درست فرمول بندی شده یا نه.

fsolve Could Not Solve Equation:

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

تولباکس بهینه سازی به صورت گرافیکی :

همان طور که در قسمت های قبل توضیح دادیم علاوه بر حل سوال و استفاده از توابع در محیط های edit  و cmd میتوانیم از پنجره ی بهینه سازی که با فرمان optimtool باز میشود ( در قسمت های قبل تصویر این پنجره را نشان دادیم ) استفاده کنیم این پنجره یک GUI  برای تولباکس بهینه سازی است. به طور خلاصه استفاده از این پنجره درچند گام زیر خلاصه میشود :

  • انتخاب solver و الگوریتم دلخواه ( براساس نوع مساله و کمک از جدول تصمیم )
  • مشخص کردن تابع هدف که قرار است مینیمم شود
  • مشخص کردن پارامتر های تابع هدف
  • مشخص کردن اپشن های اضافه
  • ران کردن
  • مشاهده ی نتیجه و وضعیت solver

mat19

بعد از مشخص کردن تابع و قید ها و options  های اضافه ، دکمه start  را میزنیم .میتوانیم در هر قسمت از pause  و resume استفاده کنیم وقتی که اجرا به انتها رسید پنجره Run solver and view results  باز میشود و ما میتوانیم در اینجا نتایج به دست امده را طبقه بندی کنیم در این قسمت ما میتوانیم با استفاده از  Plot Functions مساله را نیز رسم کنیم هر پلات انتخاب شده axis مجزا را در پنجره ی figure  رسم میکند .لیست توابع پلات در دسترس به شرح زیر است :

Current point:

این پلات برای نشان دادن یک bar plot  ازنقطه ی انتخابی در iteration  جاری میباشد.

Function count:

این تابع برای پلات ، تعداد ارزیابی تابع در هر iteration استفاده میشود.

Function value:

برای پلات مقدار تابع در هر iteration

Norm of residuals:

یک بارپلات برای نمایش نرم جاری باقی مانده در iteration  فعلی

Max constraint:

یک پلات برای نمایش ماکسیمم مقدار  constraint violation در iteration  جاری

Current step:

یک پلات برای مشخص کردن سایز مرحله ی الگوریتم در هر iteration

First order optimality:

یک پلات برای رسم ، مقدار نقض شرط بهینگی در هر مرحله

Custom function:

وارد کردن تابع پلات خودتان، درصورتی که قصد وارد کردن بیش از یک پلات را داشتید از یک cell array  استفاده کنید .

 

Getting Help in the Optimization Tool :

در GUI  تولباکس بهینه سازی در متلب یک help  مختصر و مفید به همراه مثالی کوچک آورده شده است که وقتی optim tool  را باز میکنیم پنجره سمت راست تحت عنوان  Quick Reference

میباشد که به تنهایی مفید و کافی است اما در صورت نیاز به اطلاعات جزیی تر از قسمت help more  وارد help  کلی متلب که مرتبط با آن قسمت هست خواهید شد .

سعید عربعامری
من سعید عربعامری نویسنده کتاب 28 گام موثر در فتح متلب مدرس کشوری متلب و سیمولینک و کارشناس ارشد مهندسی برق قدرتم . بعد از اینکه دیدم سایتهای متعدد یک مجموعه کامل آموزش متلب و سیمولینک ندارند به فکر راه اندازی این مجموعه شدم
http://sim-power.ir

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *