西北工业大学数学建模竞赛A题.docx

1、西北工业大学数学建模竞赛A题装 订 线第十四届西北工业大学数学建模竞赛暨全国大学生数学建模竞赛选拔赛题目A题密封号2013年5月2日剪 切 线密封号2013年5月2日 动力与能源 学院 第 队队员1队员2队员3姓名白鸽格贾海燕贺晓娟班级070112020701120507021201装 订 线摘 要摘要中要把文章中模型的方法、思想、技巧、结论体现出来。（一页之内）本文是一个寻找供应点和最佳路线的问题，可以转化为动态规划求最优解问题。首先关键词：研究对象 建立模型 求解算法 等专业术语一、 问题重述1.1. 背景资料与条件全球化竞争的加剧促使越来越多的企业开始采用供应链管理策略，以实现企业的一体

2、化管理，提高效益。然而供应链是一个复杂的网状结构系统，每一部分都面临着各种潜在的风险，而设施系统是供应链的核心，在一个设施系统中，某些个设施由于自然灾害或者其他因素的影响可能失效，从而使得企业成本增加，并直接影响国民经济的增长。因此，供应链网络的建立与道路破坏问题亟待解决。 现有某物流公司要在全国各城市之间建立供应链网络，该网络共包含49个城市，选定其中部分城市作为供应点，将货物运输到各城市。现已知各个城市的坐标，部分城市之间的道路连接关系以及在每个城市建立配送中心的固定费用和需求量，建立一个供应网络，为各城市提供货物供应。货物运输利用汽车进行公路运输，且每吨每公里运输费用为0.5元。1.2.

3、 需要解决的问题1. 从49个城市中选取部分城市做为供给点供应本城市及其它城市。建立供给点会花费固定费用，从供应点运输到需求点会产生运输费用，现需建立一个供应网络，使得总费用最小，同时给出选中作为供应点的城市以及数量，并根据坐标作出每一个供应点到需求点的连接图。2. 假定有某组织对该供应网络的道路进行破坏。可破坏的道路见表4。当某条道路被破坏后，之前运输经过该道的必须沿最短路改道运输。已知每破坏一条道路都需要成本和代价，要使破坏后公司的总费用增加25%，并破坏最少的道路。应选取哪几条线路进行破坏，并给出具体的破坏道路和总费用。 3. 当每条道路被随机破坏后，之前运输经过该道路的沿最短路改道运输

4、。由于破坏方对所选取边进行破坏时，服从一定的概率分布（见表4）。运输时产生的费用可按照各种情况下的平均费用来考虑。要使公司平均总费用至少增加10%，并破坏最少的道路。应选取哪几条线路进行破坏，并给出具体的破坏道路和平均总费用。二、 问题分析1.3. 1. 2. 2.1. 问题的重要性分析： 随着交通运输业的发展，很多物流企业在蓬勃兴起，但由于地形地貌的原因，很多城市之间无法直达，给物流企业带来高成本的巨大压力。而供应链管理策略的提出使问题迎刃而解。它不仅计算出运输的最短路径，还优化了建立物流站点的方案。可以根据具体情况制定出最优方案，提高企业效率，实行管理一体化，促进国民经济增长。2.2. 问

5、题的思路分析由题目内容可知，该题属于动态规划求最优解问题。假设每个城市为一个顶点，任意两城市之间的公路可用两点间的有向线段来表示。首先通过每个城市的坐标（见附录2）以及仅有的102条公路（见附录2）绘制出公路网络图（图1）。再通过FLOYD算法在Vissual C+6.0的编程环境中对附录2中的数据进行处理，计算出任意两个城市之间的最短距离。最终建立”0/1规划最优模型“，得出所有符合条件的供应方案，通过附录三中供货数量以及供应点的固定费用，编写程序计算出每种方案的总费用，找出其最小值即可。三、 基本假设3. 3.1. 模型一假设1) 假设一：假设附录中所给数据均合理。2) 假设二：假设每个供

6、应点的货物是充足的，可以充分满足相应城市的需求。3) 假设三：假设任意两个城市之间只有公路运输这一个途径。4) 假设四：假设运输费用与固定费用都不随外界因素变化而变化。5) 假设五: 假设破坏每条道路的成本和代价都是相同的（该假设的合理性体现在题目中对可破坏道路的随机选择）3.2. 模型二假设1) 假设一；2) 假设二；3) 假设三；（文中某处证明了该假设的合理性）4) 。3.3. 本文引用数据、资料均真实可靠。四、 符号说明4. 4.1. 模型一符号说明A： 名称，解释；B： 名称，解释；C： ；。4.2. 模型二符号说明A： 名称，解释；B： 名称，解释；C： ；。五、 模型的建立与求解5

7、. 5.1. 模型的建立1. 2. 3. 4. 5. 5.1. 5.1.1. 模型概述所谓“0/1规划最优模型”，即建立一个51*51的二维数表，对其进行0/1随机赋值（“0”表示两城市之间无供应和被供应关系；“1”表示两城市之间存在供应关系），由于一些城市不能作为供应点，故该数表可简化31*51的二维数表，通过约束条件对产生的任意供应方案进行筛选，得出所有可能的供应模式。5.1.2. 模型的运用与求解 1) 城市公路网络图： 2) 求解任意两个城市之间的最短距离： dNN 表示任意两点之间的距离； rNN 表示两点之间的插入点；（1）赋初值:对所有i,j, d(i,j) w(i,j), r(

8、i,j) j, k 1.（2）更新d(i,j), r(i,j): 对所有i,j,若d(i,k)+d(k,j)d(i,j), 则 d(i,j) d(i,k)+d(k,j), r(i,j) k.（3）若k=v，停止否则k k+1，转(2)源程序：/用Microsoft Visual C+6.0编程Floyd.cpp如下：/Floyd.cpp#include #include #include math.h#define N 6#define inf 10000000000000000int main() FILE *fp; int i,j,k; int rNN=0; double dNN=0,12

9、0,270,inf,540,799,inf,inf,inf,inf,inf,inf,inf,inf,420,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,844,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf 120,0,370,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,infinf,inf,inf,inf,inf,inf,inf,inf,inf,inf,i

10、nf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,infinf,inf,inf,inf 270,370,0,210,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,311,440,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf inf,inf,210,0,530,in

11、f,inf,inf,inf,inf,inf,inf,inf,inf,inf,430,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,630,inf,inf,760,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf 540,inf,inf,530,0,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,720,inf,inf,

12、inf,inf,inf,inf,inf,inf,inf,1521,inf,inf,inf,inf,inf,inf,186,inf,inf 799,inf,inf,inf,inf.0,330,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,387,727,inf,inf,inf,inf,inf,inf,inf,inf,inf inf,inf,inf,inf,inf,330,0,230,inf,inf

13、,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,429,347,inf,iinf,inf,inf,inf,inf,inf,inf inf,inf,inf,inf,inf,inf,230,0,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,

14、inf,inf,inf,inf,inf,819,inf,inf,inf,inf,inf,inf,inf inf,inf,inf,inf,inf,inf,inf,inf,0,280,190,inf,inf,inf,840,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf inf,inf,inf,inf,inf,inf,inf,inf,280,0,279,160,inf,660,

15、680,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,598,inf,inf,inf,inf,325,inf,inf,inf,inf,inf,inf inf,inf,inf,inf,inf,inf,inf,inf,190,279,0,inf,880,640,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,153,inf,inf,inf,in

16、f,inf,inf,inf,inf,inf,inf,inf,inf inf,inf,inf,inf,inf,inf,inf,inf,inf,160,inf,0,inf,610,inf,650,540,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,435,inf,inf,inf,inf,inf,inf,inf inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,880,inf,0,680,inf,inf,inf,inf,10

17、20,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,490,inf,inf,inf,266,592,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf inf,inf,inf,inf,inf,inf,inf,inf,inf,660,640,610,680,0,inf,inf,270,640,860,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf

18、,inf,inf,inf,inf 420,360,311,inf,inf,inf,inf,inf,840,680,inf,inf,inf,inf,0,430,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,361,inf,inf,inf,inf,349,inf,inf,inf,inf,inf,inf inf,inf,440,430,inf,inf,inf,inf,inf,inf,inf,650,inf.inf.430,0,540,inf,inf,inf,inf,inf,inf

19、,inf,inf,inf,550,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,473,285,inf,inf,inf,inf,inf inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,540,inf,270,inf,540,0,380,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,406,362,inf,inf,inf,inf i

20、nf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,640,inf,inf,380,0,780,inf,inf,inf,inf,1010,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,508,inf,inf,664,inf inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,1020,860,inf,inf,inf,780,0,710,580,inf,inf,inf,inf,inf,inf

21、,inf,inf,inf,inf,inf,inf,130,127,688,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,0,560,inf,inf,650,820,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,305,inf inf,inf,inf,inf,i

22、nf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,580,560,0,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,0,340,490,1090,inf,910,inf,inf,inf,inf,

23、inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,795,inf,inf,inf,inf inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,340,0,inf,990,2170,920,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf inf,inf,inf,inf,inf,inf,inf,inf,i

24、nf,inf,inf,inf,inf,inf,inf,inf,inf,1010,inf,650,inf,490,inf,0,650,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,560,inf inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,820,inf,1090,990,650,0,2320,inf,inf,inf,inf,inf,inf,inf,inf,in

25、f,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,2170,inf,2320,0,inf,inf,1940,inf,2672,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf inf,inf,inf,630,inf,inf,inf,inf,inf,inf,inf,

26、inf,inf,inf,inf,550,inf,inf,inf,inf,inf,910,920,inf,inf,inf,0,700,inf,640,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,637,inf,304,inf,inf,inf inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,700,0,230,500,1980,inf,inf,inf,inf,inf,inf,inf

27、,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,1940,inf,230,0,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf inf,inf,inf,760,720,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,

28、inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,640,500,inf,0,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,2870,inf,1980,inf,inf,0,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,in

29、f,inf,inf,inf,inf,inf,inf,inf inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,490,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,0,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,

30、inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,0,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,130,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,0,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,

31、inf,inf,inf inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,127,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,0,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,266,inf,inf,inf,inf,inf,688,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,0,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,inf inf,inf,inf,inf,inf,inf,inf,inf,inf,inf,153,inf,592,inf,inf,inf,inf,inf,i