试题一试题代码:453题名称:运筹学1.本试题共七题,共3页,请考生认真检查;一、某炼油厂生产三种牌号的汽油,70#,80#和85#汽油。每种汽油有不同的辛烷值和含硫量的质量要求并由三种原料油调和而成。每种原料也有不同的质量指标。每种原料每日可用数量、质量指标和生产成本见表1,每种汽油的质量要求和销售价格见表2。问该炼油厂如何安排生产才能使其利润最大?假定在调和中辛烷值和含硫量指标都符合线性相加关系。试建立数学模型。(25分)表1序号i原料辛烷值含硫量(%)成本(元/吨)可用量(吨/日)1直馏汽油621.560020002催化汽油780.890010003重整汽油900.21400500表2序号j产品辛烷值含硫量(%)销售价(元/吨)170#汽油≥70≤1900280#汽油≥80≤11200385#汽油≥85≤0.61500二、用对偶单纯形法求解下列线性规划问题:(25分)0,,9645252max321323232121xxxxxxxxxxxxz三、已知某运输问题的产销平衡表与单位运价表如下表所示,B2地区需要的115单位必须满足,试确定最优调拨方案。(20分)AiBjB1B2B3B4B5产量A1101520204050A22040153030100A33035405525130销量25115603070四、从甲,乙,丙,丁,戊五人中挑选四人去完成四项工作,已知每人完成各项工作的时间如下表所示。规定每项工作只能由一个人去单独完成,每个人最多承担一项工作,假定甲必须保证分配到工作,丁因某种原因不同意承担第四项工作。在满足上述条件下,如何分配工作,使完成四项工作总的花费时间最少。(20分)人工作一二三四甲1051520乙210515丙3151413丁15276戊94158五、求V1到各点的最短路及最短路径。(20分)v1v2v3v6v4v7v5911101111111084六、某公司有资金4百万元向A,B,C三个项目追加投资,各个项目可以有不同的投资额(以百万元为单位),相应的效益值如下表。问怎样分派资金,使总效益值最大,试用动态规划方法求解。(25分)项目投资额01234A3841486066B4042506066C3864687876七、用单纯形法解线性规划问题,如何判断下列问题:(15分)1.无可行解;2有多重解;3.有无界解。试题一答案一、解:设代表第i种原料混入第j种产品中的数量,其中i=1,2,3;j=1,2,3;则3,2,1,3,2,1,02.08.05.12.08.05.12.08.05.185907862809078627090786250010002000140090060015001200900max313332313312322212311312111313332313312322212311312111313312311313312313113312311jixxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxZijiiiiiiiiiiiijjjjjjjjjjijjiiiii二、解:原问题可化为:52,1,0945252max53243232121ixxxxxxxxxxxxZi210001x2x3x4x5x1b21x04x05x11100021100-4-60155-9jr0-1-200ijjar/-1/41/3--21x04x05x101/201/400-211/2013/20-1/4jr00-1/20-1/4-31/4431)49,411(),(*21*ZxxXTT三、解:将原问题改成产销平衡问题,并用沃格尔法给出初始解得:销产1B2B3B4B5B产jv1A10515502020205403550-152A2010401015603030301010003A30535654020552025651305'A015MM-10050-100520-20销25115603070300iu2030153020此方案还不是最优,需要调整销产1B2B3B4B5B产jv1A1015155020302015403550-252A20254001560301530010003A30153565403055302565130-5'A010MM-100150150520-30销25115603070300iu2040153030此时检验数均大于或等于0,为最优解650025*6515*3015*6035*6550*1520*25*Z四、解:1051520M831012M5079M-32105150080700807031514130~113950~113950~1527M01302M-801302M-809415807210007210004068M-3090710138401201M-90731001此时,费用最小,218553*Z其中,丙一,甲二,乙三,戌四五、解:1v2v3v4v5v6v7v0*119*101110*2011*21202121*21*2825*21vv11:21vv31vv9:31vv41vv10:41vv51vv21:541vvv61vv20:631vvv71vv25:7541vvvv六、解:阶段:以向某一项目投资作为一个阶段,如此可划分为三个阶段。状态变量:以可以提供的投资额作为状态变量is,其范围为0,1,2,3,4百万决策变量:以给某项目投资的金额作为决策变量ix,则iisx状态转移方程:iiidss140,33sk3s3x01234)(33sf3x*01234384148606638414860660123440,22sk2s2x01234)(22sf2x*0123440+3840+4142+3840+4842+4150+3840+6042+4850+4160+3840+6642+6050+4860+4166+38788188100106000,2004,11sk1s1x01234)(11sf1x*438+10664+10068+8878+8176+781641总效益最大值为164,其中3,0,1321xxx。七、解:1、无可行解:最终表人工变量不为零;或右侧常数0ib,对应的0ija;2、有多重解:0jr(非基变量)且至少有一个为零。3、有无界解:非基变量的检验数0jr,且对应的系数列向量0ija。试题二试题代码:453试题名称:运筹学考生注意∶1.本试题共七题,共3页,请考生认真检查;一、华津机器制造厂专为拖拉机厂配套生产柴油机,今年头四个月收到的订单数量分别为3000,4500,3500,5000台柴油机。该厂正常生产每月可生产柴油机3000台,利用加班还可生产1500台。正常生产成本为每台5000元,加班生产还要追加1500元成本,库存成本为每台每月200元。华津厂如何组织生产才能使生产成本最低,建立其线性规划模型。(20分)二、考虑线性规划问题:(25分)0,,232524125max321321321321xxxxxxxxxxxxz用单纯形法求解,得其终表如下:cj51240-MCBXBx1x2x3x4x5B-1b12x201-1/52/5-1/58/55x1107/51/52/59/5czjj00-3/5-29/5-M+2/5X4为松弛变量,X5为人工变量,1.上述模型的对偶模型为:;2.对偶模型的最优解为:;3.当两种资源分别单独增加一个单位时,目标函数值分别增加和;4.最优基的逆矩阵B-1=5.如果原问题增加一个变量,则对偶问题的可行域将可能变大还是变小?.三、求解下列各题(解题方法自选)(20分))3,2,1;3,2,1(01111111544121081065min332313322212312111333231232221131211333231232221131211jixxxxxxxxxxxxxxxxxxxxxxxxxxxxzij或四、用隐枚举法求解下列0-1规划问题(20分)max,,zxxxxxxxxxxxxxxxxxxxxjj57103354226322022101151234512345123452345五、用动态规划方法求解下列问题(25分)3,2,101)1(max321321jxxxxxxxzj六、今有三个仓库运送某种产品到四个市场上去,仓库的供应量是20,20和100,市场需求量是20,20,60和20,仓库与市场之间的路线上的容量如下表(容量零表示两点间无直接的路线可通)。用图论方法确定现有路线容量能否满足市场的需求,若不能,应修改哪条线路的容量。(20分)市场仓库1234供应量130100402020010502032010405100需求量20206020七.下列叙述中正确的是()(20分)1.图解法与单纯形法,虽然求解的形式不同,但从几何上理解,两者是一致的;2.若线性规划的原问题有多重最优解,则其对偶问题也一定具有多重最优解;3.如果运输问题单位运价表的某一行(或某一列)元素分别加上一个常数k,最优调运方案将不会发生变化;4.对于极大化问题maxZ=ijninjijxc11…令ijijijccbcc,max转化为极小化问题ijninjijxbW11min,则利用匈牙利法求解时,极大化问题的最优解就是极小化问题的最优解,但目标函数相差:n+c;5.如果图中从iv至各点均有惟一的最短路,则连接至其他各点的最短路在去掉重复部分后,恰好构成该图的最小支撑树。试题二答案一、解:设ix代表第i月正常生产的柴油机数量,iy代表第i月加班生产的柴油机数量,iz代表第i月末的库存量,则iz=44,3,2,1,0,,500035004500300020065005000min44333222111414141izyxyxzyxzyxzyxzyxZiiiiiiiii二、解:1、对偶模型无约束2121212121,0431225225minyyyyyyyyyyW2、由单纯形表可看出,5295291)(*y由于0,00,0,0;021212211ssssyyxxxyxy而则对偶问题的第一、二个约束是紧的,可解出522y将21,yy代入第三个约束,满足约束条件,则51415252921*),,(),(*wyyyT3、5和24、1B5/25/15/15/25、如果原问题增加一个变量,则对偶问题就增加一个约束条件,它的可行域要么减少,要么不变,绝对不会变大。三、解:此题可看作指派问题求解:561012501400381012~467~023~01244500000010019*0,1,1,1331221Zxxx,其余为最优解四、解:将最大化问题化为极小化问题,并将系数转为正,即令'1iixx,整理得)5,2,1(1032212236224532631075min''5'4'3'2'5'4'3'2'1'5'4'3'2'1'5'4'3'2'1'''jxxxxxxxxxxxxxxxxxxxxZj或01234561011781291'1x0'1x1'2x1'3x0'3x0'2x1'2x0'2x1'3x1'3x0'3x0'3x综上,该0
本文标题:运筹学卷子・1
链接地址:https://www.777doc.com/doc-3781818 .html