725 空氣濾清器連接板沖孔、沖槽、落料復(fù)合模設(shè)計(jì)【優(yōu)秀含12張CAD圖+文獻(xiàn)翻譯+說明書】,優(yōu)秀含12張CAD圖+文獻(xiàn)翻譯+說明書,725,空氣濾清器連接板沖孔、沖槽、落料復(fù)合模設(shè)計(jì)【優(yōu)秀含12張CAD圖+文獻(xiàn)翻譯+說明書】,空氣濾清器,連接,沖孔,復(fù)合,設(shè)計(jì),優(yōu)秀,優(yōu)良,12,十二,cad 開題報(bào)告 題　目 空氣濾清器連接板沖孔、沖槽、落料復(fù)合模設(shè)計(jì) 學(xué)生姓名 班級學(xué)號 專業(yè) 一、課題的目的和意義： 沖壓加工作為一個(gè)行業(yè)，在國民經(jīng)濟(jì)的加工行業(yè)中占有重要地位。根據(jù)統(tǒng)計(jì)，沖壓件在各個(gè)行業(yè)中均占有相當(dāng)大的比重，尤其在汽車、電機(jī)、儀表、軍工、家電等方面所占比重更大。采用沖壓模具生產(chǎn)零部件，具有生產(chǎn)效益高，質(zhì)量好，成本低，節(jié)約能源和原料等一系列優(yōu)點(diǎn)，它以成為當(dāng)代工業(yè)生產(chǎn)中的重要手段和工藝發(fā)展方向。 模具工業(yè)已被我國正式確定為基礎(chǔ)產(chǎn)業(yè)，并在“十五”中列為重點(diǎn)扶持產(chǎn)業(yè)。從1997年開始，我國模具工業(yè)產(chǎn)值超過了機(jī)床工業(yè)產(chǎn)值。因此模具對國民經(jīng)濟(jì)和社會(huì)發(fā)展起著舉足輕重的作用。 對于沖壓生產(chǎn)而言，單工位模具結(jié)構(gòu)單一，生產(chǎn)效率低，而且鈑金零件不能過于復(fù)雜，否則就需要多副單工位模具才能實(shí)現(xiàn)。如果采用級進(jìn)模進(jìn)行生產(chǎn)，就可以改變這些缺點(diǎn)。標(biāo)志沖模技術(shù)先進(jìn)水平的精密多工位級進(jìn)模，具有生產(chǎn)周期短、用操作人員少、精度高、壽命長和生產(chǎn)效率高等特點(diǎn)，是我國重點(diǎn)發(fā)展的精密沖模。 本次畢業(yè)設(shè)計(jì)，指導(dǎo)老師給我安排的是空氣濾清器連接板沖孔、沖槽、落料復(fù)合模設(shè)計(jì)。通過對零件進(jìn)行工藝分析，我們可以了解到零件材料為加工性能較好的45號鋼，零件的主要加工工序主要有：落料、沖孔、沖槽等。通過結(jié)合大學(xué)所學(xué)的專業(yè)知識，參考文獻(xiàn)資料，以及指導(dǎo)老師指導(dǎo)，我初步理清了本次設(shè)計(jì)的基本思路，掌握了有關(guān)畢業(yè)設(shè)計(jì)的基本方法。 二、文獻(xiàn)綜述 1、中國沖壓模具的發(fā)展現(xiàn)狀 中國沖壓模具的發(fā)展現(xiàn)狀改革開放帶了我國的經(jīng)濟(jì)進(jìn)入高速發(fā)展的時(shí)期，模具的市場的需求量也進(jìn)一步的增加。模具行業(yè)也一直以15%左右的增速再發(fā)展。因此帶來的模具工業(yè)企業(yè)的所有制成分的巨大變化，一些國有專業(yè)模具廠也如雨后春筍般的建立起來，同時(shí)也帶來了以集體、獨(dú)資、私營和合資等形式的快速發(fā)展。 賦有“模具之鄉(xiāng)”的浙江寧波和黃巖地區(qū)是現(xiàn)今我國規(guī)模最大的兩個(gè)地方；廣東地區(qū)也漸漸掀起了開建模具廠的浪潮；其中科龍、康佳等集團(tuán)紛紛建立了自己的模具制造中心；中外合資或是外商獨(dú)資形式的模具企業(yè)現(xiàn)也有幾千家。 近年許多模具企業(yè)加大了用于技術(shù)進(jìn)步的投資力度，將技術(shù)進(jìn)步視為企業(yè)發(fā)展的重要?jiǎng)恿ΑＲ恍﹪鴥?nèi)模具企業(yè)已普及了二維CAD，并陸續(xù)開始使用UG、Pro/Engineer、I-DEAS、Euclid-IS等國際通用軟件，個(gè)別廠家還引進(jìn)了Moldflow、C-Flow、DYNAFORM、Optris和MAGMASOFT等CAE軟件，并成功應(yīng)用于沖壓模的設(shè)計(jì)中。以汽車覆蓋件模具為代表的大型沖壓模具的制造技術(shù)已取得很大進(jìn)步，東風(fēng)汽車公司模具廠、一汽模具中心等模具廠家已能生產(chǎn)部分轎車覆蓋件模具。此外，許多研究機(jī)構(gòu)和大專院校開展模具技術(shù)的研究和開發(fā)。經(jīng)過多年的努力，在模具CAD/CAE/CAM技術(shù)方面取得了顯著進(jìn)步；在提高模具質(zhì)量和縮短模具設(shè)計(jì)制造周期等方面做出了貢獻(xiàn)。 例如，吉林大學(xué)汽車覆蓋件成型技術(shù)所獨(dú)立研制的汽車覆蓋件沖壓成型分析KMAS軟件，華中理工大學(xué)模具技術(shù)國家重點(diǎn)實(shí)驗(yàn)室開發(fā)的注塑模、汽車覆蓋件模具和級進(jìn)模CAD/CAE/CAM軟件，上海交通大學(xué)模具CAD國家工程研究中心開發(fā)的冷沖模和精沖研究中心開發(fā)的冷沖模和精沖模CAD軟件等在國內(nèi)模具行業(yè)擁有不少的用戶。 雖然中國模具工業(yè)在過去十多年中取得了令人矚目的發(fā)展，但許多方面與工業(yè)發(fā)達(dá)國家相比仍有較大的差距。例如，精密加工設(shè)備在模具加工設(shè)備中的比重比較低；CAD/CAE/CAM技術(shù)的普及率不高；許多先進(jìn)的模具技術(shù)應(yīng)用不夠廣泛等等，致使相當(dāng)一部分大型、精密、復(fù)雜和長壽命模具依賴進(jìn)口。 2、中國沖壓模具的發(fā)展方向 模具技術(shù)的發(fā)展應(yīng)該為適應(yīng)模具產(chǎn)品“交貨期短”、“精度高”、“質(zhì)量好”、“價(jià)格低”的要求服務(wù)。達(dá)到這一要求急需發(fā)展如下幾項(xiàng)： (1)全面推廣CAD/CAM/CAE技術(shù)模具CAD/CAM/CAE技術(shù)是模具設(shè)計(jì)制造的發(fā)展方向。隨著微機(jī)軟件的發(fā)展和進(jìn)步，普及CAD/CAM/CAE技術(shù)的條件已基本成熟，各企業(yè)將加大CAD/CAM技術(shù)培訓(xùn)和技術(shù)服務(wù)的力度；進(jìn)一步擴(kuò)大CAE技術(shù)的應(yīng)用范圍。計(jì)算機(jī)和網(wǎng)絡(luò)的發(fā)展正使CAD/CAM/CAE技術(shù)跨地區(qū)、跨企業(yè)、跨院所地在整個(gè)行業(yè)中推廣成為可能，實(shí)現(xiàn)技術(shù)資源的重新整合，使虛擬制造成為可能。 (2)高速銑削加工國外近年來發(fā)展的高速銑削加工，大幅度提高了加工效率，并可獲得極高的表面光潔度。另外，還可加工高硬度模塊，還具有溫升低、熱變形小等優(yōu)點(diǎn)。高速銑削加工技術(shù)的發(fā)展，對汽車、家電行業(yè)中大型型腔模具制造注入了新的活力。目前它已向更高的敏捷化、智能化、集成化方向發(fā)展。 (3)模具掃描及數(shù)字化系統(tǒng)高速掃描機(jī)和模具掃描系統(tǒng)提供了從模型或?qū)嵨飹呙璧郊庸こ銎谕哪Ｐ退璧闹T多功能，大大縮短了模具的在研制制造周期。有些快速掃描系統(tǒng)，可快速安裝在已有的數(shù)控銑床及加工中心上，實(shí)現(xiàn)快速數(shù)據(jù)采集、自動(dòng)生成各種不同數(shù)控系統(tǒng)的加工程序、不同格式的CAD數(shù)據(jù)，用于模具制造業(yè)的“逆向工程”。模具掃描系統(tǒng)已在汽車、摩托車、家電等行業(yè)得到成功應(yīng)用，相信在“十五”期間將發(fā)揮更大的作用。 (4)電火花銑削加工電火花銑削加工技術(shù)也稱為電火花創(chuàng)成加工技術(shù)，這是一種替代傳統(tǒng)的用成型電極加工型腔的新技術(shù)，它是有高速旋轉(zhuǎn)的簡單的管狀電極作三維或二維輪廓加工(像數(shù)控銑一樣)，因此不再需要制造復(fù)雜的成型電極，這顯然是電火花成形加工領(lǐng)域的重大發(fā)展。國外已有使用這種技術(shù)的機(jī)床在模具加工中應(yīng)用。預(yù)計(jì)這一技術(shù)將得到發(fā)展。 (5)提高模具標(biāo)準(zhǔn)化程度我國模具標(biāo)準(zhǔn)化程度正在不斷提高，估計(jì)目前我國模具標(biāo)準(zhǔn)件使用覆蓋率已達(dá)到30%左右。國外發(fā)達(dá)國家一般為80%左右。 (6)優(yōu)質(zhì)材料及先進(jìn)表面處理技術(shù)選用優(yōu)質(zhì)鋼材和應(yīng)用相應(yīng)的表面處理技術(shù)來提高模具的壽命就顯得十分必要。模具熱處理和表面處理是否能充分發(fā)揮模具鋼材料性能的關(guān)鍵環(huán)節(jié)。模具熱處理的發(fā)展方向是采用真空熱處理。模具表面處理除完善應(yīng)發(fā)展工藝先進(jìn)的氣相沉積(TiN、TiC等)、等離子噴涂等技術(shù)。 (7)模具研磨拋光將自動(dòng)化、智能化模具表面的質(zhì)量對模具使用壽命、制件外觀質(zhì)量等方面均有較大的影響，研究自動(dòng)化、智能化的研磨與拋光方法替代現(xiàn)有手工操作，以提高模具表面質(zhì)量是重要的發(fā)展趨勢。 (8)模具自動(dòng)加工系統(tǒng)的發(fā)展這是我國長遠(yuǎn)發(fā)展的目標(biāo)。模具自動(dòng)加工系統(tǒng)應(yīng)有多臺(tái)機(jī)床合理組合；配有隨行定位夾具或定位盤；有完整的機(jī)具、刀具數(shù)控庫；有完整的數(shù)控柔性同步系統(tǒng)；有質(zhì)量監(jiān)測控制系統(tǒng)。 我國沖壓模具與發(fā)達(dá)國家企業(yè)之間的差距不小，因此要發(fā)揮整體優(yōu)勢和綜合競爭力，要加強(qiáng)統(tǒng)籌協(xié)調(diào)、完善合作機(jī)制，創(chuàng)造性地工作。也需要加大對模具相關(guān)專業(yè)人才的綜合素質(zhì)培訓(xùn)投入。 2、設(shè)計(jì)內(nèi)容與步驟 （1）沖壓零件的工藝性分析：材料的沖壓性能分析、結(jié)構(gòu)形狀工藝性分析、尺寸的工藝性分析、精度的工藝性分析等。 （2）沖壓工藝的總體方案的分析和確定：單工序模方案、復(fù)合模方案、級進(jìn)模方案的對比，最終確定的方案； （3）基于所確定的總體方案，進(jìn)行排樣設(shè)計(jì)：擬定工位數(shù)、各工位的沖壓性質(zhì)和沖壓順序，繪制板料的排樣圖； （4）基于總體方案和排樣方案，進(jìn)行工藝計(jì)算，如：凸凹模尺寸及偏差、間隙、變形力、壓力中心、卸料力等計(jì)算； （5）模具關(guān)鍵結(jié)構(gòu)的方案設(shè)計(jì)：凸凹模結(jié)構(gòu)形式、導(dǎo)向、導(dǎo)料、定位、卸料等； （6）模具總體結(jié)構(gòu)設(shè)計(jì)與確定：基于上述內(nèi)容，設(shè)計(jì)并確定模具總體結(jié)構(gòu)，描述模具的工作原理和工藝動(dòng)作，并繪制二維裝配圖和相應(yīng)的三維圖； （7）選擇合理的沖壓設(shè)備（考慮設(shè)備噸位與變形力的吻合、沖裁封閉高度與設(shè)備裝模高度的吻合、模具的平面尺寸與設(shè)備工作臺(tái)面尺寸的吻合等）； （8）進(jìn)行模具零件的詳細(xì)設(shè)計(jì)：確定模具中的標(biāo)準(zhǔn)件（聯(lián)結(jié)零件：螺釘、銷釘、彈性元件等）的型號和數(shù)量，對模具中的非標(biāo)準(zhǔn)件進(jìn)行詳細(xì)的結(jié)構(gòu)尺寸設(shè)計(jì)，繪制相應(yīng)的二維零件圖； （9）編制模具中主要零件的制造工藝方案和加工方法； （10）撰寫設(shè)計(jì)說明書； （11）所有設(shè)計(jì)文檔、資料的整理、收尾、答辯。 3、繪圖任務(wù) （1） 模具總裝配圖 （2） 模具零件圖 （3） 模具總成三維圖（可選） （4） 模具主要零件三維圖（可選） 四、設(shè)計(jì)過程進(jìn)度計(jì)劃 （1）第五周：完成以上設(shè)計(jì)內(nèi)容中的“1-2” （2）第六周：完成以上設(shè)計(jì)內(nèi)容的“3-5” （3）第七八周：完成以上設(shè)計(jì)內(nèi)容的“6-7” （4）第九十周：完成以上設(shè)計(jì)內(nèi)容的“8” （5）第十一、十二周：完成以上設(shè)計(jì)內(nèi)容中的“9” （6）第十三、十四周：完成以上設(shè)計(jì)內(nèi)容中的“10” （6）第十五周：完成以上設(shè)計(jì)內(nèi)容中的“11” 指導(dǎo)教師批閱意見 指導(dǎo)教師(簽名)： 年 月 日 注：可另附A4紙 課題任務(wù)書 指導(dǎo)教師 學(xué)生姓名 課題名稱 空氣濾清器連接板沖孔、沖槽、落料復(fù)合模設(shè)計(jì) 內(nèi)容及任務(wù) 設(shè)計(jì)圖紙 模具總裝圖一張 全部模具零件圖紙（其中至少有一張電腦繪圖） 所有圖紙折合成0號圖不得少于3張。 設(shè)計(jì)說明書 1、資料數(shù)據(jù)充分，并標(biāo)明數(shù)據(jù)出處。 2、計(jì)算過程詳細(xì)、完全。 3、公式的字母含義應(yīng)標(biāo)明，有時(shí)還應(yīng)標(biāo)注公式的出處。 4、內(nèi)容條理清楚，按步驟書寫。 5、說明書要求用計(jì)算機(jī)打印。 6、設(shè)計(jì)說明書按要求格式獨(dú)立撰寫，不少于12000字。 自選一個(gè)重要模具零件編制加工工藝路線，進(jìn)行相關(guān)的計(jì)算，并編制加工工藝卡和工序卡。 翻譯一篇本專業(yè)外文文獻(xiàn)（10000個(gè)以上印刷符號），并附譯文。 擬達(dá)到的要求或技術(shù)指標(biāo) 1、保證規(guī)定的生產(chǎn)率和高質(zhì)量的沖壓件的同時(shí)，力求成本低、模具壽命長。 2、設(shè)計(jì)的冷沖模必須保證操作安全、方便。 3、沖模零件必須具有良好的工藝性，即制造裝配容易、便于管理。 4、便于搬運(yùn)、安裝、緊固到?jīng)_床上并且方便、可靠。 5、保證模具強(qiáng)度前提下，注意外形美觀，各部分比例協(xié)調(diào)。 進(jìn)度安排 起止日期 工作內(nèi)容 備注 2周 （2.28~3.11） 畢業(yè)調(diào)研 2周 （3.14~3.25） 集中實(shí)習(xí) 10周 （3.28~6.3） 畢業(yè)設(shè)計(jì) 1周 （6.6~6.10） 畢業(yè)答辯 主要參考資料 １、《冷沖壓工藝及模具設(shè)計(jì)》 劉心治主編重慶大學(xué)出版社 ２、《沖壓工藝及模具設(shè)計(jì)》萬戰(zhàn)勝主編 鐵道出版社 ３、《沖模設(shè)計(jì)》 吉林人民出版社 ４、《實(shí)用沖壓技術(shù)》 機(jī)工出版社 ５、《冷沖壓及塑料成型工藝與模具設(shè)計(jì)資料》 機(jī)工出版社 ６、《模具設(shè)計(jì)與制造簡明手冊》 馮炳堯等編 上海出版社 7、《沖壓工藝模具設(shè)計(jì)實(shí)用技術(shù)》　鄭家賢編　機(jī)械工業(yè)出版社 8、《實(shí)用板金沖壓工藝圖集》　梁炳文主編　機(jī)械工業(yè)出版社 9、《幾何量公差與檢測》甘永立主編　上?？茖W(xué)技術(shù)出版社 10、《機(jī)械制造專業(yè)英語》章躍主編　機(jī)械工業(yè)出版社 教研室 意見 年 月 日 系主管領(lǐng)導(dǎo)意見 年 月 日 零件號 材料 T10A 毛坯重量 編制 機(jī)械加工工藝過程綜合卡片 零件名稱 沖孔凸模 生產(chǎn)類型 毛坯種類 指導(dǎo) 工 序 工序名稱 工序說明 機(jī) 床 夾 具 刀 具 量 具 切 削 深 度 mm 進(jìn) 給 量 mm/r 主 軸 轉(zhuǎn) 速 r/min 切 削 速 度 m/min 時(shí) 間 定 額 min 5 下料 根據(jù)零件圖尺寸，下料F20360mm 10 車外圓面 車右端面，粗車外圓柱面尺寸：F10.6324，F(xiàn)14.4318，F(xiàn)1735，調(diào)頭車外圓F638 CA6140 三爪卡盤 外圓車刀 游標(biāo)卡尺 4.7 0.81 500 31.4 15 檢驗(yàn) 20 熱處理 按技術(shù)要求熱處理至HRC58～62 25 精車 精車F10.15mm至尺寸，并車出斜度309 CA6140 三爪卡盤 外圓車刀 游標(biāo)卡尺 0.17 0.81 500 16.6 30 磨外圓面 磨F14至尺寸 外圓磨床 三爪卡盤 砂輪 游標(biāo)卡尺 0.2 0.005 600 27.1 35 鉗工 去除工藝柄 40 檢驗(yàn) 離散應(yīng)用數(shù)學(xué) 離散應(yīng)用數(shù)學(xué)98(1999) 121-130 最小化模式下料問題 科林麥克迪爾米德 統(tǒng)計(jì)部門，牛津大學(xué)，南公園路一號，牛津大學(xué)OX1 3TG，英國收稿于1997年10月21日，接受于1999年2月8日 摘 要 在切割存量模式最小化問題，我們希望，以滿足盡可能少巨型卷軸卷軸切割各種客戶的需求，并進(jìn)一步減少使用不同的切削模式的數(shù)量。我們專注于特殊情況，其中任何兩個(gè)客戶卷軸到一個(gè)巨型合適，但沒有三事：這個(gè)案件的興趣，部分是因?yàn)樗亲詈唵蔚那闆r是不平凡的，部分是因?yàn)樗趯?shí)踐中可能會(huì)出現(xiàn)當(dāng)一個(gè)嘗試一個(gè)解決方案，以改善迭代。 我們發(fā)現(xiàn)，該模式最小化問題是強(qiáng)NP難的，即使在這種特殊情況下，當(dāng)inding最低廢液的基本問題是微不足道的。我們的分析主要論點(diǎn)集中在'均衡'的子集，并提出了涉及亞均衡的啟發(fā)式搜索方法的方法。 ? 1999 Elsevier科學(xué)BV公司保留所有權(quán)利。 關(guān)鍵詞：下料，切割模式;分區(qū); NP難;動(dòng)態(tài)規(guī)劃 1 簡介 有些材料如紙，可制造性'巨無霸'卷，這是后來成為更窄輥切，以滿足客戶的需求。為了減少浪費(fèi)，應(yīng)選擇切割方式，以盡可能少的使用客機(jī)（見[4,7,8]）。 因此，下料問??題已基本輸入一個(gè)正整數(shù)j，不同的正整數(shù)r1的,..., Rn和D1的,...,正整數(shù)的DN，以及需要的任務(wù)是，以盡可能客機(jī)的寬度j的數(shù)為滿足客戶的卷筒寬度里迪需求對每個(gè)i = 1 ,...,，全這是其中的經(jīng)典OR問題之一。它包含了強(qiáng)烈的NP -完全問題三分區(qū)：因此即使巨幅大小J外面有一層氮、多項(xiàng)式滿足每個(gè)客戶的卷軸大小國際扶輪扶輪J / 4 < < J / 2 -看[6],p。224。因此我們不能指望在合理時(shí)間內(nèi)總是能找到最優(yōu)解等問題的。 每一次不同的客戶卷軸模式是被削減，在切割機(jī)的刀需要重新設(shè)置。甲由Cn中Goulimis并在第29屆歐洲與產(chǎn)業(yè)調(diào)查研究組1996年3月有關(guān)如何找到辦法來解決上述料問題，這進(jìn)一步減少了用于切割不同模式的數(shù)量問題 - 見[1,2,9] 。 一般情況下這當(dāng)然是變得越來越難。為了探討擴(kuò)展問題雪上加霜，我們在這里考慮一個(gè)特殊的案件中，盡量減少對客機(jī)（減少廢物），數(shù)量基本問題是微不足道的。 最小化格局： 輸入：D1的正整數(shù);的DN。 任務(wù)：在切割存量問題，即要求I型迪卷軸是，任何兩個(gè)卷軸到一個(gè)巨型做它，但沒有三，工業(yè)最低廢液，進(jìn)一步減少了使用不同模式的數(shù)量。 這種特殊的情況是非常有限的部分原因是因?yàn)樗坪跏亲詈唵蔚那闆r是完全不平凡的，部分是因?yàn)樗赡軙?huì)在實(shí)踐中產(chǎn)生的，當(dāng)一個(gè)一個(gè)解決方案試圖改善迭代的興趣。例如，如果對目前使用的一些模式集合同意的大型卷軸和difer小卷軸而已，它在任何兩個(gè)小卷軸左邊的大型卷軸的寬度，那么當(dāng)我們試圖重新分配小我們面臨的正是這種卷軸的特殊情況[16]。我們調(diào)查模式是否最小化問題還很難在這個(gè)特殊的情況，并簡要考慮辦法找到好的解決辦法。 很明顯，所需要的客機(jī)數(shù)量最少的是我的di / 2]，圓了總需求的一半，它是微不足道的一個(gè)相應(yīng)的最低工業(yè)廢液。但是，它是多么容易躋身工業(yè)廢物最小的解決方案，一個(gè)能最大限度地降低使用的模式的數(shù)量，？對于這個(gè)問題的變體在沒有三個(gè)客戶卷軸它變成珍寶，但也有一些對可能不是，它是在[1]表明，問題是強(qiáng)NP -難問題。下面的定理加強(qiáng)這種不利的結(jié)果。 定理1：這個(gè)問題最小化模式是強(qiáng)NP -難問題。 對上述問題的理解關(guān)鍵是一個(gè)'平衡的一個(gè)子集'的概念。給定一個(gè)家庭d =(d1,dn)的非負(fù)整數(shù),表示x(d)的在任何解決方案中使用最少的廢物模式的最小數(shù)量。還有,另一個(gè)平衡的非空的子集{ 1,n } ,如果它能夠被分割成兩個(gè)集合A和B,t￡A di = 5^ieB di。因此,如果 di = 0然后單獨(dú)設(shè)置{i}是平衡的。讓v(d)是最大的數(shù)字的平衡子集兩兩相互無關(guān)的。 引理1：如果J2i di是偶數(shù),然后x(d)= n - v(d)。 如果i di 是奇數(shù)，令x(d) = i(d'),其中d1從D獲得通過增加一個(gè)額外的統(tǒng)籌的DN +1 = 1。]我們將在下一節(jié)中證明這個(gè)引理。 當(dāng)與一個(gè)模式最小化所面臨的問題，我們領(lǐng)導(dǎo)的定理1和引理1以上考慮啟發(fā)式方法inding亞群平衡的好包裝。不幸的是NP -完全甚至是測試，如果一個(gè)家庭中的正整數(shù)格a1,...,an有一個(gè)平衡的一個(gè)子集。這就是問題稱為弱分區(qū)是大衛(wèi)約翰遜的NP完全列[10]，其中四分之三的NP完全獨(dú)立的證據(jù)被引用，最早在[13]。 我們希望工業(yè)亞群的平衡好包裝，但我們知道這是很難工業(yè)最佳包裝，的確是很難平衡的工業(yè)任何一個(gè)子集。自然啟發(fā)式的方法是反復(fù)尋找和刪除一個(gè)平衡的一個(gè)子集，最好是小的。其中尋求一個(gè)平衡的一個(gè)子集的方法是使用'diferencing'，這里我們再次取代其diference絕對值兩個(gè)數(shù)字 - 參見[5,12,15,17]。這種方法目前正在調(diào)查中最小的格局[16]中。另一種方法是使用一個(gè)還算快速算法，保證工業(yè)均衡的子集或子集的最小平衡：我們會(huì)看到，我們可以使用一個(gè)簡單的動(dòng)態(tài)規(guī)劃方法來測試，如果有一個(gè)平衡的子集，均衡和IND一個(gè)最小的子集如果有一個(gè)，在偽多項(xiàng)式時(shí)間。最小的模式啟發(fā)式方法更普遍的情況下在降低庫存的問題被認(rèn)為是[1,2,9,11]。 該論文的其余部分計(jì)劃如下。在下一節(jié)中，我們建立的模式之間的平衡亞群的數(shù)量和包裝的關(guān)系。接下來，我們證明我們的主要結(jié)果，這個(gè)問題最小化模式是強(qiáng)NP -難問題。在此之后，我們認(rèn)為briely如何尋找平衡的子集，并inally我們做一些總結(jié)性發(fā)言。 2 模式，學(xué)位和平衡套 在這一節(jié)中，我們將證明引理1，其中涉及的圖案編號，包亞群平衡?英格斯。最小化的問題可以改寫格局在圖上。一個(gè)模式，涉及卷軸I型和J型卷筒之間將對應(yīng)頂點(diǎn)頂點(diǎn)vi和vj的邊緣。我們將讓我們的圖，包含在任何頂點(diǎn)循環(huán)但不包含多個(gè)邊緣。 給定一個(gè)圖G =（V，E）對集V = {v1，....，v2}的頂點(diǎn)，連同非負(fù)整數(shù)重量的邊緣E，我們的家庭W時(shí)，頂點(diǎn)加權(quán)第六度過度的重量與我們六邊é事件的總和與任何循環(huán)，計(jì)數(shù)兩次。給定一個(gè)向量d =（d1..... dn）的正整數(shù)，我們呼吁d如果每個(gè)頂點(diǎn)Vi有兩人加權(quán)程度地代表公克WA網(wǎng)絡(luò)。考慮以下問題。 學(xué)位： 輸入：積極intergers d1…...甚至與dn。 任務(wù)：工業(yè)用盡可能少的邊緣一個(gè)代表網(wǎng)絡(luò)。 給定一個(gè)d組=（d1…... dn）的正整數(shù)，甚至與我二，有一個(gè)度之間的解決方案和模式MINIMI ? SATION這些自然的對應(yīng)，特別是最小的邊數(shù)前者的可能等于 ×（d）項(xiàng)。 引理1：假設(shè)di是偶數(shù)。 設(shè)G w是任何代表工作，并考慮為G的K個(gè)節(jié)點(diǎn)集K表的組成部分。這當(dāng)然必須有至少k - 1條邊，如果它有這個(gè)數(shù)目，因此是對K樹，那么三分之二的頂點(diǎn)著色表明，K是平衡的。因此，在G的邊數(shù)至少有n減去若干套組成部分的平衡。因此×（D）Jsn - 的v（d）。 為了證明反向不等式，考慮任何{V1......Vn}（Ki：i € I），其中一個(gè)最不均衡。我們將證明，有代表?怨恨網(wǎng)絡(luò)G，W使得圖G有組件（Gi：I € i）如已設(shè)立文基頂點(diǎn)，這些組件是這樣，如果文是平衡的，然后是一樹基如果沒有則Gi是一加一樹循環(huán)。這將完成該引理的證明。 考慮平衡集K，其中分區(qū)A U S使得YieA= ? igBdi國際能源署。我們必須表明，有對T邊緣E對K和非負(fù)權(quán)重，我們一樹T，使得對于每一個(gè)節(jié)點(diǎn)v€ K時(shí)，對事件邊的權(quán)重之和等于的dv（其中雙回路數(shù)）。我們使用\ K|表感應(yīng)。如果A或B是空的，結(jié)果是微不足道的，因?yàn)槲覀儽仨殲槊總€(gè)V€光那假設(shè)A和B都是非空的dv = 0。選擇任何一個(gè)和b€€阿B和不失一般性假設(shè)大^分貝。減少大的分貝。現(xiàn)在K表\ {B}的是平衡的，我們可以感應(yīng)工業(yè)適當(dāng)?shù)募訖?quán)樹。然后加入與體重分貝邊緣抗體。 最后，考慮一個(gè)集K這是不均衡的，但就是這樣，相應(yīng)的要求和是偶數(shù)。如上所述，我們可以隨時(shí)更換了使用成本的一個(gè)邊緣的diference兩個(gè)要求。因此，我們能滿足所有，但一用邊緣形成一個(gè)對K樹需求，然后添加一個(gè)循環(huán)結(jié)束的組成部分。 3 最小化模式是強(qiáng)NP -難 在本節(jié)中，我們證明定理1，這個(gè)問題最小化模式是強(qiáng)NP -難問題?？偨Y(jié)三（或舒爾三）是三，這樣的兩個(gè)之和等于第三個(gè)不同的整數(shù)集合。下面的問題可以得到更充分的描述，總結(jié)成獨(dú)特的整數(shù)分區(qū)的三倍作為。 總結(jié)三元 輸入：S1…...S3n不同的正整數(shù)。 問：能否輸入三元分割成總結(jié)？ 這個(gè)問題類似于數(shù)值匹配與目標(biāo)款項(xiàng)，加里和Johnson [6]，第224，但額外的（令人驚訝的麻煩），條件是涉及的人數(shù)必須是不同的。 引理2：問題總結(jié)三元是強(qiáng)NP -完全的。 本節(jié)的大部分將用于證明上述引理，但首先，讓我們看到，它會(huì)產(chǎn)生定理1。 證明定理1（假設(shè)引理2）： 我們給一個(gè)總結(jié)，學(xué)位strightforward三倍，多項(xiàng)式時(shí)間減少?？紤]一個(gè)總結(jié)三元上述實(shí)例。以e =作為學(xué)位實(shí)例（2s1 …...2s3n）。由于硅是不同的正整數(shù)，也有規(guī)模不小于3套平衡。因此，（dHence由引理1，第十章x（d）^ 2n與x（d）為2n =當(dāng)且僅如果s1 …...s3n可分為總結(jié)三倍 現(xiàn)在考慮的問題總結(jié)三倍，這顯然是在NP。我們將證明它是強(qiáng)NP -通過給從NP -完全問題限制X3C減少完成，下述，總結(jié)每個(gè)三元組在O（n3）的。 限制X3C： 輸入：一組第三季度的X元素和一個(gè)三元組集合C在十，這樣每個(gè)X的 元素完全相同3三元載。問：可以劃分為三元X是在C？ 引理3： 限制X3C問題是NP完全的。 證明 據(jù)了解，這個(gè)問題是NP完全問題，如果每個(gè)元素被限制在最多3三倍，而不是正好3 - 見加里和Johnson [6]，第221。這是很容易對注冊整潔'的實(shí)例X，?使每個(gè)元素恰好是3的三倍。 很明顯，我們能堅(jiān)持，每個(gè)元素在2或3的三倍。我們可以在分區(qū)中的元素正好兩個(gè)三元組分為三個(gè)區(qū)塊的大小。對于每個(gè)塊{x，Y，Z}，添加新的元素三個(gè)x'，y'，z'及{x，y'，z'}，{x'，y，z'}，{x1， y'，z}，{x1，y，z'}。調(diào)用新的實(shí)例X'，C'的。顯然，每個(gè)X的元素是完全相同三三元在??C';和X可以被劃分在C到三倍，如果有僅當(dāng)X'可以被劃分為三元在C。 引理2： 考慮一個(gè)實(shí)例X，C的限制X3C，其中| X \ = \ = CI=3q。 季度全令Y = X x {1 ,..., 7}。我們將建設(shè)一個(gè)'擴(kuò)大'在Y D的收集，包含三元使得X可分為三元在C分區(qū)，當(dāng)且僅當(dāng)y可劃分為D中三元，接著我們將構(gòu)造一個(gè)實(shí)例（秒（y）的：你們的Y總結(jié)三倍，其中每個(gè)尺寸S（y）的異O（n2），），這樣的總結(jié)恰恰三倍對應(yīng)的三元組在D 形成一個(gè)二分圖G =（C，X，E）的頂點(diǎn)C部及X和頂點(diǎn)窄隙室和X GX的相鄰（即邊發(fā)射GE）的正是由于當(dāng)x ?噸G中的每個(gè)頂點(diǎn)度是三，我們可以在多項(xiàng)式時(shí)間內(nèi)找到一個(gè)合適的3邊染色：E - {1,2,3}?，F(xiàn)在，我們每個(gè)元素x GX的分割成三份（x，1），（x，2）和（x，3）。鑒于一特里普爾T = {x，y，z}氣相色譜，令T'是三重 T= {（x，at+bt= | Ct|。 5 結(jié)束語 我們已經(jīng)看到，即使是在削減庫存問題非常有限的情況下，它是強(qiáng)NP -難，盡量減少使用不同模式的數(shù)量，因此，我們不能期望能夠解決偽多項(xiàng)式時(shí)間等問題，即使。關(guān)鍵的概念，是一個(gè)平衡的子集，我們被帶往亞群平衡的考慮包裝啟發(fā)式，從而考慮尋求這種子集NP難問題。 6 如需進(jìn)一步閱讀 以下參考，也是讀者所關(guān)心的：[14]。 致 謝 我非常感謝其他參與在紅外警戒中討論的研究組成員。 參考文獻(xiàn) [1] C. Aldridge, J. Chapman, R. Gower, R. Leese, C. McDiarmid, M. Shepherd, H. Tuenter, H. Wilson, A.Zinober, Pattern Reduction in Paper Cutting, Report of the 29th European Study Group with Industry,University of Oxford, March 1996. [2] J.M. Allwood, C.N. Goulimis, Reducing the number of patterns in the 1-dimensional cutting stockproblem, Internal Report of Control Section, Electrical Engineering Department, Imperial College, 1988. [3] N. Alon, O. Goldreich, J. Hastad, R. Peralta, Simple constructions of almost k-wise independent randomvariables, Random Structures and Algorithms 3 (1992) 289-304. [4] V. Chvatal, Linear Programming, Freeman, San Francisco, 1983, pp. 195-212. [5] E.G. Coffman, G.S. Lueker, Probabilistic Analysis of Packing and Partitioning Algorithms, Wiley, New York, 1991. [6] M.R. Garey, D.S. Johnson, Computers and Intractability, Freeman, San Francisco, 1979. [7] P.C. Gilmore, R.E. Gomory, A linear programming approach to the cutting-stock problem, Oper. Res. 9 (1961) 849-859. [8] P.C. Gilmore, R.E. Gomory, A linear programming approach to the cutting-stock probelem - Part II, Oper. Res. 11 (1963) 863-888. [9] C.N. Goulimis, Optimal solutions for the cutting stock problem, European J. Oper. Res. 44 (1990) 197-208. [10] D. Johnson, The NP-completeness column: an ongoing guide, J. Algorithms 3 (1982) 182-195. [11] R.E. Johnston, Rounding algorithms for cutting stock problems, J. Asian-Pacific Oper. Res. Soc. 3 (1986) 166-171. [12] N. Karmarkar, R.M. Karp, The differencing method of set partitioning, Technical Report UCB/CSD 82/113, Computer Science Division (EECS), University of California, Berkeley, 1982. [13] A. Shamir, On the cryptocomplexity of knapsack systems, Proc. 11th Ann. ACM Symp. on Theory of Computing, 1979, pp. 118-129. [14] P.E. Sweeney, E.R. Paternoster, Cutting and packing problems: a categorized, application-orientated research bibliography, J. Oper. Res. Soc. 43 (1992) 691-706. [15] L-H. Tsai, The modiied diferencing method for the set partitioning problem with cardinality conditions, Discrete Appl. Math. 63 (1995) 175-180. [16] H. Tuenter, Personal communication, 1996. [17] B. Yakir, The diferencing algorithm LDM for partitioning: a proof of a conjecture of Karmarkar and Karp, Math. Oper. Res. 21 (1996) 85-99. 16