
مسئلهٔ برش قطعات: کمترین ضایعات، بیشترین هوش!
هدفهای این ایستگاه#
- الگوهای برش یک رول را طراحی کنی و ضایعات هر الگو را حساب کنی.
- با یک جدول، تعداد استفاده از هر الگو را برای تأمین همهٔ سفارشها پیدا کنی.
- روش حریصانه را با بهترین جواب و کران پایین مقایسه کنی.
- گزارش کتبی تایپشده بنویسی و در ارائهٔ ۴ تا ۶ دقیقهای از برنامهٔ برشت دفاع کنی.
مأموریت تو: طراح الگوهای بهینه شو
- هدف
- گزارش کتبی تایپشده بنویسی و در ارائهٔ ۴ تا ۶ دقیقهای از برنامهٔ برشت دفاع کنی.
- نمای کلی
- برای رولهای مقوای ۱۰۰ سانتی و سفارش ۱۲ نوار ۴۰، ۱۰ نوار ۳۵ و ۱۵ نوار ۲۵ سانتی (یا یکی از سناریوهای جایگزین)، الگوهای برش بساز، برنامهای با کمترین رول و ضایعات پیدا کن، درصد ضایعات را حساب کن و همه را در گزارش کتبی تایپشده و ارائهٔ ۴ تا ۶ دقیقهای توضیح بده.
بخش ۱: ماجرا: نجار، خیاط و خمیر شیرینی#
یک نجار چطور از تختهٔ بلند دهها قطعه میبرد و آخرش فقط کمی خاکاره میماند؟ خیاط چطور الگوها را روی پارچه میچیند که یک سانت هم هدر نرود؟ پشت این کار مسئلهای کلاسیک به نام «مسئلهٔ برش قطعات» (Cutting Stock Problem) است: در شیشهبری، چاپخانه، کارخانهٔ کاغذ، و حتی آشپزخانهای که میخواهد از یک ورق خمیر بیشترین شیرینی را قالب بزند. (هشدار: شیرینیهای قالبزده را پیش از شمردن نخور!)
بخش ۲: مادهٔ خام#
منبع استاندارد با اندازهٔ ثابت: رول کاغذ ۱۰۰ سانتی، ورق مقوا ۷۰ × ۵۰، یا تختهٔ ۲ متری.
بخش ۳: سفارشها#
قطعههای کوچک با اندازه و تعداد مشخص؛ مث ۲۰ قطعهٔ ۳۰ سانتی و ۱۵ قطعهٔ ۴۵ سانتی.
بخش ۴: هدف#
کمترین ضایعات، یا کمترین تعداد رول مصرفی. این دو معمواً لبه هم وابستهاند.
بخش ۵: جعبهابزار : ۲ الگوی برش#
«الگوی برش» نقشهٔ چیدمان قطعهها روی یک واحد مادهٔ خام است. روی تختهٔ ۲۰۰ سانتی با قطعههای ۳۰، ۴۵ و : ۵۰ الگوی A چهار قطعهٔ ۵۰ است (ضایعات ۰)؛ الگوی B دو ۴۵ و دو ۳۰ (۱۵۰ = ۶۰ + ۹۰، ضایعات ۵۰)؛ الگوی C سه ۴۵ و یک ۳۰ (۱۶۵ = ۳۰ + ۱۳۵، ضایعات ۳۵).

بخش ۶: همهٔ الگوهای خوب#
رول ۱۰۰ سانتی و نوارهای ۴۰، ۳۵ و ۲۵. الگویی «بیشینه» است که دیگر هیچ نواری در باقیماندهاش جا نشود (باقیمانده کمتر از ۲۵). همهٔ این الگوها: چهار ۲۵ (ضایعات ۰)؛ ۴۰ + ۳۵ + ۲۵ (ضایعات ۰)؛ دو ۳۵ + ۲۵ (ضایعات ۵)؛ ۴۰ + دو ۲۵ (ضایعات ۱۰)؛ ۳۵ + دو ۲۵ (ضایعات ۱۵)؛ دو ۴۰ (ضایعات ۲۰). همان مثال کتاب: «۲ نوار ۴۰ = ۸۰ سانت، ضایعات ۲۰».
بخش ۷: جعبهابزار : ۳ روش حریصانه#
- قطعهها را از بزرگ به کوچک مرتب کن.
- یک رول بردار.
- هر قطعه را در اولین رولی بگذار که جا دارد؛ اگر هیچ رولی جا نداشت، رول تازه باز کن.
- تا تمام شدن سفارشها ادامه بده. (نام این روش «اولین جا، بزرگترها اول» یا FFD است.)

بخش ۸: حریصانه در برابر بهینه#
مجموع سفارش: ۱۲۰۵ = ۳۷۵ + ۳۵۰ + ۴۸۰ = ۲۵ × ۱۵ + ۳۵ × ۱۰ + ۴۰ × ۱۲ سانت؛ پس دستکم ÷ ۱۲۰۵⌈ ۱۳ = ⌉۱۰۰ رول لازم است. روش حریصانه ۱۴ رول مصرف میکند (ضایعات ۱۹۵ سانت). اما برنامهٔ هوشمند با ۱۳ رول کار را تمام میکند: ۱۰ بار الگوی (۴۰ + ۳۵ + ۲۵)، ۲ بار (چهار ۲۵) و ۱ بار (دو ۴۰). چون ۱۳ همان کران پایین است، مطمئنیم بهتر از این ممکن نیست! (۳ نوار ۲۵ اضافه هم برای سفارش بعدی میماند.)



بخش ۹: دام حریصانه#
قطعههای ۴۵، ۴۰، ۳۵، ۲۰، ۲۰، ۲۰ و ۲۰ سانتی (مجموع ۲۰۰) روی رول ۱۰۰. حریصانه: رول اول ۴۵ + ۴۰ (باقی ۱۵، هیچ چیز جا نمیشود)، رول دوم ۳۵ + ۲۰ + ۲۰ + ۲۰، رول سوم ۲۰؛ یعنی ۳ رول. اما (۴۵ + ۳۵ + ۲۰) و (۴۰ + ۲۰ + ۲۰ + ۲۰) هر دو دقیقً۱۰۰ اند؛ پس ۲ رول کافی است. ساده بودن روش حریصانه خوب است، ولی تضمینی برای بهترین جواب نیست.
بخش ۱۰: چرا این مسئله سخت است؟#
ریاضیدانها ثابت کردهاند مسئلهٔ برش (و خواهرش «بستهبندی در جعبه») «NPسخت» است: برای سفارشهای بزرگ، هیچ روش سریعی شناخته نشده که همیشه بهترین جواب را تضمین کند. خبر خوب: روش «بزرگترها اول» هیچوقت از حدود ۱۱/۹ برابرِ بهترین جواب (بهعلاوهٔ یکی دو رول) بدتر نمیشود، و کارخانهها با «برنامهریزی خطی» و نرمافزار به جوابهای خیلی نزدیک به بهینه میرسند. حتی ۱٪ کمتر ضایعات در یک کارخانهٔ بزرگ، صرفهجویی چشمگیری است.



بخش ۱۱: سناریوهای جایگزین (رول ۱۰۰ سانتی)#
سناریو سفارش نکته کارگاه نجاری۲۰ × ۴۵، ۲۵ × ۳۰، ۱۵ × ۲۰ کران پایین ⌈۲۱۰۰ ÷ ۱۰۰⌉ = ۲۱ خیاطخانه۴۰ × ۳۵، ۴۰ × ۱۵الگوی ۳۵ + ۳۵ + ۱۵ + ۱۵ دقیقً۱۰۰ است چاپخانه۱۰ × ۶۰، ۱۸ × ۲۵، ۲۲ × ۶۰۱۰ + ۲۵ + ۱۰ = ۹۵؛ آیا بهتر هم هست؟ چالش آزاد طول رول و دستکم ۳ سفارش به انتخاب تو کران پایین و برنامهات را مقایسه کن
بخش ۱۲: مراحل انجام پروژه#
- مسئله را بنویس: طول رول و فهرست کامل سفارشها.
- دستکم ۴ الگوی برش بساز و ضایعات هر الگو را حساب کن.
- جدولی بساز: از هر الگو چند بار، و هر بار چند قطعه از هر نوع تأمین میشود.
- تعداد کل رول، ضایعات کل و درصد ضایعات را حساب کن: ۱۰۰ × )ضایعات ÷ کل مصرف(.
- جوابت را با کران پایین و با روش حریصانه مقایسه کن.
- گزارش کتبی تایپشده بنویس و ارائه را آماده کن.
بخش ۱۳: ساختار ارائهٔ ۴ تا ۶ دقیقهای#
مقدمه (حدود ۱ دقیقه): چالش را با یک تصویر از ضایعات واقعی معرفی کن. الگوها (حدود ۱ تا ۲ دقیقه): الگوهایت را با نوارهای رنگی نشان بده. برنامه (حدود ۲ دقیقه): از هر الگو چند بار و چرا؛ مقایسه با حریصانه و کران پایین. نتیجه (حدود ۱ دقیقه): درصد ضایعات و اهمیت بهینهسازی در صنعت. تمرین سریع: از یک کاغذ A۴ بیشترین کارت ۸ × ۵ سانتی را ببر و ضایعات را بسنج. الگوها، جدول و محاسبهها را در گزارش کتبی تایپشده بیاور. گزارش را به تسهیلگر سرپرست بده و ارائه را با نوارهای کاغذی یا اسلاید اجرا کن.
خودآزمایی#
گزینهٔ درست را انتخاب کن و «بررسی پاسخها» را بزن.
نمایش پاسخنامه
۱. ۱۵؛ ۲. ۹؛ ۳. ساده و معمواً لخوب است، اما تضمینی برای بهترین جواب ندارد
پرسشهای مرور و کاربرد#
- الگوی بیشینه یعنی چه و چرا فقط سراغ الگوهای بیشینه میرویم؟
- کران پایین چطور به تو میگوید جوابت بهینه است؟
- یک مثال بزن که روش حریصانه در آن بهترین جواب را نمیدهد.
- برش دوبعدی (شیشه، پارچه) چه سختی تازهای دارد؟
مهر گذرنامه: پیش از رفتن به ایستگاه بعد#
پیش از رفتن به ایستگاه بعدی، این موارد را علامت بزن:
آفرین! یک مهر دیگر در گذرنامهٔ ریاضیات خورد.