Feasible region — ناحیه جواب‌های مجاز

ناحیه جواب‌های مجاز (همچنین مجموعه جواب‌های مجاز، به انگلیسی Feasible region, feasible set) — در تحقیق در عملیات، بهینه‌سازی و مدل‌سازی ریاضی، مجموعه‌ای است از تمام جواب‌های ممکن (مجموعه مقادیر متغیرها) که همه قیدهای تعیین‌شده برای مسئله را برآورده می‌کنند.

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

تعریف و شکل‌گیری

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

• نامعادلات: کران‌های بالا یا پایینی برای مقادیر متغیرها یا ترکیب آن‌ها تعیین می‌کنند (برای مثال، «مصرف منبع A نباید از ۱۰۰ واحد تجاوز کند»، «مقدار محصول تولیدشده باید حداقل ۵۰ عدد باشد»).
• معادلات: برآورده شدن دقیق یک شرط را می‌طلبند (برای مثال، «حجم کل حمل‌ونقل باید برابر ۱۰۰۰ تن باشد»، «تراز جریان‌های ورودی و خروجی برابر صفر است»).
• شرایط علامت متغیرها: اغلب متغیرها باید نامنفی، صحیح یا متعلق به یک مجموعه گسسته معین باشند.

یک نقطه (یا بردار مقادیر متغیرها) در صورتی و فقط در صورتی به ناحیه جواب‌های مجاز تعلق دارد که به طور همزمان تمام این قیدها را برآورده کند.

تفسیر هندسی

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

• در فضای دوبُعدی (۲ متغیر): هر قید خطی از نوع نامعادله، یک نیم‌صفحه تعریف می‌کند. ناحیه جواب‌های مجاز اشتراک این نیم‌صفحه‌هاست — یک چندضلعی محدب (که ممکن است نامکران یا تهی باشد).
• در فضای سه‌بُعدی (۳ متغیر): هر قید خطی از نوع نامعادله، یک نیم‌فضا تعریف می‌کند. ناحیه جواب‌های مجاز اشتراک این نیم‌فضاهاست — یک چندوجهی محدب (چندوجهی).
• در فضای چندبُعدی: ناحیه جواب‌های مجاز که با قیدهای خطی تعریف می‌شود، یک چندوجهی محدب (پلی‌توپ) است.

در حالت قیدهای غیرخطی، ناحیه جواب‌های مجاز می‌تواند شکل پیچیده‌تری داشته باشد و لزوماً محدب نباشد.

نقش در بهینه‌سازی

ناحیه جواب‌های مجاز نقشی بنیادین در بهینه‌سازی ایفا می‌کند:

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

ویژگی‌های ناحیه جواب‌های مجاز (در مسائل برنامه‌ریزی خطی)

در مسائل برنامه‌ریزی خطی (LP)، که در آن‌ها همه قیدها و تابع هدف خطی هستند، ناحیه جواب‌های مجاز ویژگی‌های مهمی دارد:

• محدب بودن: اگر دو نقطه به ناحیه جواب‌های مجاز تعلق داشته باشند، تمام پاره‌خط واصل این دو نقطه نیز به ناحیه جواب‌های مجاز تعلق دارد. این ویژگی تضمین می‌کند که جواب بهینه (در صورت وجود و یکتایی) در یکی از رأس‌های چندوجهی ناحیه جواب‌های مجاز قرار خواهد داشت.
• بسته بودن: ناحیه جواب‌های مجاز شامل مرزهای خود نیز می‌شود (به دلیل نامعادلات غیرتند ≤، ≥ و معادلات).

ناحیه جواب‌های مجاز می‌تواند:

• کراندار باشد: ابعاد محدودی داشته باشد.
• نامکران باشد: در یک یا چند جهت به بی‌نهایت امتداد یابد.
• تهی باشد: هیچ نقطه‌ای نداشته باشد.

همچنین ببینید

• تحقیق در عملیات
• بهینه‌سازی
• مدل ریاضی
• قیدها
• جواب مجاز
• جواب بهینه
• تابع هدف
• برنامه‌ریزی خطی
• مجموعه محدب

منابع

• Ventzel E. S. تحقیق در عملیات: مسائل، اصول، روش‌شناسی. — مسکو: Nauka، ۱۹۸۸.
• Ackoff R., Sasieni M. مبانی تحقیق در عملیات. — مسکو: Mir، ۱۹۷۱.
• Taha, Hamdy A. Operations Research: An Introduction. — Pearson. (10th ed., 2017)
• Hillier, Frederick S.; Lieberman, Gerald J. Introduction to Operations Research. — McGraw-Hill Education. (11th ed., 2021)