روش‌های بهینه‌سازی در اکسل
بررسی روش های مختلف بهینه‌سازی موجود در اکسل تحت منوی Solver
بطور کلی به تخصیص منابع محدود به فعالیت‌های تعریف شده به منظور افزایش بازدهی و دستیابی به جواب بهینه و بهترین راه‌حل را بهینه‌سازی گویند. روش‌های مختلفی از جمله روش‌های خطی، غیرخطی و الگوریتم‌های مختلفی برای بهینه‌سازی منابع ارائه شده است. در نرم‌افزار اکسل ۳ روش به منظور بهینه‌سازی توابع هدف مختلف تحت منوی Solver ارائه شده است:
- Simplex LP
- GRG Nonlinear
- Evolutionary
روش‌های بهینه‌سازی
-
Simplex LP:
برنامه‌ریزی خطی (LP) یکی از روش‌های ساده و کاربردی بهینه‌سازی و برنامه‌ریزی ریاضی میباشد. بطور خلاصه می‌توان چنین بیان نمود که در برنامه‌ریزی خطی تابع هدف و محدودیت‌ها همگی بصورت خطی تعریف می‌شوند. بخش‌های اصلی یک مدل برنامه‌ریزی خطی عبارتند از:
- ۱) تابع هدف که بیانگر بیشینه یا کمینه نمودن عملکرد مدل است.
- ۲) محدودیت‌ها که بیانگر محدودیت‌های مدل در جهت رسیدن به اهداف مدل می‌باشند.
نکته مهم در خصوص برنامه‌ریزی ۴ فرض تناسب، جمع‌پذیری، بخش‌پذیری و معین بودن میباشد.
روش سیمپلکس در واقع الگوریتمی است که در آن یک رویه نظام‌گرا آنقدر تکرار می‌گردد تا سرانجام به جواب مطلوب برسد. در یک دستورالعمل جبری سروکار داشتن با معادلات، به مراتب آسان‌تر از نامعادلات است. بنابراین نخستین قدم در روش سیمپلکس تبدیل محدودیت‌ها از نامعادله به معادله میباشد. این نکته لازم بذکر است که محدودیت‌های نامنفی را می‌توان به شکل نامعادله باقی گذاشت. بعنوان مثال نحوه تبدیل نامعادلات به معادلات در شکل زیر نشان داده شده است. همانطور که در شکل زیر نشان داده شده است در دستگاه جدید دو متغیر بیشتر وجود دارد و بدین معناست که در حل این دستگاه ۲ درجه آزادی خواهیم داشت. زیرا می‌توان این دو متغیر را مساوی هر مقدار دلخواهی قرار داده و دستگاه سه معادله‌ای را بر حسب سه متغیر باقیمانده حل نمود. این مقادیر دلخواه در روش سیمپلکس مساوی صفر انتخاب می‌شوند. متغیرهایی که برابر صفر در نظر گرفته شده‌اند، متغیرهای غیر اساسی و سایر آن‌ها متغیرهای اساسی نام دارند که مخالف صفر می باشند.
بطور کلی اگر لازم باشد روش سیمپلکس بصورت خلاصه بیان شود، می‌توان چنین بیان نمود که در این روش دستگاه معادلات در جستجوی مجموعه‌ای از جواب‌های اساسی موجه، پی در پی حل می‌شود، بطوریکه هر جواب اساسی موجه جدید از جواب قبلی بهتر باشد تا سرانجام یک جواب بهینه بدست آید. با تبدیل یکی از متغیرهای غیراساسی به اساسی و در مقابل تبدیل یکی از متغیرهای اساسی به غیراساسی (متغیر اساسی خروجی) می‌توان از جواب موجه فعلی به یک جواب موجه جدید رسید. جواب اساسی موجهی بهینه است که از تمام جواب‌های اساسی موجه مجاور خود بهتر باشد.
گام های انجام روش سیمپلکس
۱) قدم ابتدایی: مشخص نمودن یک جواب موجه ابتدایی
۲) قدم تکراری: حرکت به سمت یک جواب اساسی موجه بهتر
۳) دستور توقف: در صورت عدم وجود جواب اساسی موجه بهتر، عملیات متوقف گردد
روش سیمپلکس همواره می‌تواند جواب بهینه مساله برنامه‌ریزی خطی را بدست آورد ولی یکی از مشکلات در خصوص استفاده از این الگوریتم، همانگونه که بیان گردید خطی بودن تابع هدف و محدودیت‌ها میباشد. بنابراین در صورت برخورد با مسائلی که تابع هدف و یا محدودیت‌های آن از نوع خطی نمی‌باشند استفاده از این روش صحیح نمی‌باشد و می‌بایست از روش‌های بهینه‌سازی غیرخطی همانند GRG استفاده نمود.
روش گرادیان کاهش یافته عمومی GRG
روش برنامه ریزی غیرخطی به نسبت دیگر روش‌های بهینه‌سازی در سیستم‌های منابع آب کاربرد کمتری دارند. زیرا فرایند بهینه‌سازی در این روش‌ها به نسبت دیگر روش‌ها کند بوده و فضا و زمان زیادی از رایانه می‌گیرد. در مدل‌های برنامه‌ریزی غیرخطی ارتباط بین متغیرهای تصمیم‌گیری دست کم در یکی از موارد غیرخطی است. عامل غیرخطی بودن می‌تواند در تابع هدف یا در یک یا چند محدودیت باشد. در حالت واقعی بسیاری از محدودیت‌ها و هدف‌ها بصورت غیرخطی هستند. روش‌های گوناگونی برای حل برنامه‌ریزی غیرخطی وجود دارد که از این میان می‌توان به روش‌های ضریب لاگرانژ، تابع‌های اولیه و روش گرادیان اشاره کرد که در نرم‌افزار Excel، امکان بهینه‌سازی با استفاده از روش گرادیان کاهش‌یافته GRG قرار داده شده است.
بیشتر روش‌های حل مسائل برنامه‌ریزی غیر خطی عمومی شامل خطی کردن مساله و به کار بردن تکنیک برنامه‌ریزی خطی است که بطور خلاصه مراحل زیر برای استفاده از آن‌ها طی می‌شود:
۱- خطی نمودن تمام محدودیت‌های تابع هدف حول نقاط عملیاتی، بطوریکه مساله به فرم برنامه‌ریزی خطی تبدیل شده و سپس استفاده از برنامه ریزی خطی برای حل مساله.
۲- تکرار روش برنامه‌ریزی خطی برای رسیدن به جواب مناسب با خطی کردن توابع محدودیت‌ها و تابع هدف و چنانچه به جواب مناسب نرسید با خطی کردن دوباره محدودیت‌ها و توابع هدف حول نقطه جدید جواب بهینه مساله پیدا می‌شود.
در روش‌های بالا این امکان وجود دارد که روش به همگرایی نرسد و این خود یکی از معایب روش‌های فوق است، در واقع می‌توان چنین بیان نمود که بهترین الگوریتم عمومی موجود به منظور بهینه‌سازی مسائل با تابع هدف یا محدودیت‌های غیرخطی، استفاده از الگوریتم گرادیان کاهش یافته عمومی GRG است.
GRG توسعه یافته الگوریتم Wolfe برای محدودیت‌های خطی اصلاح شده که تابع هدف و محدودیت آن‌ها غیرخطی است، محسوب می‌شود. در اصل روش محدودیت‌های خطی یا خطی شده را شامل می‌شود و متغیر جدید با محدودیت تعریف خواهد شد .
در بهترین حالت این روش می‌تواند یک نقطه بهینه محلی (Local) برای یک مدل غیرمحدب پیدا نماید. این نکته لازم بذکر است که در این روش امکان گیر افتادن در نقاط بهینه موضعی وجود دارد، بنابراین گاهی ممکن است که بهینه‌سازی قبل از پایان یافتن فرآیند بهینه‌سازی و رسیدن به جواب بهینه متوقف گردد.
در هنگام استفاده از این روش هنگامیکه پیغام “Solver found a solution” ظاهر می‌گردد بدین معناست که الگوریتم توانسته است یک نقطه بهینه برای تابع هدف پیدا نماید و نقطه‌ی بهینه دیگری برای متغیرها در جهت رسیدن تابع هدف به مقدار بیشینه یا کمینه وجود ندارد. همچنین نمایش ” Solver has converged to the current solution ” بمعنای آن است که مقدار قدر مطلق تغییرات تابع هدف در ۵ تکرار آخر تغییر چندان محسوسی نداشته است.
با استفاده از روش GRG بندرت اتفاق می‌افتد که پیغام ” Solver cannot improve the current solution ” که بمعنای عدم بهبود تابع هدف است، نمایش داده شود ولی در صورت رخ دادن چنین اتفاقی نیاز است برای حل تابع هدف و یافتن مقادیر متغیرها، برخی از محدودیت‌های مدل حذف گردند. در صورت عدم امکان انجام این‌کار نیاز است که از روش‌های دیگر بهینه‌سازی از جمله Evolutionary استفاده نمود.
Evolutionary
Evolutionary algorithm یکی از الگوریتم‌های بهینه‌سازی فراشناختی مبتنی بر ازدحام جمعیت است. این الگوریتم در شاخه هوش مصنوعی قرار می‌گیرد و شامل الگوریتم‌هایی است که در آن‌ها جستجو از چندین نقطه در فضای جواب آغاز می‌شود. از تفاوت‌های الگوریتم Evolutionary با سایر روش‌های بهینه‌سازی می‌توان به این موارد اشاره نمود که در این الگوریتم تنها یک نقطه مورد جستجو قرار نمی‌گیرد، بلکه جمعیتی از نقاط بطور همزمان مورد بررسی قرار می‌گیرند. همچنین در این روش محدودیتی برای تابع هدف وجود ندارد. علاوه بر این‌ها، با استفاده از این روش تعداد زیادی از نقاط بهینه بدست می‌آید که انتخاب جواب بهینه پایانی برعهده کاربر میباشد. از جمله الگوریتم‌های فرگشتی می‌توان به الگوریتم ژنتیک، الگوریتم کلونی زنبور عسل، الگوریتم بهینه‌سازی مورچگان، راهبرد فرگشتی و الگوریتم رقابت استعماری اشاره نمود.
بطور خلاصه می‌توان چنین بیان نمود که بهینه‌سازی با استفاده از این الگوریتم‌ها بدین صورت است که در ابتدا تعدادی از اعضای جامعه بصورت تصادفی انتخاب می‌گردند، سپس مقدار تابع هدف به ازای هریک از مقادیر تصادفی، محاسبه می‌شود که مقادیر مربوط به تابع هدف بعنوان اولین نسل شناخته می‌شوند. در این مرحله میزان برازش مقادیر تابع هدف محاسبه با مقدار مورد نظر بررسی شده و در صورتیکه هیچ از یک معیارهای خاتمه الگوریتم تامین نشده باشد، ایجاد نسل جدید آغاز می‌شود. لازم بذکر است که در شکل‌گیری نسل جدید، میزان شایستگی هر یک از اعضا در بهینه‌سازی تاثیر خواهد داشت و اعضایی که مقدار تابع هدف مربوط به آن‌ها به مقدار مدنظر نزدیک‌تر باشد، سهم بیشتری در تولید نسل جدید خواهند داشت. سپس هر یک از اعضای نسل با یک احتمال معین تغییر ژنتیکی (جهش) می‌یابند و به ازای نسل جدید مجددا مقدار تابع هدف محاسبه شده و چرخه فوق تکرار می‌گردد. تا زمانیکه یکی از معیارهای بهینه‌سازی تحقق یابد.
یکی از نکات حائز اهمیت در انتخاب این روش لزوم وجود جهش میباشد که در نرم‌افزار Excel نیز امکان تعیین احتمال آن از سوی کاربر وجود دارد. زیرا در صورت عدم وجود جهش، بتدریج پس از چندین تکرار، نسل‌ها مشابه یکدیگر می‌گردند و بهبودی رخ نخواهد داد. بنابراین ممکن است الگوریتم در دام بهینه‌های محلی گیر افتد که جهش باعث برون‌رفت از آن‌ها می‌شود.