鋼構(gòu)件的優(yōu)化排料問(wèn)題(共21頁(yè))

1、精選優(yōu)質(zhì)文檔-傾情為你奉上鋼構(gòu)件的優(yōu)化排料問(wèn)題1、 問(wèn)題的重述1.1 背景在當(dāng)今激烈的市場(chǎng)競(jìng)爭(zhēng)中, 降低生產(chǎn)成本、提高生產(chǎn)效率和增強(qiáng)對(duì)市場(chǎng)的應(yīng)變能力, 是企業(yè)保持競(jìng)爭(zhēng)力的主要實(shí)現(xiàn)手段。在鋼構(gòu)件制造產(chǎn)品的生產(chǎn)過(guò)程中，依照產(chǎn)品零件尺寸從板料中截取大小適當(dāng)?shù)牧慵^(guò)程稱(chēng)之為排料，也稱(chēng)之為下料。排料是鋼構(gòu)件制造的第一道工序。在這道工序中，不同的排料方案具有不同的材料利用率，而原材料的利用率直接影響產(chǎn)品的成本。材料費(fèi)用是制造企業(yè)主要的生產(chǎn)成本, 一般占總成本的 60% 80% , 在大批量生產(chǎn)中, 材料的利用率即使提高 1% , 所創(chuàng)造的經(jīng)濟(jì)效益也相當(dāng)可觀。據(jù)調(diào)查,優(yōu)化下料后,制造企業(yè)材料利用率可平均提高

2、 5% 10%。另外由于切割工藝的要求，切割只能實(shí)行“一刀切”的工藝（在整料或余料中，從一邊的某點(diǎn)到另外一邊某點(diǎn)的連線一次切割，但可以在切割下來(lái)的板料中再次切割）。板材的利用率就是所有零件面積之和與在一刀切工藝后繼續(xù)切割的那部分板材面積的比值。1.2 問(wèn)題對(duì)于第一問(wèn)，對(duì)1張板料和若干規(guī)則形狀零件，求如何在板料中擺放零件使其板料的利用率最高。規(guī)則形狀零件即指矩形零件。其描述一般只需用矩形的長(zhǎng)和寬。規(guī)則形狀零件的排料問(wèn)題的實(shí)質(zhì)是研究如何組合零件擺放問(wèn)題，使得在整個(gè)原料上擺放大量的不同長(zhǎng)和寬的零件產(chǎn)生的廢料最少、整料和余料的利用率最高。排放時(shí)，其零件間的搭接關(guān)系的處理相對(duì)容易，只需考慮長(zhǎng)、寬兩個(gè)因素

3、（含預(yù)留的損耗量）。板材大小:2350*900【1張】。表1是九個(gè)規(guī)則形狀零件的具體規(guī)格。 表1零件一二三四五長(zhǎng)（mm）350350500500500寬（mm）300200240210350個(gè)數(shù)22222零件六七八九長(zhǎng)（mm）300250500500寬（mm）250200400200個(gè)數(shù)2222對(duì)于第二問(wèn)，對(duì)1張板料和若干不規(guī)則形狀零件，如何在板料中擺放零件使其板料的利用率最高。與第一問(wèn)類(lèi)似，但是此時(shí)需要切割出來(lái)的零件不具有矩形般對(duì)邊平行的條件，切割較為麻煩，同時(shí)可能會(huì)造成更多邊角料的產(chǎn)生，降低板料的利用率。圖1和表2是題目要求的兩種不規(guī)則零件的具體形狀和規(guī)格。板材大小:2380*1630 【

4、1張】。 表2零件一二個(gè)數(shù)1414 圖1零件一 零件二對(duì)于第三問(wèn)，考慮到實(shí)際的切割過(guò)程中，一張板料并不能滿(mǎn)足所有零件的生產(chǎn)需求，故而要求設(shè)計(jì)對(duì)2張板料和若干規(guī)則形狀零件，如何在板料中擺放零件使其板料的利用率最高。還有一點(diǎn)與問(wèn)題一不同，即各零件要求生產(chǎn)的個(gè)數(shù)有所改變。板材大小:4550*1630 【2張】。具體見(jiàn)下表3。 表3零件一二三四五個(gè)數(shù)40566零件六七八九個(gè)數(shù)42242、符號(hào)規(guī)定與模型假設(shè)2.1 符號(hào)規(guī)定符號(hào)表示意義L板材的長(zhǎng)度W板材的寬度hi矩形件的長(zhǎng)，i=1，2，3 w矩形件的寬，i=1，2，3 ni矩形件的數(shù)量，i=1，2，3 板材利用率Ri零件的種類(lèi)，i=1，2，3 2.2 模

5、型假設(shè)1. 切割機(jī)垂直切割，不考慮料板的厚度，即將問(wèn)題轉(zhuǎn)化為二維平面問(wèn)題；2. 切割不會(huì)導(dǎo)致料板的長(zhǎng)度或?qū)挾葴p小，忽略切割損耗；3. 切割方式為一刀切，即在整料或余料中，從一邊的某點(diǎn)到另外一邊某點(diǎn)的連線一次切割；4. 忽略切割效率，本文著眼點(diǎn)在于料板利用率的提高；5. 對(duì)于問(wèn)題二中的六邊形，可看作是矩形一角刪去一個(gè)150150的正方形，而這一步驟利用一刀切不可能實(shí)現(xiàn)，故而假設(shè)六邊形ABCDEF當(dāng)作五邊形ABCDE對(duì)待（圖2），該零件的后續(xù)加工后文不予考慮。 圖23、問(wèn)題分析本題目三個(gè)問(wèn)題所研究的是一刀切下料, 問(wèn)題一和問(wèn)題三屬于二維規(guī)則圖形的優(yōu)化排料問(wèn)題，問(wèn)題二屬于二維不規(guī)則圖形的優(yōu)化排料問(wèn)題

6、。排料問(wèn)題是典型的優(yōu)化組合問(wèn)題，具有很高的計(jì)算復(fù)雜性，屬于NP完全問(wèn)題?！耙坏肚小钡膶?shí)際現(xiàn)象給了本問(wèn)題一個(gè)最基礎(chǔ)的約束，使得排樣有了一個(gè)這樣一個(gè)基礎(chǔ)：每次切割都將板材一分為二。圖 3 給出了一刀切下料與非一刀切下料的比較。圖3問(wèn)題一和問(wèn)題三要求制作的零件規(guī)格有9種, 因此屬于多零件下料問(wèn)題。多種零件, 需要解決如何選擇將零件合理高效的布置在板材上。本文的研究目的是在這些約束條件下實(shí)現(xiàn)優(yōu)化排樣, 提高板材利用率。排樣目標(biāo)為: 盡可能提高一塊板的利用率。排料需要滿(mǎn)足的基本約束條件有：零件之間互不重疊；零件的排布不得超出板材邊緣；滿(mǎn)足一刀切條件。4、模型建立4.1 模型的準(zhǔn)備由于問(wèn)題一和二要求在一張

7、料板上規(guī)劃，問(wèn)題三要求在兩張規(guī)格相同的料板上規(guī)劃，故而在料板數(shù)量上簡(jiǎn)化模型，僅考慮在一張規(guī)格已知的料板進(jìn)行排料規(guī)劃。對(duì)于二維排料問(wèn)題，排料方式要滿(mǎn)足零件長(zhǎng)，寬方向上的套裁。將N個(gè)零件記為R1、R2、Rn合理的排布在板材A中，其中滿(mǎn)足： Max（畏）=Max（j=0NSprA*100%） （1.1） 且滿(mǎn)足： （1）RrA j=1,2N,（2）RjRk= （jk ， j k=1,2N） (1.2)其中畏為排料的材料利用率，應(yīng)滿(mǎn)足畏最大的原則。Spj為第j個(gè)板材Rj的零件面積，A為第一次一刀切后繼續(xù)用于一刀切的原料板材的面積，也即布局板材所消耗的原料面積，一般有A=A0+A1+A2 （其中A0=r

8、=0NSpr，A1為工藝廢料，A2為結(jié)構(gòu)廢料）。從式（1.1）中可以看出，理論上若廢料（包括工藝廢料和結(jié)構(gòu)廢料）面積減至0，材料的利用率能夠接近1，但該理論值在實(shí)際生產(chǎn)中無(wú)法達(dá)到。工藝廢料由行業(yè)的工藝要求產(chǎn)生，如切割損耗和余料，本題在建模過(guò)程中暫不考慮實(shí)際生產(chǎn)中的切割損耗。結(jié)構(gòu)廢料由具體板材的結(jié)構(gòu)形狀所決定。在生產(chǎn)中結(jié)構(gòu)廢料無(wú)法控制，要提高材料的利用率只有從減少工藝廢料入手，通過(guò)采用更合理的排料方案，減少余料（工藝廢料）。4.2 模型的建立4.2.1問(wèn)題一模型的建立設(shè)共有M張面積大小都為A的板材，N類(lèi)目標(biāo)零件板材。記板材的集合為：（X=Wi，H i iM，零件集合為：Y=wj，hj jN j類(lèi)

9、零件的數(shù)量為nj, 板材i上j 類(lèi)零件的數(shù)量為nji，已知第k 個(gè)j 類(lèi)零件在板材上的排列位置可以由其左下角坐標(biāo)與右上角坐標(biāo)唯一確定, 可記第k個(gè)j 類(lèi)零件在下料板材i上的左下角坐標(biāo)為(x0jki，y0jki), 右上角坐標(biāo)記為(x1jki，y1jki) 零件k 在0 縱排下料板材i上的排列方式記為pjki= ，目標(biāo)是最大化板材的利用率。 1 橫排根據(jù)以上分析，將多板材下料問(wèn)題用數(shù)學(xué)模型表示為：Max（畏）=Max（j=0NSprA*100%） （1.3）prA j=1,22N, (1.4）pjpk= （jk j k=1,22N） （1.5）j，kmaxx1jkiWi， （1.6）j，kmax

10、y1jkiHi， （1.7）1Inji=nj （1.8）式(1.3)為目標(biāo)函數(shù)，表示最大板材利用效率；式(1.4)為零件規(guī)格約束；式(1.5)保證零件互不重疊；式(1.6)和式(1.7)為板材規(guī)格約束，式(8)為零件數(shù)量約束。4.2.2 問(wèn)題二模型的建立該問(wèn)屬于二維不規(guī)則零件排樣問(wèn)題2，此類(lèi)問(wèn)題的求解主要有兩種思路：一種是對(duì)這類(lèi)問(wèn)題直接在原材料上進(jìn)行擺放；另一種則是將不規(guī)則零件轉(zhuǎn)化為規(guī)則矩形件，然后按照矩形件進(jìn)行優(yōu)化排樣。4如果將不規(guī)則零件排放在矩形形狀的板材上，其在板材上的位呈由三個(gè)參數(shù)決定，這三個(gè)參數(shù)是該零件的一個(gè)給定點(diǎn)在板材上的坐標(biāo)（x,y）和該零件的排放角度，這三個(gè)參數(shù)確定后，該零件的

11、其他各頂點(diǎn)參數(shù)均可通過(guò)這三個(gè)參數(shù)計(jì)算出來(lái)。5首先定義以下參數(shù)：排樣零件；排樣零件圖形；排樣零件給定點(diǎn)的坐標(biāo)。零件在板材上的排樣定位過(guò)程如下：先將該零件的給定點(diǎn)在板材上平移至，然后再將該零件以為軸作角度為的旋轉(zhuǎn)，這時(shí)零件在板材上的方向可表示為。則零件排樣優(yōu)化的模型為：其中L為板材的長(zhǎng)，W為板材的寬；N為排樣零件的數(shù)目；為排樣零件的面積；變量表示零件在板材上的排樣狀態(tài)，如果可以排放則取1，不能排放則取0。排樣的約束條件如下：其中第一式約束了任意兩個(gè)零件互不重疊；第二，三式約束了零件中任意點(diǎn)的坐標(biāo)都必須在排樣材料范圍內(nèi)，不能超出板材之外。我們對(duì)于問(wèn)題二的求解采用第二種方法，由于問(wèn)題二給出的五邊形和六

12、邊形并不是特別復(fù)雜的多邊形，同時(shí)五邊形具有直角。我們采用窮舉法列出了6種較為常見(jiàn)排列方案，在這里對(duì)每種方案的利用率進(jìn)行討論，得出最佳矩形件優(yōu)化方案。矩形面積：利用用率： .5/*100%=82.25% 方案一（圖4）矩形面積：=399*617=利用效率：=/*100%=90.01% 方案二（圖5）矩形面積：=411*558=利用效率：=/*100%=96.41%方案三（圖6）矩形面積：=411*664=利用效率：=/*100%=83.56% 方案四（圖7）矩形面積：=462*519=利用效率：=/*100%=92.21%方案五（圖8）矩形面積：=400*350=利用效率：=/*100%=91.

13、96%方案六（圖9）經(jīng)過(guò)綜合分析，我們擬采用方案三和方案六組合切割。至此，將不規(guī)則形狀零件的排料問(wèn)題簡(jiǎn)化為矩形零件的排料問(wèn)題，可參照問(wèn)題一模型來(lái)求解。4.2.3 問(wèn)題三模型的建立與前兩問(wèn)有所不同的是，問(wèn)題三要求在兩張規(guī)格相同的料板上進(jìn)行排料。經(jīng)過(guò)計(jì)算得知，故而我們?cè)趩?wèn)題一模型的基礎(chǔ)上，又可分兩種方案進(jìn)行比較：（1）在一張板材上進(jìn)行排板，看是否可以節(jié)省一整張料板；（2）在兩張板材上進(jìn)行排版，排板順序?yàn)閮蓮埻瑫r(shí)進(jìn)行，以求獲得更大的剩余的料板整體面積。4.3 算法模型4.3.1算法結(jié)構(gòu)框圖 圖104.3.2 排樣算法基本規(guī)則：（1）插入規(guī)則 大邊尺寸，指板材或者零件長(zhǎng)度和寬度的較大邊尺寸。 最大零件

14、，指大邊尺寸最大的待處理零件。 最小空穴，指大邊尺寸最小的待下料板材。啟發(fā)式算法6將待下料零件按大邊尺寸降序排序，將原料板材按大邊尺寸升序排序, 并規(guī)定新一輪的下料排樣總是選取待下料零件中的最大零件，搜索空穴列表，從滿(mǎn)足零件下料尺寸的空穴中選擇最小空穴1作為下料板材。(2) 放置規(guī)則靠左靠下在求解初始排樣方案中，對(duì)于給定空穴，規(guī)定從待排零件中選擇高度最低、寬度最大的零件靠左靠下放置。(3) 轉(zhuǎn)向規(guī)則整除求余設(shè)空穴小邊為x ( x= min( W，L)，W和L分別為空穴的寬度和長(zhǎng)度)，按插入規(guī)則和放置規(guī)則選定的零件寬度為w長(zhǎng)度為l，則x與w，l之間滿(mǎn)足以下線性關(guān)系: x= aw + l1 ，x=

15、 bh + d2。若d1 d2 ,則按照w|x的方式放置零件，否則按照l(shuí)|x的方式放置。（4）切割線替換規(guī)則1對(duì)于任意可行解, 若存在另一條切割線滿(mǎn)足第一條切割線的切割條件, 則以這條切割線為第一條切割線所形成的排樣方案與原解相同。證明: 如圖11所示, 已知區(qū)域 O 存在以 x 為第一條切割線的可行解 Ix, 則 O 中存在局部區(qū)域P, 使得P 中以 x 為第一條切割線的解 ioxI,現(xiàn)已經(jīng)找到另外一條滿(mǎn)足性質(zhì) 1 的切割線 y, 需要證明 Iy= Ix 。此時(shí)切割線 y 有兩種情況: 一種為 y平行于 x, 另一種為 y 垂直于 x。下面分別就這兩種情況進(jìn)行證明。（1） y平行于x。x 將

16、 O 劃分為 A C 和 B 兩部分, y將O 劃分為 A 和 B C 兩部分。易知iACI且iBI, 同理iAiAC 且 iCiAC , 根據(jù)集合的傳遞性, 有iAI且 iCI 。所以以 y 為第一條切割線所形成的排樣方案與原解相同。（2） y垂直于x。 x 將 O 劃分為 A D 和 B C 兩部分, y 將 O 劃分為 C D和 A B 兩部分。易知： iADI 且 iBCI, 同理iAiAD 且 iDiAD , iBiBC且 iCiBC , 根據(jù)集合的傳遞性, 有 iAI, iBI, iCI, iDI。所以以 y 為第一條切割線所形成的排樣方案與原解相同。切割線替換定理得證。 圖114

17、.3.3排樣優(yōu)化思想：采用二叉樹(shù)的生成過(guò)程來(lái)描述板材的分割過(guò)程，則生成的二叉樹(shù)就表示一個(gè)排樣結(jié)果，即得到一個(gè)全局排樣解。用I=N，G|N=nj,G=gj，j=1，2， 表示一個(gè)全局排樣解，其中N表示排樣解中各類(lèi)零件的個(gè)數(shù)集合；G表示排樣解中零件的規(guī)格集合。i=Ni，Gi|NiN，GiG是I的局部區(qū)域，則稱(chēng)i是I的一個(gè)局部解。一刀切的切割特點(diǎn)決定了滿(mǎn)足一刀切約束的排樣解具有以下條件:條件1 排樣解中的第一條切割線必須滿(mǎn)足：長(zhǎng)度等于分割區(qū)域中與其平行的那條邊的長(zhǎng)度，且不影響任意零件的完整性。條件2 設(shè)I為滿(mǎn)足一刀切的全局解，對(duì)于I中的任意局部解i，i一定滿(mǎn)足一刀切。條件3 對(duì)于任意可行解，若存在另

18、一條切割線滿(mǎn)足第一條切割線的切割條件，則以這條切割線為第一條切割線所形成的排樣方案與原解相同。4.4下料優(yōu)化問(wèn)題的二叉樹(shù)算法的構(gòu)造二叉樹(shù)是一種常用的空間數(shù)據(jù)結(jié)構(gòu)，因其結(jié)構(gòu)簡(jiǎn)單，操作方便、快速而廣泛應(yīng)用于數(shù)據(jù)的排序和計(jì)算內(nèi)部尋址等方面。本文主要基于VC+6. 0開(kāi)發(fā)平臺(tái)，對(duì)零件排料涉及到的二叉樹(shù)算法進(jìn)行了編寫(xiě)。在排樣過(guò)程中，由于一刀切的特性，1塊矩形區(qū)域劃分后，可得到2塊小的矩形區(qū)域。在這2塊矩形區(qū)域繼續(xù)進(jìn)行排樣，就會(huì)得到4塊矩形區(qū)域。不斷進(jìn)行下去，這個(gè)排樣過(guò)程就是一種二叉樹(shù)的結(jié)構(gòu)。本文將二叉樹(shù)用于矩形物體布局空間狀態(tài)的表達(dá)，具體應(yīng)用如下:已知一個(gè)布局空間的矩形區(qū)域，按權(quán)值從可選布局物體中選擇一

19、個(gè)相對(duì)于該矩形區(qū)域來(lái)說(shuō)是最優(yōu)的布局物體A，并將其定位于該矩形區(qū)域的左下角。這樣原布局空間變成了一個(gè)形區(qū)域。將這個(gè)形區(qū)域分成圖12所示2個(gè)矩形A1和A2，分別用根結(jié)點(diǎn)的左、右2個(gè)子結(jié)點(diǎn)表示。這樣，剩余的布局空間就變成了2個(gè)獨(dú)立的布局空間，分別對(duì)這2個(gè)布局空間重復(fù)上述過(guò)程，直至沒(méi)有可選布局物體滿(mǎn)足要求時(shí)停止分解。圖12 其中，每個(gè)圓圈和數(shù)字代表二叉樹(shù)的節(jié)點(diǎn)，代表在矩形中進(jìn)行了一次子排樣。根節(jié)點(diǎn)1為板材，進(jìn)行一次子排樣后，會(huì)生成2塊空白矩形，相應(yīng)產(chǎn)生2個(gè)節(jié)點(diǎn):節(jié)點(diǎn)2和節(jié)點(diǎn)3。節(jié)點(diǎn)2的空白矩形進(jìn)行一次子排樣后，又會(huì)產(chǎn)生2個(gè)新的節(jié)點(diǎn):節(jié)點(diǎn)4和節(jié)點(diǎn)5。節(jié)點(diǎn)之間的關(guān)系如圖13所示：圖13二叉樹(shù)路徑中的標(biāo)號(hào)x

20、i表示空白矩形分割方式。以節(jié)點(diǎn)1為例，定義X1=0時(shí)，對(duì)節(jié)點(diǎn)1的進(jìn)行子排樣后的空白區(qū)域進(jìn)行橫劃分。X1=1時(shí)，對(duì)剩余空白區(qū)域的劃分為豎劃分。顯然，當(dāng)x1取值不同時(shí)，生成的節(jié)點(diǎn)2, 3中的原始空白矩形也不一樣，更影響了后面的節(jié)點(diǎn)和排樣結(jié)果。具體步驟如下:1. 定義零件，二叉樹(shù)節(jié)點(diǎn)的結(jié)構(gòu)體，將板材和零件的長(zhǎng)、寬與數(shù)量放置到數(shù)組中,并將零件按照長(zhǎng)度從高到低，相同長(zhǎng)度按照寬度從寬到窄進(jìn)行排序。如下所示：/定義待排零件struct ORIGINAL_SQUAREint length; /長(zhǎng)int width; /寬int num; /數(shù)量;/定義已排零件struct SQUAREint length;

21、/長(zhǎng)int width; /寬int num; /數(shù)量;/定義二叉樹(shù)節(jié)點(diǎn)struct NODE struct SQUARE blankSquare; /排布前的空白矩形struct SQUARE *filledSquare; /空白矩形內(nèi)排布的一列矩形int fillesSquareNumber; /排布的矩形數(shù)目int originalIndex; /排布的是哪個(gè)初始矩形int remainLength; /順著排布方向無(wú)法排布的矩形的長(zhǎng)int remainWidth; /順著排布方向無(wú)法排布的矩形的寬struct NODE *lastNode;/上個(gè)節(jié)點(diǎn)的地址;/構(gòu)建數(shù)組，存儲(chǔ)數(shù)據(jù)，冒泡排

22、序#includeusing namespace std;int main(int argc,char *argv)/建立九行三列的二維數(shù)組int row,col;int i,n,k;int* p; /p是一個(gè)二維int數(shù)組row=9;col=3;p = new int*row; /創(chuàng)建行指針 for(i=1; i=row;i+)pi = new intcol; /為每一行分配空間 coutn請(qǐng)按順序依次輸入零件的長(zhǎng),寬與數(shù)量,并用空格隔開(kāi):n;for(n=1;n=row;n+) for(k=1;kpnk;coutn您輸入的是:n;coutn長(zhǎng)度t寬度t數(shù)量n;for(n=1;n=row;n+

23、) for(k=1;k=col;k+) cout pnkt; cout n;cout按照零件長(zhǎng)度從高到低,相同長(zhǎng)度下寬度從寬到窄排序得:n;for(n=1; n=row; n+) /for循環(huán)進(jìn)行冒泡排序 for(int j = n+1;j =row;j+) if(pn1 pj1) int t = pn1; pn1 = pj1; pj1 = t; int r = pn2; pn2 = pj2; pj2 = r; int w = pn3; pn3 = pj3; pj3 = w; if(pn1 = pj1&pn2 pj2) int t = pn2; pn2 = pj2; pj2 = t; int

24、w = pn3; pn3 = pj3; pj3 = w; coutn長(zhǎng)度t寬度t數(shù)量n;for(n=1;n=row;n+) for(k=1;k=col;k+) cout pnkt; cout n; cout endl; return 0;2.一張板材上的每次下料都優(yōu)先選擇長(zhǎng)度最長(zhǎng)，寬度最寬的零件靠左、靠下排列。此處選擇權(quán)值法，引入權(quán)值公式計(jì)算板材的利用率：Int w=1*u+2*t + 3*r+ 4*a其中，u表示單個(gè)待排零件占空白區(qū)域比例; t表示一次子排樣下的所有零件面積之和占空白區(qū)域比例; r表示剩余區(qū)域局部矩形的寬度；a表示剩余區(qū)域的面積; 1，2，3，4分別代表u,t,r,a的加權(quán)系

25、數(shù)。 以上的加權(quán)法直接影響的僅僅是一次排樣，但由于全部零件的排樣是由各個(gè)零件排樣完成的，因此，通過(guò)調(diào)整加權(quán)系數(shù)，可以改變板材中排樣的進(jìn)程。多次調(diào)整權(quán)值并橫向比較。選取總體排樣率最高的權(quán)值，就可以得到較優(yōu)的解。3.在滿(mǎn)足約束條件的情況下建立二叉樹(shù)并實(shí)現(xiàn)遍歷、搜索等操作：#include#include#includeusing namespace std;/二叉樹(shù)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的形式定義/二叉樹(shù)結(jié)點(diǎn)typedef struct BiTNodechar data; /數(shù)據(jù)struct BiTNode *lchild,*rchild; /左右孩子指針BiTNode,*BiTree;/二叉樹(shù)的創(chuàng)建/按先

26、序序列創(chuàng)建二叉樹(shù)int CreateBiTree(BiTree &T)char data;/按先序次序輸入二叉樹(shù)中結(jié)點(diǎn)的值（一個(gè)字符）,#表示空樹(shù)cindata;if(data = #)T = NULL;elseT = (BiTree)malloc(sizeof(BiTNode);/生成根結(jié)點(diǎn)T-data = data;/構(gòu)造左子樹(shù)CreateBiTree(T-lchild);/構(gòu)造右子樹(shù)CreateBiTree(T-rchild);return 0;/輸出/二叉樹(shù)的遍歷/遞歸算法void Visit(BiTree T)if(T-data != #)coutdata;/先序遍歷void Pre

27、Order(BiTree T)if(T != NULL)/訪問(wèn)根節(jié)點(diǎn)Visit(T);/訪問(wèn)左子結(jié)點(diǎn)PreOrder(T-lchild);/訪問(wèn)右子結(jié)點(diǎn)PreOrder(T-rchild);/中序遍歷 void InOrder(BiTree T) if(T != NULL) /訪問(wèn)左子結(jié)點(diǎn) InOrder(T-lchild); /訪問(wèn)根節(jié)點(diǎn) Visit(T); /訪問(wèn)右子結(jié)點(diǎn) InOrder(T-rchild); /后序遍歷void PostOrder(BiTree T)if(T != NULL)/訪問(wèn)左子結(jié)點(diǎn)PostOrder(T-lchild);/訪問(wèn)右子結(jié)點(diǎn)PostOrder(T-rch

28、ild);/訪問(wèn)根節(jié)點(diǎn)Visit(T);int main()BiTree T;CreateBiTree(T);cout”先序遍歷：n”;PreOrder2(T);cout”n”;cout中序遍歷：n;InOrder2(T);cout”n”;cout后序遍歷：n;LevelOrder(T);cout”n”; return 0;4.4.1問(wèn)題一的輸出結(jié)果圖144.4.2問(wèn)題二的輸出結(jié)果圖154.4.3問(wèn)題三的輸出結(jié)果圖165、模型求解5.1 問(wèn)題一的求解參考問(wèn)題一的方法，畫(huà)出了近似最優(yōu)切法圖使得利用率較大，得到具體切法如圖17：圖17剩料為400300的矩形，故=1nSiS-S余=1nSi2500900-300400=99.94% 5.2 問(wèn)題二的求解類(lèi)似問(wèn)題一，我們畫(huà)出了近似最優(yōu)切法圖使得利用率較大，得到具體切法如圖18。根據(jù)附件二和假設(shè)的條件易求得五邊形和六邊形的面積分別為：.5和。而余料為411311的矩形。可求得：=1nSiS-S余=1nSi23801630-411311=89.3%圖185.3 問(wèn)題三的求解類(lèi)似問(wèn)題一，我們畫(huà)出了近似最優(yōu)切法圖使得利用率較大，得到具體切法如圖