中国矿业大学：《运筹学》课程教学资源（作业习题）测试题三（题目）

测试题三一、填空与判断（本题20分，填空题每空5分，判断题每空2分）1、在单纯形法中，初始基可能由三种类型的变量组成。2、若对偶问题为无界解，其原问题的解为3、线性规划用两阶段法求解时，第一阶段的目标函数通常写为minz=Zxa（xa为人工变量)，但也可写为minz=Zk,xai,只要所有k,均为大于零的常数（）。4、如果原问题中的约束方程AX≤b变成AX≥b,则其对偶问题的唯一改变就是将非负的约束y≥0变成非正的约束y≤0（)。5、运输问题是一种特殊的线性规划模型，因而求解结果也可能出现下列四种情况之一：有唯一最优解，有无穷多最优解，无界解，无可行解（）。6、用分支定界法求解一个极大化的整数规划问题，当得到多于一个可行解时，通常可任取其中一个作为下界值，再进行比较剪枝（）。7、任何含n个节点（n-1）条边的图一定是树图（）。二、（本题10分）某电子产品装配工厂，生产A、B、C三种规格电子产品。装配工作在同一生产线上完成，三种产品装配时的工时消耗分别为6、8和10小时。生产线每月正常工作时间为200小时，三种规格电视机销售后，每台可获利分别为500元、650元和800元。每月销量预计为12台、10台、6台。该厂经营目标如下：P1：利润指标定为每月1.6×10*元；P2：充分利用生产能力；P3：加班时间不超过24小时；P4：产量以预计销量为标准。为确定生产计划，试建立该问题的目标规划模型。三、（本题10分）某企业要进行一项工程项目，工作的相互关系如下表。6dJ工序Ce0g/Ib紧前工序a,ba,bCd,e2433X12时间/天根据以上资料：（1）绘制网络计划图：（2）计算各结点的时间参数；（3）确定关键路线和总工期

1 测试题三 一、填空与判断（本题 20 分，填空题每空 5 分，判断题每空 2 分） 1、在单纯形法中，初始基可能由 三种类型的 变量组成。 2、若对偶问题为无界解，其原问题的解为 。 3、线性规划用两阶段法求解时，第一阶段的目标函数通常写为   i ai min z x ( ai x 为 人工变量)，但也可写为   i i ai min z k x ,只要所有 i k 均为大于零的常数 ( )。 4、如果原问题中的约束方程 AX  b 变成 AX  b ,则其对偶问题的唯一改变就是将非 负的约束 y  0 变成非正的约束 y  0 ( )。 5、运输问题是一种特殊的线性规划模型，因而求解结果也可能出现下列四种情况之一： 有唯一最优解，有无穷多最优解，无界解，无可行解 ( )。 6、用分支定界法求解一个极大化的整数规划问题，当得到多于一个可行解时，通常可 任取其中一个作为下界值，再进行比较剪枝 ( )。 7、任何含 n 个节点（n-1）条边的图一定是树图 ( )。 二、（本题 10 分）某电子产品装配工厂，生产 A、B、C 三种规格电子产品。装配工作 在同一生产线上完成，三种产品装配时的工时消耗分别为 6、8 和 10 小时。生产线每 月正常工作时间为 200 小时，三种规格电视机销售后，每台可获利分别为 500 元、650 元和 800 元。每月销量预计为 12 台、10 台、6 台。该厂经营目标如下： P1：利润指标定为每月 1.6×104元；P2：充分利用生产能力； P3：加班时间不超过 24 小时；P4：产量以预计销量为标准。 为确定生产计划，试建立该问题的目标规划模型。 三、（本题 10 分）某企业要进行一项工程项目，工作的相互关系如下表。 工序 a b c d e f g 紧前工序 / / a，b a，b b c d，e 时间/天 4 2 3 4 3 1 2 根据以上资料：（1）绘制网络计划图；（2）计算各结点的时间参数；（3）确定关键路 线和总工期

四、（本题20分）对于线性规划问题：minf=6x,+4x,+7x3X, + 3x ≥23x, + 2x, + x, ≥ 4- X, +2x, +2x, ≥5X,X2,x,≥0（1）写出此问题的对偶问题：（2）求出此问题和它的对偶问题的最优解和最优值（要求利用互补松弛定理）。五、（本题20分）某汽车零件制作商，在不同的地方开设了3个工厂，从这些厂将汽车零件运至设在全国各地的4个仓库，并希望运费最小。下表列出了单位运价以及3个厂的供应量和4个仓库的需求量。请求出运费最小的运输方案。仓库1234供应量运价工厂甲235150乙243021丙143270需求量40502535六、（本题20分）某厂拟建两种不同类型的冶炼炉。甲种炉每台投资为2个单位，乙种炉每台投资为1个单位，总投资不能超过10个单位：又该厂被许可用电量为2个单位，乙种炉被许可用电量为2个单位，但甲种炉利用余热发电，不仅可以满足本身需要，而且可供出电量1个单位。已知甲种炉每台收益为6个单位，乙种炉每台收益为4个单位。试问：应建甲、乙两种炉各多少台，使之收益最大？要求：（1）写出该整数规划问题的数学模型。（2）表1是通过单纯形法给出该整数规划问题的松弛问题的最优解和终表，请你在此基础上用割平面法计算本题的最优解。表10.bXiX2X3X4基变量0X12/5-1/518/501X214/51/52/500-32.8-16/5-2/5-z2

2 四、(本题 20 分)对于线性规划问题：                     , , 0 2 2 5 3 2 4 3 2 min 6 4 7 1 2 3 1 2 3 1 2 3 1 3 1 2 3 x x x x x x x x x x x f x x x （1）写出此问题的对偶问题；（2）求出此问题和它的对偶问题的最优解和最优值(要 求利用互补松弛定理)。 五、（本题 20 分）某汽车零件制作商，在不同的地方开设了 3 个工厂，从这些厂将汽 车零件运至设在全国各地的 4 个仓库，并希望运费最小。下表列出了单位运价以及 3 个厂的供应量和 4 个仓库的需求量。请求出运费最小的运输方案。 仓库 运价 工厂 1 2 3 4 供应量 甲 2 1 3 5 50 乙 2 2 4 1 30 丙 1 4 3 2 70 需求量 40 50 25 35 六、（本题 20 分）某厂拟建两种不同类型的冶炼炉。甲种炉每台投资为 2 个单位，乙 种炉每台投资为 1 个单位，总投资不能超过 10 个单位；又该厂被许可用电量为 2 个单 位，乙种炉被许可用电量为 2 个单位，但甲种炉利用余热发电，不仅可以满足本身需 要，而且可供出电量 1 个单位。已知甲种炉每台收益为 6 个单位，乙种炉每台收益为 4 个单位。试问：应建甲、乙两种炉各多少台，使之收益最大？要求：（1）写出该整数 规划问题的数学模型。（2）表 1 是通过单纯形法给出该整数规划问题的松弛问题的最 优解和终表，请你在此基础上用割平面法计算本题的最优解。 表 1 基变量 b X1 X2 X3 X4  i X1 18/5 1 0 2/5 -1/5 X2 14/5 0 1 1/5 2/5 -z -32.8 0 0 -16/5 -2/5