《运筹学》习题（五）
班级
姓名
一、某旅客需从○1号站到达1○0站，试指出一条最短路径。交通状况如下图
答：
○210
○54
4○12
3
9
○37
10
6
8
○66
35
9○881○0
○94
○48
○74
图中圆圈内数字表示旅行可能通过的站号，
箭头表示旅行路线，箭头旁边数字表示距离
二、将正数a分成三部分，使其连乘积最大。试建立动态规划模型并求解。
f三、设某厂计划全年生产某种产品A，其四个季度的订货量分别为600件、700件、500件、1200件。已知生产产品A的生产费用与产品数量的平方成正比，其比例系数是0005，厂内有仓库可存放未销售掉的产品，其存储费为每件每季度1元，问每一季度各应生产多少产品，才能使总费用最少？
f附：《运筹学》习题（四）答案
一、解答：设原来的产地m个，销地
个，单位运价为cij，总运费为S。
m


1、因为S‘m



cijxijkcrjxrj
cijxijkxrjSkar所以总运价将增
i1j1
j1
i1j1
j1
ir
加kar。由于用闭回路法检验时，若每行有闭回路的顶点时，求其检验数时必为一个加一个减，正好将k抵消，故最优调运方案不变；
2、因为S‘m



m

m
cijxijkcipxip
cijxijkxipSkbp所以总
i1j1
i1
i1j1
i1
jp
运价将增加kbp。最有调运方案不变，道理同上；
m

m

3、因为
kcijxijk
cijxijkS，所以总运费变为原来的k倍，最优调运方案
i1j1
i1j1
不变，道理同上。二、简答：1、运输问题的基变量个数一定为m
，因为rArAbm
12、求运输问题的最优方案能采用单纯形方法，但计算量相当大，而采用表上作业法则可大
大减少计算工作量，而且表上作业法也是一种简单、容易掌握的方法；
、因为闭回路的定义为xi1j1xi1j2xi2j2xi2j3xirjrxirj1i1i2，…ir两两不同，j1j2…jr两
两不同，并且r≤mr≤
故闭回路上顶点的个数为2r≤m
。
4、不能
三、初始方案表
检验数表
销地
产
产地
B1B2B3B4量
销地
产
产地
B1B2B3B4量
A1
015
15
A1
16415
A2
0151025
A2
3
25
A3销量
5
5
5151510
A3销量
20201155151510
改进方案及检验数表
销地
产地
B1
A1
0
B2
B3
B4
5（16）10
产量15
A2（3）10
15（4）25
A3
5（20）（20）（15）5
销量
5
15
15
10
f销地B1产地
B2B3
B4产量
A1（3）5161015
A2
01015（4）25
A3
51717125
销量
5151510
表中所有检验数均非负，所以为最优调运方案。其最小运输费用为335。
四r