بهینه‌سازی مسائل تک‌هدفه

مسئله بهینه‌سازی

مسائل بهینه‌سازی تک‌هدفه داری یک تابع هدف f هستند که برمبنای آن کیفیت راه حل‌های ممکن را ارزیابی می‌کنند. تابع هدف f را می‌توان به عنوان نگاشتی از فضای جست و جوی S به فضای هدف R تعریف کرد.

فضای جست‌و‌جوی S فضایی است که شامل تمام مقادیر مجاز برای متغیرهای حل مسئله بهینه‌سازی می‌شوند.

در صورتی که مسئله دارای n متغیر مشتقل باشد، فضای جست و جو دارای n بعد خواهد بود و در هر موقعیت در این فضا با بردار x نشان داده خواهد شد.

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

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

برای مثال در شکل زیر فضای جواب مسئله کمینه‌سازی تابع رستریجین را مشاهده می‌کنید که نقاط (1) و (3) نقاط بهینه نسبی و نقطه (2) نقطه بهینه مطلق است. در مسائل پیچیده‌ی دنیای واقعی همیشه کل فضای جواب در دسترس نیست و این امر باعث ایجاد شبه در بهینه نسبی یا مطلق بودن جواب بدست آمده می‌شود که با توجه به روش‌‌های حل مختلف، راه‌هایی برای جلوگیری در به دام افتادن جواب بدست آمده در نقاط بهینه نسبی می‌شود که در ادامه آموزش به آن پرداخته خواهد شد.

انواع مسائل بهینه‌سازی

مسائل بهینه‌سازی دودویی، گسسته و پیوسته

بر اساس نوع متغیرهای مجهول، مسائل بهینه‌سازی را میتوان به سه دسته دودویی،  گسسته و پیوسته تقسیم کرد.

مسائل بهینه‌سازی دودویی به مسائلی اطلاق می‌شود که متغیرهای مجهول آن را بتوان در قالب یک رشته دودویی(Binary) ارائه کرد. برای مثال در صورتی که هدف انتخاب زیر مجموعه‌ای از میان مجموعه ای بزرگتر باشد، انتخاب عدم انتخاب هر عضو مجموعه می‌تواند به صورت صفر یا یک نشان داده شود در نتیجه هر راه حل کاندید، رشته ای دودویی به اندازه ابعاد مجموعه خواهد بود که اعداد صفر و یک در آن به ترتیب بیانگر عدم انتخاب و انتخاب آن عضو است.

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

 مسائل بهینه‌سازی پیوسته، متغیرهای مجهول در آنها از نوع اعداد حقیقی هستند. برای نمونه توابع ریاضی که نقاط کمینه یا بیشینه آن‌ها مورد سؤال است، جزء این دسته از مسائل قرار میگیرند. برای مثال مسئله کمینه‌سازی تابع رستریجین، مسئله بهینه‌سازی پیوسته‌ای است که راه حل کاندید آن شامل یک متغیر یا مقادیر پیوسته در بازه [۵.۱۲,۵.۱۲-] است.

برخی مسائل وجود دارد که به صورت همزمان دارای متغیرهایی با انواع مختلف گسسته و پیوسته، دودویی و پیوسته، گسسته و دودویی است.

مسائل بهینه سازی مقید و بدون قید

یکی از مؤلفه هایی که مسائل بهینه سازی را از یکدیگر متمایز می کند وجود یا عدم وجود قید (محدودیت) در آنهاست. در بسیاری از مسائل مجموعه ای از قیود (محدودیت‌ها) وجود دارد که لازم است متغیرها در آنها صدق کند تا نتایج معنادار باشند. در بسیاری از کاربردهای عملی، محدودیت‌هایی در مقدار متغیرهای مسئله وجود دارد که به صورت قید (محدودیت) به مسئله بهینه‌سازی اضافه می‌شود. قیود به روش‌های مختلف فرموله می‌شوند؛ مانند قیود مساوی، نامساوی، ارتباط بین متغیرها و… در زیر مثالی از یک مسئله بهینه‌سازی مقید ارائه شده است.

در مثال زیر، هدف کمینه‌سازی مقید تابع هدف f با n متغیر است که قید مساوی g و قیود نامساوی h و k نیز به مسئله اضافه شده است. با توجه به روش حل می‌توان این مسئله مقید را به صورت مقید یا با استفاده از تبدیل آن به مسئله نامقید حل کرد.

مسئله بهینه‌سازی قطعی و غیر قطعی

در مسائل بهینه‌سازی قطعی فرض می‌شود داده ورودی مسئله کاملاً معلوم و تعریف شده است.

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

مسائل بهینه‌سازی غیر قطعی که داده ورودی مسئله را قطعی در نظر نمی‌گیرند و به آن ماهیت عدم قطعیت می‌یخشند؛ عمدتاً به صورت آماری یا فازی تعریف می‌شوند. در  مسائل غیر قطعی آماری، متغیرها از توزیع‌های آماری مانند توزیع آماری پواسون، یکنواخت، برنولی و… استفاده می‌کنند. همانطور که گفته شد، نوع دیگر مسائل غیر قطعی مسائل فازی هستند. این مسائل متغیرهای عدم قطعیت را به صورت اعداد فازی مثلثی، ذوزنقه‌ای، LR و… استفاده می‌کنند. برای حل آن از روش‌های آماری مختلف به‌منظور رباست‌سازی مدل ریاضی یا متغیر غیر قطعی است.

این نکته حائل اهمیت است که یکی از راه‌های ساده و سریع برای انتخاب موضوع پرپوزال یا پایان‌نامه یا مقالات علمی داخلی و خارجی، تبدیل مسائل قطعی تغریف شده از قبل به مسائل غیر قطعی و حل آن است!

مسائل بهینه‌سازی با یک موقعیت بهینه و چندگانه

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

مسائل بهینه‌سازی تک‌هدفه

در مثال بالا، هدف کمینه‌سازی مقید تابع هدف f با n متغیر است که قید مساوی g و قیود نامساوی h و k نیز به مسئله اضافه شده است. با توجه به روش حل می‌توان این مسئله مقید را به صورت مقید یا با استفاده از تبدیل آن به مسئله نامقید حل کرد.

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

مسائل برنامه‌ریزی تسهیلات به چهار دسته عمده مکان‌یابی، مسیریابی، تخصیص و طراحی تقسیم می‌شوند.

مسائل مکانیابی تسهیلات به تعیین مکان یک تسهیل (ساختمان، دستگاه، وسیله و…) جدید نست به یک تعداد وسیله موجود می‌پردازد. مکانی که به دنبال آن هستیم، جایی است که یک تابع هزینه کل تعریف‌شده را حداقل می‌کند و هزینه کل مذکور متناسب با فاصله در نظر گرفته می‌شود. مسائل تک‌هدفه مکانیابی در ساده‌ترین شکل ممکن به صورت زیر فرمول‌بندی می‌شوند:

m وسیله موجود در نقاط مشخص P ، قرار گرفته‌اند. یک تهسیل جدید قرار است در نقطه x قرار بگیرد. هزینه حمل و نقل مستقیماً متناسب با فاصله بین تهسیل جدید و موجود در نظر گرفته میشود. (x,p)d فاصله پیموده شده در هر سفر بین نقاط P و X و W ضرب هزینه هر واحد فاصله پیموده‌شده در تعداد سفرهای سالیانه بین تسهیل جدید و موجود را نشان میدهد. هزینه کل سالیانه سفر بین تسهیل جدید و همه تسهیلات موجود به وسیله فرمول زیر بیان می شود.

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

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

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

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

یکی از معروف‌ترین مسائل طراحی تسهیلات، چیدمان واحدهای صنعتی است که تشابهاتی با مسئله مکانیابی تسهیلات دارد. در مسائل چیدمان علوه‌بر ضریب هزینه هر واحد جابه‌جایی W، ضریب جریان مواد و تعداد سفرهای مورد نیاز را نیز در نظر گرفت.

با این حال، مسائل مکانیابی و چیدمان تهسیلات تفاوت‌هایی دارند که عبارت‌اند از:
• چدیمان به معنای جانمایی، طرح استقرار و Layout است.
• مکانیابی به معنای جایابی و Location  است.
• مکان‌یابی یک هدف بلندمدت‌تر و استراتژیک‌تر نسبت به چیدمان است.
• ابتدا مکان‌ یک تهسیل مشخص شده و سپس آن را در محل مناسب آن قرار می‌دهند.

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

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

زمانبندی

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

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

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

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

لجستیک

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

از مهمترین مسائل لجستیک می‌توان کنترل موجودی، مدیریت حمل‌ونقل و زنجیره تأمین را نام برد.

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

مدیریت حمل‌و‌نقل بخشی حیاتی از لجستیک و زنجیره تأمین است که بر برنامه‌ریزی، اجرا، نظارت و بهینه‌سازی جابه‌جایی کالاها، افراد یا اطلاعات بین نقاط مبدأ و مقصد تمرکز دارد. این فرآیند شامل انتخاب روش حمل‌ونقل، مسیرهای مناسب، نظارت بر عملیات حمل‌ونقل و مدیریت هزینه‌های حمل‌ونقل با استفاده از شناسایی و انتخاب مسیرهای کوتاه‌تر، حل مسئله فروسنده دوره‌گرد ( TSP ) و… می‌شود.

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

حل دقیق مسائل تک‌هدفه

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

بنابر نوع مسئله، روش‌های حل دقیق متفاوتی وجود دارد:

1. اگر مسئله برنامه‌ریزی خطی باشد، آنگاه روش‌های سیمپلکس، ترسیمی، M بزرگ و 2فاز(دوگان) پیشنهاد می‌شوند.

2. اگر مسئله برنامه‌ریزی غیر خطی باشد، آنگاه روش‌های  گرادیان، کروش کان تاکر ( KKT ) برنامه‌ریزی درجه‌دوم (برنامه‌ریزی کوادراتیک)، لاگرانژ و نقاط تصادفی پیشنهاد می‌شوند.

3. اگر مسئله برنامه‌ریزی عدد صحیح باشد، آنگاه روش‌های صفحات برشی، صفحات گمری، شاخه و کران، انشعاب و برش و الگوریتم بالاس پیشنهاد میشوند.

4. دیگر روش‌های حل دقیق از جمله برنامه‌ریزی پویا و محاسبات عددی (نیوتن-رافسون و الگوریتم‌های تکراری) نیز بنا به ماهیت مسئله می‌توان استفاده کرد.

حل تقریبی مسائل تک‌هدفه

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

یکی از روش‌های حل معقول برای مسائل NP-hard، روش‌های حل تقریبی است.

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

روش‌های ابتکاری

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

روشهای فراابتکاری

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

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

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

بنابر نوع مسئله و اهمیت زمان یا کیفیت حل انواع الگوربتم‌های فراابتکاری را می‌توان انتخاب و استفاده کرد.