习 题
第二章 线性规划习题
2－1 某桥梁工地需集合料3万立方米，集合料含量为：粘土含量不大于0.8％，细沙含量在5％～8％之间，粗沙含量在60％～70％之间，砾石含量在20％～30％之间，现有材料数量及单价如下表所示。 33粘土 细砂 20000 15 粗砂 25000 12 砾石 10000 7 现有存储量（m） 2000 单价（元/ m） 4
问如何配料才能使集合料的总成本费用最低？（试列出数学模型）。 2—2 将下列线性规划问题化成标准型：
① maxS?4x1?5x2?x4
?4x1?x2?30?4x?3x?3x?x?801234??s.t.?4x2?4x3?x4??10
?3x3?4x4?8???x1,x2,x3,x4?0② minS?3x1?4x2?3x3?x4
?x1?x4?40?x?x?x?40123??s.t.?x1?x2?x4??40
?3x2?4x3?8???x1,x2?0,x3?0 2—3 用图解法求解下列线性规划问题：
maxS?2x1?5x2
?x1?4?x?3?s.t.?2
x?2x?82?1??x1,x2?0（答案：S??19，X???2,3?T。）
1
2—4 用单纯形法求解下列线性规划问题 ① minS?4x1?3x2?8x3
?x1?x3?2? s.t.?x2?2x3?5
?x,x,x?0?123
（答案：S??15，X??(0,5,0,)T。） ② maxS?x1?2x2?3x3?x4 ?x1?2x2?3x3?15?2x?x?5x?20?3 s.t. ?12
x?2x?x?x?101234???x1,x2,x3,x4?0
（答案：S??15，X??(5/2,5/2,5/2,0)T。）
第三章 特殊类型的线性规划习题
3－1用表上作业法求解以下运输问题。
产地 销地 A 2 4 6 3 B 4 3 3 3 C 7 2 5 2 D 6 5 4 2 产 量 5 2 3 10 甲 乙 丙 销 量 3－2某市区交通愿望图有三个始点和三个终点，始点发生的出行交通量ai，终点吸引的交通量bj及始终点之间的旅行费用如下所示。问如何安排出行交通量fij才能使总的旅行费用为最小？
始点 终点 D1 5 10 9 20 D2 4 4 8 30 D3 2 7 4 50 ai 30 40 30 Σ100 O1 O2 O3 bj 3－3某运输公司有5辆汽车分别担负五条运输线的运输任务，由于车辆性能、路线等级及司机水平不同，不同车辆在不同运输线上所需的运输费用是不一样的，试问如何分配
2
这五辆汽车才能使总的运输费用最少？
车辆 运输线 R1 5 7 3 6 7 R2 6 4 4 7 9 R3 9 6 5 4 8 R4 3 3 3 9 10 R5 4 5 6 7 5 T1 T2 T3 T4 T5 3－4用隐枚举法求解下列规划问题： min S?4x1?3x2?2x3 ?2x1?5x2?3x3?4?4x?x?3x?3?23 s.t ?1
x?x?13?2??x1,x2,x3?1或0 (答案：min S=2，x1=0，x2=0，x3=1)
3－5用分支定界法求解下列问题
max S＝－2x1＋x2 ?x1?x2?0??3x?x?3?12s.t ?
x?2x?302?1??x1，x2?0，整数
(答案：max S＝6，x1＝3，x2=12)
3
第四章 图论习题
4-1 求下列各图的最小树
题4-1图
4-2 某市区六个居民点的分布如题图4-2图所示，现需沿道路在六个居民点之间辅设煤气管线，试求使管道总长度为最佳的最佳辅设方案。 （图中连线为现状道路网）
4-3 某地区七个城镇间的公路交通网如题图4-3图所示，试用标号法计算从A城到G城的最短路线。
（图中弧旁数据为公路长度）
题4-2图 题4-3图
4-4 在题4-4图中，用标号法计算A点到H点的最短路
4-5 在题4-5图中，求任一点至另一任意点之间的最短路线。
4
题4-4图 题4-5图 4-6 在题4-6图所示的网络中，弧旁的数据为(Cij,fij)：
① 确定所有的割集； ② 求最小割量； ③ 求出网络最大流。
4-7 某地区的公路交通网络如题图4-7图所示，弧旁数据为路段通行能力（即容量，百辆/小时），试求网络通行能力（即最大流）。
题4-6图 题4-7图
4-8 某矿区有两个堆料场x1、x2及三个货运码头y1，y2，y3，堆料场的原媒通过如题4-8图所示的交通网络运送到码头。试确定从堆料场到码头的最大运送能力。 4-9 某地区的公路交通网络如题4-9图所示，弧旁数据为(bij,cij)（bij为行驶费用，cij为容量）。试求该交通网络的最小费用最大流。
题4-8图 题4-9图
5