当k=1时
*?d(B3,C1)?f3(C1)?3?5?8?????**f2(B3)?min?d(B3,C2)?f3(C2)?5?4?9??8??*d(B,D)?f(D)?3?5?8??3343??
*?d(A,B1)?f2(B1)?3?7?10?????**f1(A)?min?d(A,B2)?f2(B2)?2?6?8??8??*d(A,B)?f(B)?1?8?9323????
可得到从A到E的最短距离为8，最短路径为A?B2?C1?D1?E。
5．设某公司要从驻地1城出发到2、3、4这三个城市举办新产品推介会。由于四个城市之间来去的运输方式不同，因而来去的运输费用各不相同。四个城市之间的运输费用如下表所示。 问该公司应如何选择行进路线，使从驻地1城出发到其他城市依次且仅一次，再回到驻地，总的运输费用最小。
表10-14 四个城市之间的运输费用表
运 城 市 j 城 市 费 i 1 2 3 4 1 2 3 4 解：由边界条件知
0 9 7 8 6 0 4 5 7 5 0 6 8 6 7 0 ?)?d12?9,f0(3,o?)?d13?7,f0(4,o?)?d12?8, f0(2,o当k=1时，从城市V1出发，经过1个城市到达Vi的最短距离为
f1(2,?3?)?f0(3,o?)?d32?7?5?12f1(2,?4?)?f0(4,o?)?d42?8?6?14f1(3,?2?)?f0(2,o?)?d23?9?4?13f1(3,?4?)?f0(4,o?)?d43?8?7?15f1(4,?2?)?f0(2,o?)?d24?9?5?14f1(4,?3?)?f0(3,o?)?d34?7?6?13
当k=2时，从城市V1出发，经过2个城市到达Vi的最短距离为
f2(2,{3,4})?min(f1(3,{4})?d32,f1(4,{3})?d42)?min(15?5,13?6)?19p2(2,{3,4})?4f2(3,{2,4})?min(f1(4,{2})?d43,f1(2,{4})?d23)?min(14?7,14?4)?18p2(3,{2,4})?2f2(4,{2,3})?min(f1(3,{2})?d34,f1(2,{3})?d24)?min(13?6,12?5)?17p2(4,{2,3})?2当k=3时，从城市V1出发，经过3个城市到达Vi的最短距离为
f3(1,{2,3,4})?min(f2(2,{3,4})?d21,f2(3,{2,4})?d31,f2(4,{2,3})?d41)?min(19?6,18?7,17?8)?25所以最短路径有3条，为1?3?4?2?1,1?4?2?3?1,1?3?2?4?1，最短距离为25.
6．（1）用动态规划求解极大值问题：
2maxz?x1x2x3?2x?3x2?x3?4st.?1?xi?0,(i?1,2,3)
（2）试用动态规划求解极大值问题。
22maxz?max(4x12?x2?2x3?12)?3x1?2x2?x3?9st.??xi?0(i?1,2,3)7．设有一个线性规划模型为
maxz?max(x1?(x2?3)2?(4?x3)2)?x1?x2?x3?8st.??xi?0(i?1,2,3)取整数 试用动态规划求解。
8 某公司决定投资60万元（以10万元为单位），以提高三种主要产品 A、B、C 的产量。现决定每种产品至少要投资10万元。各种产品投资不同资金后可获得的期望利润如下：
分配的 投资金额 10 20 30 40
利 润 产品 A 14.5 16.4 18.0 19.6 产品 B 16.2 18.4 19.9 24.1 产品 C 15.9 18.4 22.6 24.2
试确定如何安排对各种产品的投资数，可获得最大期望利润 阶段：k = 1, 2, 3, 4 分别考虑产品A、B、C和终止阶段； 状态：sk 表示第 k 阶段初的现有资金数； 决策：uk 表示第 k 阶段的投入资金数； 状态转移方程：sk+1 = sk – uk 动态规划基本方程：
fk(sk)?ma?xvk(sk,uk)?fk?1(sk?1)?
f4(s4)?0
最后得到解：产品A投资10万，产品B投资10万，产品C投资20万 总的期望利润为49.1万。
1．某台机器可连续工作4年，也可于每年末卖掉，换一台新机器，已知各年初购置一台新机器的价格及不同役龄机器年末的处理价如表11-8，又有新机器第一年运行的维修费为0.3万元，使用1、2、3年后的维修费分别为：0.8，1.5，2万元，制定该机器的最优更新方案，使4年内购买、更换、及维修的总费用最少。
表11-8 各年初购置一台新机器的价格及不同役龄机器年末的处理价
j 年初购置价 使用（第第一年 2.5 2.0 第二年 2.6 1.6 第三年 2.8 1.3 第四年 3.1 1.1 j年的机器处理价j年末的处理价） 2．求下图中v1??v7的最大流量
v26531055v5914v1v446410v7v3v6图11-41 网络图
3．有六口海上油井，相互间距离如表11-9所示。1号井离海岸最为5海里。已知，每铺设1海里的成本为：人工费30万元，油管费50万元，其它费用100万元。问从海岸经1号井铺设油管，把各油井连接起来，应如何铺设使总成本最低，最低总成本是多少？单位：海里
表11-9 六口海上油井相互间距离
油井 2 3 4 5 6 1 2 3 4 5 1.3 2.1 0.9 0.7 1.8 0.9 1.8 1.2 2.6 2.6 1.0 2.5 0.8 1.6 0.9 4．如图11-42，顶点代表村庄，顶点旁边的数字是该村人口，线段上的数字是路长，现准备在这一地区的某一村庄设立一个医院。问应将医院建在那一个地址，使其居民就医走的总路程最短。
200110250230403003204500
20515150图11-42 村庄及人口5．两家工厂x1和x2生产一种商品，商品通过如图11-43所示的网络运送到市场
y1,y2,y3，试用标号法确定从工厂到市场所能运送最大总量。
x11857193y14222248771371215y224426x2图11-43 商品运送网络y3
1．指出如下箭线式网络图中的错误。 解：（a）2→4之间有两项工序，不符合规定。
（b）1→2→3有回路，不符合规定。
2．对下图所示的箭线式网络图计算各项的相关参数。包括： （1）结点时间； （2）工序时间； （3）总时差与自由时差； （4）找出关键路线并计算工期。
22143835078523428747916图12-21 习题3箭线网络图 0 4
0 5
3 2