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

测试题一答案一、（本题15分）已知如下线性规划问题：maxz=2x+x,+5x,+6x[2x +x + X ≤82x, +2x, +X +2x, ≤12[,x,,x≥0已知其对偶问题的最优解为Y*=(4,1)。试用对偶理论求出原问题的最优解。解：对偶问题是：minw=8y+12yz2y+2y,≥22y, ≥1y+y,≥5J+2y,≥6y,y2≥0设原问题最优解为X*=(x1，x2，x3，x4)T，将Y*带入对偶间题约束条件中，得(1)(2)为严格不等式；由互补松弛条件知，x =x, =0。因为y=40，及y2=1≠0，所以原问题的两个约束条件应取等号，故有x+ x=8[x; +2x, =12解方程组得：x，=x=4，所以原问题的最优解为X*=(0,0,4,4)，最优值z=44。二、（本题20分）某汽车零件制作商，在不同的地方开设了3个工厂，从这些厂将汽车零件运至设在全国各地的4个仓库，并希望运费最小。下表列出了单位运价以及3个厂的供应量和4个仓库的需求量。请求出运费最小的运输方案。仓库运价1234供应量工厂1213550222413043132702535需求量4050-

1 测试题一答案 一、（本题 15 分）已知如下线性规划问题： 1 2 3 4 1 3 4 1 2 3 4 1 2 3 4 max 2 5 6 2 8 2 2 2 12 , , , 0 z x x x x x x x x x x x x x x x                  已知其对偶问题的最优解为 Y ＊ =(4,1)。试用对偶理论求出原问题的最优解。 解：对偶问题是： 设原问题最优解为 X ＊＝(x1，x2 ，x3，x4) T , 将 Y ＊ 带入对偶问题约束条件中，得(1)(2)为严格不等式；由互补松弛条件知， * * 1 2 x x   0 。 因为 y1=4≠0，及 y2=1≠0，所以原问题的两个约束条件应取等号，故有 解方程组得： * * 3 4 x x   4 , 所以原问题的最优解为 X ＊ =(0,0,4,4)，最优值 z=44。 二、（本题 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 2 1 2 2 1 2 1 2 1 2 min 8 12 2 2 2 2 1 5 2 6 , 0 w y y y y y y y y y y y                * * 3 4 * * 3 4 8 2 12 x x x x       

解：（1）用伏格尔法求出初始运输方案，如下表：仓库运价3241供应量工厂1500502303053402570402535需求量50（2）用位势求空格检验数。由u, +y,=Cy[u = 2u + V2 = C2=2u, = -1u, + Vg = C13 = 3u, =0u2+V4=C24=1y, =1u, +V, = C31 =1V2 = 2u+V,= C33=3V3 = 3[u+ V4= C34=2[V4 = 2对空格，可由,=c-(u,+y,)得01 =1,014 =3,021=2,022=1,023=2,032 =2,检验数均为非负，故当前方案最优，x2*=50,x24=30,x31=40,x33=25,x34=5,其余全为0，最优值为Z=205三、（本题20分）某市准备在下一年度预算购置一批救护车，已知每辆救护车购置价格为20万元。救护车用于所属的两个县，各分配x和xB台，A县救护站从接到求救电话到救护车出动的响应时间为（40-3xA）min，B县相应的响应时间为（50-4xB）min，该市确定如下优先级目标。P1：救护车的购置费用不超过400万元：P2：A县的响应时间不超过5min；P3：B县的响应时间不超过5min。要求：（1）建立目标规划模型（不用求解）。（2）若对优先级目标作出调整，P2变P1，P3变P2，Pi变P3，重新建立目标规划模型（不用求解）。解：设x.为分配给A县的救护车数，xB为分配给B县的救护车数量。2

2 解：（1）用伏格尔法求出初始运输方案，如下表： 仓库 运价 工厂 1 2 3 4 供应量 1 50 0 50 2 30 30 3 40 25 5 70 需求量 40 50 25 35 （2）用位势求空格检验数。由                                                  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 分）某市准备在下一年度预算购置一批救护车，已知每辆救护车购置价 格为 20 万元。救护车用于所属的两个县，各分配 xA和 xB台，Ａ县救护站从接到求救 电话到救护车出动的响应时间为（40-3xＡ）min，B 县相应的响应时间为（50-4xB）min， 该市确定如下优先级目标。 P1：救护车的购置费用不超过 400 万元； P2：A 县的响应时间不超过 5min； P3：B 县的响应时间不超过 5min。 要求：（1）建立目标规划模型（不用求解）。 （2）若对优先级目标作出调整，P2变 P1，P3变 P2，P1 变 P3，重新建立目标规划 模型（不用求解）。 解：设 xA为分配给 A 县的救护车数，xB为分配给 B 县的救护车数量

minz=Pd+P,d,+Pd,20x +20x +dj -d = 400(1）目标规划模型为：40-3x+d-d±=5s.t.50-4xB+dj-d±=5xxg≥0,d,dt≥0(i=12,3)(2）与（1）比较，只是目标函数改变了，而约束条件没有变化。故（2）的目标规划模型为：minz=Pd++Pd,+P,d20x+20xg+d,-d=40040-3x+d,-d,=5s.t.50-4xg+dj-d=5x,x≥0,d,d≥0(i=1,2,3)四、（本题20分）有一份中文说明书，需译成英、日、德、俄四种文字，分别记作A、B、C、D。现有甲、乙、丙、丁四人，他们将中文译成不同语种的说明书所需时间如下表所示，问如何分派任务，可使总时间最少？任务BcDA人员甲671124598乙34丙110丁5982解：1）变换系数矩阵，增加0元素[61172-2594404059458500404a建1(cg)=24310420930382-259S6030712）试指派（找独立0元素）3

3 (1) 目标规划模型为：                                     , 0, , 0( 1,2,3) 50 4 5 40 3 5 20 20 400 . . min 3 3 2 2 1 1 1 1 2 2 3 3 x x d d i x d d x d d x x d d s t z Pd P d P d A B i i B A A B (2) 与（1）比较，只是目标函数改变了，而约束条件没有变化。故（2）的目标规划模 型为：                                     , 0, , 0( 1,2,3) 50 4 5 40 3 5 20 20 400 . . min 3 3 2 2 1 1 1 2 2 3 3 1 x x d d i x d d x d d x x d d s t z Pd P d P d A B i i B A A B 四、（本题 20 分）有一份中文说明书，需译成英、日、德、俄四种文字，分别记作 A、 B、C、D。现有甲、乙、丙、丁四人，他们将中文译成不同语种的说明书所需时间如 下表所示，问如何分派任务，可使总时间最少？ 任务 人员 A B C D 甲 6 7 11 2 乙 4 5 9 8 丙 3 1 10 4 丁 5 9 8 2 解：1）变换系数矩阵，增加 0 元素 2）试指派（找独立 0 元素） 2 1 4 2 5 9 8 2 3 1 10 4 4 5 9 8 6 7 11 2 ( )                 cij              3 7 6 0 2 0 9 3 0 1 5 4 4 5 9 0             3 7 1 0 2 0 4 3 0 1 0 4 4 5 4 0

4?433）作最少的直线覆盖所有0元素444）没有被直线通过的元素中选择最小值为1，变换系数矩阵，将没有被直线通过的所有元素减去这个最小元素；直线交点处的元素加上这个最小值。得到新的矩阵，重复2）步进行试指派343OO4-得最优解矩阵为：0000000000即完成4个任务的总时间最少为：2十4十1+8=15五、（本题25分）某厂拟建两种不同类型的冶炼炉。甲种炉每台投资为2个单位，乙种炉每台投资为1个单位，总投资不能超过10个单位：又该厂被许可用电量为2个单位，乙种炉被许可用电量为2个单位，但甲种炉利用余热发电，不仅可以满足本身需要，而且可供出电量1个单位。已知甲种炉每台收益为6个单位，乙种炉每台收益为4个单位。试问：应建甲、乙两种炉各多少台，使之收益最大？该问题也可如下表表示。（要求用割平面法求解该整数规划问题）甲种炉(x)乙种炉(x2)限量2110每台投资/单位22-1用电量/单位46收益/单位解：设X,X为甲乙种炉应建台数，则4

4 3）作最少的直线覆盖所有 0 元素 4）没有被直线通过的元素中选择最小值为 1，变换系数矩阵，将没有被直线通过的所 有元素减去这个最小元素；直线交点处的元素加上这个最小值。得到新的矩阵，重复 2） 步进行试指派 得最优解矩阵为： 即完成 4 个任务的总时间最少为：2＋4＋1+8=15 五、（本题 25 分）某厂拟建两种不同类型的冶炼炉。甲种炉每台投资为 2 个单位，乙 种炉每台投资为 1 个单位，总投资不能超过 10 个单位；又该厂被许可用电量为 2 个单 位，乙种炉被许可用电量为 2 个单位，但甲种炉利用余热发电，不仅可以满足本身需 要，而且可供出电量 1 个单位。已知甲种炉每台收益为 6 个单位，乙种炉每台收益为 4 个单位。试问：应建甲、乙两种炉各多少台，使之收益最大？该问题也可如下表表示。 （要求用割平面法求解该整数规划问题） 甲种炉(x1) 乙种炉(x2) 限 量 每台投资/单位 2 1 10 用电量/单位 -1 2 2 收益/单位 6 4 解：设 x1,x2为甲乙种炉应建台数，则             3 7 1 2 4 3 1 4 4 5 4 ◎ ◎ ◎ Ø Ø             3 7 1 2 4 3 1 4 4 5 4 ◎ ◎ ◎ Ø Ø √ √ √             2 6 2 4 4 1 5 3 4 3 ◎ ◎ ◎ Ø ◎ Ø             0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 1

max z=6x, +4x2一2x +x2 ≤10-X +2x2≤2s.t.X,2≥0,且为整数用单纯形法求最优解，见下表。bXiX30.基变量X2X4205X310112201X4-1-06400-z5XI11/21/2010701X45/21/214/50-30-301-Z1XI18/502/5-1/501X214/51/52/500-16/5-2/5-32.8-z=32.8最优解为x=（，号00）1214=X3+X2+-X455"354确定割平面方程：2.14=取x,-2(x+×)≤0555从而，构造割平面，并且标准化，加入最优表中，用对偶单纯形法求最优解，见下表。bXiX2X3X4Xs基变量Xi1018/52/5-1/50X201014/51/52/5001Xs-4/5-1/5-2/50-32.80-16/5-2/50-ZbXiX2X3X4基变量XsX41001/2-1/2X22010012001X41/2-5/200-30-32-1-Z5

5              , 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 用单纯形法求最优解，见下表。 基变量 b X1 X2 X3 X4  i X3 10 2 1 1 0 5 X4 2 -1 2 0 1 - -z 0 6 4 0 0 X1 5 1 1/2 1/2 0 10 X4 7 0 5/2 1/2 1 14/5 -z -30 0 1 -3 0 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 最优解为 x ( , ,0,0) , 0 32.8 5 14 5 0 18  z  T 确定割平面方程： ) 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

X=(4,2,0,2,T，z=32。此解为整数解，故计算停止。6

6 X 4,2,0 2,0 z 32 T    （ ， ），  。此解为整数解，故计算停止