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

测试题三答案一、填空与判断（本题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.6X10*元：P2：充分利用生产能力；P3：加班时间不超过24小时；P4：产量以预计销量为标准。为确定生产计划，试建立该问题的目标规划模型。解：设生产电子产品A为x1台，B为x2台，C为x3台，该问题的目标规划模型为1

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：产量以预计销量为标准。 为确定生产计划，试建立该问题的目标规划模型。 解：设生产电子产品 A 为 x1 台，B 为 x2 台，C 为 x3 台，该问题的目标规划模型为

minz=pr-d,+pzd,+p,d,+p4-(d,+d++d,+d,+d+d)[500x +650x, +800x; +d; d, =1.6×1046x+8x,+10x,+d,-d,=200d +dj-dt=24s.t.x +di -dt =12x2+d;-d=10x, +dg-dt =6,x2,x, ≥0,d,,d ≥0(i=1,2,.,6)三、（本题10分）某企业要进行一项工程项目，工作的相互关系如下表。bdf工序ace0b紧前工序-a,bbcd, ea,2434312时间/天根据以上资料：（1）绘制网络计划图：（2）计算各结点的时间参数；（3）确定关键路线和总工期。答案：关键路线为一③一④6.即工序序列为a-d-g，总工期为10天。oD36[10]1P24合合四、（本题20分）对于线性规划问题：minf=6x,+4x,+7xx,+3x,≥23x +2x, +x, ≥4- X +2x +2x, ≥5X,x2,x≥0（1）写出此问题的对偶问题：（2）求出此问题和他的对偶问题的最优解和最优值。2

2                                                               , , 0; , 0( 1,2, ,6) 6 10 12 24 6 8 10 200 500 650 800 1.6 10 s.t. min ( ) - 1 2 3 6 - 3 6 5 - 2 5 4 - 1 4 3 - 2 3 2 - 1 2 3 2 4 1 - 1 2 3 1 6 - 5 6 - 4 5 - 3 3 4 4 - 2 2 - 1 1 x x x d d i  x d d x d d x d d d d d x x x d d x x x d d z p d p d p d p d d d d d d i i 三、（本题 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）确定关键路 线和总工期。 答案：关键路线为①—③—④—⑥，即工序序列为 a-d-g，总工期为 10 天。 四、(本题 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）求出此问题和他的对偶问题的最优解和最优值

解（1）对偶问题为maxz=2yi+4y2+5ysyi+3y2-y,≤62y2+2y,≤43yi + y +2y, ≤7Ji,y2,y,≥0（2）引入松弛变量y4Ys,Y6，将对偶问题标准化得maxz=2yi+4y2+5y+0·y4+0·ys+0ye[Ji+3y2-y, +y4=62y2 +2y, +y, = 43yi + y2 +2y, + y6= 7yi,y2,y3,y4,ys,≥0用单纯表迭代，b基yly3y4y2y56,y6613-1001--y44020102y5s[2]073120Iy67/20000524-z8140108y41/2201100-1/2y3300-11--1y6[3]2-1000-10-Z-5/2701-1/05/6y413/320100y311/211001/3y1-1/3-1/3000-12-1/3-3/2-2/3-2求得最优解为3

3 解（1）对偶问题为                   , , 0 3 2 7 2 2 4 3 - 6 max 2 4 5 1 2 3 1 2 3 2 3 1 2 3 1 2 3 y y y y y y y y y y y z y y y （2）引入松弛变量 , , , 4 5 6 y y y 将对偶问题标准化得                            , , , , , 0 3 2 7 2 2 4 3 - 6 max 2 4 5 0 0 0 1 2 3 4 5 6 1 2 3 6 2 3 5 1 2 3 4 1 2 3 4 5 6 y y y y y y y y y y y y y y y y y z y y y y y y 用单纯表迭代， 基 b y1 y2 y3 y4 y5 y6  i y4 6 1 3 -1 1 0 0 - y5 4 0 2 [2] 0 1 0 2 y6 7 3 1 2 0 0 1 7/2 -z 0 2 4 5 0 0 0 y4 8 1 4 0 1 1/2 0 8 y3 2 0 1 1 0 1/2 0 - y6 3 [3] -1 0 0 -1 1 1 -z -10 2 -1 0 0 -5/2 0 y4 7 0 13/3 0 1 5/6 -1/ y3 2 0 1 1 0 1/2 0 y1 1 1 -1/3 0 0 -1/3 1/3 -z -12 0 -1/3 0 0 -3/2 -2/3 求得最优解为

Y*=(1,0,2,7,0,0)利用互补松弛定理，因为y=1>0,y=2>0，2* =12x +3x2 = 2所以[-x +2x, +2x, =5’又因为) +3y2-<6(r"), 即x, =0. 112yJx2=3x, = 2X"=(0,所以所以632x, +2x, =5[x=3z =12五、（本题20分）某汽车零件制作商，在不同的地方开设了3个工厂，从这些厂将汽车零件运至设在全国各地的4个仓库，并希望运费最小。下表列出了单位运价以及3个厂的供应量和4个仓库的需求量。请求出运费最小的运输方案。仓库运价23供应量14工12135502224130314327040502535需求量解：（1）用伏格尔法求出初始运输方案，如下表：仓库23运价4供应量1工厂50015023030325540705025需求量4035（2）用位势求空格检验数。由4

4        12 1,0,2,7,0,0 z Y （ ）T 利用互补松弛定理，因为 1 1 0, 3  2  0   y y ， 所以         - 2 2 5 3 2 1 2 3 1 2 x x x x x ，又因为 3 - 6( ) 1 2 3  y  y y  Y ，即 0. x1  所以             3 2 3 6 11 2 2 3 3 2 2 5 3 2 x x x x x ，所以         12 3 2 , 6 11 0, z X （ ）T 。 五、（本题 20 分）某汽车零件制作商，在不同的地方开设了 3 个工厂，从这些厂将汽 车零件运至设在全国各地的 4 个仓库，并希望运费最小。下表列出了单位运价以及 3 个厂的供应量和 4 个仓库的需求量。请求出运费最小的运输方案。 仓库 运价 工厂 1 2 3 4 供应量 1 2 1 3 5 50 2 2 2 4 1 30 3 1 4 3 2 70 需求量 40 50 25 35 解：（1）用伏格尔法求出初始运输方案，如下表： 仓库 运价 工厂 1 2 3 4 供应量 1 50 0 50 2 30 30 3 40 25 5 70 需求量 40 50 25 35 （2）用位势求空格检验数。由

u,+V,=c,[u, = 2[u + V2 = Ci2= 2u, = -1u, + V3=C13=3u,=0u, + V4 = C24 =1y =1u, + V, = C3 =1V2 = 2u, +Vs=C33=3V3 = 3[u3+V4=C34=2V4 = 2对空格,可由,=C,-(u, +v,)得Q11=1,O14=3,021 =2,022 =1,023=2,032 =2,检验数均为非负，故当前方案最优，x2=50,x24=30,x3=40,x3=25,x34=5,其余全为0，最优值为z=205。六、（本题20分）某厂拟建两种不同类型的冶炼炉。甲种炉每台投资为2个单位，乙种炉每台投资为1个单位，总投资不能超过10个单位：又该厂被许可用电量为2个单位，乙种炉被许可用电量为2个单位，但甲种炉利用余热发电，不仅可以满足本身需要，而且可供出电量1个单位。已知甲种炉每台收益为6个单位，乙种炉每台收益为4个单位。试问：应建甲、乙两种炉各多少台，使之收益最大？要求：（1）写出该整数规划问题的数学模型。（2）表1是通过单纯形法给出该整数规划问题的松弛问题的最优解和终表，请你在此基础上用割平面法计算本题的最优解。表1bX1X20.基变量X3X40X112/518/5-1/501X214/51/52/500-32.8-16/5-2/5-z解：设x1,x2为甲乙种炉应建台数，则maxz=6x, +4x,2x +x2 ≤10-x, +2x2 ≤2s.t.[x,x2≥0,且为整数确定割平面方程：5

5                                                  2 3 2 1 0 1 2 2 3 1 1 3 2 4 3 2 1 3 2 1 3 4 3 4 3 3 3 3 3 1 3 1 2 4 2 4 1 3 1 3 1 2 1 2 v v v v u u u u v c u v c u v c u v c u v c u v c u v c i j ij 对空格，可由 ( ) ij ij i j   c  u  v 得 1, 3, 2, 1, 2, 2, 1 1  1 4   2 1   2 2   2 3   3 2  检验数均为非负，故当前方案最优， 50, 30, 40, 25, 5, 1 2  2 4  3 1  3 3  3 4       x x x x x 其余全为 0，最优值为 z=205。 六、（本题 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 解：设 x1,x2 为甲乙种炉应建台数，则              , 0,且为整数 2 2 2 10 . . max 6 4 1 2 1 2 1 2 1 2 x x x x x x s t z x x 确定割平面方程：

2141X2+-X3A5554.x+21取x,-2=3*+号x)≤0555从而，构造割平面，并且标准化，加入最优表中，用对偶单纯形法求最优解，见下表。X3bX4X1X2X5基变量1002/5X1-1/518/5011/52/50X214/500X5-1/5-2/51-4/5000-z-32.8-16/5-2/5X1X2X3X4X5b基变量X141001/2-1/2000211X20201X41/2-5/2000-3-1-32-ZX*=(4,2,0,2,0)，2*=32。此解为整数解，故计算停止。6

6 ) 0 5 2 5 1 5 4 2 5 14 5 2 5 1 2 3 4 2 3 4         x x x x x x 取 （ 从而，构造割平面，并且标准化，加入最优表中，用对偶单纯形法求最优解，见下表。 基变量 b X1 X2 X3 X4 X5 X1 18/5 1 0 2/5 -1/5 0 X2 14/5 0 1 1/5 2/5 0 X5 -4/5 0 0 -1/5 -2/5 1 -z -32.8 0 0 -16/5 -2/5 0 基变量 b X1 X2 X3 X4 X5 X1 4 1 0 1/2 0 -1/2 X2 2 0 1 0 0 1 X4 2 0 0 1/2 1 -5/2 -z -32 0 0 -3 0 -1 4 2,0,2,0 32 * * X  z  （ ， ）T ， 。此解为整数解，故计算停止