author avatar
شریف نگار
بروزرسانی در تاریخ ۱۳۹۹/۰۷/۲۷

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

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

حل روش انشعاب و تحدید در نرم افزار گمز معمولا حل می شود و می توان مسئله را با سرعت بالاتری نسبت به سایر نرم افزارها حل کرد. نرم افزار گمز دارای انعطاف پذیری بالایی بوده و به راحتی می‌توان محدودیت‌ها را اضافه و کم کرد. حل اینگونه مسائل می‌تواند در نرم‌افزارهای دیگر نیز انجام پذیرد. همچنین برای حل روش شاخه و کران می توان از نمودار گرافیکی نیز استفاده کرد. برای حل این مسئله و ترسیم فضای جواب می‌توانید با جستجو کردن  php Symplex در گوگل و کلیک بر روی سایت phpsymplex.com محاسبات را به صورت آنلاین انجام داده و بدون نیاز به داشتن دانش کافی در مورد مدلسازی و کدنویسی مسائل در نرم افزارهای مختلف مسئله را حل کند. همچنین مراحل مختلف روش سیمپلکس را می توانید در این وبسایت ببینید.

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

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

آموزش روش شاخه و کران یا انشعاب و تحدید در گمز با مثال فیلم

دیدگاه ها

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

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