试题 试题代码:453题名称:运筹学 考生注意: 1·本试题共七题,共3页,请考生认真检查 2.请务必将答案写在答卷纸上,写在试卷上的答案无效 「总分 得分 签字 某炼油厂生产三种牌号的汽油,70#,80#和85#汽油。每种汽油有不同的辛烷值和含硫 量的质量要求并由三种原料油调和而成。每种原料也有不同的质量指标。每种原料每日可用 数量、质量指标和生产成本见表1,每种汽油的质量要求和销售价格见表2。问该炼油厂如 何安排生产才能使其利润最大?假定在调和中辛烷值和含硫量指标都符合线性相加关系。试 建立数学模型。(25分) 表 序号i原料辛烷值含硫量(%)|成本(元吨)可用量(吨/) 直馏汽油 催化汽油 0.8 1000 重整汽油 90 0.2 1400 表2 产品 辛烷值 含硫量(%)销售价(元吨) 70#汽油 80#汽油 ≤l 1200 85#汽油 ≥85 0.6 二、用对偶单纯形法求解下列线性规划问题:(25分) max2=2x,+x x,+x 2x,+x<5 4x2+6x3≥9 x1,x2,x2≥0 已知某运输问题的产销平衡表与单位运价表如下表所示,B地区需要的115单位必须
试题一 试题代码：453 题名称：运筹学 考生注意∶ １．本试题共 七 题，共 3 页，请考生认真检查； ２．请务必将答案写在答卷纸上，写在试卷上的答案无效。 题号 一 二 三 四 五 六 七 总分 得分 签字 一、某炼油厂生产三种牌号的汽油，70#，80#和 85#汽油。每种汽油有不同的辛烷值和含硫 量的质量要求并由三种原料油调和而成。每种原料也有不同的质量指标。每种原料每日可用 数量、质量指标和生产成本见表 1，每种汽油的质量要求和销售价格见表 2。问该炼油厂如 何安排生产才能使其利润最大？假定在调和中辛烷值和含硫量指标都符合线性相加关系。试 建立数学模型。（25 分) 表 1 序号 i 原料 辛烷值 含硫量（％） 成本（元/吨） 可用量（吨/日） 1 直馏汽油 62 1.5 600 2000 2 催化汽油 78 0.8 900 1000 3 重整汽油 90 0.2 1400 500 表 2 序号 j 产品 辛烷值 含硫量（％） 销售价（元/吨） 1 70＃汽油 ≥70 ≤1 900 2 80＃汽油 ≥80 ≤1 1200 3 85＃汽油 ≥85 ≤0.6 1500 二、用对偶单纯形法求解下列线性规划问题：（25 分） , , 0 4 6 9 2 5 5 max 2 1 2 3 2 3 2 3 1 2 3 1 2 + + + + = = + x x x x x x x x x x z x x 三、已知某运输问题的产销平衡表与单位运价表如下表所示，B2 地区需要的 115 单位必须
满足,试确定最优调拨方案。(20分) 130 销量 25 l15 70 四、从甲,乙,丙,丁,戊五人中挑选四人去完成四项工作,已知每人完成各项工作的时间如 下表所示。规定每项工作只能由一个人去单独完成,每个人最多承担一项工作,假定甲必须 保证分配到工作,丁因某种原因不同意承担第四项工作。在满足上述条件下,如何分配工作 使完成四项工作总的花费时间最少。(20分) 四 工作 丙 丁 2 五、求V1到各点的最短路及最短路径。(20分) 六、某公司有资金4百万元向A,B,C三个项目追加投资,各个项目可以有不同的投资额 (以百万元为单位),相应的效益值如下表。问怎样分派资金,使总效益值最大,试用动态 规划方法求解。(25分) 项目 投资额
满足，试确定最优调拨方案。（20 分） Ai Bj B1 B2 B3 B4 B5 产量 A1 10 15 20 20 40 50 A2 20 40 15 30 30 100 A3 30 35 40 55 25 130 销量 25 115 60 30 70 四、从甲, 乙, 丙, 丁, 戊五人中挑选四人去完成四项工作，已知每人完成各项工作的时间如 下表所示。规定每项工作只能由一个人去单独完成，每个人最多承担一项工作，假定甲必须 保证分配到工作，丁因某种原因不同意承担第四项工作。在满足上述条件下，如何分配工作， 使完成四项工作总的花费时间最少。（20 分） 人 工作 一 二 三 四 甲 10 5 15 20 乙 2 10 5 15 丙 3 15 14 13 丁 15 2 7 6 戊 9 4 15 8 五、求 V1 到各点的最短路及最短路径。（20 分） v1 v2 v3 v6 v4 v7 v5 9 11 10 11 11 11 10 8 4 六、某公司有资金 4 百万元向 A，B，C 三个项目追加投资，各个项目可以有不同的投资额 （以百万元为单位），相应的效益值如下表。问怎样分派资金，使总效益值最大，试用动态 规划方法求解。（25 分） 项目 投资额 0 1 2 3 4 A 38 41 48 60 66
B 七、用单纯形法解线性规划问题,如何判断下列问题:(15分) 1.无可行解; 2.有多重解 3.有无界解 试题一答案 、解:设代表第i种原料混入第j种产品中的数量,其中i=1,2,3;j=1,2,3:则 mx=902102+30X0-60x-90x2,12x j=1 ∑ 500 62x1+78x2+90x31270∑xn 62x1+78x2,+90x3≥80 5x1+0 08x2+02x1≤∑x 1.5x13+08x23+02x3≤∑xB x20.l=1,2,3,J=1,2,3 解:原问题可化为: max Z=2x, +x2 x1+x2+x3=5 2x,+x2+x,=5 x2≥0,1=1,2.5
B 40 42 50 60 66 C 38 64 68 78 76 七、用单纯形法解线性规划问题，如何判断下列问题：（15 分） 1. 无可行解； 2. 有多重解； 3. 有无界解。 试题一答案 一、解：设代表第 i 种原料混入第 j 种产品中的数量，其中 i=1，2，3；j=1，2，3；则 0, 1,2,3, 1,2,3 1.5 0.8 0.2 1.5 0.8 0.2 1.5 0.8 0.2 62 78 90 85 62 78 90 80 62 78 90 70 500 1000 2000 max 900 1200 1500 600 900 1400 3 1 1 3 2 3 3 3 3 3 1 1 2 2 2 3 2 2 3 1 1 1 2 1 3 1 1 3 1 1 3 2 3 3 3 3 3 1 1 2 2 2 3 2 2 3 1 1 1 2 1 3 1 1 3 1 3 3 1 2 3 1 1 3 1 3 3 1 2 3 1 3 1 3 1 3 1 2 3 1 1 = = + + + + + + + + + + + + = + + − − − = = = = = = = = = = = = = = = x i j x x x x x x 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 i j i i i i i i i i i i i i j j j j j j j j j j i j i j i i i i 二、解：原问题可化为： 0, 1,2 5 4 9 2 5 5 max 2 2 3 5 2 3 4 1 2 3 1 2 = − − + = − + + = + + = = + x i x x x x x x x x x Z x x i
0 0 b x 0 0 x|0 -1 2 0 0 l/2 0 xs5|0 2 1/4 1/2 -1/4 1/4 X=(x12x2)=( 119 4 三、解:将原问题改成产销平衡问题,并用沃格尔法给出初始解得: B B B B Bs 10 A L 15 35 40 30 A2 0 10 10 130 20 M-10 l15 此方案还不是最优,需要调整 B B B3 B 4 Bs
2 1 0 0 0 1 x 2 x 3 x 4 x 5 x 1 b 2 1 x 0 4 x 0 5 x 1 1 1 0 0 0 2 1 1 0 0 -4 -6 0 1 5 5 -9 j r 0 -1 -2 0 0 j aij r / - 1/4 1/3 - - 2 1 x 0 4 x 0 5 x 1 0 1/2 0 1/4 0 0 -2 1 1/2 0 1 3/2 0 -1/4 j r 0 0 -1/2 0 -1/4 -31/4 4 31 ) 4 9 , 4 11 ( , ) ( * 1 2 * = = = Z X x x T T 三、解：将原问题改成产销平衡问题，并用沃格尔法给出初始解得： 销 产 B1 B2 B3 B4 B5 产 j v A1 10 5 15 50 20 20 20 5 40 35 50 -15 A2 20 10 40 10 15 60 30 30 30 10 100 0 A3 30 5 35 65 40 20 55 20 25 65 130 5 ' A 0 15 M M-10 0 5 0 -10 0 5 20 -20 销 25 115 60 30 70 300 i u 20 30 15 30 20 此方案还不是最优，需要调整 销 产 B1 B2 B3 B4 B5 产 j v
15 15 0 35 40 55 130 30 30 0 0 A 20 15 30 M-10 l15 300 15 此时检验数均大于或等于0,为最优解 Z=25*20+15*50+65*35+60*15+30*15+65*25=6500 1051520M 831012M(5079M-3 31514130 113 50 950 1527M0 1302 13 b 2 M-80 94158 071 01M90 731001 此时,费用最小,z=3+55+8=21 其中,丙→ 戌 五、解 v3 V6 11* 20 21 VI →1 V1→>V3->ve V4
A1 10 15 15 50 20 30 20 15 40 35 50 -25 A2 20 25 40 0 15 60 30 15 30 0 100 0 A3 30 15 35 65 40 30 55 30 25 65 130 -5 ' A 0 10 M M-10 0 15 0 15 0 5 20 -30 销 25 115 60 30 70 300 i u 20 40 15 30 30 此时检验数均大于或等于 0，为最优解 25* 20 15*50 65*35 60*15 30*15 65* 25 6500 * Z = + + + + + = 四、解： 10 5 15 20 M 8 3 10 12 M 5 0 7 9 M-3 2 10 5 15 0 0 8 0 7 0 0 8 0 7 0 3 15 14 13 0 ~ 1 13 9 5 0 ~ 1 13 9 5 0 ~ 15 2 7 M 0 13 0 2 M-8 0 13 0 2 M-8 0 9 4 15 8 0 7 2 10 0 0 7 2 10 0 0 4 0 6 8 M-3 0 9 0 7 1 0 13 8 4 0 12 0 1 M-9 0 7 3 10 0 1 此时，费用最小， 3 5 5 8 21 * Z = + + + = 其中，丙 一， 甲 二， 乙 三， 戌 四 五、解： 1 v 2 v 3 v 4 v 5 v 6 v 7 v 0* + + + + + + 11 9* 10 + + + 11 10* + 20 + 11* 21 20 + 21 21* + 21* 28 25* 1 2 v → v 11 ： 1 2 v →v 1 3 v → v 9 ： 1 3 v → v 1 4 v →v 10 ： 1 4 v →v 1 5 v → v 21 ： 1 4 5 v → v → v 1 6 v → v 20 ： 1 3 6 v → v → v 1 7 v → v 25 ： 1 4 5 7 v → v → v → v
六、解: 阶段:以向某一项目投资作为一个阶段,如此可划分为三个阶段。 状态变量:以可以提供的投资额作为状态变量1,其范围为0,1,2,3,4百 决策变量:以给某项目投资的金额作为决策变量x,则x≤S 状态转移方程 k=30≤s3≤4 fc 0123 01234 k=2,0≤s,≤4 f2(S2) 40+38 01234 40+4142+38 40+4842+4150+38 0 40+6042+4850+4160+38 0000 40+6642+6050+4860+4166+38 fro 38+10664+10068+8878+8176+78 总效益最大值为164,其中x=1x2=0,x3=3 七、解: 1、无可行解:最终表人工变量不为零:或右侧常数b0 2、有多重解:≤0 (非基变量)且至少有一个为零 3、有无界解:非基变量的检验数>0,且对应的系数列向量≤0
六、解： 阶段：以向某一项目投资作为一个阶段，如此可划分为三个阶段。 状态变量：以可以提供的投资额作为状态变量 i s ，其范围为 0，1，2，3，4 百 万 决策变量：以给某项目投资的金额作为决策变量 i x ，则 i i x s 状态转移方程： i i di s +1 = s − k = 3,0 s3 4 3 s 3 x 0 1 2 3 4 ( ) 3 3 f s 3 x * 0 1 2 3 4 38 41 48 60 66 38 41 48 60 66 0 1 2 3 4 k = 2,0 s2 4 2 s 2 x 0 1 2 3 4 ( ) 2 2 f s 2 x * 0 1 2 3 4 40+38 40+41 42+38 40+48 42+41 50+38 40+60 42+48 50+41 60+38 40+66 42+60 50+48 60+41 66+38 78 81 88 100 106 0 0 0，2 0 0 k =1,s1 = 4 1 s 1 x 0 1 2 3 4 ( ) 1 1 f s 1 x * 4 38+106 64+100 68+88 78+81 76+78 164 1 总效益最大值为 164，其中 x1 =1, x2 = 0, x3 = 3。 七、解： 1、无可行解：最终表人工变量不为零；或右侧常数 bi 0 ，对应的 aij 0 ； 2、有多重解： rj 0 （非基变量）且至少有一个为零。 3、有无界解：非基变量的检验数 rj 0 ，且对应的系数列向量 aij 0