地板磚的鋪設(shè)問題的探究

1、地板磚的鋪設(shè)問題的探究謝欽 徐寶玉 沈燕摘要房屋地板磚的鋪設(shè)將一種固定形狀的材料鋪設(shè)到某種物體表面的問題。在地板磚的鋪設(shè)問題中，需要考慮地板磚的成本、鋪設(shè)人工費(fèi)用以及地板磚破損成本等方面，目標(biāo)是為了使成本最小化，并達(dá)到美觀的效果在問題1中，由于整個(gè)建筑的平面圖較復(fù)雜，我們把整個(gè)圖進(jìn)行分割簡化為14個(gè)矩形區(qū)域。首先我們采用高斯函數(shù)求未被切割的地板磚的塊數(shù)，利用自定義的向上取整公式得到所需總的地板磚的塊數(shù)，然后根據(jù)01規(guī)劃算出被切割的長度，加上安裝工人的費(fèi)用則得到總費(fèi)用的表達(dá)式；在問題2中，首先我們利用問題1中的向上取整算出各種規(guī)格的地板磚所需要的總塊數(shù)分別是800*800需要260塊 ，600*

2、600需要421塊，600*300需要804塊，400*400需要934塊，300*300需要1509塊，然后再用計(jì)算所需每種規(guī)格地板磚的總面積與被鋪設(shè)的區(qū)域的總面積得的利用率分別是800*800利用率0.78 ，600*600利用率0.85 ，600*300利用率0,89，400*400利用率0.87，300*300利用率0.95。在用01規(guī)劃算和高斯函數(shù)計(jì)算出各個(gè)規(guī)格地板磚的切割總長度，再分別乘于切割單價(jià)，由于鋪設(shè)的面積大小相同所以安裝費(fèi)用相同，因此我們暫時(shí)不考慮，只計(jì)算各個(gè)規(guī)格地板磚的切割費(fèi)與購買費(fèi)用之和分別是800*800費(fèi)用是 47207元，600*600費(fèi)用是55131元，600*

3、300費(fèi)用是64714.5元，400*400費(fèi)用是67648.25元，300*300費(fèi)用是68300元，經(jīng)過比較可以知道800*800規(guī)格的費(fèi)用最低在問題3中，在問題3中，先考慮使用整塊鋪設(shè)，且整塊鋪設(shè)優(yōu)先選用邊長的，我們只考慮四種變長情況，即800*800，600*600，400*400和300*300最后不能被整塊鋪設(shè)的地方用300*300鋪設(shè)，因?yàn)槭Ｏ碌拿娣e往往很小（且靠矩形總面積的邊界），用大磚切割不經(jīng)濟(jì)。最后每個(gè)區(qū)域300*300的塊數(shù)>=2時(shí)，我們同樣把2塊300*300換成1塊300*600的。在這個(gè)問題的考慮中我們使用了多元目標(biāo)的線性規(guī)劃，在考慮區(qū)域的邊長被組合鋪設(shè)后是否

4、有剩余，采用了01規(guī)劃。利用了C語音編程求解 在問題4中，則是對模型改進(jìn)的建議，我們認(rèn)為要考慮墻體的厚度及余料的利用，這樣我們就能更節(jié)省關(guān)鍵詞 高斯函數(shù) 01規(guī)劃 向上取整 多目標(biāo)線性規(guī)劃問題的重述假定工程中能購買到的地板磚的尺寸、價(jià)格、安裝費(fèi)用、破損概率等參數(shù)如表1所示的5種類型的地板磚。根據(jù)需要鋪設(shè)的房屋地面結(jié)構(gòu)用地板磚進(jìn)行鋪設(shè)。假設(shè)每塊地板磚只能沿著平行于邊的方向切割，最多只能切割一次，且切割所用人工費(fèi)跟切割長度成正比。1) 綜合考慮影響地板磚鋪設(shè)成本的因素，并建立計(jì)算地板磚鋪設(shè)總成本的模型。2) 假如只使用一種尺寸的地板磚進(jìn)行鋪設(shè)，設(shè)計(jì)一種算法進(jìn)行地板磚的自動鋪設(shè)，同時(shí)計(jì)算出鋪設(shè)地板磚

5、的塊數(shù)、利用率和總費(fèi)用，綜合比較分析哪種尺寸的地板磚鋪設(shè)成本最低。3) 若允許使用多種尺寸的地板磚進(jìn)行混合鋪設(shè)，設(shè)計(jì)一種算法是的實(shí)現(xiàn)地板磚的自動鋪設(shè)，并且計(jì)算鋪設(shè)各種尺寸地板磚的塊數(shù)、利用率和總費(fèi)用。4) 根據(jù)以上3問得出的模型、算法及計(jì)算結(jié)果，為地板磚鋪設(shè)提出一些意見和建議。問題的分析由于本題中，用地板磚對房屋的鋪設(shè)需要考慮的因素有：購買地板磚的費(fèi)用，安裝工人的工資，切割工人的工資，美觀程度地板磚的規(guī)格參數(shù)以及切割方式的限制，我們對題目的分析如下：1對于問題一的分析首先要得出在鋪設(shè)地板磚中未被切割的塊數(shù)以及總需要的塊數(shù)（已把損耗考慮進(jìn)去），則被切割的地板磚的塊數(shù)就是兩者之差，然后算出美觀的程

6、度，利用總數(shù)得出所需要的地板磚的總成本，再加上安裝工人的安裝費(fèi)，所有之和就是總費(fèi)用2對于問題2的分析利用每種規(guī)格的地板磚自分別計(jì)算出所需的總的地板磚的塊數(shù)（已把損耗考慮進(jìn)去）和不需要被切割的地板磚的塊數(shù)，用鋪設(shè)的面積除于所購瓷磚的總面積則計(jì)算出利用率，3對于第3問的分析 用多種地板磚進(jìn)行鋪設(shè)，要考慮其規(guī)格對矩形區(qū)域的限制，因此可以進(jìn)行多目標(biāo)線性規(guī)劃，對各種規(guī)格的地板磚進(jìn)行逐一考慮，在計(jì)算美觀度，利用率，總費(fèi)用與第二問中的數(shù)據(jù)進(jìn)行對比，體現(xiàn)多種地板磚進(jìn)行混鋪時(shí)的優(yōu)缺點(diǎn)。4對于問題4的分析由于以上的問題沒有將余料的考慮進(jìn)行利用，則需要進(jìn)行余料重新利用的考慮問題的假設(shè)1假設(shè)在鋪設(shè)地板磚的過程中，進(jìn)過

7、切割后的剩余的的余料不再利用。2假設(shè)在進(jìn)行對鋪設(shè)的區(qū)域的面積時(shí)，忽略墻體的厚度。3假設(shè)地板磚在切割的過程中，不會產(chǎn)生損耗。符號說明鋪設(shè)第個(gè)矩形地板磚的安裝費(fèi)用 第種地板磚的長 第種地板磚的破損概率。 第種地板磚的寬 切割單位長度的地板磚所需費(fèi)用 地板磚類型 （i=1,2,3,4,5） 被鋪設(shè)的矩形區(qū)域（編號為k=1,2,3。14） 鋪設(shè)第個(gè)矩形所需的第種地板磚的塊數(shù)。 鋪設(shè)第個(gè)矩形購買地板磚的費(fèi)用 第個(gè)矩形的長 第塊區(qū)域切割長度 被切割的塊數(shù) 所需型地板磚的數(shù)量 第種地板磚的單價(jià) 鋪設(shè)第個(gè)矩形地板磚的切割費(fèi)用。 戶型面積 所需地板磚的面積 第塊區(qū)域的面積 第個(gè)矩形的寬 房屋地板磚鋪設(shè)總花費(fèi) 鋪

8、設(shè)第個(gè)矩形地板磚所需總費(fèi)用。 單位面積的安裝費(fèi)用 Z利用率 美觀度 模型的建立與求解問題1首先由于鋪設(shè)的平面比較復(fù)雜，我們把平面分為如圖1.1所示，圖1.1建立模型一房屋地板磚鋪設(shè)總花費(fèi)計(jì)算公式為： (1)其中鋪設(shè)第個(gè)矩形區(qū)域地板磚所需總費(fèi)用計(jì)算公式： (2)則鋪設(shè)第個(gè)矩形購買地板磚的費(fèi)用計(jì)算公式： (3)定義為向上取整公式，即不小于的最小整數(shù) (4)其中不需要被切割的地板磚的塊數(shù)： (5)鋪設(shè)第個(gè)矩形地板磚的安裝費(fèi)用計(jì)算公式： (6)鋪設(shè)第個(gè)矩形地板磚的切割費(fèi)用計(jì)算公式： (7)而對于切割費(fèi)用的的計(jì)算，運(yùn)用01規(guī)劃，令 (8) (9) 則切割長度的數(shù)學(xué)表達(dá)為： (10) 美觀度計(jì)算公式 (1

9、1)問題2模型二對于用同一種尺寸的地板磚進(jìn)行鋪設(shè)，先利用模型一中的以下公式： (12)可求的所需的第種地板磚的總塊數(shù)則利用率的可表示為: （13）總費(fèi)用可表示為 （14）經(jīng)過計(jì)算的到的數(shù)據(jù)如圖2.1所示地板磚的規(guī)格所需塊數(shù)(塊)地板磚購買費(fèi)用切割費(fèi)用（元）總費(fèi)用利用率800*80026046800407472070.777284600*60042154730401551310.853391600*30080464320396.564716.50.893726400*40093467248400.2567648.250.865498300*300150967905395683000.95236圖

10、2.1問題3準(zhǔn)別條件：優(yōu)先使用整塊鋪設(shè)，且整塊鋪設(shè)優(yōu)先選用邊長的，五中磚的規(guī)格中，4種是正方形，剩下的 300*600，可以切分為2塊300*300，在考慮問題的時(shí)候，因?yàn)槿魏我环N長寬不同矩形都會有兩種鋪法，而對與正方形來就沒有這種考慮我們只考慮四種變長情況，即800*800，600*600，400*400和300*300，而當(dāng)整塊300*300的塊數(shù)出現(xiàn)>=2時(shí)，我們把兩塊300*300的合并成一塊300*600，根據(jù)單位面積的價(jià)格，大磚更加經(jīng)濟(jì)。最后不能被整塊鋪設(shè)的地方用300*300鋪設(shè)，因?yàn)槭Ｏ碌拿娣e往往很?。ㄇ铱烤匦慰偯娣e的邊界），用大磚切割不經(jīng)濟(jì)。當(dāng)計(jì)算所用300*300的塊

11、數(shù)>=2時(shí)，我們同樣把2塊300*300換成1塊300*600的。首先，根據(jù)盡量鋪大塊的磚，（且在考慮中只有涉及4種規(guī)格的正方形磚），從矩形的長和寬分別進(jìn)行考慮。長（length）的考慮使得四種規(guī)格組合的邊長相加最大程度達(dá)到到區(qū)域邊長，且限制條件1：邊長越長的磚塊越優(yōu)先。限制條件2區(qū)域總變長-組合邊長<300,同理從寬（weith）的角度使得四種規(guī)格組合的邊長相加最大程度達(dá)到到區(qū)域?qū)掗L，限制條件1：邊長越長的磚塊越優(yōu)先。限制條件2區(qū)域?qū)掗L-組合寬長<300。數(shù)學(xué)公式 區(qū)域長的角度 設(shè)需要邊長800的數(shù)量i1,邊長是600的數(shù)量為i2，邊長為400的數(shù)量為i3,邊長為300的數(shù)

12、量是i4 區(qū)域?qū)挼慕嵌?設(shè)需要邊長800的數(shù)量j1,邊長是600的數(shù)量為j2，邊長為400的數(shù)量為j3,邊長為300的數(shù)量是j4數(shù)學(xué)模型3根據(jù)題目的要求，我們得到以下的限制條件: Length-(800*i1+600*i2+400*i3+300i4)<300 （15） Wdith-(800*i1+600*i2+400*i3+300i4)<300 （16） (17) (18) (19) (20) (21) (22) (23) (24)運(yùn)用C語言編程序求解代碼見附錄 結(jié)果每個(gè)區(qū)域有兩組數(shù)據(jù)i1 i2 i3 i4 j1,j2,j3,j4 如圖3.1所示圖3.1具體的得到的最佳組合數(shù)據(jù)如表

13、3.2所示區(qū)域號碼ij 12,0,1,00,0,1,022,0,1,01,0,0,032,0,1,01,0,0,044,0,0,01,0,0,153,0,0,01,0,1,062,0,1,01,1,0,075,0,1,04,0,0,084,0,0,02,1,0,094,0,0,14,0,0,0104,1,0,03,0,0,0112,0,1,03,0,0,0123,0,0,03,0,0,0136,1,0,03,1,0,01412,0,0,05,0,1,0表3.2磚塊計(jì)算公式某個(gè)區(qū)域需要的磚塊數(shù)量 (25) (26) (27) (28)進(jìn)過C語言計(jì)算得到每個(gè)區(qū)域的各種規(guī)格的地板磚的最佳結(jié)果，如表3

14、.3所示區(qū)域號碼800的整塊數(shù)600的整塊數(shù)400的整塊數(shù)300的整塊數(shù)100502202032020440011530606233072008088500916001110124001160601290001318130014600240表3.3再考慮剩下剩下來的面積用300*300的鋪設(shè)。我們考慮到如果區(qū)域的長被組合完全鋪滿，那么最后不能被整塊鋪余下的面積，會是不到300mm的寬乘以區(qū)域的長，最后鋪設(shè)的要切割的300*300的塊數(shù)，就是區(qū)域的長除以300mm向上取整。按照這個(gè)思路。我們可以建立模型 （29） （30）有四種情況，記作（x,y）1、 長有剩余，寬有剩余。記作(x,y)=（1，

15、1）2、 2、長有剩余，寬沒有剩余。記作（x,y）=（0，1）3、長沒有剩余，寬有剩余。記作（x,y）=（1，0）4、長沒有剩余，寬沒有剩余。記作（x,y）=（0，0）最后補(bǔ)的300*300的塊數(shù)為 將所有300mm*300mm換成300mm*600mm最終用混合鋪設(shè)的磚塊數(shù)分別為如表3.4所示區(qū)域號碼800*600600*600400*400600*300300*30010055022026032022044007153061062336172008131885091916001111012407011606401290001131813001146002480表3.4最終我們得到混合鋪法所

16、需要的各尺寸地板磚的塊數(shù)及總費(fèi)用和利用率，見表3.5所示地板磚的規(guī)格所需塊數(shù)(塊)地板磚購買費(fèi)用切割費(fèi)用（元）總費(fèi)用利用率800*80018433120407464580.870332600*600273510600*300927360400*400282016300*300145表3.5問題4模型的評價(jià)與改進(jìn)模型的優(yōu)點(diǎn)： 1. 結(jié)合數(shù)學(xué)期望的概念對地磚切割單后單價(jià)做了合適的處理，使得求解方便準(zhǔn)確，與實(shí)際的結(jié)合性強(qiáng)。 2. 模型求解中運(yùn)用了攤還算法的思想， 3. 在混合地板鋪設(shè)的求解中運(yùn)用了窮舉算法，在求解小規(guī)模問題時(shí)，算法簡單，可靠性高。 5. 應(yīng)用了較為嚴(yán)謹(jǐn)?shù)臄?shù)學(xué)知識進(jìn)行計(jì)算及求解 模型的

17、缺點(diǎn)： 1.采取線性整數(shù)規(guī)劃求解問題時(shí),模型較為理想化，現(xiàn)實(shí)存在的一些問題不能充分考慮。 2.對于一些結(jié)構(gòu)復(fù)雜及形狀不規(guī)則的戶型，區(qū)域劃分較為困難，應(yīng)用此模型求解時(shí)較復(fù)雜。 3.未考慮實(shí)際情況下多種類型地板磚混合鋪設(shè)對美觀效果的影響。參考文獻(xiàn)1 薛定宇 陳陽泉，高等應(yīng)用數(shù)學(xué)問題的MATLAB求解（第二版），北京：清華大學(xué)出版社，2008年。2 同濟(jì)大學(xué)數(shù)學(xué)系，工程數(shù)學(xué)-線性代數(shù)（第五版），北京：高等教育出版社，2007年3 鄧君智，關(guān)于高斯函數(shù)在建筑學(xué)中的一個(gè)應(yīng)用方地磚最少塊數(shù)估計(jì)，數(shù)學(xué)的實(shí)踐與認(rèn)識，第34 卷第2 期：P111-P114，2004 年。4 俱鵬岳，鋪設(shè)矩形地面所需矩形地磚的最

18、優(yōu)估計(jì)，西北師范大學(xué)學(xué)報(bào)(自然科學(xué)版)，第45卷2009年第 2 期：P17-P20，2009年。5 張偉，地板磚鋪設(shè)問題 /view/7cfe3d91680 203d8ce2f2434. html?qq-pf-to=pcqq.c2c，2013年8月25日。附錄1、C源程序一/*名稱長度寬度b12150500b22100900b32000900c133001150c224001200c321001500r145003450r233002300r335003450r439002400r521002400r624002400r754003000r896004500*/#include<std

19、io.h>long fun(double length ,double width,long s1,long s2);int main()/long length , width;long b1,b2,b3,c1, c2,c3,r1,r2,r3,r4,r5,r6,r7,r8;long s1,s2;long sum;int i=0;for(i=1;i<=5;i+)sum=0;scanf("%d*%d",&s1,&s2);b1=fun(2150,500,s1,s2);/printf("%dn",b1);b2=fun(2100,90

20、0,s1,s2);b3=fun(2000,900,s1,s2);c1=fun(3300,1150,s1,s2);c2=fun(2400,1200,s1,s2);c3=fun(2100,1500,s1,s2);r1=fun(4500,3450,s1,s2);r2=fun(3300,2300,s1,s2);r3=fun(3500,3450,s1,s2);r4=fun(3900,2400,s1,s2);r5=fun(2100,2400,s1,s2);r6=fun(2400,2400,s1,s2);r7=fun(5400,3000,s1,s2);r8=fun(9600,4500,s1,s2);sum=

21、b1+b2+b3+c1+c2+c3+r1+r2+r3+r4+r5+r6+r7+r8;printf(":%dn",sum);system("pause"); long fun(double length ,double width,long s1,long s2) long L;L=ceil(length/s1)*ceil(width/s2);return L;C源程序二#include<stdio.h>int main()/long s1,s2,s3,s4,s5; /地磚塊的面積 int i1=0,i2=0,i3=0,i4=0; /行 int

22、 j1=0,j2=0,j3=0,j4=0;/ int an1,an2,an3,an4; /地磚塊的邊長種類 /long sk14;int length,width;int n=0;int b=0;length=9600;width=4500;an1=800;an2=600;an3=400;an4=300;/s1=an12;/s2=an22;/s3=an2*an4;/s4=an32;/s5=an42; /sk14=length*width;for(i1=length/an1,j1=width/an1;i1>=0,j1>=0;i1-,j1-) /printf("%dn&quo

23、t;,i1); for(i2=(length-i1*an1)/an2,j2=(width-j1*an1)/an2;i2>=0,j2>=0;i2-,j2-) for(i3=(length-i1*an1-i2*an2)/an3,j3=(width-j1*an1-j2*an2)/an3;i3>=0,j3>=0;i3-,j3-) for(i4=(length-i1*an1-i2*an2-i3*an3)/an4,j4=(width-j1*an1-j2*an2-j3*an3)/an4;i4>=0,j4>=0;i4-,j4-) /if(length-(i1*an1+i2*

24、an2+i3*an3+i4*an4)<300&&(width-(j1*an1+j2*an2+j3*an3+j4*an4)=0) /printf("%d %d %d %d %d %d %d %d n",i1,i2,i3,i4,j1,j2,j3,j4); /n+; if(length-(i1*an1+i2*an2+i3*an3+i4*an4)=0) printf("%d %d %d %d n",i1,i2,i3,i4); n+; printf("nn");if(width-(j1*an1+j2*an2+j3*an3+

25、j4*an4)=0) printf("%d %d %d %d n",j1,j2,j3,j4); printf("%d",n); system("pause"); C源程序三#include <stdio.h>int main()int l4=800,600,400,300;int w4=800,600,400,300;int L14=2150,2100,2000,3300,2400,2100,4500,3300,3500,3900,2100,2400,5400,9600;int W14=500,900,900,1150,1

26、200,1500,3450,2300,3450,2400,2400,2400,3000,4500;int i144=2,0,1,0,2,0,1,0,2,0,1,0,4,0,0,0,3,0,0,0,2,0,1,0,5,0,1,0,4,0,0,0,4,0,0,1,4,1,0,0,2,0,1,0,3,0,0,0,6,1,0,0,12,0,0,0;int j144=0,0,1,0,1,0,0,0,1,0,0,0,1,0,0,1,1,0,1,0,1,1,0,0,4,0,0,0,2,1,0,0,4,0,0,0,3,0,0,0,3,0,0,0,3,0,0,0,3,1,0,0,5,0,1,0;int k,m;int kuai800;int kuai600;int kuai400;int kuai300;int kuai4;int n=0;for(k=0;k<14;k+) n+; printf("%d &quo