北京工业大学数学建模作业5.doc

数学建模作业51设备购置问题 某单位计划购买一台设备在今后4年内使用。可以在第一年初购买该设备，也可以在任何一年末将设备卖掉，于下年初更换新设备。表1和表2给出各年初购置新设备的价格、设备的维护费及卖掉旧设备的回收费。问如何确定设备的更新策略，使4年内的总费用最少？表1 第1年 第2年 第3年 第4年 年初购置价/万元 2.5 2.6 2.8 3.1 表2 设备役龄 01 12 23 34 年维护费/万元 0.3 0.5 0.8 1.2 年末处理回收费/万元 2.0 1.6 1.3 1.1解：分类讨论：只用一台，花钱：购置：2.5维护：0.3+0.5+0.8+1.2四年后卖了得1.1共支出:2.5+0.3+0.5+0.8+1.2-1.1=4.2万元用两台:分两种:一:各用两年,购置:2.5+2.8维护:2*(0.3+0.5)卖了得:2*1.6共支出:2.5+2.8+2*(0.3+0.5)-2*1.6=3.7万元二,一个一年,一个三年,分两类:1.先三年购置:2.5+3.1维护:0.3+0.3+0.5+0.8卖了得:2.0+1.3共支出:2.5+3.1+0.3+0.3+0.5+0.8-(2.0+1.3)=4.22.先一年购置:2.5+2.8维护:0.3+0.3+0.5+0.8卖了得:1.3+2.0共支出:3.7三,用三台分三类:第三台两年购置:2.5+2.6+2.8维护:0.3+0.3+0.3+0.5卖了得:2.0+2.0+1.6共支出:3.7第二台两年:购置:2.5+2.6+3.1维护:0.3+0.3+0.3+0.5卖了得:2.0+2.0+1.6共支出:4.0第一台两年:购置:2.5+2.8+3.1维护:0.3+0.3+0.3+0.5卖了得:2.0+2.0+1.6共支出:4.2四台:购置:2.5+2.6+2.8+3.1维护:0.3*4卖了得:2.0*4共支出:4.2所以方案是:先买一台,两年更换,或者先买一台,第二年再一台,第三年再一台,共三台或者先一台,第二年换都是花费3.7万!2生产计划与库存管理解：3指派问题分配甲、乙、丙、丁四个人去完成五项任务。每人完成各项任务时间如表5-2所。由于任务数多于人数，故规定其中有一个人可兼完成两项任务，其余三人每人完成一项。试确定总花费时间为最少的指派方案。表5-2 任务人ABCDE甲乙丙丁2539342429382742312628364220402337333245解：加工假设的第五个人是戊，他完成各项工作时间去甲、乙、丙、丁中最小者，构造表为5A-4表5A-4 任务人ABCDE甲乙丙丁戊25393424242938274227312628362642204023203733324532对表5A-4再用匈牙利法求解，得最优分配方案为甲-B，乙-D和C，丙-E，丁-A，总计需要131小时。代码如下：model:sets:person/1.4/;job/1.5/;arrange(person,job):time,x;endsetsdata:time=25 29 31 42 3739 38 26 20 3334 27 28 40 3224 42 36 23 45;enddatamin=sum(arrange:time*x);for(person(i):sum(job(j):x(i,j)=1);for(job(j):sum(person(i):x(i,j)=1);for(arrange:bin(x);End4旅行商问题5最优连线问题6最大流问题7加分实验（所的税缴纳选址）所得税管理部门计划对某个地区中的所得税交纳点网络进行重新设计。下图1是对此地区内的城市和主要道路的示意图。城市旁边的黑体数字表示城市的居民数目，单位为千人。在连接城市之间的弧上标出了它们之间的距离，单位为千米（斜体字）。为覆盖各个城市，所得税管理部门决定在三个城市中设置纳税点。 问题：应在哪三个城市中设置纳税点才能够使居民与最近的纳税点之间平均距离最小？图1 此区域内的城市和道路图2 问题的分析本问题的目标是从一个由多个城市组成区域内中，选出一定数目的城市设置纳税点, 建立所得税交纳点网络，实现居民与最近的纳税点之间平均距离最小。对于每个城市纳税点的建立与否只有两种可能，所以可以通过计算城市间的最短路径，然后充分利用地区的城市居民以及道路信息，采用合适的方法搜索纳税点；再确定各纳税点管辖的区域，直到求得最优解。本问题重点要解决如何选择纳税点和如何划分纳税区域，即建立合理的最优纳税点搜索和区域划分模型。由图1，得到地区内城市总数；计划设置的纳税点数目城市标号，。各城市的居民数、城市间道路信息如下表：表1 各城市的居民数城市标号123456789101112（千人）15101218524111613221920表2 道路信息城市标号123456从该城市出发的道路数324243与该城市直接相连的城市标号、及道路长度（千米，括号内内容）2（15）5（24）7（11）1（15）3（22）2（22）5（16）9（20）4（18）3（18）6（24）1（24）3（16）8（12）9（24）4（12）9（12）12(22）城市标号789101112从该城市出发的道路数346243 与该城市直接相连的城市标号、及道路长度（千米，括号内内容）1（18）8（15）10（22）5（12）7（15）9（30）11（25）3（20）5（24）6（12）8（30）11（19）12（19）77（22）11（19）8（25）9（19）10（19）12（21）6（22）9（19）11（21）城市标号123456从该城市出发的道路数324243与该城市直接相连的城市标号、及道路长度（千米，括号内内容）2（15）5（24）7（11）1（15）3（22）2（22）5（16）9（20）4（18）3（18）6（24）1（24）3（16）8（12）9（24）4（12）9（12）12(22）城市标号789101112从该城市出发的道路数346243 与该城市直接相连的城市标号、及道路长度（千米，括号内内容）1（18）8（15）10（22）5（12）7（15）9（30）11（25）3（20）5（24）6（12）8（30）11（19）12（19）77（22）11（19）8（25）9（19）10（19）12（21）6（22）9（19）11（21）3 模型假设为了便于建立模型，考虑了一些实际情况，做出了以下假设，假设系统满足如下一些条件：（1）各城市人口基本保持不变；（2）城市间至少有一条可到达的路径实现互连；（3）每个城市的居民只能到离该城市最近的纳税点缴税；（4）若与某些城市最近的纳税点有若干个，即其可能与若干个纳税点的距离相同且最邻近，为保证各纳税点工作负担波动不大，该城市的居民只能到最邻近的其中一个纳税点缴税；4 模型建立4.1模型一：0-1规划的穷举法模型该模型首先采用改善的Floyd-Warshall算法计算出城市间最短路径矩阵；然后，用0-1规划的穷举法获得模型目标函数的最优解。目标函数： （1）约束条件： ， （2）（3），（4） ， （5）， （6）表3 符号意义符号意义地区内城市总数计划设置的纳税点数目第个城市的标志城市的居民数城市和间可行的最短路径长度表示是否在城市设置纳税点；表示城市是否到城市纳税式（2）表示地区内有且仅有一个城市是城市的居民的缴税点；式（3）表示应开设个纳税点。式（4）表示若，则；若，则或；即表示只有在城市设置纳税点时，城市的居民才有可能去缴税。式（5）中，时，表示不在城市设置纳税点；时，表示在城市设置纳税点。式（6）中，时，表示城市不到城市纳税；时，表示城市到城市纳税。模型思路流程图为：图2 模型一的思路流程图4.2模型二：0-1规划的分区模型若已确定城市A、B为纳税点，城市C、D中居民分别属于B、A纳税点管辖范围，即。假设D中居民通过C到达A，则表示C到A的距离小于C到B的距离，这与实际情况相反。所以各纳税点管辖的区域相互独立，即D中居民到A的最短路径线路上，绝对不会包含B（）纳税点管辖的城市（如C）。如下图，粗线条表示D到A的最短路径：图3 各纳税点管辖的区域相互独立举例图根据各纳税点管辖的区域相互独立的原理，采用启发式搜索的方法分区，考虑到居民数较多且交通便利的两城市，一般不在同一纳税点缴税的实际情况，增加一些假设条件，本模型将利用这些假设条件指导搜索过程，实现合理的分区。分区后，各纳税点管辖的城市互不相关，最终获得若干分区方案；然后，分别求各个方案的最优解；最后，获得整个模型的全局最优解。其中，各方案的最优解求解方法为：先独立求各区域设置一个纳税区域时的最优解，然后各区域叠加，就可以获得该方案最优解。目标函数为：（7）约束条件：式（2）、（3）、（5）、（6）、 ， （8） ， （9） ， (10) ， (11)式中，：启发式搜索获得的方案数；：表示城市属于第个纳税区域。其余各符号意义，以及约束条件式（2）、（3）、（5）、（6）的意义均与模型一相同。式（8）表示城市属于且仅属于其中一个纳税区域。式（9）表示纳税区域有且仅有一个纳税点。式（10）表示只有城市、在同一区域，且在设置纳税点时，城市的居民才有可能去缴税。式（11）中时，表示城市不在区域纳税；时，表示城市在区域纳税。模型流程图为：图4 模型二的思路流程图4.3模型三：最近邻法分区模型本模型与模型二的目标函数相同。只是模型二是在一定的假设条件的基础上，采用启发式搜索指导分区，各区域相互独立。而本模型的初始纳税点和分区方法不需要很多额外的假设条件，充分利用了从各城市出发的道路数和居民数，而且各区域不需要相互独立，可能有若干城市属于两个或两个以上区域。模型流程图为：图5 模型三的思路流程图分区方法具体步骤如下：首先利用从各城市出发的道路数和居民数，确定初始化的N个纳税点。（1）第一步，对各城市按从城市出发的道路数由大到小进行排序；（2）第二步，剪枝，然后对于从城市出发的有效道路数相同的几个城市，按居民数由大到小排序；（3）第三步，选择排序结果的前N个城市作为初始的纳税点。其次，采用最近邻分类法，即根据其他城市与这N个纳税点的最短距离，确定其属于那个纳税区域，实现分区，获得分区结果A。然后，从分区结果A的各区域抽取一个城市作为纳税点，采用最近邻法对其他城市重新分区，直到遍历完分区结果A各区域包含的所有城市。5问题的求解5.1求解过程中采用的主要算法5.1.1 最短路径算法模型一、二、三均需要计算出两城市间距离矩阵，模型二还需要记录对应的最短路径，以便分区时作为参考条件。最短路径算法主要由改善的floyd-warshall算法实现，最后获得由任意两城市间距离矩阵和对应的最短路径。算法具体原理如下：step1：构造邻接矩阵。若城市和间无直接连通的道路，则令元素为正无穷大；否则为和直接连通的道路长度。具体步骤如下：step1_1：的值初始化为正无穷。step1_2：令 ，即的对角线元素设为0。step1_2：若城市和间有直接连通的道路，则令为该道路的长度。step2：获得两城市间距离矩阵和城市间的最短路径矩阵。、的元素分别表示为、， 对于所有的城市、和，如果，则令，（表示从城市到要经过城市，若，表示两城市可直达）。具体步骤如下：step2_1：令，为的同维零矩阵，；step2_2：若，执行下一步；否则，转向step2_8；step2_3：step2_4：若，执行下一步；否则，转向step2_1；step2_5：；step2_6：若，执行下一步；否则，转向step2_3；step2_7：若，则令，；城市通过最短路径到时，要经过城市，；转向step2_6。step2_8：得到距离矩阵和城市间最短路径矩阵，算法终止。流程图如下：图6 改善的floyd-warshall算法流程图5.1.2 启发式搜索算法启发式搜索算法将在模型二中使用，搜索的算法对该模型非常重要，搜索结果将直接指导分区过程。本模型采用的启发式搜索算法是在一些合理的假设条件下进行的，假设条件如下： （1）交通便利的城市，即从该城市出发的道路数多的城市，优先设置为分区的区域中心。（2）若干城市的交通状况相同，即从这些城市出发的道路数相同，则人数多的城市优先设置为分区的区域中心；（3）每个分区包含的城市数目相同或相差不大，即对于城市总数是要建立的纳税点数的整数倍的情况，各区包含城市数为。算法原理图如下：图8 启发式搜索流程图其中，从城市出发的有效道路数表示剪枝后的道路数（剪枝：把与区域中心相连的道路减去）。5.1.3 0-1规划算法模型一、二均需要利用0-1规划法求目标函数最优解，两模型0-1规划法原理相同，只是模型一是从个模型中求解出个最优纳税点，而模型二是从个城市中求解出一个最优纳税点。下面以模型一为例说明0-1规划法算法具体原理：step1：构造由各城市居民数构成的行向量，其元素表示为城市的居民数。step2：初始化最小距离加权和，为设置的三个交税点的加权和。step3：确定纳税点、各纳税区域，求得最小距离加权和。具体步骤如下：step3_1：；step3_2：若，执行下一步；否则，转向step3_12；step3_3：；step3_4：若，执行下一步；否则，转向step3_；step3_5：，表示选择的纳税点为城市、和；step3_6：若，执行下一步；否则，转向step3_4；step3_7：初始化各纳税区域组成的城市向量n1、n2、n3（n1、n2、n3设为长为的零向量），各区域包含的城市数c1、c2、c3（均设为0）,以及距离加权和，令；step3_8：若，执行下一步；否则，转向step3_6；step3_9：比较城市和假设的纳税点城市、和的距离，以确定的缴税点；Matlab程序如下： if (D(n,i)=D(n,j)&(D(n,i)=D(n,k) sum0=sum0+D(n,i)*P(1,n); c1=c1+1; n1(1,c1)=n; elseif (D(n,j)=D(n,i)&(D(n,j)=D(n,k) sum0=sum0+D(n,j)*P(1,n); c2=c2+1; n2(1,c2)=n; elseif(D(n,k)=D(n,i)&(D(n,k)=SUMbreak;endstep3_11：若，更新纳税点、各纳税区域和最小距离加权和；否则，执行下一步；部分Matlab程序如下：if sum0SUMSUM=sum0;%更新最小加权和node(1,1)=i;%更新选址点node(1,2)=j;node(1,3)=k;nn1=zeros(1,c1);nn1=n1(1,1:c1); %更新各纳税区域nn2=zeros(1,c2);nn2=n2(1,1:c2);nn3=zeros(1,c3);nn3=n3(1,1:c3);endstep3_12：，转向step3_6；step3_13：得到纳税点向量node、对应的各纳税区域向量nn1、nn2、nn3，求得最小距离加权和，算法终止。原理图如下：图8 01规划算法流程图5.2问题的具体求解5.2.1 用模型一求解该模型为线性规划模型，我们采用Matlab程序求解。step1：用Matlab编程实现的2.1中介绍的最短路径算法求出城市间的最短路径距离矩阵。step1_1：利用城市间道路信息，构造邻接矩阵。表 3 邻接矩阵（行标、列标均表示城市编号）列行 step1_2：获得两城市间距离矩阵和城市间最短路径矩阵。部分Matlab程序如下：%基于MATLAB的最短路Warshall-Floyd 算法 % Initializen=length(A); % Vertex numberD=A; % Distance matrixW=zeros(n); % Route matrix% Update distance matrix D and route matrix Rfor k=1:n % Iteration steps for i=1:n for j=i+1:n if D(i,k)+D(k,j)D(i,j) D(i,j)=D(i,k)+D(k,j); D(j,i)=D(i,j); W(i,j)=k; W(j,i)= W(i,j); end end end end 结果如表4、表5：表4 距离矩阵（行标、列标均表示城市编号）列行 表4 城市间最短路径矩阵（行标、列标均表示城市编号）列行 step2：用Matlab编程实现的2.2中介绍0-1规划法求得纳税点向量node、对应的各纳税区域向量nn1、nn2、nn3，求得最小距离加权和；部分Matlab程序如下：node=zeros(1,3);%选取的三个交税点，初始化for i=1:1:10 for j=i+1:1:11 for k=j+1:1:12 sum0=0; %初始化距离加权和 n1=zeros(1,10);n2=n1;n3=n1;%初始化的各纳税区域 c1=0;c2=0;c3=0;%初始化的各纳税区域城市数 for n=1:1:12 if (D(n,i)=D(n,j)&(D(n,i)=D(n,k) sum0=sum0+D(n,i)*P(1,n); c1=c1+1; n1(1,c1)=n; elseif (D(n,j)=D(n,i)&(D(n,j)=D(n,k) sum0=sum0+D(n,j)*P(1,n); c2=c2+1; n2(1,c2)=n; elseif(D(n,k)=D(n,i)&(D(n,k)=SUM break; end end if sum0SUM SUM=sum0;%更新最小加权和 node(1,1)=i;%更新选址点 node(1,2)=j; node(1,3)=k; nn1=zeros(1,c1);nn1=n1(1,1:c1);%更新各纳税区域nn2=zeros(1,c2);nn2=n2(1,1:c2);nn3=zeros(1,c3);nn3=n3(1,1:c3); end end endend结果如下：The weighted sum minmum is : 2438；The selected sites are : 1 6 11The selected districts are : 1 2 5 7 3 4 6 9 8 10 11 12即纳税点为城市1、6,、11；城市1、5、7到1缴税，城市3、4、9到6缴税，城市8、10、12到11缴税；求得最小距离加权和为2438（千米）。step3：求目标函数的最优解，即居民与最近的纳税点之间平均距离的最小值。Matlab程序如下： average=SUM/sum(P);fprintf(The weighted average minmum is :nn)disp(average)结果如下：The weighted average minmum is : 13.1784即居民与最近的纳税点之间平均距离的最小值为13.1784。5.2.2 用模型二求解step1：用Matlab编程实现的floyd-warshall算法求出城市间的最短路径距离矩阵和城市间最短路径矩阵。求解过程、结果同模型一。step2：用Matlab编程实现2.3中的启发式搜索算法，进行分区，获得各个区域城市集合；step2_1：用Matlab编程实现的冒泡排序法（程序在。），选择3个区域中心。step2_1_1：依据从各城市出发的道路数选择区域中心，更新从各城市出发的有效道路数。从表2知，从城市9出发的道路数最多，为6，则设置9为区域一的中心，如下图。更新从各城市出发的有效道路数，结果如表5。从城市1,3,5,7,8,11出发的有效道路数均为3，执行step2_1_2。图9 step2_1_1选择结果（图中用灰色标记的城市）表5 第一次搜索后从各城市出发的有效道路数结果城市标号123456789101112对应的有效道路数323232330232step2_1_2：依据城市1,3,5,7,8,11的城市居民数，从中选择新的区域中心，并更新从各城市出发的有效道路数。从表1知，其中城市11的居民数最多，为19，则设置11为区域二的中心，如下图。更新从各城市出发的有效道路数，结果如表6。从城市1,3,5,7出发的有效道路数均为3，执行step2_1_3。图10 step2_1_2后选择结果（图中用灰色标记的城市）表6 第二次搜索后从各城市出发的有效道路数结果城市标号123456789101112对应的有效道路数323232320101step2_1_3：依据城市1,3,5,7的城市居民数，从中再选择一个区域中心。从表1知，其中城市1的居民数最多，为15，则设置1为区域三的中心，如下图，3个区域的中心搜索完成。执行step2_2。图11 step2_1_3后选择结果（图中用灰色标记的城市）step2_2：根据step1获得最短路径距离矩阵和城市间最短路径，依次扩展搜索得到的区域三、二、一的中心，获得3个区域的城市集合。step2_2_1：扩展区域三的中心；图12（a）区域三step2_2_2：扩展区域二的中心；图12（b）区域二step2_2_3：扩展区域一的中心。图12（c）区域一最后获得的分区结果如下图：图13 分