2016年昆明理工大学质量发展研究院F004运筹学复试笔试最后押题五套卷
● 摘要
一、计算题
1． 有四个工件J I ，J Z ，J 3，J 4，要求在三台设备A ，B ，C 上顺次加工，各工件在各设备上的加工时间示于表中，试构造一启发式算法，用于寻求使总加工时间最短的工件加工顺序。
表
【答案】可设计如下启发式算法:
利用该启发式算法求解，求解过程如表所示。
表
，总加工时间为40。 所以，最优加工顺序为
2． 某线性规划问题有m 个小等号约束条件等号约束条件
【答案】对于m 个小等号约束条件，令:
第 2 页，共 46 页
，P 个大
，现要求在m 个小等号约束条件中取L
个，P 个大等号约束条件取q 个，试将这些条件写在一个模型中。
对于P 个大等号约束条件，令:
3． 某工厂的生产任务最近波动很大，为降低成本宜雇佣临时工，但熟练的生产工人临时难以雇到，培训新 手的费用又高，今后四个月需要工人数量如下表所示:
表
每月超过需要量聘用，每人浪费600元，聘用或解聘费为200元乘上两个月份聘用人数之差的平方。以这四 个月的总花费最小为目标，写出本问题中厂方应如何聘用工人的动态规划的模型。（假定工资按实际工作时间计算，则聘用人数可为分数）
【答案】按月份将问题分为四个阶段，阶段变量k=1，2，3，4，设状态变量s k 为第k 月末的工人，
允许决策集合为数，决策变量u k 表示第k 月招聘或解聘的工人数（招聘为正，解聘为负）
，d k 表示第k 个月所需的工人数，状态转移方程为
第1个月至第k 个月的最小总花费。 动态规划的基本方程为:
时，
，其数值计算如表所示。
表
。
为
第 3 页，共 46 页
当时，，其数值计算如表所示 表
当时，，其数值计算如表所示： 表
所以，得到最优解为：
4． 田忌和齐王赛马，他们各有上、中、下三匹不同等级的马，但是齐王的马比田忌同等级的马稍高一筹，即齐王同等级的马要胜过田忌同等级的马，但是不同级别的马则相差很远。每匹马只能出场一次，采取三局两胜 的记分方法。请给出比赛结果田忌的赢得矩阵。 【答案】设齐王和田忌的策略集分别为
田忌的赢得可用表表示。
表
，
第 4 页，共 46 页