徐州工程学院
数理学院
案例分析报告
课程名称运筹学及应用
案例分析题目救灾物资运输问题
专业
班级
姓名
学号
指导教师
成绩等级
目录
小组成员分工………………………………………………………………………一．问题描述………………………………………………………………………二．问题分析………………………………………………………………………三．模型建立………………………………………………………………………四．模型求解与程序设计………………………………………………………五．结果分析………………………………………………………………………
一．问题描述
在1998年的夏天,我国长江流域发生洪涝灾害,上海市政府紧急调运一批救灾物资运往灾区,帮助灾区人民度过困难。

但是从上海到灾区途中要经过至少三个不同城市，而且有许多不同的行驶路线，不同的行驶路线其路程长度不一。

时间紧，任务急，市政府召开紧急会议，研究一条最短的物资运输路线，以最快的速度将救灾物资运输到灾区人民的手中。

下图显示的网络就是从上海（节点A）至灾区（节点E）的公路网络，其中，节点1B、2B、3B为第一次可能经过的城市，节点1C、2C、3C为第二次可能经过的城市，节点1D、2D为第三次可能经过的城市，弧线上的数字表示两个相邻城市间公路的长度。

上海至灾区的公路网络图
二．问题分析
从A点出发有三种可以选择的方案：到B1，B2，B3，,如果只考虑一段内距离最短，可能为A-B1，A-B2，A-B3。

再从B1点出发，到C1，C2，C3，如果只考虑一段内距离最短，可能为A-B1-C1，A-B1-C2，A-B1-C3; 从B2点出发，到C1，C2，C3，如果只考虑一段内距离最短，可能为A-B2-C1，A-B2-C2，A-B2-C3; 从B3点出发，到C1，C2，C3，如果只考虑一段内距离最短，可能为A-B3-C1，A-B3-C2，A-B3-C3; 从C1点出发，到D1，D2，如果只考虑一段内最短，可能为A-B1-C1-D1，A-B1-C1-D2，A-B1-C2-D1，A-B1-C2-D2，A-B2-C1-D1 A-B2-C1-D2,
A-B2-C2-D1，A-B2-C2-D2， A-B3-C1-D1，A-B3-C1-D2，A-B3-C2-D1，A-B3-C2-D2,从D1点出发，如果只考虑一段内距离最短，可能为A-B1-C1-D1-E，A-B1-C2-D1-E, A-B2-C1-D1-E, A-B2-C2-D1-E，A-B3-C1-D1-E, A-B3-C2-D1-E。

从D2点出发，如果只考虑一段内距离最短，可能为A-B1-C1-D2-E，A-B1-C2-D2-E, A-B2-C1-D2-E, A-B2-C2-D2-E，A-B3-C1-D2-E, A-B3-C2-D2-E。

通过比较最终可以得到一条最短的路径。

采用逆序算法，可以简化上述过程。

这是一个多阶段决策问题，可以将全部过程化为四个阶段，每个阶段开始时确定一条路径，且上一阶段要对下一阶段产生影响，目标是使总路径最短。

从最后一个阶段向前反推，求解目标决策，从而得到最优的选择。

使上海市政府能够以最快的速度将救灾物资运输到灾区人民的手中。

三．模型建立
1、到达灾区E之前肯定到达D1或D2，如果上个地点是D1，则最优决策为D1->E,距离为
d(D1,E),记f(D1); 如果上个地点是D2，则最优决策为D2->E,距离为d(D2,E),记f(D2);
2、到达离灾区E还剩两站时肯定到达C1或C2或C3的某一点，如果上个地点是C1，则C1到E的路线有两条，即C1->D1->E或C1->D2->E,从中选取最短的一条，所以从C1出发到E
的最优选择为
Min{d(C1,D1)+f(D1),d(C1,D2)+f(D2)} 从而得到最短路线，记最短距离为f(C1)
同理可得C2到E的最优选择为
Min{d(C2,D1)+f(D1),d(C2,D2)+f(D2)} 从而得到最短路线，记最短距离为f(C2)
同理可得C3到E的最优选择为
Min{d(C3,D1)+f(D1),d(C3,D2)+f(D2)} 从而得到最短路线，记最短距离为f(C3)
3、到达离灾区E还剩三站时肯定到达B1或B2或B3的某一点,B1到达E的最优选择为
Min{d(B1，C1)+f(C1),d(B1,C2)+f(C2),d(B1,C3)+f(C3)} 从而得到最短路线，记最短距离为f(B1)
B2到达E的最优选择为
Min{d(B2，C1)+f(C1),d(B2,C2)+f(C2),d(B2,C3)+f(C3)} 从而得到最短路线，记最短距离为f(B2)
B3到达E的最优选择为
Min{d(B3，C1)+f(C3),d(B3,C2)+f(C2),d(B3,C3)+f(C3)} 从而得到最短路线，记最短距离为f(B3)
4、综合考虑，从A到E的最优选择为
Min{d(A，B1)+f(B1),d(A,B2)+f(B2),d(A,B3)+f(B3)} 从而得到最短路线，记最短距离为f(A)
令
a= d(D1,E) a1= f(D1) a2= d(D2,E) a3= f(D2)
b= d(C1,D1) b1= d(C1,D2) b2= f(C1)
c= d(C2,D1) c1= d(C2,D2) c2= f(C2)
d= d(C3,D1) d1= d(C3,D2) d2= f(C3)
e= d(B1，C1) e1= d(B1,C2) e2= d(B1,C3) e3= f(B1)
f= d(B2，C1) f1= d(B2,C2) f2= d(B2,C3) f3= f(B2)
g= d(B3，C1) g1= d(B3,C2) g2= d(B3,C3) g3= f(B3)
h= d(A，B1) h1= d(A,B2) h2= d(A,B3) h3= f(A)
四．模型求解与程序设计
五．结果分析
第一阶段得到D1->E距离为3，D2->E距离为4；
第二阶段得到从C1到的最短路线为C1->D1->E 最短距离为6，从C2到E的最短路线为C2->D2->E 最短距离为7，从C3到E的最短路线为C3->D1->E 最短距离为6；
第三阶段从B1到E的最短路线为B1->C2->D2->E 最短距离为11，从B2到E 的最短路线为B2->C1->D1->E或B2->C2->D2->E 最短距离为9，从B3到E的最短路线为B3->C2->D2->E 最短距离为9;
第四阶段得到最终的最优路线为A->B3->C2->D2->E,最短距离为12。

因此，上海市政府采用A->B3->C2->D2->E路线，才能够以最快的速度将救灾物资运输到灾区人民的手中。