当前位置：问答库＞考研试题

一、计算题

1． 某工厂的生产任务最近波动很大，为降低成本宜雇佣临时工，但熟练的生产工人临时难以雇到，培训新 手的费用又高，今后四个月需要工人数量如下表所示:

表

每月超过需要量聘用，每人浪费600元，聘用或解聘费为200元乘上两个月份聘用人数之差的平方。以这四 个月的总花费最小为目标，写出本问题中厂方应如何聘用工人的动态规划的模型。（假定工资按实际工作时间计算，则聘用人数可为分数）

【答案】按月份将问题分为四个阶段，阶段变量k=1，2，3，4，设状态变量s k 为第k 月末的工人，

允许决策集合为数，决策变量u k 表示第k 月招聘或解聘的工人数（招聘为正，解聘为负）

，d k 表示第k 个月所需的工人数，状态转移方程为

第1个月至第k 个月的最小总花费。 动态规划的基本方程为:

时，

，其数值计算如表所示。

表

。

为

当时，，其数值计算如表所示 表

当时，，其数值计算如表所示： 表

所以，得到最优解为：

2． 出从1节点到U 节点的最短路径

图

【答案】Dijkstra 算法，即标号法求解

（l ）对节点l 进行P 标号，即P （1）=0，其余点进行T 标号，即T （j ）=+∞ 因为

而

（2）修改节点3、5的T 标号

因为

（3）修改节点6，8的标号

故将节点2进行P 标号，

故将点5进行P 标号，

因为

（4）修改节点9的标号

因为

（5）修改节点7的标号

因为

（6）修改节点9、11的标号

因为

（7）修改节点12的标号

因为

顶节点12已经进行了P 标号，且

故将点12进行P 标号，

于是得到节点1到节点12的最短路程为18，最短路故将点9进行P 标号，

故将点8进行P 标号，

故将点4进行P 标号，

故将点6进行P 标号，

线为1→2→5→8→11→12

3． 某公司从两个不同的仓库向三个客户提供某种产品，由于在计划期内供不应求，公司决定重，各客户的需点保证某些 客户的需要，同时又使总运输费用最低，现己知各仓库的供应量（吨），相关数据如表所示。 求量（吨）及从各仓库到每一客户的单位运费（元/吨）

表公司供应客户需求量表

根据供求关系和公司经营的条件，公司确定了以下目标变量: P 1表示客户几的需要;

P 2表示至少满足各客户75%的需要; P 3表示使总运费最少;

P 4表示从仓库A 2至客户B 1，只能用船运货，最小运量为1000吨;

P 5表示从仓库A 2至客户B 3，从仓库戊至客户残之间的公路正在大修，运货量应尽量少; P 6表示平衡用于