سوال ۱۳۷ کنکور ارشد مدیریت ۱۴۰۵

پاسخ: گزینهٔ ۱.

این یک مسئلهٔ برش انبار (cutting-stock problem) است و جمله‌ای که باید مدل شود — «نسبت ضایعات به طول کل شیشه‌های برش داده‌شده حداکثر ۱۰ درصد باشد» — یک محدودیت نسبتی (ratio constraint) است. نسبت، خطی نیست؛ پس پیش از آنکه بتواند در یک مدل برنامه‌ریزی خطی (LP) ظاهر شود باید طرفین‌وسطین شود. تمام صورت سؤال روی همین یک حرکت بنا شده است.

گام ۱ — الگوهای برش و ضایعات هر کدام

طول شیشهٔ خام $150$ سانتی‌متر است و طول‌های سفارش‌داده‌شده $40$، $50$ و $80$ سانتی‌متر هستند. باقیمانده تنها زمانی ضایعات محسوب می‌شود که کوتاه‌تر از ۴۰ سانتی‌متر باشد — پس هر الگویی که $\ge 40$ سانتی‌متر باقی بگذارد مغلوب است، چون هنوز یک قطعهٔ ۴۰ سانتی‌متری دیگر در آن جا می‌شود. بنابراین دقیقاً شش روش کارا باقی می‌ماند:

پس بردار ضایعات $w = (20,\,30,\,10,\,20,\,30,\,0)$ است — شش عدد، یعنی شش متغیر، و همین نکته از همان ابتدا می‌گوید پاسخ باید گزینهٔ ۱ یا ۲ باشد.

گام ۲ — خطی‌سازی نسبت

کل ضایعات برابر $\sum_j w_j x_j$ است؛ طول کل شیشهٔ برش داده‌شده به ازای هر برگ $150$ سانتی‌متر، یعنی در مجموع $150\sum_j x_j$ است. سیاست مسئله می‌گوید

$\frac{\sum_{j} w_j x_j}{150 \sum_{j} x_j} \le 0.10$

مخرج اکیداً مثبت است، پس طرفین را در آن ضرب و جمله‌ها را مرتب می‌کنیم:

$\sum_{j} w_j x_j \le 0.10 \times 150 \sum_{j} x_j = 15 \sum_{j} x_j \;\Rightarrow\; \sum_{j} (w_j - 15)\, x_j \le 0$

گام ۳ — جای‌گذاری شش عدد ضایعات

$(20-15)x_1 + (30-15)x_2 + (10-15)x_3 + (20-15)x_4 + (30-15)x_5 + (0-15)x_6 \le 0$

$5x_1 + 15x_2 - 5x_3 + 5x_4 + 15x_5 - 15x_6 \le 0$

که دقیقاً همان گزینهٔ ۱ است.

اگر علامت‌ها را بخوانید، معنای محدودیت روشن می‌شود: $15$ سانتی‌متر همان سهمیهٔ مجاز ضایعات هر برگ است ($10\%$ از $150$). روش‌های ۱، ۲، ۴ و ۵ بیش از این سهمیه ضایعات دارند و ضریب مثبت می‌گیرند (بودجه مصرف می‌کنند)؛ روش‌های ۳ و ۶ کمتر از سهمیه ضایعات دارند و ضریب منفی می‌گیرند (بودجه تولید می‌کنند). محدودیت می‌گوید هزینهٔ الگوهای پرضایعات باید با الگوهای کم‌ضایعات جبران شود.

کالبدشکافی گزینه‌های انحرافی

تلهٔ رایج: محدودیتی به شکل «نسبت A به B حداکثر $\alpha$» را همیشه باید به‌صورت $A - \alpha B \le 0$ نوشت، در حالی که مخرج به‌صورت یک عبارت متغیر حفظ می‌شود — نه به‌صورت یک عدد ثابت در سمت راست. وجود عدد ثابتی مانند $1.5$ یا $15$ در سمت راست، اثر انگشت آشکار همین خطاست (گزینه‌های ۳ و ۴). تلهٔ دوم: خواندن «طول کل شیشه‌های برش داده‌شده» به معنای طول کل قطعات قابل استفاده ($150\sum x_j - \sum w_j x_j$) به‌جای طول شیشهٔ خام مصرف‌شده؛ این خوانش به $\sum w_j x_j \le \tfrac{1}{11}\!\left(150\sum x_j\right)$ می‌رسد که با هیچ گزینه‌ای جور درنمی‌آید و همین تأیید می‌کند مخرج موردنظر طراح، طول شیشهٔ خام است.