روش ترسیمی (حل هندسی)
|
در ادامه، روش ترسیمی برای حل مسائل توضیح داده شده است.
این روش در درس تحقیق در عملیات 1 در دانشگاه‌ها تدریس می‌شود و جزوه مباحث مطرح در کنکور نیز می‌باشد.
حل هندسی (روش ترسیمی):
یکی از روش‌هایی که برای حل مسائل به کار برده می‌شود، حل هندسی یا ترسیمی می‌باشد. در این روش، بایستی محدودیت‌های مسئله را در فضای دو بعدی ترسیم کنیم.
سپس به سه روش می‌توانیم جواب بهینه را بدست آوریم:
1- تست نقاط گوشه‌ای
2- بردار گرادیان تابع هدف
3- رسم بردار گرادیان محدودیت‌های گذرنده از نقاط گوشه‌ای
روش اول (تست نقاط گوشه‌ای):
در این روش، تمام نقاط گوشه‌ی موجود در مسئله باید تست شوند، آن نقطه‌ی گوشه‌ای بهینه است که جواب بهتری نسبت به سایر نقاط گوشه داشته باشد. یکی از ضعف‌های این روش این است که باید تمام شماری شود یعنی تمام نقاط گوشه‌ای بررسی شوند.
مثال: مسئله زیر را با استفاده از روش ترسیمی حل کنید و جواب بهینه را بدست آورید.
حل با روش اول (تست نقاط گوشه‌ای):
حل: فضای دو بعدی مسئله ترسیم می‌شود (می‌توانید از ابزارهای آنلاین نیز برای ترسیم استفاده نمایید):
در این مثال، 4 نقطه گوشه‌ای وجود دارد که باید تمام آنها بررسی شوند:
حل با روش دوم (رسم بردار گرادیان تابع هدف): متداول‌ترین روش
بردار گرادیان (بردار C) چیست؟ ضرایب تابع هدف را بردار گرادیان گوییم
* حرکت تابع در جهت بردار گرادیان، بیشترین افزایش را دارد (max)
* حرکت تابع در خلاف جهت بردار گرادیان، بیشترین کاهش را دارد (min)
حل با روش سوم (رسم بردار گرادیان محدودیت‌های گذرنده از نقاط گوشه‌ای):
بردار گرادیان محدودیت‌های گذرنده از نقاط گوشه‌ای را رسم و مخروط حاصل از آنها را هاشور می‌زنیم. در مسئله min سازی، بردار –C را روی تمام نقاط گوشه‌ای گذاشته و می‌کشیم (و در max سازی، بردار C) نقطه گوشه‌ای که بردار –C داخل مخروط (max، بردار C) قرار بگیرد، نقطه بهینه است.
نکته: بردار گرادیان (بردار ضرایب) برای هر محدودیت در خلاف جهت ناحیه‌ای که محدودیت به عنوان فضای شدنی مشخص می‌کند در سوال، کشیده می‌شود.
نکته: بردار گرادیان محدودیت‌ها، عمود بر آنها می‌باشد.
حالت‌های موجود برای حل با روش ترسیمی:
1- جواب بهینه منحصر به فرد (یکتا) متناهی، دارای یک نقطه بهینه است که آن هم، همان گوشه است.
2- جواب بهینه نامتناهی:
نکته: اگر جواب بهینه نامتناهی شود حتما ناحیه هم نامتناهی است. اما اگر ناحیه نامتناهی باشد حتما جواب بهینه نامتناهی نیست (یعنی ممکن است جواب بهینه منحصر به فرد نیز باشد).
3- جواب بهینه چندگانه (دگرین):
بی‌نهایت نقطه بهینه داریم.
نکته: در حالت جواب بهینه چندگانه مجموع نقاط بهینه ناشمارا می‌باشد
نکته: شرط لازم جواب بهینه چندگانه موازی بودن تابع هدف با یکی از محدودیت‌ها می‌باشد. (فقط در فضای دو بعدی این حرف صادق است)
4- ناموجه (نشدنی): یک مسئله LP را موجه می‌نامیم اگر حداقل یک نقطه وجود داشته باشد که در تمام محدودیت‌ها صدق کند.
5- تباهیدگی: در فضای دو بعدی اگر از یک نقطه بیش از دو محدودیت بگذرد، نقطه تبهگن وجود دارد. (جواب تبهگن وجود دارد).
ویدیو آموزشی روش ترسیمی:
بسیار عالی بود توضیحات. ممنون از شما
سلام
تشکر از نظر شما
موفق باشید
ممنون از توضیحات روان و خوبتون
سلام مهدی عزیز،
تشکر از نظر ارزشمند شما
موفق باشید.