习题6

1 某公司打算向它的三个营业区增设6个销售店，每个营业区至少增设1个。各营业区每

年增加的利润与增设的销售店个数有关，具体关系如表6-19所示。试规划各营业区应增设销售店的个数，以使公司总利润增加额最大。 表6-24 增设销售店个数 1 2 3 4 营业区A 100（万元） 160 190 200 营业区B 120（万元） 150 170 180 营业区C 150（万元） 165 175 190 2 某工厂有100台机器，拟分4个周期使用，在每一周期有两种生产任务，据经验把机器

投入第一种生产任务，则在一个周期中将有六分之一的机器报废，投入第二种生产任务，则有十分之一的机器报废。如果投入第一种生产任务每台机器可收益1万元，投入第二种生产任务每台机器可收益0.5万元。问怎样分配机器在4个周期内的使用才能使总收益最大？

3 某公司生产一种产品，估计该产品在未来四个月的销售量分别为300、400、350和250件。生产该产品每批的固定费用为600元，每件的变动费用为5元，存储费用为每件每月2元。假定第一个月月初的库存为100件，第四个月月底的存货为50件。试求该公司在这四个月内的最优生产计划。

4 用动态规划求解下述规划问题 （1）maxz?52maxz?2x?x （2）m?i11?x2

5i?1?mi?1i2?6 ?10 2x12?3x2mi?0 (i?1,2,3,4,5) x1,x2?0

5某公司经销A、B、C三种产品，由于运输能力的限制，该公司每月只能把6吨的产品运

回公司进行销售。产品A、B、C的单件重量分别为20、30和40公斤；进货的批量分别为50、40和20件；单位产品利润分别为80、130和150元。试确定该公司每月A、B、C三种产品的最佳进货量，以使总利润最大。 6 某公司需要在近四周内采购一批原料，估计在未来四周内的价格可能有60、80、90和100四种状态，各状态发生的概率分别为0.2、0.3、0.3和0.2，试求各周应以什么样的价格购入原料，才能使采购价格期望值最小。 7 思考题

（1）解释下列概念：状态、决策、状态转移方程、阶段指标函数、最优指标函数、边界条件。

（2）简述动态规划的最优性原理和基本方程。

（3）建立动态规划模型时应注意哪五点，他们在模型中的作用是什么？ （4）什么是随机动态规划，其特点是什么？

（5）动态规划方法是否是一种特殊算法，为什么？它有哪些局限性或缺陷?

（6）将一个实际的多阶段决策问题如果要建立动态规规划模型来求解有哪些基本步骤？

（7）一维资源分配与二维资源分配问题在构造动态规划模型中有哪些区别? 8 案例练习

（1）投资时机决策问题

某投资者看好生命周期有10年的项目，并准备对其进行投资。由于市场的不确定性，投资成本以及项目未来的收益是不确定的变量。如果“现在”投资，投入成本为200万元。可得到的收益的现值为250万元。但是受到市场波动的影响，投资成本和收益每年都有上涨和下跌两种可能，并且根据资料统计，若上涨，涨幅均为20%，若下跌，跌幅均为10%。投资者可在3年内做出投资决策，不考虑利率因素，利用动态规划确定最佳投资时机。要求：建立模型，并编程实现计算。 （2）设备更新问题

假设某化工厂的设备已使用2年，设备更新的相关数据如表6-25 所示 ，确定 5 年内的设备更新决策及在此决策下的最利润。试建立动态规划模型，并编程实现计算。 表6-25 设备更新的相关数据表

习题7

1 用遗传算法和粒子群算法求下面函数的最小值点和最小值

f(x,y)?esin50x?sin(60ey)?sin(70sinx)?sin(sin80y)1?sin(10(x?y)?(x2?y2)42 用遗传工具箱的ga求解器求解下面有约束极值问题

minf(x1,x2)?x12?2x22?4x1?8x2?15?9?x?x?0s.t.??x1,x2?02122

习题8

1． 某快餐店给一公司送快餐，应按照什么路线送货才能使送货时间最短？图8-38给出了快餐店到该公司的交通图如，图中表示7个地名，其中v1表示快餐店，v7表示该公司，点之间的联线（边）表示两地之间的道路，边所赋的权数表示开车送快餐通过这段路所需要的时间。

v22421535v57682v1v4v73v3图8-38

v6

2． （设备更新问题）某企业使用一台设备，在每年年初，企业领导部门就要决定是购置新的，还是继续使用旧的，若购置新设备，就要支付一定的购置费用；若继续使用旧设备，则需支付一定的维修费用。已知该设备在各年年初的价格如表8-5所示： 表8-5 设备在各年年初的价格表

第1年 11 第2年 11 第3年 12 第4年 12 第5年 13 还已知使用不同时间（年）的设备所需要的维修费用如表8-6所示： 表8-6 设备所需要的维修费用表 使用年数 维修费用 0-1 5 1-2 6 2-3 8 3-4 11 4-5 18 如何制定一个几年之内的设备更新计划，使得总的支付费用最小？

3．某电力公司要沿道路为8个居民点架设输电网络，连接8个居民点的道路图如图8-39所示，其中，v1,v2,?,v8表示8个居民点，图中的边表示可架设输电网络的道路，边上的赋权数为这条道路的长度，单位为公里，请设计一个输电网络，联通这8个居民点，并使总的输电线路长度为最短。

v245v63v12234v7v5562v32v87v4图8-39

4. 某大学准备对其所属的7个学院办公室计算机联网，这个网络的可能联通途径如图8-40所示，图中v1,v2,?,v7表示7个学院办公室，图中的边可能联网的途径，边上的所赋的权数为这条路线的长度，单位为百米。请设计一个网络能联通7个学院办公室，并使总的线路长度为最短。