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

《运筹学》试卷A标准答案及评分标准一、填空题（每空题1.5分共15分）1、02、最优解3、负4、高、大5、不含圈（或连通图），有且仅有p-1条边6、人工变量、不能全部出基7、相等8、动态规划注：本题能答出等价的名词即给分二、解：设P、Q的产量分别为X1、X，吨。则线性规划模型为（5分）maxz=3x+5x2x+3x2≤122x, + X2 ≤102x+2x, ≤12[X,X2 ≥0三、解：标准化：（4分）z=3xi +5x2max= 12x+3x2+X3= 102x, + X2+X42x, +2x2+x, =12[X1,X2,X3,X4,X ≥0取 B=(P,P,P)作为初始可行基，做初始单纯形表，并逐步选代得：（12 分)35000Cj0XBbCBxiX2x3X4X50121100[3] 12/3X30020110110/1x41222000112/2X5350009j-

1 《运筹学》试卷 A 标准答案及评分标准 一、 填空题（每空题 1.5 分 共 15 分） 1、0 2、最优解 3、负 4、高、大 5、不含圈（或连通图），有且仅有 p-1 条边 6、人工变量、不能全部出基 7、相等 8、动态规划 注：本题能答出等价的名词即给分 二、解：设 P、Q 的产量分别为 x1、x2吨。则线性规划模型为 （5 分）                 0 2 2 12 2 10 3 12 3 5 1 2 1 2 1 2 1 2 1 2 x ,x x x x x x x max z x x 三、解：标准化：（4 分）                    0 2 2 12 2 10 3 12 3 5 1 2 3 4 5 1 2 5 1 2 4 1 2 3 1 2 x ,x ,x ,x ,x x x x x x x x x x max z x x 取   3 4 P5 B  P ,P , 作为初始可行基，做初始单纯形表，并逐步迭代得：（12 分） cj 3 5 0 0 0 θ CB XB b x1 x2 x3 x4 x5 0 0 0 x3 x4 x5 12 10 12 1 2 2 [3] 1 2 1 0 0 0 1 0 0 0 1 12/3 10/1 12/2 σj 3 5 0 0 0

541/301/31012X2060105/3-1/318/5x404003-2/31Xs[4/3]4/30-5/3000j5-1/43011/20X2010011/2-5/4x433100-1/23/4x100-10-1aj从上表看出，所有。j<0，因此X=(3,3, 0, 1, 0)或X=(3, 3) (2分)最优解为：最优值为：7z*=3X3+5X3=24 。(2分)(10分）四、解：对偶规划maxw=yi+4ymax w= yi +4y2+≥3- yi- y2 ≤-3或- J +2y2 = 2- yi +2y2 = 2[,≥0,y,无约束≥0,y,无约束max w=-y, +4y2Ji-2 ≤-3或注：能答出等价模型之一即可Ji +2y2 = 20,无约束五、（20分）解：解：（1）最小元素法：（也可以用其他方法，酌情给分）设xi为由 A;运往 B;的运量（i=1,2,3;j=1,2,3,4），列表如下：销地产量B2B3B4B,产地1252525252035501530销量15203035100.5分2

2 5 0 0 x2 x4 x5 4 6 4 1/3 5/3 [4/3] 1 0 0 1/3 -1/3 -2/3 0 1 0 0 0 1 12 18/5 3 σj 4/3 0 -5/3 0 0 5 0 3 x2 x4 x1 3 1 3 0 0 1 1 0 0 1/2 1/2 -1/2 0 1 0 -1/4 -5/4 3/4 σj 0 0 -1 0 -1 从上表看出，所有σj≤0，因此 最优解为：   T X0  3, 3, 0, 1, 0 或   T X0  3, 3 （2 分） 最优值为： z*=3×3+5×3=24 。（2 分） 四、解：对偶规划 （10 分）              1 2无约束 1 2 1 2 1 2 0 2 2 3 4 y , y y y y y max w y y 或               1 2无约束 1 2 1 2 1 2 0, 2 2 -3 max 4 y y y y y y w y y 或              1 2无约束 1 2 1 2 1 2 0, 2 2 -3 max 4 y y y y y y w y y 注： 能答出等价模型之一即可 五、（20 分）解： 解： （1）最小元素法：（也可以用其他方法，酌情给分） 设 xij为由 Ai 运往 Bj的运量（i=1,2,3; j=1,2,3,4）, 列表如下： 销 地 产 地 B1 B2 B3 B4 产 量 1 2 3 15 20 30 25 5 5 25 25 50 销 量 15 20 30 35 100 .5 分

所以，基本的初始可行解为：X14=25，X22=20，X24=5X31=15, X33 =30, X34=5其余的xij=0.2分（2）求最优调运方案：①会求检验数，检验解的最优性：G1=2；12=2；Q13=3；.3分021-1; 23-5; 032=-1....2分①会求调整量进行调整：=5销产量地B2B3B4B,产地25251225151053305015销量15203010035...3分?再次检验011-1; 012=2; 013=2;...3分021-0; 023=4; 034=1.....④能够写出正确结论最优方案为：X14-25，X22=15，X24=10，X31=15,X32=5，X33=30其余的x=0...1分最少运费为535...1分。六、解：...3分（1）益损矩阵如下表所示：销售S2SiS3S4Ss进货1002501502003003030303010030Ar1045454545150A2-10256060A320060305407575A4250As300-50-15205590（2）乐观法（最大最大）：A5，订购300个；.......2分.（3）后悔值法：后悔矩阵如下表所示：...3分最大后悔SiS2S3S4Ss值15306004560Al153045A,200453

3 所以，基本的初始可行解为：x14 =25； x22=20 ； x24 =5 ； X31 =15； x33 =30； x34=5 其余的 xij=0。 .2 分 （2）求最优调运方案： ○1 会求检验数，检验解的最优性：11=2；12=2；13=3； 21=1；23=5；32= - 1.3 分 ○2 会求调整量进行调整：=5 .2 分 销 地 产 地 B1 B2 B3 B4 产 量 1 2 3 15 15 5 30 25 10 25 25 50 销 量 15 20 30 35 100 .3 分 ○3 再次检验 11=1；12=2；13=2； 21=0；23=4；34= 1.3 分 ○4 能够写出正确结论 最优方案为：x14=25 ， x22 =15， x24 =10， x31 =15，x32 =5 ，x33=30 其余的 xij=0。 .1 分 最少运费为： 535 .1 分。 六、解： （1）益损矩阵如下表所示：.3 分 销 售 进 货 S1 100 S2 150 S3 200 S4 250 S5 300 A1 100 30 30 30 30 30 A2 150 10 45 45 45 45 A3 200 －10 25 60 60 60 A4 250 －30 5 40 75 75 A5 300 －50 －15 20 55 90 （2）乐观法（最大最大）：A5 ，订购 300 个；.2 分 （3）后悔值法：后悔矩阵如下表所示：.3 分 S1 S2 S3 S4 S5 最大后悔 值 A1 0 15 30 45 60 60 A2 20 0 15 30 45 45

4020153040A3015A46040206020As806040080A3，订购200个。..2分七、解：（10分）1、把对四个工厂投资依次看成4个阶段的决策过程，对第k个工厂投资看作是第k个阶段的决策，k=1,23,4,2、状态变量：表示第k个阶段可用于第k,k+1,,4个工厂投资的资金总额；3、决策变量：uk表示第k个阶段对第k个工厂的投资额；4、允许决策集合：U={0,100,…),5、状态转移方程为：Sk+1=Sk-k，S,=6006、阶段指标函数为：8k(s)表示第k 个阶段、状态变量为k、决策变量为"k时第k个工厂的利润增长额；7、令f(s）为从第k个阶段开始到最后一个阶段末的最优值8、最优指标函数递推关系：f(sk）=maxigk(st）+fk(sk1))；LEL9、边界条件：Js(ss)=0注：①关键步骤不能出现原则上的错误，否则，本题不得分；②非原则性错误，每错一处扣1分。八、用标号法求v1到v6的最短路。（10分）(4.vl)(9.v3)V4 (10,v2)V2614(0.0)ViVe8(12.v5)(14,v4)V3 (6.v2)7Vs(10.v4)(11,v2)(8,v1)(13,v3)最短路为：Vi,V2,V3,V4,Vs,V6（1分）长度为：12(1分)4

4 A3 40 20 0 15 30 40 A4 60 40 20 0 15 60 A5 80 60 40 20 0 80 A3 ，订购 200 个。.2 分 七、解：（10 分） 1、把对四个工厂投资依次看成 4 个阶段的决策过程，对第 k 个工厂投资看作是 第 k 个阶段的决策， k 1,2,3,4 ； 2、状态变量： k s 表示第 k 个阶段可用于第 k, k 1,  ,4 个工厂投资的资金总额； 3、决策变量： k u 表示第 k 个阶段对第 k 个工厂的投资额； 4、允许决策集合： {0,100, , } k k U   s ； 5、状态转移方程为： sk1  sk  uk ,s1  600 ； 6、阶段指标函数为： ( ) k k g s 表示第 k 个阶段、状态变量为 k s 、决策变量为 k u 时 第 k 个工厂的利润增长额； 7、令 ( ) k k f s 为从第 k 个阶段开始到最后一个阶段末的最优值 8、最优指标函数递推关系： ( ) max{ ( ) ( )} 1 1   k k  k k u U k k f s g s f s k K ； 9、边界条件： f 5 (s5 )  0。 注：○1 关键步骤不能出现原则上的错误，否则，本题不得分； ○2 非原则性错误，每错一处扣 1 分。 八、用标号法求 v1 到 v6 的最短路。（10 分） 最短路为：v1,v2,v3,v4,v5,v6（1 分） 长度为：12 （1 分） 4 V4 V3 V5 V1 V2 V6 6 2 8 7 3 7 1 5 2 (0,0) (4,v1) (6,v2) （8,v1） (9,v3) (10,v2) (10,v4) (11,v2) (13,v3) (12,v5) (14,v4)