求解最短路与成本最优方案：图解题和比较方案

8-1 分别用逆序解法和顺序解法求解图8-16中从S1到S5的最短路问题。

图8-16

8-2 某旅游者要从A地出发到终点F,事先得到的路线图如图8-17所示,请帮他找到一条最短路径。

图8-17

8-3 某公司有资金4万元,投资A,B,C三个项目,每个项目的投资效益与投入该项目的资金有关。三个项目A,B,C的投资效益(单位:万吨)和投入资金(单位:万元)的关系如表8-6所示,问如何对这三个项目的最优投资进行分配,使总投资效益最大?

表8-6

8-4 某有限公司有五台新设备,将有选择地分配给下属的三个工厂,所得收益如表8-7所示(单位:千元)。问该公司应如何分配设备,可使总收益最大?

表8-7

8-5 某企业计划委派10个推销员到4个地区推销产品,每个地区分配1~4个推销员。各地区月收益(单位:10万元)与推销员人数的关系如表8-8所示。问企业如何分配4个地区的推销人员,才能使月收益最大?

表8-8

8-6 现有一面粉加工厂,每星期上五天班,生产成本和需求量如表8-9所示。

表8-9(www.xing528.com)

面粉加工没有生产准备成本,每袋面粉的存储费为hk＝0．5元/袋,按天交货,分别比较下列两种方案的最优性,求成本最小的方案。

(1)星期一早上和星期五晚上的存储量为零,不允许缺货,仓库容量为s＝40袋;

(2)其他条件不变,星期一初存量为8。

8-7 在未来四个月里,某公司将利用一个仓库经销某种商品。该仓库的最大容量为900件,每月月初订购商品,并于月底取到订货。据估计,今后四个月这种商品的购价pk和售价qk如表8-10所示(单位:千元)。假定商品在第一个月月初开始经销时仓库已经有该种商品200件,已知数据如表8-10所示,问如何安排每个月的订货量和销货量,才能使这四个月的总利润最大(不考虑仓储费用)?

表8-10

8-8 已知某背包问题的数据如表8-11所示,最大限制重量为5,问如何携带,总价值最大?

表8-11

8-9 10吨集装箱最多只能装9吨,现有3种货物供装载,每种货物的单位重量及相应单位价值如表8-12所示,问应该如何装载货物,才能使总价值最大?

表8-12

8-10 用动态规划方法求解以下背包问题:

8-11 某种机器可以在高、低两种负荷下生产。在高负荷生产条件下,机器完好率为0．7,即如果年初有u台完好机器投入生产,则年末完好的机器数量为0．7u台。年初投入高负荷运行的u台机器的年产量为8u吨,系数8称为单台产量。在低负荷生产条件下,机器完好率为0．9,单台产量为5吨。假设开始时有1 000台完好机器,问如何制订一个五年计划(要求每年年初将完好的机器一部分分配到高负荷生产条件下,剩下的机器分配到低负荷生产条件下),才能使五年的总产量为最高?

8-12 有一个车队总共有车辆100辆,分别送两批货物去A,B两地,运到A地的利润与车辆数目满足关系100x,x为车辆数,车辆抛锚率为30%,运到B地的利润与车辆数y关系为80y,车辆抛锚率为20%,总共往返3轮。请设计使总利润最高的车辆分配方案。