数学应用实践..ppt

第0步：初始化 function [weight,tree,p]=mintree2(w,v0) n=size(w,1);%顶点个数 label=inf*ones(1,n);%标记各顶点与子树邻接边上最小的边权 sb=1:n; labsb=inf.*sb;%待确定集，及其各点标记 father=zeros(1,n);%father(u)记录优选的与u连接的顶点 p=ones(1,n);%每一步被选入确定集合中的顶点 tree=[];%树枝 u=v0;label(v0)=0;father(1)=v0;p(1)=v0； sb(v0)=[];labsb(v0)=[]; %最小树树根从v0点开始 le=length(sb);k=1; while le~=0 for i=1:le %考察待确定集中所有点 v=sb(i); if w(u,v)=label(v) label(v)=w(u,v); labsb(i)=label(v);father(v)=u; end end [y,s]=min(labsb); u=sb(s); %s是待定集中到确定集最近的点 sb(s)=[];labsb(s)=[]; %在待定集除去s le=length(sb); k=k+1;p(k)=u; tree=[tree [father(u) u w(father(u),u)]]; end weight=sum(tree(3,:)); 1997 B 题截断切割 某些工业部门，如贵重石材加工等，采用截断切割的加工方式，这里的截断切割，是指将物体沿某个切割平面分成两部分，从一个长方体中加工一个已知尺寸，位置预定的长方体（这两个长方体的对应面是平行的），通常要经过6 次截断切割。设水平切割单位面积的费用是垂直切割单位面积费用的r 倍，且当先后两次垂直切割的平面，不管它们之间是否穿插水平切割，不平行时，因调整刀具需额外费用。 试为这些部门设计一种安排各面加工次序（称… 切割方式）的方法，使加工费用最少(由工艺要求，与水平工作台接触的长方体底面是事先指定的),详细要求如下： 1 需考虑的不同切割方式的总数。 2 给出上述问题的数学模型和求解方法。 3 试对某部门用的如下准则做出评价，每次选择一个加工费用最少的切割面进行切割。 4 对于 e=0 的情况有无简明的优化准则。 5 用以下实例验证你的方法： 待加工长方体和成品长方体的长，宽，高分别为10，14.5,19 和3,2,4,两者左侧面，正面，底面之间的距离分别为6,7,5(单位为厘米，垂直切割费用为每平方厘米1 元，r 和e 的数据有4 组： 1) r=1, e=0; 2) r=1.5, e=0; 3) r=8, e=0; 4) r=1.5, 2 ≦ e ≦ 15 ; 对最后一组数据应给出所有最优解,并进行讨论. 分析 毛坏、成品均为长方体，且这两个长方体的对应面是平行的， 切割费用与切割面积成正比，水平切割r元/cm^2,垂直切割1元/cm^2, 换方向加调整费e元 工作台水平接触长方体底面 第一次切割不计刀具调整费 模型 将加工过程中所有可能的状态用6维向量。6各分量分别表示左右、前后、上下是否被切割，是则取值1，否则取值0。例如，毛胚状态(000000)，成品状态(111111)，已切除右侧，前面和下面的毛胚状态为(011001)。 将 一个状态表示为一个顶点，共有2^6=64个顶点。 从一个状态经切割转移到另一个状态，构成一条有向边，切割费用为该边的权。 从毛胚(000000)到成品(111111)的有向路代表了一个切割过程，有向路的权就是加工费用。 于是，最小费用切割问题的数学模型： 求赋权有向图G=(V,E,w)从顶点(000000)到顶点(111111)的最短路。 进一步，如果只考虑平行切割边距大者先切割，足以保证切割面积最小，并可用3维数组代替6维数组，(x,y,z)分别表示左右、前后、上下状态，未被切割取值0，边距大的部分已被切割取值1，两边都切割好取值2。这样顶点个数为3^3=27. 于是，最小费用切割问题的数学模型： 求赋权有向图G’=(V’,E’,w’)从顶点(000)到顶点(222)的最短路。 a0=[10 14.5 19];%毛胚的长、宽、高 a1=[3 2 4];%成品的长、宽、高 d1=[6 7 9];%左、前、底的边距 r=1;e=0; d2=a0-a1-d1;%右、后、上的边距 切除后a=(a(1) a(2) a(3)) 水平面积a(1)*a(2),垂直面积 a(1)*a(3)或a(2)*a(3) 程序片段 %构造顶点集 ver