发布时间 : 星期日 文章2011高教社杯全国大学生数学建模竞赛B题（题目改变）参考答案更新完毕开始阅读3eaa301cfe4733687f21aa0c
其中，xij取0或1，xij?1表示第i号平台去封锁j号出口。 封锁全市的出口的所用的距离为
??distancexj?1i?11780ijij
我们要求最短距离，所以目标函数为：
min??distancexj?1i?11780ijij
由于一个出口只能由一个交巡警平台去封锁，所以应满足条件
?xi?180ij?1(j?1,2,17,17)；而且一个交巡警平台只能封锁一个或者零个出口，
所以应满足条件?xij?1j?1(i?1,2,,80)。
综上，可以建立模型如下：
min??distancexj?1i?11780ijij
?80??xij?1(j?1,2,?i?1s..t ?17??x?1(i?1,2,ij?j?1?5.2.2 模型的求解
5.2.2.1 距离矩阵的求解（Floyd算法）
输入：邻接矩阵A 输出：最短距离矩阵D 1) 初始化：D[u,v]?A[u,v] 2) For k:1 to n For i:1 to n
,17)
,80) For j:1 to n
If D[i,j]?D[i,k]?D[k,j] then D[i,j]?D[i,k]?D[k,j];
3) 算法结束
5.2.2.2 分配矩阵X的求解
本题明显是任务分配问题，所以便直接采用现有的算法——匈牙利算法直接求解[1]。
输入：距离矩阵distance(即效益矩阵) 输出：分配矩阵X
4
Step1:变换效益矩阵,使新矩阵中的每行每列至少有一个0.
（1）行变换:找出每行最小元素,再从该行各元素中减去这个最小元素. （2）列变换:从所得新矩阵中找出每列中的最小元素,再从该列各元素中减去这个最小元素.
Step2:进行试指派,以寻找最优解. （1）逐行检查
从第一行开始,如果该行只有一个零元素,就对这个零元素打上括号,划去与打括号零元素同在一列的其他零元素,如果该行没有零元素,或有两个或多个零元素（已划去的不计在内）,则转下行.
打括号的意义可理解为该项任务已分配给某人.如果该行只有一个0,说明只能有唯一分配.划掉同列括号零元素可理解为该任务已分配,此后不再考虑分配给他人.当该行有两个或更多的零元素时,不计括号内的,其理由是至少有两个分配方案,为使以后分配时具有一定的灵活性,故暂不分配.
(2）逐列检查
在行检查的基础上,由第一列开始检查,如果该列只有一个零元素,就对这个零元素打括号,再划去与打括号零元素同行的其它零元素.若该列没有零元素或有两个以上零元素,则转下一列.
（3）重复（1）、（2）两步后,可能出现以下三种情况:
① 每行都有一个零元素标出括号,显然打括号的零元素必然位于不同行不同列,因此得到最优解.
② 每行每列都有两个或两个以上的零,这表示对这个人可以分配不同任务中的任意一个.这时可以从所剩零元素最少的行开始,比较这行各零元素所在列中元素的个数,选择零元素少的那列这个零元素打括号,划掉同行同列的其他它零元素,然后重复前面的步骤,直到所有0都作了标记.
③ 矩阵中所有零都作了标记,但标有(0)的元素个数少于m个,则转下步. Step3:做最少的直线覆盖所有零元素,以确定该系数矩阵中能找到最多的独立0元素.
· 对没有（）的行打√;
5
· 对打√的行上所有含0元素的列打√; · 再对打√的列上有（）的行打√; · 重复上两步,直到过程结束;
· 对没有打√的行划横线,对所有打√的列划垂线. 这就得到了能覆盖矩阵中所有0元素的最少直线数. Step4:非最优阵的变换——零元素的移动.
（1）在没有被直线覆盖的所有元素中,找出最小元素; （2）所有未被直线覆盖的元素都减去这个最小元素; （3）覆盖线十字交叉处的元素都加上这个最小元素; （4）只有一条直线覆盖的元素的值保持不变.
Step5:回到Step2,反复进行,直到矩阵中每行每列都有一个打（）的0元素为止,即找到最优解.
通过Matlab编程，我们得到如下结果： 交巡警平台路口编号 96 99 177 175 178 323 181 325 328 386 322 100 379 483 484 485 479 封锁城市出口路口编号 151 153 177 202 203 264 317 325 328 332 362 387 418 483 541 572 578 两者之间的距离（mm） 136.7433169 137.7727033 0 720.6915699 260.9737384 280.7569901 389.9959925 0 0 170.1597281 295.2729349 192.0129215 227.4081328 0 270.0635828 136.4331338 341.7491166 全部封锁的时间为上表中的最大距离（720.6915699）除以速度60 0mm/h(按比例尺等效过后的速度)，为1.2012小时，显然不合常理，通过观察上表的最后
6
一列，我们发现720.6915699远远大于周围的数，如果能够减小这个数，那么封锁整个城市的时间就会降下来。
从这个结果显示来看：在编号为175的路口应该设置一个交巡警平台，这样可以大大减少封锁全市的时间。
下表给出每个出口被封锁所花费的时间： 出口路口位置 151 153 177 202 203 264 317 325 328 332 362 387 418 483 541 572 578 所用封锁时间（h） 0.227906 0.229621 0 1.201153 0.434956 0.467928 0.649993 0 0 0.2836 0.492122 0.320022 0.379014 0 0.450106 0.227389 0.569582 六、模型的评价与推广
6.1 模型优点
1、对题目所给数据大部分都进行了合理的应用和处理，对于实际问题理解的较为到位。
2、模型建立的思路简单清晰，算法较为灵活、执行效率教高。
3、模型能应用于其他种类的应急设施设置，整个模型有很好的通用性。 6.2 模型缺点
1、在整个模型中我们都把所有的平台或者出口想象成一个点，这是在显示中不可能的。
2、模型中我们没有交通的堵塞的问题，认为出警速度是一致的。
7