DP
1. 下列关于动态规划问题的说法不正确的是（ ）。 A．应用推理或逆推法可能会得出不同的最优解 B．状态变量应具有无后效性
C．动态规划模型中，阶段是按时间或空间划分的 D．问题的阶段数等于问题中的子问题的数目
2. 用动态规划方法求解多阶段问题时，指标函数应满足（ ）。 A．定义在全过程和后部子过程上的数量函数 B．具有可分离性，满足递推关系 C．严格单调
D．以上A、B、C都是
3. 下述的（ ）不能设为动态规划中的状态变量。 A．生产企业某种产品的每月月初库存 B．某种设备每年年末的可利用量 C．送货车辆行驶过的路程 D．送货车辆行驶时的速度
4. 某求极大值的线性规划问题的单纯形表如下：其中d、a1、c1为待定常数。
基变量 b d 4 x1 1 0 0 x2 -3 x3 2 1 -2 x4 0 1 0 x1 x2 a1 c1 cj?zj A．dB．dC．dD．d该线性规划问题无界的时候，满足下面（ ）。
?0,c1?0且a1?0 ?0,c1?0且a1?0 ?0,c1?0且a1?0 ?0,c1?0且a1?0
一、某投资者有总数为40万元的固定资金，他可在三个不同的投资机会中投资（比如，股
1
票、银行、土地），投资额分别为xi(i?1,2,3)。假定他做过预测，知道从每项投资中可获得效益分别为g1(x1)?x1，g2(x2)?x22，g3(x3)?x3，问如何分配投资数额才能使从
所有投资中获得的总效益最大？ 二、某公司现有资金5千万元，拟对3个分公司增加投资，已知投资所获年效益如下表所示，问公司如何应对分配资金，才能使公司总的年收益最大？（用动态规划方法求解）
分公司 1 2 3 投资额 （千万元） 0 1 2 3 4 5
三、某农业种植基地有某种肥料共5单位，准备供给三块农田施用，每块农田至少需要一个单位的肥料，肥料必须按整数单位施用。每块农田施肥数量与增产数量关系如下表所示。试求对每块田施多少单位的肥料，才使总的增产量最多。要求：用动态规划方法求解，有必要的求解过程。
四、（包含两个小题）
1. 某厂按合同规定须于当年每个季度末分别提供10、15、25、20台统一规格的柴油机。已知该厂各季度的生产能力及生产每台柴油机的成本如下表所示。又如果生产出来的柴油机当季不交货，每台每积压一个季度需储存、维护等费用0.15万元。要求在完成合同的情况下，将该生产与存储问题表达成总费用最小的运输平衡表。 季节 1 2 3 4 生产能力/台 25 35 30 10 单位成本/万元 10.8 11.1 11.0 11.3 0 3 7 9 12 13 0 5 10 11 11 11 0 4 6 11 12 12 2. 某运输问题的一个运输方案如下表所示。格子右上角的黑体数字为相应供需方之间的运价。右下角的斜体数字为相应的运输量。
需方 供方 B1 2 1 20 3 B2 3 10 2 40 4 2
B3 5 45 3 6 30 供应量（吨） 55 60 30 A1 A2 A3
需求量（吨） 20 50 75 145 （1）该方案是不是最优运输方案？为什么？ （2）用闭合回路法进行一步调整。
五、（包含两个小题）
1. 某工厂的生产任务最近波动很大，为降低成本宜雇佣临时工，但熟练的生产工人临时难以雇到，培训新手费用又高，今后四个月需要工人数量如下表所示：
月份 需求量 1 250 2 210 3 230 4 190 每月超过需要量聘用，每人浪费600元，聘用或解聘费为200元乘上两个月份聘用人数之差的平方，以这四个月的总花费最小为目标，写出本问题中厂方应如何聘用工人的动态规划的模型。（假定工资按实际工作时间计算，则聘用人数可为分数）
2. 某公司有资金4百万元，可向A、B、C三个分公司增加投资，已知各分公司增加不同数量资金后增加的相应效益如表所示，问如何分配资金可使公司总效益最大？（提示：用动态规划方法）
单位：百万元 分公司 0 A B C
六、某种机器可在高低两种不同的负荷下生产，设机器在高负荷下生产的产量函数为
0 0 0 1 21 22 26 投资额 2 35 37 40 3 50 55 58 4 60 66 68 g?8u1，其中u1为投入生产的机器数量，年完好率为a?0.7;在低负荷下生产的产量函
数为h?5y，其中，
y为投入生产的机器数量，年完好率为b?0.9。
（1）假设开始生产时完好的机器数量s1?1000台，试问每年如何安排机器在高低负荷
下的生产，使在五年内生产的产品总数量最高。（要求：用动态规划逆推法求解）
（2）上述问题中如要求第五年度结束时，完好的机器数量为500台，问每年如何安排机器在高、低负荷下的生产，使五年内生产的产品总产量最高。试列出满足这一约束条件的动态规划模型。
七、某城市有3所小学。管理部门将城市分为六个区，每个区的人数数量大致相同。下表给出了每一所学校与每一个区域之间的近似距离。最右一列给出了明年每个区域的入学新生的数量。最下面的两行表示了每一所学校所能够安排的最少和最多的学生数量。
区域 1 2 3 4
距离学校的距离 学校1 1.0 1.4 1.2 0.8 学校2 1.5 1.3 0.9 1.1 3
新生人数 学校3 2.5 1.7 1.0 2.0 500 500 550 600 5 6 最小招生数 最大招生数 2.6 1.8 1200 1700 1.3 1.0 1100 1800 0.7 1.2 1000 1400 650 600 教育管理部门认为：划分入学区域界限的适当目标是使学生到学校的平均路程最短。在这个初步的计划中，他们要确定为了实现这个目标每一个区域内有多少学生要安排到哪一所学校，同时要满足表中最后两行规定的约束条件。 （1） 建立该问题的运输问题表格。
（2） 按运输问题的最小元素法给出一个较好的初始分配方案。 （3） 已知分配方案如下： 区域 学校1 1 2 3 4 5 6 最小招生数 最大招生数 500 100 0 600 0 0 1200 1700 距离学校的距离 学校2 0 400 200 0 0 600 1100 1800 学校3 0 0 350 0 650 0 1000 1400 500 500 550 600 650 600 新生人数 解释上述方案； （4） 上述方案有两个问题引起管理层的关注。一个是把区域2、3的学生分给了两个学校，
这一做法不符合同一学区的学生在同一所学校就学的惯例。教育管理者决定禁止将一个区域分配给两个或以上的学校。同时，还希望同一所学校均接收2个区域。试建立符合上述要求的数学模型。
IP
1. 对一个目标函数求最大的整数规划问题，下列说法不正确的是（ ） A．任一可行解的目标函数值不可能大于其松弛问题的目标函数值； B．割平面方程是决策变量取整数的一个必要条件； C．松弛问题的最优解可能是此整数规划问题的最优解；
D．整数规划问题解的目标函数值一定不小于其相应的松弛问题解的目标函数值。
2. 下列关于整数规划问题的说法正确的是（ ）。
A．用分支定界法得到松弛问题的若干个可行解，取其中目标函数值最大的为上界。 B．整数规划问题解的目标函数值不劣于其相应的松弛问题解的目标函数值。 C．割平面方程是决策变量取整数的一个必要条件。 D．割平面有可能割去整数可行解。
3. 在用匈牙利法求解分配问题时，最终求得的分配元应是（ ）。 A．零元素
4
B．独立零元素
C．不同行的零元素 D．非零元素
4. 用匈牙利法求解指派问题时，不可以进行的操作是（ ）。 A．效益矩阵的每行同时乘以一个常数 B．效益矩阵的每行同时加上一个常数 C．效益矩阵的每行同时减去一个常数 D．效益矩阵乘以一个常数
5. 在求解整数规划问题时，不可能出现的是（ ）。 A．唯一最优解 B．无可行解 C．多重最优解 D．无穷最优解
一、某企业生产并销售某种产品，可以在生产厂甲、乙两处生产，经考察，可以选择租赁A、B两个仓库作为地区分拨库存。生产厂的生产能力、产品出厂价格及各生产厂到备选地区仓库的运输费率如表1。
表1 生产厂甲 生产厂乙 生产能力 10000 50000 出厂价格 （元/件） 3 3.5 运输费率（元/件） 仓库A 2 3 仓库B 3 4 货物经地区仓库供应到销售区1和销售区2。地区仓库的库存策略实行零库存。备选仓库的作业能力、租赁费用、从各仓库到销售区的运输费率及各销售区的需求量如表2。
表2
作业能力 租赁费用 运输费率（元/件） （件/年） （万元/年） 销售区1 销售区2 仓库A 仓库B 需求量（件/年） 30000 无限 20 35 1 4 20000 2 3 30000 试建立一个整数规划模型，决定租赁的仓库及货物从生产厂到销售区总费用最小的方案（不
必求解）。
二、某公司今年有四个投资项目，各项目在以后连续4年中所需投资额不等，所生产的收益也不等，具体如下表所示。 项目 A B C D 收益现值 第1年 80 40 30 28 15 8 10 8 35 5
所需资金 第2年 20 10 0 5 30 第3年 20 6 5 5 25 第4年 15 5 2 0 20 各年度可用现金 要求：建立此问题的整数规划模型优化该公司的投资方案（只建模型）。
三、某汽车生产厂生产三种汽车：微型轿车、中级轿车、高级轿车。每种轿车需要的资源数量、销售价格和成本如下表所示：
微型车 中型车 高级车 钢材（吨） 人工（小时） 售价（万元） 原料及人工成本（万元） 2.5 50 1 0.5 3 70 3 1.2 3.5 90 10 6 该厂下一个生产周期可使用的资源为钢材7000吨，人工工时60000小时，为达到经济规模，每种汽车的每生产周期产量必须到达一定的数量才可进行生产。工厂规定的经济规模为：微型车1500辆，中型车1200辆，高级车1000辆。工厂一个生产周期的生产能力为：微型车2000辆，中型车2000辆，高级车1200辆。启动三种轿车的生产线一个生产周期的固定费用分别为100万元、120万元、150万元。请构造一个使该厂的利润最大的整数规划模型。
四、某厂生产三种产品A、B、C，每种产品需要的资源数量、销售价格和成本如下表所示：
A B C 原料甲（吨） 原料乙（吨） 人工（小时） 售价（万元） 原料及人工成本（万元） 3.5 3 50 2 1 4 5 70 3 2 5 5 90 9 7 该厂下一个生产周期可使用的资源为原料甲9000吨、原料乙7000吨，人工工时60000
小时，为达到经济规模，每种产品的每生产周期产量必须达到一定的数量才可进行生产。工厂规定的经济规模为：A1500件，B1200件，C1000件。工厂一个生产周期的生产能力为：A3000件，B3500件，C1500件。启动三种产品的生产线一个生产周期的规定费用分别为120万元、150万元、180万元。请构造一个使该厂的利润最大的整数规划模型。
6