西工大2013年数学建模竞赛A题 二等奖论文.doc

一、问题重述:
全球化竞争的加剧促使越来越多的企业开始采用供应链管理策略,以实现企业的一体化管理。供应链是一个复杂的网状结构系统,每一部分都面临着各种潜在的风险,任何一部分出现问题都可能给整个供应链带来严重的影响,因此如何分析、评价和提高供应链系统的可靠性变得日益迫切。
设施系统是供应链的核心,在供应链研究中有着极其重要的地位。在一个设施系统中,某些个设施由于自然灾害或者其他因素的影响可能失效,例如911恐怖袭击事件、2004年的印度洋海啸、2008年的汶川地震等都对诸多行业的设施系统造成了严重的破坏。
现有某物流公司要在全国各城市之间建立供应链网络。需要选定部分城市作为供应点,将货物运输到各城市。通常每个供应点的货物是充足的,可以充分满足相应城市的需求。
设该公司考虑共考虑49个城市的网络,城市的坐标见表1。城市之间的道路连接关系见表2。在每个城市建立配送中心的固定费用和需求量表3,并假定作为供应点的城市其供应量可以满足有需要的城市的需求。现将要建立一个供应网络,为各城市提供货物供应。货物运输利用汽车进行公路运输。。现提出如下问题:
现在要从49个城市中选取部分城市做为供给点供应本城市及其它城市。建立供给点会花费固定费用,从供应点运输到需求点会产生运输费用,要使总费用最小,问建立多少个供应点最好。给出选中作为供应点的城市,并给出每个供应点供应的城市。同时根据坐标作出每一个供应点到需求点的连接图。
假定有某组织对该供应网络的道路进行破坏。并非所有的道路都可以被破坏,可破坏的道路见表4。当某条道路被破坏后,该条道路就不能再被使用,以前运输经过该道路的只有改道,但总是沿最短路运输。如果破坏方选取的策略是使对方总费用增加25%,而每破坏一条道路都需要成本和代价,因此需要破坏最少的道路。问破坏方选取哪几条线路进行破坏。给出具体的破坏道路和总费用。
假定各道路能否被破坏具有随机性,当某条道路被破坏后,该条道路就不能再被使用,以前运输经过该道路的只有改道,但总是沿最短路运输。由于破坏方选取一些边进行破坏时,这些边不一定被破坏,而是服从一定的概率分布。设可破坏的边及各边破坏的概率见表4。运输时产生的费用可按照各种情况下的平均费用来考虑。如果破坏方选取的策略是使对方平均总费用至少增加100%,同样需要破坏最少的道路。问破坏方将选取哪几条线路进行破坏。给出具体的破坏道路和平均总费用。
二、问题的基本假设与说明:
. 假设题目所给的数据真实可靠
. 假设所有城市之间均可以通过公路交通进行物资运输
. 假设各个城市之间的直线距离即它们之间的公路长度,仅将城市的坐标作图使用
. 假设问题2中对任意道路破坏的成功率为百分之百
. 假设破坏方是一个实际的组织,会从现实的角度考虑破坏计划的实施
,海啸等自然灾害的影响
. 假设在运输过程中不出现交通事故等影响运输的其他人为因素
三、符号说明:
. ——目标函数,即为总费用
. ——用最优方案给i点运输的运费
. ——第i个城市点建站的0 1变量
. ——第i个城市的需求量
. ——城市i的建站费用
. ——i点到j点的最短公路长度
. ——i点到建站点的最短公路长度(当=1时,=0)
四、模型的建立与求解:
. 问题1:
:
通过对问题的分析与数据的整理,可以根据Floyd算法求出任意两个城市之间的最短公路长度,得到一个49×49的矩阵D。
(1)Floyd算法的基本思想是:
递推产生一个矩阵序列 A0,A1,A2,……Ak,……,An,其中表示从顶点到顶点的路径经过的顶点序号不大于k的最短路径长度。计算用的迭代公式: (i,j)=min((i,j),(i,k)+(k,j)) 其中,k 表示迭代次数, i,j,k∈{1,2,3„,n} 得出i区到j区的最短距离矩阵 D, 当k=n时,即是各项之间的最短距离。
每个数字的列标就表示两个城市,而数字本身就表示这两个城市之间的最短公路长度,如:
D(i,j)=a
即表示i城市与j城市之间的最短运输长度为a,而
D(i,j)=D(j,i)
即该矩阵本身是一个对称矩阵,且D(a,a)=0.
求出最短公路长度的矩阵之后,就可以进一步解决设置供给点的问题。根据题意,原本来说从49个城市中选取n个作为供给点,一共是有种方案,但是由于某些城市的建站费用过高,不适合建立供给点,通过剔除,由成本出发考虑,一共有28个城市可以作为供给点,也就表明其中21个无法建站的城市的Pi值恒为0。假设从这28个城市中选取n个作为供给点