西南交通大学 运筹学 模拟试题一

试题一 试题代码试题代码453453题名称运筹学题名称运筹学 考生注意∶考生注意∶ １．本试题共１．本试题共 七七题，共题，共 3 3 页，请考生认真检查；页，请考生认真检查； ２．请务必将答案写在答卷纸上，写在试卷上的答案无效。２．请务必将答案写在答卷纸上，写在试卷上的答案无效。 题号一二三四五六 得分 签字 一、某炼油厂生产三种牌号的汽油，70，80和 85汽油。每种汽油有不同的辛烷值和含硫 量的质量要求并由三种原料油调和而成。 每种原料也有不同的质量指标。 每种原料每日可用 数量、质量指标和生产成本见表 1，每种汽油的质量要求和销售价格见表2。问该炼油厂如 何安排生产才能使其利润最大假定在调和中辛烷值和含硫量指标都符合线性相加关系。 试 建立数学模型。 （25 分 序号 i 1 2 3 序号 j 1 2 3 二、用对偶单纯形法求解下列线性规划问题 （25 分） 原料 直馏汽油 催化汽油 重整汽油 产品 70＃汽油 80＃汽油 85＃汽油 辛烷值 62 78 含硫量（％） 1.5 0.8 表 1 成本（元/吨） 600 900 可用量（吨/日） 2000 1000 500 销售价（元/吨） 900 1200 1500 七总分 900.21400 表 2 辛烷值含硫量（％） ≥70 ≥80 ≥85 ≤1 ≤1 ≤0.6 maxz  2x 1  x 2        x 1  x 2  x 3 5 2x 2  x 3  5 4x 2 6x 3 9 x 1,x2 ,x 3  0 三、已知某运输问题的产销平衡表与单位运价表如下表所示， B2地区需要的 115 单位必须满 足，试确定最优调拨方案。 （20 分） AiBj A1 A2 A3 销量 四、 从甲, 乙, 丙, 丁, 戊五人中挑选四人去完成四项工作， 已知每人完成各项工作的时间 如下表所示。规定每项工作只能由一个人去单独完成， 每个人最多承担一项工作， 假定甲必 须保证分配到工作，丁因某种原因不同意承担第四项工作。 在满足上述条件下，如何分配工 作，使完成四项工作总的花费时间最少。 （20 分） 人 工作 甲 乙 丙 丁 戊 10 2 3 15 9 5 10 15 2 4 15 5 14 7 15 20 15 13 6 8 一二三四 B1 10 20 30 25 B2 15 40 35 115 B3 20 15 40 60 B4 20 30 55 30 B5 40 30 25 70 产量 50 100 130 五、求 V1到各点的最短路及最短路径。 （20 分） v3 9 v1 10 v4 11 11 v2 11 4 v5 10 11 v6 8 v7 六、 某公司有资金 4 百万元向 A， B， C 三个项目追加投资， 各个项目可以有不同的投资额 （以 百万元为单位） ，相应的效益值如下表。问怎样分派资金，使总效益值最大，试用动态规划 方法求解。 （25 分） 项目投资额 A 0 38 1 41 2 48 3 60 4 66 B C 40 38 42 64 50 68 60 78 66 76 七、用单纯形法解线性规划问题，如何判断下列问题 （15 分） 1. 无可行解； 2. 有多重解； 3. 有无界解。 试题一答案试题一答案 一、解设代表第 i 种原料混入第 j 种产品中的数量，其中 i1，2，3；j1，2，3；则 maxZ  900x i1 1200x i2 1500x i3 600x 1j 900x 2 j 1400x 3 j i1i1i1j1j1j1 333333 x j1 3 3 1j  2000 1000  500 3 x j1 3 2 j x j1 3 j 62x 11  78x 21 90 x 31  70x i1 i1 3 62x 12  78x 22 90 x 32  80x i2 i1 3 62x 13  78x 23 90 x 33  85x i3 i1 1.5x 11  0.8x 21  0.2x 31 x i1 i1 3 3 1.5x 12  0.8x 22  0.2x 32 x i2 i1 3 1.5x 13  0.8x 23  0.2x 33 x i3 i1 x ij  0,i 1,2,3, j 1,2,3 二、解原问题可化为 maxZ  2x 1 x 2 x 1 x 2 x 3  5 2x 2 x 3 x 4  5  4x 2 x 3 x 5  9 x i  0,i 1,25 2 x 1 0 21000 x 1 x 2 x 3 x 4 x 5 11100 02110 0-4-601 0-1-200 -1/41/3-- 101/201/4 00-211/2 013/20-1/4 00-1/20-1/4 b 1 5 5 -9 x 4 0 x 5 r j r j /a ij 2 x 1 0 x 4 0 x 5 r j -31/4 三、解将原问题改成产销平衡问题，并用沃格尔法给出初始解得 销 B 3 B 5 B 1 B 2 B 4 产 11 9  X* x 1 ,x 2 T , T 4 4 31 Z* 4 产 50 100 130 20 300 v j A 1 A 2 A 3 10 5 20 10 30 5 0 15 25 20 15 50 40 10 35 65 M M-10 115 30 20 20 15 60 40 20 0 5 60 15 20 5 30 30 55 20 0 -10 30 30 40 35 30 10 25 65 0 5 70 20 -15 0 5 -20 A 销 u i 此方案还不是最优，需要调整 销 B 1 B 2 产 B 3 B 4 B 5 产 v j A 1 A 2 A 3 10 15 20 25 30 15 0 10 25 20 15 50 40 0 35 65 M M-10 115 40 20 30 15 60 40 30 0 15 60 15 20 15 30 15 55 30 0 15 30 30 40 35 30 0 25 65 0 5 70 30 50 100 130 20 300 -25 0 -5 -30 A 销 u i * 此时检验数均大于或等于0，为最优解 Z 25*20 15*50  65*35 60*15 30*15 65*25  6500 四、解 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