دانلود مقاله یک الگو با مدل «متوسط ـ P» جهت کمینه‌ کردن اتلاف ترکیب

اختصاصی از فی بوو دانلود مقاله یک الگو با مدل «متوسط ـ P» جهت کمینه‌ کردن اتلاف ترکیب دانلود با لینک مستقیم و پر سرعت .

یک الگو با مدل «متوسط ـ P» جهت کمینه‌ کردن اتلاف ترکیب و برش با کاربردی در صنعت شیشه

چکیده:
یکی از مسائل عمده در صنعت شیشه کمینه کردن اتلاف برش ایجاد شده هنگام بریدن قطعات بزرگ به تکه‌های کوچک می‌باشد. در بحث و کاربردها قطعات در کارگاه تولید می‌شوند. بسیاری از اندازه‌های متفاوت قطعات قابل کاربرد هستند و قید و بندهای فنی تعدد الگوهای برش را به تولید تنها یک نوع تکه در قطعه محدود می‌سازد.
بنابراین در یفاتن زیر مجموعة بهینه‌ای از الگوهای برش متمرکز نمی‌شویم بلکه در انتخاب زیرمجموعة بهینه‌ای شامل تعداد محدودی از اندازه‌ها برای قطعات بریده شده تلاش می‌کنیم.
در این مقاله در مورد فرموله کردن برنامة خطی ۰-۱ جهت حل این مسئله براساس الگوی «متوسط P» بحث می‌کنیم. اطلاعات به دست آمده از آزمون این برنامه در عمل، کاهش قابل ملاحظه‌ای را در اتلاف ناشی از برش در عملیات کارگاه موردنظر نشان می‌دهد. و به طور واضح در روش‌های دقیق مرسوم، از ملاحظات محاسبة زمان به نتایج بهتری می‌رسد.
لغات کلیدی: کمینه کردن اتلاف برش، مسئله ترکیب، مسئله «متوسط ـ P»، برنامه‌ریزی اعداد صحیح (interger program)
۱. معرفی
یکی از مسائل عمده بسیاری از تولیدکنندگان کمینه کردن اتلاف برش ناشی از بریدن قطعات بزرگ به تکه‌های کوچک می‌باشد. این مسئله به طور عمومی به عنوان «برش قطعات» شناخته می‌شود [۵] و به نحو گسترده‌ای و به روش‌های مختلف، مطابق با دیدگاه فنی فرایند تولید، محدودیتها و اهداف آن، مورد مطالعه قرار گرفته است. یک بخش مهم و مشکل مسئله هنگامی است که سازماندهی (نصب) نیز شامل می‌شود.
هدف این مقاله معرفی روشی جدید برای حل کردن دسته‌ای از مسائل برش قطعات به همراه سازماندهی می‌باشد. این روش بر پایة فرموله‌سازی مسئله با توجه به الگوی «متوسط P» بهترین راه حل را در یک نسبت ثابت و پر بازده‌تر از روشهای دقیق کلاسیک استفاده شده برای مسائل مشابه، تقریب می‌کند.
در این مقاله، این روش را دربارة مشکلی که از همین نوع و در یکی از مشهورترین کارخانه‌های شیشة جهان وجود دارد، امتحان می‌کنیم. یک فاز کلیدی فرایند تولید شیشه، که یک قسمت مرتبط با کل اتلاف برش ایجاد شده می‌باشد، از برش قطعات مستطیلی بزرگ به تکه‌های کوچک به سایزهای مختلف تشکیل شده است. در بسیاری از صنایع، کمینه کردن اتلاف برش ناشی از چندین فازی، یک مسئله دوبعدی برش قطعات است که یافتن بهترین چینش تکه‌های مورد نیاز در قطعات اندازه‌ای مشخص، مطلوب است.
یک ترکیب تکه‌ها در یک قطعة ساده الگوی برشی را که چندین بار قابل تکثیر است، معرفی می‌کند و عموماً شامل تکه‌هائی از سایزهای مختلف می‌شود.
در کاربرد ما:
(۱) قطعات در کارگاه تولید می‌شوند و تعداد زیادی از اندازه‌های متفاوت قطعات قابل کاربرد هستند.
(۲) معیارها و محدودیت‌های سازماندهی و تکنولوژیکی تعدد الگوهای برش را به تولید نوع ساده‌ای از تکه‌ها در قطعات محدود می‌کند.
با توجه به (۱) و (۲) فوق، توجه اصلی به انتخاب اندازه‌های قطعات می‌شود نه الگوهای برش. از آنجا که اندازه‌های قطعات متغیرهای تصمیم‌گیری هستند و نه داده‌های مسئله، می‌توان در کل اندازة ایده‌آل قطعات بدون اتلاف برش را که به عنوان اجتماع اندازه‌های تکه‌ها به دست می‌آیند را انتخاب نمود. اگرچه، با توجه به هزینه‌های نصب و طیف (تولورانس) برش، امکان تولید همة اندازه های قطعات ایده‌آل مورد نیاز برای پوشش دادن تکه‌های مورد نیاز در طول دورة برنامه ریزی موجود نیست. بنابراین یک راه برای رسیدن به اتلاف برش صفر، در عمل، قابل دستیابی نیست. علاوه بر این، این مثال ساده نشان می‌دهد که ممکن است قطعة ایده‌آل و استانداردی برای کمینه شدن اتلاف برش یافت نشود.
مثال ۱: فرض کنید ما باید d1=4.8 تکة 145×57 و d2=4.8 تکه 135×60 (سانتی‌متری) تولید کنیم. و هزینه‌های نصب ما را مجبور به استفاده از تنها یک سایز قطعه می‌نماید. همچنین تصور کنید، با توجه به طیف شکاف دهنده‌ها و تولورانس تنها دو سایز قطعه استاندارد و ایده‌آل قابل کاربرد است: 580×285 برای مورد ۱ و 540×300 برای مورد ۲ (هر قطعه از ۲۰ تکه حاصل شده است). یافتن اندازة نهائی قطعه باعث ایجاد (10216) 10071 مترمربع اتلاف برش خواهد شد. در حالی که یک قطعة 580×300؛ که برای هیچ کدام از دو نوع تکه ایده‌ال نیست. تنها 497 مترمربع اتلاف ایجاد خواهد نمود. بحث فوق در مورد تمایل برای «مسئله ترکیب» (Assorment Problem) ویژه، که می‌خواهیم مجموعة محدودی از «اندازه‌های قطعات» که به ما اجازه تولید کارگاه و جزئیات فرایند را توصیف می‌کنیم که به این مسئله مربوط هستند.(۱۰۱) و در مورد مسائل مشابهی که در این حوزه با آن مواجه می‌شویم بحث می‌کنیم. (۱۰۲) ادامة مقاله به ترتیب ذیل سازماندهی شده است.
در بخش ۲ یک تعریف رسمی سهل‌الوصول و آسان به شکل برنامه خطی صحیح (integer linear programming) در بخش ۲-۱ توصیف می‌شود یک فرض ساده‌کننده در بخش ۲-۲ پیشنهاد می‌شود و نتایج آن تحلیل می‌شوند. براساس این فرض در بخش ۲-۳ یک مدل «متوسط ـ P» (p-mediam) برای کمینه کردن اتلاف برش و ترکیب معرفی و بررسی می‌کنیم و آن را به فرموله‌سازی برنامة‌ خطی ۰-۱ با محدودیتهای جانبی که ویژگیهای فرایند واقعی است متصل می‌نمائیم. بخشی راجع به پیچیدگی روشهای توصیف شده و مسائل بهینه سازی مربوطه در بخش ۲-۴ خواهیم داشت.
در بخش ۳ از اطلاعات این زمینه، روشها و راه‌کارها آزمون خواهد شد. نتایج محاسباتی کاربری و بازدهی مدل (p-mediam) متوسط ـ P را نشان می‌دهند که در هر دو بخش روشهای حال حاضر کارگراهی (با کاهش قابل توجه اتلاف برش) و روشهای دقیق جاری (با راه‌حلهای مشابه به دست آمده در زمانی فوق‌العاده کوتاه‌تر)، به نتایج بهتری می‌رسد.
۱-۱. ویژگی‌ها و امتیازات فرایند پایه‌ای
فرایند تولید متشکل از سه فاز عمده می‌باشد: (شکل ۱ را ببینید)
۱. شناوری: شیشه در کوره ذوب می‌شود. نواری از شیشه صاف کوره را ترک می‌کند و روی یک تسمه جریان می‌یابد. صفحات مستطیلی (قطعات) دارای اندازه‌های پهنا [610 و 450] و ارتفاع [321 و 280] (داده‌ها به سانتی‌متر هستند) می‌باشند که به وسیله تغییر پهنای نوارها و برشگرهای عمودی حاصل می‌شوند.
یک هزینه (ثابت) هنگام اتلاف شیشه طی نصب، به ازای هر تغییر در پهنا وجود خواهد داشت در حالی که تغییرات ارتفاع هزینة نصب ایجاد نخواهد کرد.
در انتهای مرحله قطعات بسته‌بندی می‌شوند و به انبار فرستاده می‌شوند.
۲. برش آف لاین (offline cotting): قطعات از انبار آورده شده به قسمتهای مستطیلی کوچکتری (مطابق با نیازها) بریده می‌شوند (تکه‌ها). پنج ماشین برش که هر کدام با یک سیستم محافظه خارجی تجهیز شده‌اند. با پیشرفت تولید، محافظ با تکه‌هائی از یک اندازه پر می‌شود تا هنگامی که بسته‌بندی کامل شود و به دنبال آن، محافظ (بافر) تخلیه می‌شود.
از آنجا که تکه‌های در حال انتقال امکان گردش ندارند، همه تکه‌های الگوی برش به روش یکسانی جا می‌افتند.
۳. شکل دهی: یک یا چند قسمت معین از هر تکه مستطیلی بعد از قالب‌گیری و خم‌کاری به دست می‌آید. چهار نوع شیشه رنگی تولید می‌شود. از آنجا که تغییر رنگ گران‌ترین است (می‌تواند سه روز ببرد) طرح تولید اصلی به طور چرخه‌ای در فرایندهائی از ۱۰ روز تا ۲ ماه، سازماندهی شده است و در هر فرایند از همان رنگ تولید می‌شود. بنابراین برنامه‌ریزی افق تولید مرحلة شناوری (float) با همة چرخة تولید مطابقت دارد. به عبارتی با دورة بین دو فرآیند از تولید یک رنگ واحد. همانگونه که قبل از این ملاحظه شد تکه‌های نهائی مستقیماً در مرحلة شناوری تولید نمی‌شوند بلکه قطعات تولید می‌شوند که اجزای میانی جهت برش مجدد در مراحل بعدی هستند. این روش جهت ساماندهی سفارشهای خارج از طرح و برنامه به کار گرفته می‌شود. در حقیقت سفارشات مشتریان در مراحل پیشرفته تنها در یک ماه کاملا شناخته می‌شود. در حالی که طول افق طرح‌ریزی براساس برآورد ملزومات محاسبه می‌شود.
اگرچه امکان ترکیب اندازه‌های مختلف قطعات به توسعة به کارگیری مواد کمک خواهد کرد[۷]. ترکیب اندازه‌های قطعات در انبار باید در مقدار معینی، به منظور برآمدن نیازهای تحویل قطعه و کاهش هزینه‌های نصب، برای ماشینهای برش، حفظ شود.
منابع اتلاف از چهار نوع هستند:
● نقص و عیب شیشه (به مقدار ۸-۹ درصد تولید کل)
● اتلاف برش به ازای تغییرات پهنا و برش آف‌لاین (offline) (۴-۵٪)
● شکستگیهای هنگام تحویل (تقریباً ۳٪)
● شکستگیهای هنگام برش آف‌لاین (offline cutting) (کمتر از ۱ درصد)
در این مقاله ما روی اتلاف برش به ازای تغییرات پهنا و برش آف‌لاین متمرکز می‌شویم.
این اتلاف ۳۰٪ اتلاف کل را شامل می‌شود و می‌تواند با برنامه‌ریزی اندکی در حد قابل ملاحظه‌ای کاهش یابد. در بحث ما، اتلاف برش با تفاوت بین سطح کل ماده استفاده شده و سطح کل ماده به دست آمده و مطلوب محاسبه می‌شود. بر این اساس «بیش تولیدی» (over production) به عنوان افت محاسبه می‌شود. در حقیقت، اگر نوعی «تکه» (item) بیش تولید شود، بیش تولیدی شامل برش تنها یک قطعه خواهد شد، و هزینة سازماندهی این تکه‌ها از ارزش خود تکه‌ها بیشتر خواهد شد.
۱-۲. مسائل مرتبط
Al-khayal et al [۱] (مرجع شماره ۱) آل ـ خیال محیط صنعتی مشابهی را توصیف می‌کند اما مسئله متفاوتی را بررسی می‌کند. در این حالت تکه‌های (item) مورد نیاز، در واقع، مستقیماً از نوار شیشه‌ای بریده می‌شوند و با استفاده از «خطوط محرک» (spurlines) تخلیه می‌شوند. برخلاف بحث ما، اندازه‌های متفاوت «تکه» با یک الگوی برش یکسان می‌تواند تولید شود. علاوه بر این، از آنجائی که نصب‌های واقع شده در خطوط محرک (spurlines) به اندازة تکه‌ها وابسته است الزاماً تکه‌ها باید آسان و به سهولت لیست‌بندی شوند. بنابراین یک مسئله دو بعدی برش قطعه به همراه مسئله لیست‌بندی خواهیم داشت.
در متون موجود، مسئله برش قطعه که در آن الگوهای برش به منظور داشتن اجزاء میانی و قسمتهای نهائی به کار گرفته شوند، غالباً «چند مرحله‌ای» (multistage) نامیده می‌شوند. منابع [۶] و [۱۲] را ببینید. اگرچه فرایندی که در این مقاله مورد نظر است از بیش از یک مرحله تشکیل شده است، مسئله ما به طور مناسبی نمی‌تواند در چنین زمره‌ای قرار گیرد. در حقیقت هیچ الگوی برشی مولد اندازه‌های مختلف قطعه ها در مرحلة شناوری به کار نرفته است. اما پهناهای مختلف قطعه به سادگی با باریک و عریض کردن نوار شیشه‌ای به دست می‌آیند و اتلاف در این مرحله تنها در طی تغییرات پهنا رخ می‌دهد.
با توجه به برخی موارد، مسئله ما با یک قطعه برش با اندازه‌های متعدد قطعه مرتبط است.
در متون، دلایل متعددی برای این مسئله یافته می‌شود، آغاز آن با کارهای اساسی «گیلمور» (Gilmore) و «گوموری» (Gomory) [۷] و اخیراً با «اسچیلینگ» [Schilling] و «جورجیادیس» (Georgiadis) [۹] و «بلو» (Belov) و «اسچتاور» (Scheithouer)[۳] مسئله تقریباً همیشه با فرموله‌سازی کلاسیک گیلمور و گوموری مدل‌سازی می‌شود، که تعدد اندازه‌های قطعه با حل مسئله مشخص قیمت‌گذاری هر اندازه قطعه سازماندهی می‌شود. بلو و اسچتاور گزارش می‌دهند که صرفاً به حساب آوردن اندازه‌های متفاوت قطعه برخاسته از ترکیب غیرمنفی صحیح طول‌های تکه‌ها کافیست و بر این اساس برنامه‌ریزی الگوریتم پویا و فعال تولید الگوهای برش شاخص را آماده می‌کنند. در حقیقت چنین الگوریتمی می‌تواند به آسانی برای هدف ما تغییر یابد و متحول شود.
علاوه بر این، در مورد ما، فرض (۲) (ii) مسئله قیمت‌گذاری را کم اهمیت خواهد نمود.
اگرچه هنگامی که فرموله‌سازی گیلمور و گوموری برای محدود کردن بیشترین تعداد اندازه‌های استفاده شده سازگار شود، آسان‌سازی آن جهش‌ها ضعیفی خواهد داشت و روش، غیر عملی خواهد شد. (این عیب، همچنین هنگامی که کسی بخواهد تعداد الگوهای برش مختلف استفاده شده را کاهش دهد یا به حداقل برساند، رخ می‌دهد) ([۴] [۱۰] [۱۱] را ببینید)
مسئله انتخاب بهترین لیست اندازه‌های قطعه‌ها که ترکیب آنها را محدود کند و اتلاف برش را به کمترین برساند به عنوان «مسئله انتخاب ترکیب» یا «مسئله انتخاب اندازه ـ قطعه» (Assortment or stock-size selection pmb.) معروف است. یک برنامه‌ریزی فرموله‌سازی صحیح و خودآموز حل این مسئله در مرجع [۸] آورده شده است.
با توجه به فرض ۲ (ii) این مسئله تعمیمی از ماست که به هر حال NP-hard باقی می‌ماند. بخش ۲-۴ را ببینید. خصوصی‌سازی بیشتر مسئله، که بتوان تنها یک تکه را در هر قطعه برید در منبع [۲] ذکر شده است که الگوریتم برنامه پویای چند جمله‌ای ـ زمان پیشنهاد شده است.
۲. فرموله‌سازی مسئله و روشهای حل:
در این بخش در مورد مسئله ذیل بحث می‌کنیم:
مسئله ۲: چه اندازه‌های متفاوت قطعه در فرایند جهت برآوردن نیاز تکه‌ها با توجه به موارد زیر باید تولید شود؟
(i) میزان تغییرات پهنا را به مقدار معینی محدود سازد q
(ii) ترکیب اندازه‌های مختلف قطعه را به مقدار معینی محدود سازد p
(iii) مساحت قطعات استفاده شده را تا حد ممکن کاهش دهد.
چه هنگام یک اندازة تنهای تکه از هر اندازة قطعه می‌تواند بریده شود؟
با توجه به پارامترهای p و q نمونه‌ای از مسئله ۲ به صورت زیر تعریف شده است:
● J= مجموعة اندازه‌های مختلف قابل دسترس قطعات J=n
● I= مجموعة اندازه‌های مختلف تکه که در فرایند تولید می‌شود. I=m
● di= پیش نیاز i امین اندازة تکه I i
جائی که هر تکه یا قطعهI J j با اندازه‌اش همراه است، به صورت زوجی از اعداد صحیح (wj,hj) داده می‌شود.
۲-۱ فرموله‌سازی به عنوان برنامه‌ریزی خطی صحیح (integer)
برای I i و J j قرار می‌دهیم aij ماکزیمم عدد تکه‌های I امین اندازه که می‌تواند از قطعه با j امین اندازه بریده شود. پارامتر aij با یک الگوی برش «اشباع» (saturating) مطابقت دارد. بدون انحراف از کلیت موضوع، دقیقا چنین الگوئی با هر زوج (i,j) بنا می‌شود، قرار می‌دهیم xij، درجه و سطح فعالیت آن (Activation). همچنین قرار می‌دهیم: Cij=wjhj مساحت قطعه J j (البته در بین همة اندازه‌های قطعات که مقدار یکسانی از تکه‌های نوع i تولید می‌کنند، تنها آنکه کمترین سطح را داراست شامل خواهد شد)
فرموله‌سازی گیلمور ـ گوموری از مسئله جهت کمینه کردن اتلاف برش کلی (محاسبه شده طبق بخش ۱-۱) به صورت زیر است:
(۱) min c(x)=
(۲) برای I i،
(۳) برای J j، I i، (integer) صحیح و 0 Xij
یک راه حل برای برنامة صحیح فوق، الزاماً، شامل ماکزیمم مقدار مجاز «اندازه‌های مختلف قطعات» و «تغییرات پهنا» نخواهد شد. (عبارات (i) و (ii) از مسئله ۲) بنابراین ثابت‌ها و متغیرهای اضافی باید افزوده شود. قرار می‌دهیم:
● K= مجموعة پهناهای مختلف کاربردی قطعه‌ها
● J Jk= مجموعة همة اندازه‌های کاربردی قطعه‌های همراه با پهنای kام K) (k قرار می‌دهیم Ik, yi متغیرهای تصمیم‌گیری ۰-۱ تعریف شده برای J j، K k
به صورت ذیل:
}
{
یک راه‌حل کاربردی برای مسئله ۲ باید در محدودة ذیل باشد:
(۴) برای I i و J j، Xij
(۵)
(۶) برای J jو K k و Zk yj
(۷)
(۸) ۰
که ] Mij=[یک کران بالا برای سطح فعال الگوی (i,j) است.
۲-۲ یک فرض ساده کننده:
اگرچه مسئله (۱) – (۳)، حتی با یک اندازة تکه، مشکل است (بخش ۲-۴ را ببینید). برنامه‌های تجاری به طور معمول نمونه‌های عملی را در چند ثانیه حل می‌کنند.
اگرچه افزودن نصب‌ها، مکرراً، اینگونه مسائل را دشوار می‌‌سازد. در واقع، با توجه به محدودیت‌های فعالسازی (۴)، آسان‌سازی خطی مسئله (۱) ـ (۸)، عموماً، برای راه‌انداختن یک روش کارای branch-and-bound (شاخه و جهش) بسیار ضعیف است. برای مواجه با این معضل، اجازه دهید فرض ساده‌کنندة زیر را داشته باشیم.
فرض ۲-۱ هر اندازة تکة I i باید دقیقاً با یک قطعة اندازه J j تولید شود.
در حقیقت فرض ۲-۱ می‌تواند به راه‌حلهای بهتری منجر شود. (sub option) همانگونه که در مثال زیر نشان داده شده است.
مثال ۳ فرض کنید می‌خواهیم ۱۳ تکه ۱۰×۱۰ (سانتی‌متری) تولید کنیم، و قطعات A و B با اندازه‌های CA= 20×25 و CB= 20×35 موجودند. یک الگوی جامع که قطعة A (قطعة B) را شامل شود ۴ (۶) تکه حاصل می‌کند. در یک روش حل بهینه صرف‌نظر از فرض ۲-۱، می‌توان یک قطعة A و ۲ قطعة B را انتخاب نمود با مصرف کلاً ۱۰۹ سانتی‌متر مربع، در مادة خام. اگرچه یک راه‌حل بهینه با در نظر گرفتن فرض ۲-۱، ۴ قطعة A می‌دهد با مصرف کلی 2cm2 مادة خام. قرار می‌دهیم.
d=min i I{di} {Cj/aij} , C=maxj J{Cj}
موارد ذیل می‌تواند ثابت شود.
قضیه‌ها: قرار می‌دهیم X* پاسخ بهینة مسئله ۲. آنگاه یک پاسخ کاربردی X سازگار با فرض ۲-۱ وجود خواهد داشت و همچنین
(۹)
برهان: قرار می‌دهیم J:Xij*>0} J(i)={j مجموعه‌ قطعه‌های فعال شده با X* جهت تولید تکة I برای هر I i، ji اندازة قطعه به شکل:

برای همة J(i) j. یک پاسخ X که نیاز I i را پوشش دهد با تولید صرفاً di قسمت از قطعه ji به طور مشخص قابل دستیابی است، به عنوان اینکه «اندازه‌های مختلف قطعه» و «تغییرات پهنا» که فعال می‌سازد بیش از X* نباشد.
فرض کنید X* هر I i را با تولید di1 قسمت از قطعه ۱ پوشش دهد و di2 از قطعه ۲ و ... و din از قطعة n و di1+di2+di3+…=din هزینه‌های X,X* به روشنی ایجاب می‌کند که:
C(x)<
C(x*)
که ما نسبت‌ها را گرد (تقریب) نمی‌کنیم و، در نخستین جهش، بدترین حالت که در آن آخرین قطعه استفاده شده تا تنها یک تکه را ببرد، در نظر می‌گیریم. از این رو:

از آنجا که wihi Cj/aij برای هر I i و J j داریم

که I{wihi} C=mini. بنابراین در چنین موارد تولید ماده (جرم)، همانگونه که در مورد کارگاه‌ها در این مقاله ذکر شد، فرض ۲-۱ اثر عملیاتی بر کمینه شدن اتلاف برش ندارد (بخش ۳ را برای جزئیات بیشتر ببینید). اما از دیدگاه محاسباتی فریت آن کاملاً مرتب است.
فرض ۲-۱ در واقع برنامة صحیح (integer) (۳)-(۱) را به partition matroid تبدیل می‌کند، و به عبارتی ساده‌تر، فرموله‌سازی ترکیباتی خالص (و پر بازده‌تری) از مسئله ۲ ارائه می‌کند، همانگونه که در بخش بعد خواهیم دید.
۲-۳ یک الگوی «متوسط – p» "p-median"
قرار می‌دهیم:
Cij= مساحت قطعه استفاده شده هنگام تولید همة پیش نیازهای تکه i با قطعه j و J) I , j (i
همچنین قرار می‌دهیم yij متغیرهای تصمیم‌گیری ۰-۱ (تابع علامت یا همانی م) برای I i و J j با شرح ذیل
{
و قرار می‌دهیم Zk , yi همانگونه که در بخش ۲ تعریف شده‌اند. یک پاسخ تقریبی (در مورد قضیه‌ها) برای مسئله ۲ با تحلیل برنامة خطی ۰-۱ زیر به دست می‌آید:
(۱۰) min
(۱۱) I i
(۱۲) J j I i yi yij
(۱۳)
(۱۴) K k و Jk j Zk yi
(۱۵)
(۱۶) عدد صحیح و ۰
هدف فرمولهای ۱۶ تا ۱۰ کمینه کردن اتلاف کلی برش است.
محدودیتهای ۱۱ تا ۱۳ و عبارات (۱۶) ناحیه کاربردی یک مسئله «متوسط ـ p» (p-mediam) را توصیف می‌کند. در حالت خاص، محدودیتهای (۱۱) مطلوبیت را تضمین می‌کنند و محدودیتهای (۱۲) قطعة j را هنگام استفادة برخی تکه‌های (i) فعال می‌کنند. محدودیت (۱۳) ترکیب اندازه‌های قطعة تولید شده را محدود می‌کند. افزون شرط‌های (۱۴) (۱۵) اجازة کنترل تعداد تغییرات پهنا را می‌دهد. به ویژه شرط (۱۴) متغیرهای Zk را فعال می‌سازد و شرط (۱۵) تغییرات را به ماکزیمم مجاز q محدود می‌سازد. قضیه ۴ بیان می‌کند.
نتیجه ۵: برنامة (۱۶) – (۱۰) کاملاً دقیق است که پاسخ‌های بهینة آن به پاسخ بهینة مسئله ۲ میل می‌کند همانگونه که پیش نیازهای مینیمم تکه‌ها افزایش می‌یابد. فرمولهای (۱۶) – (۱۰) می‌تواند با افزودن نامعادلات مناسب توسعه یابد.
پیشنهاد ۶: آسان‌سازی خطی برنامه (۱۶)(۱۰) یک پاسخ (۱۷) نیز هست بنابراین ما به سادگی باید نشان دهیم آسان‌سازی خطی فرمولهای (۱۶)(۱۰) با نامعادلات زیر پیاده‌سازی می‌شود.
, i I , k K
برهان: به طور واضح، هر پاسخ صحیح (۱۶)-(۱۰) یک پاسخ (۱۷) نیز هست. بنابراین ما، به آسانی، باید نشان دهیم آسان‌سازی خطی فرمول (۱۶)-(۱۰) یک پاسخ منفصل و چند تکه می‌پذیرد که با برخی از موارد شرط (۱۷) از هم جدا می‌شوند. در واقع تصور کنید قطعه‌های (۱) و (۲) پهنای یکسانی دارند.
سپس:
Y11=y21=X12=X22=0.5 , y1=y2=0.5 , Z1=0.5
پاسخی است برای z1 y1 z1 , yi1 y2 (i=1,2) yi2
اما اذعان نمی‌کند z2 z1 , yz1+yz2 y11+y12
مشاهده کنید که اگرچه نامعادلات (۱۴) می‌تواند با نامعادلات (۱۷) در فرمولهای (۱۶)-(۱۰) جایگزین شوند.
آخری و نهائی در تأثیر عمومی قالب، در آسان‌سازی خطی مسئله، همانگونه که در مثال ذیل نشان داده شده، نیست.
مثال ۷: مجدداً تصور کنید قطعات ۱ و ۲ پهنای یکسانی دارند. آنگاه نکتة:
Y11+y12 z16 y21+y22 z2
اما تأئید نمی‌کند که z1 z1 , y1 y2
۲-۴ نکته‌ای درباره پیچیدگی (میزان دشواری)
پیچیدگی محاسباتی مسئله ۲ فوراً با مشاهده برنامه (۳)-(۱) معلوم می‌شود. که برای یک تکه منفرد از اندازه واحدی نوشته شده است، به ما اجازه می‌دهد تا اعداد صحیح و مثبت x1, …,xn را با جست و جو و چک‌کردن بیابیم.

فرمت این مقاله به صورت Word و با قابلیت ویرایش میباشد

تعداد صفحات این مقاله  23  صفحه

پس از پرداخت ، میتوانید مقاله را به صورت انلاین دانلود کنید