试题 试题代码:453试题名称:运筹学 考生注意 1.本试题共七题,共3页,请考生认真检查 2.请务必将答案写在答卷纸上,写在试卷上的答案无效。 题号 四 总分 得分 华津机器制造厂专为拖拉机厂配套生产柴油机,今年头四个月收到的订单数量分别为 3000,4500,3500,5000台柴油机。该厂正常生产每月可生产柴油机3000台,利用加班还 可生产1500台。正常生产成本为每台5000元,加班生产还要追加1500元成本,库存成本 为每台每月200元。华津厂如何组织生产才能使生产成本最低,建立其线性规划模型。(20 分) 考虑线性规划问题:(25分) max==5x,+12x, +4x x1+2x2 ≤5 3x=2 X1 ≥0 用单纯形法求解,得其终表如下: B-b babi xI 4 X 1/525 1/5 29/5-M+2/5 X4为松弛变量,Xs为人工变量 1.上述模型的对偶模型为: 2.对偶模型的最优解为: 3.当两种资源分别单独增加一个单位时,目标函数值分别增加和 4.最优基的逆矩阵B= 5.如果原问题增加一个变量,则对偶问题的可行域将可能变大还是变小? 三、求解下列各题(解题方法自选)(20分)
试题 二 试题代码：453 试题名称：运筹学 考生注意∶ １．本试题共 七 题，共 3 页，请考生认真检查； ２．请务必将答案写在答卷纸上，写在试卷上的答案无效。 题号 一 二 三 四 五 六 七 总分 得分 签字 一、华津机器制造厂专为拖拉机厂配套生产柴油机，今年头四个月收到的订单数量分别为 3000，4500，3500，5000 台柴油机。该厂正常生产每月可生产柴油机 3000 台，利用加班还 可生产 1500 台。正常生产成本为每台 5000 元，加班生产还要追加 1500 元成本，库存成本 为每台每月 200 元。华津厂如何组织生产才能使生产成本最低，建立其线性规划模型。（20 分） 二、考虑线性规划问题：（25 分） , , 0 2 3 2 2 5 max 5 12 4 1 2 3 1 2 3 1 2 3 1 2 3 − + = + + = + + x x x x x x x x x z x x x 用单纯形法求解，得其终表如下： c j 5 12 4 0 -M CB XB x1 x2 x3 x4 x5 B -1b 12 x2 0 1 -1/5 2/5 -1/5 8/5 5 x1 1 0 7/5 1/5 2/5 9/5 c z j − j 0 0 -3/5 -29/5 -M+2/5 X4 为松弛变量，X5 为人工变量， 1．上述模型的对偶模型为： ； 2．对偶模型的最优解为： ； 3．当两种资源分别单独增加一个单位时，目标函数值分别增加 和 ； 4．最优基的逆矩阵 B -1 = 5．如果原问题增加一个变量，则对偶问题的可行域将可能变大还是变小？ . 三、求解下列各题（解题方法自选）（20 分）
minz=5x1+6x2+10x13+8x21+10x2+12x23 +4x21+4x2+5 x1+x12+x12=1 x21+x2+x23 x21+x2+x2=1 x1+x21+ 11 x1+x2+x2=1 x3+x23+x3 xn=1或0(i=12,3j=12,3) 四、用隐枚举法求解下列0-1规划问题(20分) maxz=5x1+7x2+10x3+3x4+x5 x1-3x+5x3+x4-4x5≥2 2 xI 2-3x3-2x4+2x5 2x2+2 五、用动态规划方法求解下列问题(25分) max==x1(1-x2)x3 ≥0j=1,2,3 六、今有三个仓库运送某种产品到四个市场上去,仓库的供应量是20,20和100,市场需 求量是20,20,60和20,仓库与市场之间的路线上的容量如下表(容量零表示两点间无直 接的路线可通)。用图论方法确定现有路线容量能否满足市场的需求,若不能,应修改哪条 线路的容量。(20分) 市场 仓库 供应量 0 100 需求量 七.下列叙述中正确的是( )(20分) 1.图解法与单纯形法,虽然求解的形式不同,但从几何上理解,两者是一致的 2.若线性规划的原问题有多重最优解,则其对偶问题也一定具有多重最优解 3.如果运输问题单位运价表的某一行(或某一列)元素分别加上一个常数k,最优调运 方案将不会发生变化:
1 0( 1,2,3; 1,2,3) 1 1 1 1 1 1 4 4 5 min 5 6 10 8 10 12 13 23 33 12 22 32 11 21 31 31 32 33 21 22 23 11 12 13 31 32 33 11 12 13 21 22 23 = = = + + = + + = + + = + + = + + = + + = + + + = + + + + + x i j x x x x x x x x x x x x x x x x x x x x x z x x x x x x ij 或 四、用隐枚举法求解下列 0-1 规划问题（20 分） ( ) max , , z x x x x x x x x x x x x x x x x x x x x j j= + + + + − + + − − + − − + − + − − = = 5 7 10 3 3 5 4 2 2 6 3 2 2 0 2 2 1 0 1 1 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 2 3 4 5 五、用动态规划方法求解下列问题（25 分） 0 1,2,3 1 max (1 ) 1 2 3 1 2 3 = − + = − x j x x x z x x x j 六、今有三个仓库运送某种产品到四个市场上去，仓库的供应量是 20，20 和 100，市场需 求量是 20，20，60 和 20，仓库与市场之间的路线上的容量如下表（容量零表示两点间无直 接的路线可通）。用图论方法确定现有路线容量能否满足市场的需求，若不能，应修改哪条 线路的容量。（20 分） 市场 仓库 1 2 3 4 供应量 1 30 10 0 40 20 2 0 0 10 50 20 3 20 10 40 5 100 需求量 20 20 60 20 七．下列叙述中正确的是 （ ）（20 分） 1. 图解法与单纯形法，虽然求解的形式不同，但从几何上理解，两者是一致的； 2. 若线性规划的原问题有多重最优解，则其对偶问题也一定具有多重最优解； 3. 如果运输问题单位运价表的某一行（或某一列）元素分别加上一个常数 k，最优调运 方案将不会发生变化；
∑∑ 4.对于极大化问题maxZ=1=1=1 c=mx,}b=c-c转化为极小化向 mnW=∑∑bx 题 则利用匈牙利法求解时,极大化问题的最优解就是极小化 问题的最优解,但目标函数相差:n+c; 5.如果图中从v至各点均有惟一的最短路,则连接至其他各点的最短路在去掉重复部 分后,恰好构成该图的最小支撑树 试题二答案 、解:设x代表第i月正常生产的柴油机数量, y代表第i月加班生产的柴油机数量, 2代表第i月末的库存量,则=1=4 minz=500Cx+6500∑y+200∑ x1+y1≥3000 二1+x2+y2≥4500 22+x3+y3 ≥3500 3+x4+y4=5000 x2,y1,-≥0,i=1,2,3,4 解: min W=5y,+2y2 y1+2y2≥5 2y1-y2≥12 y1+3y2≥4 1、对偶模型 y≥0,y2无约束 2、由单纯形表可看出 y1*=+(-3)=3由于 yn×x1=0,y2×x2=0,而x1≠0,x2≠0 ya=0,y2=0 则对偶问题的第一、二个约束是紧的,可解出2=-3 将M1,y2代入第三个约束,满足约束条件,则y*=(y,y2)=(普,-3w*=均 3、5和2 2/5-1/5 4、B-1=(1/52/5 5、如果原问题增加一个变量,则对偶问题就增加一个约束条件,它的可行域要么减少
4. 对于极大化问题 max Z = ij n i n j ij c x =1 =1 …令 ij ij ij c = max c ,b = c − c 转化为极小化问 题 ij n i n j ij W b x = = = 1 1 min ，则利用匈牙利法求解时，极大化问题的最优解就是极小化 问题的最优解，但目标函数相差： n+c； 5. 如果图中从 i v 至各点均有惟一的最短路，则连接至其他各点的最短路在去掉重复部 分后，恰好构成该图的最小支撑树。 试题二答案 一、解：设 i x 代表第 i 月正常生产的柴油机数量， i y 代表第 i 月加班生产的柴油机数量， i z 代表第 i 月末的库存量，则 i z =4 , , 0, 1,2,3,4 5000 3500 4500 3000 min 5000 6500 200 3 4 4 2 3 3 1 2 2 1 1 4 1 4 1 4 1 = + + = + + + + + = + + = = = x y z i z x y z x y z x y x y Z x y z i i i i i i i i i 二、解： 1、 对偶模型 1 2无约束 1 2 1 2 1 2 1 2 0, 3 4 2 12 2 5 min 5 2 y y y y y y y y W y y + − + = + 2、 由单纯形表可看出， 5 29 5 29 1 y * = −(− ) = 由 于 0, 0 0; 0, 0, 0 1 2 1 1 2 2 1 2 = = = = s s s s y y y x y x 而x x 则对偶问题的第一、二个约束是紧的，可解出 5 2 y2 = − 将 1 2 y , y 代入第三个约束，满足约束条件，则 5 141 5 2 5 29 y* = ( y1 , y2 ) = ( ,− ),w* = T 3、5 和 2 4、 = −1 B − 1/ 5 2 / 5 2 / 5 1/ 5 5、如果原问题增加一个变量，则对偶问题就增加一个约束条件，它的可行域要么减少
要么不变,绝对不会变大 、解:此题可看作指派问题求解: 584 1012 467 000 100 优解x21=1,412=Nx3=1,其余为0Z*=19 四、解:将最大化问题化为极小化问题,并将系数转为正,即令x=1-x,整理得 mnz=5x1+7x,+10x2+3x4+x-26 x1-3x2+5x3+x4-4xs≤-2 x1+6x2-3x3-2x4+2x5≤l 2x2+2x3-x4-xs≤-3 0或l( 综上,该0-1规划无可行解 五、解:按三个变量划分为三个阶段,状态转移方程 f(s3)=mx{x3}=,x3*=S2 0≤x3≤S3 第二阶段。(3)=mx(s)=mm(2-x)=s2 0≤x2sS20≤x2SS2 其中 f()=mx41×s2}=mxx×(2-x1)= 0≤x1≤2 0≤x1≤2 其中x*=3 最优解x1* 六、解:依题意,首先给出一个可行流
要么不变，绝对不会变大。 三、解：此题可看作指派问题求解： 5 6 10 1 2 5 0 1 4 0 0 3 8 10 12 ~ 4 6 7 ~ 0 2 3 ~ 0 1 2 4 4 5 0 0 0 0 0 0 1 0 0 最优解x21 =1, x12 =1, x33 =1,其余为0，Z* =19 四、解：将最大化问题化为极小化问题，并将系数转为正，即令 ' i 1 i x = − x ，整理得 0 1( 1,2, 5) 2 2 3 2 6 3 2 2 1 3 5 4 2 min 5 7 10 3 26 ' ' 5 ' 4 ' 3 ' 2 ' 5 ' 4 ' 3 ' 2 ' 1 ' 5 ' 4 ' 3 ' 2 ' 1 ' 5 ' 4 ' 3 ' 2 ' 1 ' ' ' = = − + − − − − + − − + − + + − − = + + + + − x j x x x x x x x x x x x x x x Z x x x x x j 或 0 1 2 3 4 5 6 7 8 9 10 11 12 1 ' x1 = 0 ' x1 = 1 ' x2 = 1 ' x3 = 0 ' x3 = 0 ' x2 = 1 ' x2 = 0 ' x2 = 1 ' x3 = 1 ' 0 x3 = ' x3 = 0 ' x3 = 综上，该 0-1 规划无可行解 五、解：按三个变量划分为三个阶段，状态转移方程 第三阶段： 3 3 3 3 3 * 2 f (s ) = max x = s , x = s 0 3 3 x s 第二阶段： 2 4 2 ' 1 2 2 ' 3 2 ' 2 2 2 f (s ) = max x (s ) = max x (s − x ) = s 2 ' 0 2 x s 2 ' 0 2 x s 其中 2 2 ' 1 x2 * = s ( 1 ) 2 ' 2 x = − x 第一阶段： 27 8 2 2 4 1 1 1 2 4 2 1 1 1 1 f (s ) = max x s = max x (2 − x ) = 0 x1 2 0 x1 2 其中 3 2 x1 * = 27 8 3 2 3 3 1 3 ' 2 3 2 2 2 1 * * , * 1 * 1 , * = = = − = − = = Z 最优解x x x x 六、解：依题意，首先给出一个可行流
在初始流上増流到不能再增,得到如下结果: m 此时已不能再增流,流量∫=105,不能满足市场的需求量。应修改仓库3到市场 3和4的容量,分别增流10和5即能满足需求 七、解:3、5正确
s Ⅰ Ⅲ Ⅱ 2 1 t 4 3 20，10 30，20 10，0 40，0 10，10 20，0 40，40 5，5 10，0 20，20 20，0 60，50 20，5 50，0 在初始流上增流到不能再增，得到如下结果： s Ⅰ Ⅲ Ⅱ 2 1 t 4 3 20，20 30，10 10，10 40，0 10，10 20，10 40，40 5，5 10，10 20，20 20，20 60，50 20，15 50，10 此时已不能再增流，流量 f = 105 ，不能满足市场的需求量。应修改仓库 3 到市场 3 和 4 的容量，分别增流 10 和 5 即能满足需求。 七、解：3、5 正确
