离散数学模型与实验

《离散数学模型与实验》由会员分享，可在线阅读，更多相关《离散数学模型与实验（72页珍藏版）》请在金锄头文库上搜索。

1、离散模型与实验离散模型与实验 第七章：离散模型与实验7.1 7.1 截断切割截断切割 7.2 7.2 锁具装箱锁具装箱7.3 7.3 钻井布局钻井布局7.4 7.4 讨论题讨论题下一页上一页下一页上一页下一页上一页7.1 截断切割 7.1.1 问题的提出这是1997年全国大学生数学建模竞赛的B题，问题如下：某些工业加工部门，经常需要从一个长方体中加工出一个尺寸已知，位置预定的长方体（设长方体的对应表面是平面），通常采用截断切割的加工方式，这里“截断切割”是指将物体沿某个切割平面分成两部分，因此，一般情况下，须经过6次截断切割，分别截去原长方体的前后、左右、上下6个方向多余的部分。下一页上一页下

2、一页上一页下一页上一页设水平切割单位面积的费用是垂直切割单位面积费用的r倍，且当先后两次垂直切割的平面不平行时，因调整刀具需额外费用e，显然，若截去各个多余小块的先后顺序不同，则加工费用不同，试设计一种确定最优加工次序的方法，使加工费用最少。用以下实例验证你的方法：待加工长方体与成品长方体的长、宽、高分别为10；14.5；19和3；2；4二者左面，前面，底面之间的距离分别为6；7；9（单位cm），垂直切割费用为1元/cm2，r和e的数据有以下4组：a）r=1；e=0； b）r=1.5；e=0；c）r=8；e=0； d）r=1.5；2e15下一页上一页下一页上一页下一页上一页7.1.2 模型假设

3、及符号说明 （1）假设水平工作台接触的长方体底面是事先指定的。（2）假设第一次切割前调整刀具的费用不计。（3）假设加工前后，两长方体对应的表面平行。（4）假设垂直切割费用为1元/cm2，水平切割费用为r元/cm2。（5）假设调整一次刀具的费用为e。（6）假设总的加工费用为C。（7）假设待加工长方体的长、宽、高分别为a、b、c，为常数，成品长方体的长、宽、高分别为A、B、C，也是常数。（8）假设待加工长方体与成品长方体的左面、前面、后面、下面、上面之间的距离为 且为常数。 下一页上一页下一页上一页下一页上一页7.1.3 问题分析及数学模型根据所给的实际问题，从一个长方体加工出一个尺寸位置预定的长

4、方体，通常情况下，需要经过6次截断切割，如果我们假定这6个切割面分别位于左、右、前、后、下、下面，那么可将它们相应地编号为1、2、3、4、5、6。这样这6个数字的一个全排列代表着一种切割顺序。例如，排列1 2 3 4 5 6代表的的切割顺序为“左前后右下上”。我们将这6个数字的所有全排列记为集合S，即： 因此问题转化为求总的切割费用C在S上的最小值问题。下一页上一页下一页上一页下一页上一页总的切割费用应包含二部分，一部分为加权的切割面积之和，另一部分是刀具调整费用之和, 因此，数学模型为：其中：表示 进行切割后，加工面 的切割面积； ：为相应切割面的权，由题意有：为调整刀具的次数。 下一页上一

5、页下一页上一页下一页上一页7.1.4 模型的分析及计算当e=0时（1）式成为：由于集合S为有限集，只有 个元素，代表着720种切割方式，r给定，切割顺序固定则很容易计算出加工费用。比较出所有不同切割方式下的费用，便可得到最小费用下的切割方式。下面给出MATLAB计算程序。1）建立可行的加工顺序表。2）用穷举法求出720种切割方式下的费用。3）求最小费用及其对应的切割方式。 下一页上一页下一页上一页下一页上一页在MATLAB编辑器中建立如下文件。 %截断切割ch711 %文件名：ch711.m a0=10 14.5 19;a1=3 2 4;d1=6 7 9;r=1; d2=a0-a1-d1;d=

6、d1,d2;d=d(1,4,2,5,3,6);p=0; for i=1:6for j=1:6,if(j-i)=0,for k=1:6,if(k-i)*(k-j)=0,for l=1:6,if(l-i)*(l-j)*(l-k)=0,for m=1:6,if(m-i)*(m-j)*(m-k)* (m-l)=0,for n=1:6,if(n-i)*(n-j)*(n-k)* (n-l)*(n-m)=0,p=p+1;x(p,:)=i j k l m n;endendend endendend下一页上一页下一页上一页下一页上一页endendendendend f=1 1 2 2 3 3; for p=1:

7、720o=x(p,:);cost=0;a=a0;for i=1:6j=o(i);aa=a;aa(f(j)=;if f(j)=3cost=cost+r*aa(1)*aa(2);elsecost=cost+aa(1)*aa(2);enda(f(j)=a(f(j)-d(j);endc(p)=cost; end minc=min(c),find(c=minc);minx=x(ans,:) 下一页上一页下一页上一页下一页上一页执行后输出 最小切割费用 minc =374 最优切割顺序 minx =5 3 1 6 4 25 3 6 1 4 2即当r=1,e=0时最优切割顺序有两条，它们分别是“下前左上后右

8、”和“下前上左后右”，最小切割费用为374元。当e0时，模型为（1）式，即下一页上一页下一页上一页下一页上一页由于垂直切割的方向有两个，因此至少调整一次刀具，而垂直切割共进行四次，故调整刀具的次数至多，于是额外费用有e，2e，3e，三种可能。所以我们把全体切割顺序按刀具的调整费用分类，共分三类，同类的刀具调整费用是相等的，故可先分别求出在e=0时每一类的最小费用及加工顺序，再将每一类的最小切割费用加上相应的刀具调整费用，便得到总的加工费用，从而比较各类加工顺序求出整体最优的加工顺序。下面给出MATLAB计算程序。1）计算出三类可行的加工顺序及相应的切割费用表；2）对每一个最小费用的切割顺序，与

9、刀具调整费用结合考虑；3）求出总的费用最小时的切割顺序及调整刀具次数。 下一页上一页下一页上一页下一页上一页%截断切割ch712 %文件名：ch712.m function minc,minx1,minx2,minx3=cutorde(a0,a1,d1,r) minc=inf,inf,inf;minx1=;minx2=;minx3=; k1=0;k2=0;k3=0; v1=1 2 3 4 5 6; %建立可行的加工顺序表 x1 ,x2, x3及相应的切割费用表 for i1=1:6,o1=v1(i1);v2=v1;v2(i1)=;for i2=1:5,o2=v2(i2);v3=v2;v3(i2

10、)=;for i3=1:4,o3=v3(i3);v4=v3;v4(i3)=;for i4=1:3,o4=v4(i4);v5=v4;v5(i4)=;for i5=1:2,o5=v5(i5);o6=v5(3-i5);x=o1,o2 o3 o4 o5 o6;c=cost(x,a0,a1,d1,r);z=adjustnum(x);switch zcase 1,k1=k1+1;x1(k1,:)=x;c1(k1)=c;case 2,k2=k2+1;x2(k2,:)=x;c2(k2)=c;case 3,k3=k3+1;x3(k3,:)=x;c3(k3)=c;下一页上一页下一页上一页下一页上一页end end

11、endendend end minc=min(c1) min(c2) min(c3);find(c1=minc(1); minx1=x1(ans,:);find(c2=minc(2); minx2=x2(ans,:);find(c3=minc(3); minx3=x3(ans,:);下一页上一页下一页上一页下一页上一页%求切割费用的子函ch713.m function c=cost(x,a0,a1,d1,r) c=0; d2=a0-a1-d1;a=a0; for p=1:6switch x(p)case 1,c=c+a(2)*a(3);a(1)=a(1)-d1(1);case 2,c=c+a(

12、2)*a(3);a(1)=a(1)-d2(1);case 3,c=c+a(1)*a(3);a(2)=a(2)-d1(2);case 4,c=c+a(1)*a(3);a(2)=a(2)-d2(2);case 5,c=c+r*a(1)*a(2);a(3)=a(3)-d1(3);case 6,c=c+r*a(1)*a(2);a(3)=a(3)-d2(3);end end下一页上一页下一页上一页下一页上一页%求调整刀具次数的子函数ch714.m function z=adjustnum(x) z=-1;v0=0; for p=1:6if x(p)4.5 %除掉高差为5的情况 下一页上一页下一页上一页下

13、一页上一页g1=0; else h1=a1; if abs(a1-a2)0.5 h2=a2; elseif abs(a2-a3)0.5 h2=a3; elseif abs(a3-a4)0.5 h2=a4; elseif abs(a4-a5)0.5 h2=a5; end %除去只有二个高差的情况 if abs(a3-h1)*(a3-h2)+abs(a4-h1)*(a4- h2)+ abs(a5-h1)*(a5-h2)jnumjnum=mjnum;jno=mjno;ydian=-i,-j;endend endfunction jnum,jno,ydian,jiao=zjing2(dianxy,wc

14、e) jnum=0;ttdiannum=size(dianxy,2);下一页上一页下一页上一页下一页上一页%直角坐标化为极坐标ch732.m dianjb=zeros(2,ttdiannum); newdianxy=zeros(2,ttdiannum); dianjb(1,:)=sqrt(sum(dianxy.2); dianjb(2,:)=atan(dianxy(2,:)./dianxy(1,:);%开始搜索 for h=0:pi/360:pi/2%逆时针旋转h度角fujiao=dianjb(2,:)-h;newdianxy(1,:)=dianjb(1,:).*cos(fujiao);new

15、dianxy(2,:)=dianjb(1,:).*sin(fujiao); 下一页上一页下一页上一页下一页上一页%在旋转后的直角坐标中搜索newdiany=newdianxy(2,:);for i=0:wce/2:1newdianxy(1,:)=newdianxy(1,:)+i;%x zhou come backnewdianxy(2,:)=newdiany;for j=0:wce/2:1mjnum=0; mjno=;newdianxy(2,:)=newdianxy(2,:)+j;gedianxy=round(newdianxy);distance=newdianxy-gedianxy;下一页上一页下一页上一页下一页上一页for k=1:ttdiannumif distance(1,k)2+distance(2,k)2jnumjnum=mjnum;jno=mjno;ydian=-i,-j;jiao=h*180/pi;endendend end下一页上一页下一页上一页下一页上一页执行后输出 问题一(ch731.m) 可利用井数 jnum=4 井号：2 4 5 10 移动值为 0.3500, -0.1500 问题二(ch732