برنامهریزی خطی؛ ناحیه شدنی و مقدار بهینه
آموزش رسم محدودیتها، تشخیص نیمصفحه، یافتن رأسهای ناحیه شدنی و بهینهسازی تابع هدف.
پاسخ کوتاه
در برنامهریزی خطی، محدودیتهای نامعادلهای یک ناحیه چندضلعی میسازند و تابع هدف روی آن کمینه یا بیشینه میشود. اگر جواب بهینه متناهی وجود داشته باشد، دستکم در یکی از رأسهای ناحیه شدنی رخ میدهد.
رسم مرزها
هر نامعادله را ابتدا به معادله خط مرزی تبدیل کن. خط پیوسته برای ≤ یا ≥ و در مسائل صرفاً هندسی خطچین برای < یا > به کار میرود. سپس با یک نقطه آزمایشی نیمصفحه درست را تعیین کن.
ناحیه شدنی
ناحیه شدنی اشتراک همه نیمصفحهها و شرطهایی مانند x≥0 و y≥0 است. نقطهای که فقط یکی از محدودیتها را نقض کند مجاز نیست. پیش از بهینهسازی مطمئن شو ناحیه خالی یا نامحدود نیست.
یافتن رأسها
رأسها از تقاطع جفت خطهای مرزی و برخورد با محورها ساخته میشوند. هر نقطه تقاطع را در همه محدودیتها آزمایش کن؛ تقاطع دو مرز ممکن است بیرون ناحیه شدنی قرار داشته باشد و رأس معتبر نباشد.
تابع هدف
تابع هدف Z=ax+by را در همه رأسهای معتبر حساب کن و مقادیر را مقایسه کن. اگر خط تراز تابع هدف با یک ضلع بهینه موازی باشد، همه نقاط آن ضلع میتوانند مقدار بهینه یکسان داشته باشند.
مثال و تست کوتاه
برای x≥0، y≥0 و x+y≤6، رأسها (0,0)، (6,0) و (0,6) هستند. تابع Z=2x+y در این رأسها صفر، 12 و 6 میشود؛ پس بیشینه 12 در نقطه (6,0) رخ میدهد.
چکلیست حل تست
- ناحیه شدنی اشتراک همه محدودیتهاست.
- هر تقاطع را در تمام نامعادلهها کنترل کن.
- تابع هدف را روی رأسهای معتبر محاسبه کن.