قیود در مسائل بهینهسازی: شرطهایی که پاسخ باید آنها را برآورده کند
قیود چیست و چرا در بهینهسازی ضروری است؟
در بسیاری از مسائل بهینهسازی1، متغیرهای تصمیم نمیتوانند هر مقدار دلخواهی را بپذیرند. برای نمونه، یک کارخانه نمیتواند بیش از ظرفیت ماشینآلات خود تولید کند یا یک دانشآموز نمیتواند برای مطالعه تمام دروس، بیش از 24 ساعت در روز زمان صرف کند. به این محدودیتها، قید (Constraint) میگوییم. قیود، دامنهای را تعیین میکنند که پاسخ بهینه باید درون آن قرار بگیرد. بدون در نظر گرفتن قیود، پاسخ بهینه ممکن است غیرعملی یا نشدنی باشد.
دستهبندی قیود: برابری، نامساوی و دامنه متغیرها
قیود در بهینهسازی ریاضی معمولاً به سه شکل ظاهر میشوند. شناخت هر کدام برای حل مسئله ضروری است.
| نوع قید | نماد ریاضی | مثال علمی (دبیرستانی) |
|---|---|---|
| قید برابری | $g(x) = 0$ | مخزن باید دقیقاً 100 لیتر آب داشته باشد. |
| قید نامساوی | $h(x) \le 0$ | وزن بار مجاز حداکثر 500 کیلوگرم است. |
| قید دامنه (کران) | $a \le x \le b$ | دمای واکنش بین 0 تا 100 درجه سلسیوس باشد. |
در بسیاری از مسائل واقعی، ترکیبی از این قیود وجود دارد. برای نمونه، در مسئله برنامهریزی تولید، قید منابع (نامساوی) و قید تقاضای دقیق (برابری) همزمان دیده میشوند.
مثال عملی: بیشینه کردن سود با محدودیت بودجه
یک شرکت تولیدی دو محصول A و B میسازد. سود حاصل از هر واحد محصول A برابر 5 واحد و از هر واحد B برابر 4 واحد است. اگر x تعداد محصول A و y تعداد محصول B باشد، تابع سود برابر است با:
اما شرکت با دو قید مواجه است: بودجه کل کمتر از 100 واحد پولی و فضای انبار حداکثر 30 واحد. ساخت هر A نیاز به 2 واحد بودجه و هر B نیاز به 3 واحد بودجه دارد. همچنین هر محصول A یک واحد فضا و هر B دو واحد فضا میگیرد. قیود به صورت زیر نوشته میشوند:
$x + 2y \le 30$ (محدودیت فضای انبار)
$x \ge 0, y \ge 0$ (قیود عدممنفی)
حل این مسئله با روش ترسیمی یا جبری نشان میدهد که پاسخ بهینه در نقطه برخورد دو قید فعال (بودجه و فضا) رخ میدهد. این پاسخ یعنی $x=30$ و $y=0$ نیست، بلکه جواب تقاطع خطوط است. بدین ترتیب میبینیم که قیود نه تنها پاسخ را محدود میکنند، بلکه شکل پاسخ نهایی را تعیین مینمایند.
چالشهای مفهومی در درک قیود
۱. آیا همیشه قیود به صورت نامساوی نوشته میشوند؟
خیر. در بسیاری از مسائل علمی مانند معادلات شیمیایی یا تعادل بازار، قیود به صورت تساوی دقیق ظاهر میشوند. مثلاً در یک واکنش شیمیایی، مجموع جرم مواد واکنشدهنده باید دقیقاً برابر جرم فرآوردهها باشد که یک قید برابری است.
۲. اگر مسئله بدون قید حل شود، چه خطایی رخ میدهد؟
پاسخ بهینه ممکن به سمت بینهایت میل کند (مسئله کراندار نباشد) یا مقداری به دست آید که در عمل امکانپذیر نیست. برای نمونه، یک کشاورز بدون قید آب و زمین ممکن است تصمیم به کشت بیرویه بگیرد که غیرعملی است.
۳. قید فعال (Active) به چه معناست و چرا مهم است؟
قید فعال قیدی است که در پاسخ بهینه، به صورت تساوی برقرار است (یعنی با حداکثر مقدار خود برابر شده). تشخیص قیود فعال به سادهسازی مسئله کمک میکند. در مثال بودجه، اگر بودجه تمام شود، آن قید فعال است. در غیر این صورت، قید غیرفعال (غیر مؤثر) نامیده میشود.
نحوه اعمال قیود: روشهای پایه
برای حل مسائل بهینهسازی با قید، دو روش اصلی در سطح دبیرستان رایج است:
روش جایگزینی (برای قید برابری): اگر یک قید برابری داشته باشیم، یک متغیر را بر حسب متغیر دیگر نوشته و در تابع هدف جایگذاری میکنیم. سپس مسئله بدون قید میشود.
روش ترسیمی و بررسی گوشهها (برای قید نامساوی): در مسائل با دو متغیر، ناحیه شدنی (منطقهای که همه قیود را ارضا میکند) رسم شده و مقدار تابع هدف در رأسهای این ناحیه محاسبه میشود. پاسخ بهینه همواره در یکی از رأسها قرار دارد.
$\max \quad f(x_1, x_2, ..., x_n)$
$\text{subject to} \quad g_i(x_1, ..., x_n) \le 0, \quad i=1..m$
$\quad \quad \quad \quad h_j(x_1, ..., x_n) = 0, \quad j=1..p$
جمعبندی
پاورقی
1 بهینهسازی (Optimization): فرآیند یافتن بهترین پاسخ (بیشینه یا کمینه) برای یک تابع تحت شرایط معین.
2 قید (Constraint): شرط یا محدودیتی که متغیرهای مسئله باید آن را برآورده سازند.
3 قید فعال (Active Constraint): قیدی که در نقطه بهینه با مقدار حدی خود (تساوی) برقرار است.
4 ناحیه شدنی (Feasible Region): مجموعه تمام نقاطی که همه قیود مسئله را همزمان ارضا میکنند.
