《运筹学》课程教学资源（试卷习题）运筹B卷（答案）

《运筹学》试卷B标准答案及评分标准一、判断题（正确的划／号，错误的划×号，每题1分共10分）1、/2、X3、/4、X5、/6、X 7、X8、X 9、X 10、V二、解：设甲、乙、丙的投入量分别为x1，X2，X3千克。则线性规划模型为（10分)minz= 2x +2x, +3x3[20x,+40x2+10x,≥2510x,+20x,+20x,≥18[,X2,,≥0三、解：标准化：（4分）maxz=-2x2+6xg-4xs=14+2x5X +3x2 - X3= 24-2x2 +4x, +x4-4x2 +3x,+8x,+x。=20[X1,X2,X3,4,X5,X≥0取 B=(P,P,P)作为初始可行基，做初始单纯形表，并并逐步选代得：（12分）60-20-40cj0x2XBbx1x3x4x5x6CB3-10201410X10-2002410[4]24/4X4-40200308120/3X60-260°j0-420201[5/2]01/4020/2.5X10660-1/21/410X3020-5/2081-3/4X600-3/2-40oj1

1 《运筹学》试卷 B 标准答案及评分标准 一、 判断题（正确的划 √ 号，错误的划 ╳ 号，每题 1 分 共 10 分） 1、√ 2、╳ 3、√ 4、╳ 5、√ 6、╳ 7、╳ 8、╳ 9、╳ 10、√ 二、解：设甲、乙、丙的投入量分别为 x1，x2，x3千克。则 线性规划模型为 （10 分）                , , 0 10 20x 20 18 20 40 10x 25 min 2 2 3 1 2 3 1 3 3 1 2 3 1 2 3 x x x x x x x z x x x 三、解：标准化：（4 分）                          , , , , , 0 4 3 8 20 2 4 24 3 2 14 max 2 6 4 1 2 3 4 5 6 2 3 5 6 2 3 4 1 2 3 5 2 3 5 x x x x x x x x x x x x x x x x x z x x x 取   1 4 P6 B  P ,P , 作为初始可行基，做初始单纯形表，并逐步迭代得：（12 分） cj 0 -2 6 0 -4 0 θ CB XB b x1 x2 x3 x4 x5 x6 0 0 0 x1 x4 x6 14 24 20 1 0 0 3 -2 -4 -1 [4] 3 0 1 0 2 0 8 0 0 1 － 24/4 20/3 σj 0 -2 6 0 -4 0 0 6 0 x1 x3 x6 20 6 2 1 0 0 [5/2] -1/2 -5/2 0 1 0 1/4 1/4 -3/4 2 0 8 0 0 1 20/2.5 - - σj 0 1 0 -3/2 -4 0

-282/5104/501/10X2610012/501/53/10X3022100101-1/2X6-2/500-8/5-24/50aj(2分)从上表中看出，所有≤0，故X*=（0，8，10，0，0,22)T,(2分)z*=-2X8+6X10=44(10分)四、解：对偶规划W=2yi +3y2 +2y3w=-2y +3y2 +2y3maxmax2y1+y3≤3+y3≤3-2yi2yi +y2 -2y, ≤-2-2yi +y2 -2y, ≤-2-yi +2y2 +2y, ≥4- yi-2y2 -2y, ≤-4或3yi-2y2 +y =0-3yi -2y2 +y3 =0≤0,y2≥0,无约束≥0,y2≥0,,无约束五、（20分）解：（1）最小元素法：设Xij为由A;运往B的运量（i=1,2,3；j-1,2,3,4），列表如下：销地B3B4B2产量B,产地14371I23463396620销量35.5分所以，基本的初始可行解为：X13=4X14=3:X21=3X23 =21X32 =6X34=3.2分其余的xij=0.（2）求最优调运方案：O11 = 1,012 = 2,022 = 1,①会求检验数，检验解的最优性：..3分024 = -1,031 =10,033 =122

2 -2 6 0 x2 x3 x6 8 10 22 2/5 1/5 1 1 0 0 0 1 0 1/10 3/10 -1/2 4/5 2/5 10 0 0 1 σj -2/5 0 0 -8/5 -24/5 0 从上表中看出，所有σj≤0，故 X*=（0，8，10，0，0，22）T， （2 分） z*=－2×8+6×10=44 （2 分） 四、解：对偶规划 （10 分）                            1 2 3无约束 1 2 3 1 2 3 1 2 3 1 3 1 2 3 0 0 3 2 0 2 2 4 2 2 2 2 3 2 3 2 y , y , y y y y y y y y y y y y max w y y y 或                             1 2 3无约束 1 2 3 1 2 3 1 2 3 1 3 1 2 3 0, 0, - 3 2 0 2 2 -4 - 2 2 2 - 2 3 max 2 3 2 y y y y y y y y y y y y y y w y y y 五、（20 分） 解：（1）最小元素法： 设 xij 为由 Ai 运往 Bj 的运量（i=1,2,3; j=1,2,3,4）, 列表如下： 销 地 产 地 B1 B2 B3 B4 产 量 1 2 3 3 6 4 1 3 3 7 4 9 销 量 3 6 5 6 20 .5 分 所以，基本的初始可行解为：x13=4 ； x14 =3 ； x21 =3 x23 =21 x32 =6 x34=3 其余的 xij=0。 .2 分 （2）求最优调运方案： ○1 会求检验数，检验解的最优性： 11 12 22 24 31 33 1, 2, 1, 1, 10, 12              .3 分

..2分①会求调整量进行调整：0=1销地B3产量B,B2B4产地152721433396销量365620.3分?再次检验....3分①能够写出正确结论解为：X13=5：X14=2X21=3X24=1，X32=6X34=3..分其余的xij-0....分最少运费f=3×5+10×2+1×3+8×1+4×6+5×3=85六、解：（1）益损矩阵如下表所示：......3分销售S1S2S3S4订购500100015002000A50015001500150015000A21000300030003000A3150015001500450045000A42000300030006000（2）悲观法：A1，订购500公斤。...2分....3分（3）后悔矩阵如下表所示：S1S2S3S4030004500Al5001500A210001500015003000150001500A;15003000A,20004500300001500按后悔值法商店应取决策为A2或A3，即订购1000公斤或1500公斤。...2分七、解：(1）设阶段变量k表示年度，因此，阶段总数n=3。3

3 ○2 会求调整量进行调整：  1 .2 分 销 地 产 地 B1 B2 B3 B4 产 量 1 2 3 3 6 5 2 1 3 7 4 9 销 量 3 6 5 6 20 .3 分 ○3 再次检验 .3 分 ○4 能够写出正确结论 解为：x13=5 ； x14 =2 ； x21 =3 x24 =1， x32 =6 x34=3 其余的 xij=0。 .1 分 最少运费 f              3 5 10 2 1 3 8 1 4 6 5 3 85 .1 分 六、解： （1）益损矩阵如下表所示：.3 分 销 售 订 购 S1 500 S2 1000 S3 1500 S4 2000 A1 500 A2 1000 A3 1500 A4 2000 1500 0 －1500 －3000 1500 3000 1500 0 1500 3000 4500 3000 1500 3000 4500 6000 （2）悲观法：A1 ，订购 500 公斤。.2 分 （3）后悔矩阵如下表所示：.3 分 S1 S2 S3 S4 A1 500 0 1500 3000 4500 A2 1000 1500 0 1500 3000 A3 1500 3000 1500 0 1500 A4 2000 4500 3000 1500 0 按后悔值法商店应取决策为 A2或 A3 ，即订购 1000 公斤或 1500 公斤。.2 分 七、解： (1) 设阶段变量 k 表示年度，因此，阶段总数 n=3

(2）状态变量ss表示第k年度初拥有的完好机床台数，同时也是第k-1年度末时的完好机床数量。(3）决策变量uk，表示第k年度中分配于生产产品PI的机器台数。于是Sk-uk便为该年度中分配于生产产品P2的机器台数，（4）状态转移方程为：Sk+1 =0.35us +0.65(S -uk)(5)允许决策集合，在第k段为：Ur(st)=(ur|0≤u,≤st)(6)阶段指标函数：设gk(sk,uk)为第k年度的产量，则gk(Sk,uk)=45uk +35(Sk -us)(7）递推方程。令f（s）表示由第k年的状态sk出发，采取最优分配方案到第3年度结束这段时间的产品最优产量，根据最优化原理有以下递推关系：fr(s)=max(gr(sk,ur)+ fk+I(sk+1)MEUK(8）边界条件为：3+1(S3+1)= 0注:①关键步骤不能出现原则上的错误，否则，本题不得分；②非原则性错误，每错一处扣1分。八、解：V, Z)(14)2(V-8)V (V2 7)V.(0. 0)V6)2(V=6)(.8)Lvi3)最短路线长为：8由V到V。的最短路线为：V-→V,→V,→V。.评分标准：正确标号：8分：正确写出结论：2分注：没有永久性标号“”记号的要酌情扣分。4

4 (2) 状态变量 sk 表示第 k 年度初拥有的完好机床台数，同时也是第 k–1 年度末时的完好机 床数量。 (3) 决策变量 uk，表示第 k 年度中分配于生产产品 p1 的机器台数。于是 sk– uk 便为该年 度中分配于生产产品 p2 的机器台数． (4) 状态转移方程为: (5) 允许决策集合，在第 k 段为： (6) 阶段指标函数：设 gk(sk,uk)为第 k 年度的产量，则 (7) 递推方程。 令 ( ) k k f s 表示由第 k 年的状态 sk 出发，采取最优分配方案到第 3 年度结束这段时间 的产品最优产量， 根据最优化原理有以下递推关系： ( ) max ( , ) 1 ( 1 )   k k k  k k u U k k f s g s u f s k K (8) 边界条件为: 注： ○1 关键步骤不能出现原则上的错误，否则，本题不得分； ○2 非原则性错误，每错一处扣 1 分。 八、解： 由 V1 到 V9 的最短路线为: V1→V3→ V7→V9 ． 最短路线长为：8 评分标准：正确标号：8 分；正确写出结论：2 分 注： 没有永久性标号“——”记号的要酌情扣分。 0.35 0.65( ) k 1 k k uk s   u  s  ( ) { } k k k k k U s  u 0  u  s ( , ) 45 35( ) k k k k k uk g s u  u  s  f 31 (s31 )  0 V1 V9 V5 V2 V4 V6 V8 4 3 2 3 4 8 3 3 3 1 2 2 1 V3 (0, 0) (V 1,4 ) (V 1,3 ) (V 2, 7 ) (V2,6) ) (V 2，7 ) (V3,6 ) (V 7 , 8 ) (V7 ,8)