管理运筹学试题及答案(线性规划-运输问题-动态规划-最短路最大流)

《管理运筹学》试题及参考答案一、【线性规划】（20分）请用大M法和两阶段法求解下列线性规划问题。032274326325min4321432143214321x,x,x,xxxxxxxxx.t.sxxxxz参考答案：①大M法：把原问题化为标准形式，在约束条件中加入人工变量5x，6x，得到：032274326325min6543216432154321654321x,x,x,x,x,xxxxxxxxxxx.t.sMxMxxxxxz...........(2分)这里M是一个任意大的正数。用单纯形法计算如下：表1-1jc5-23-6MMiBCBXb1x2x3x4x5x6xM5x71234101.75M6x3211[2]011.5jjzcj5-3M-2-3M3-4M-6-6M00M5x1-30[1]01-21-64x1.510.50.5100.53jjzcj11+3M16-M003M+333x1-30101-2-64x12.50.501-0.51.5jjzcj29100M-6M+15．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．（8分）因为M是一个很大的正数，所以此时检验数j均大于0，因此该问题的最优解T,,,X）（1100*，最优值为3*z．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．（9分）②两阶段法：在原问题的约束方程中加入人工变量5x，6x，得到第一阶段的数学模型：032274320000min6543216432154321654321x,x,x,x,x,xxxxxxxxxxx.t.sxxxxxx．．．．．．．．（11分）用单纯形法计算如下：表1-2jc000011iBCBXb1x2x3x4x5x6x15x71234101.7516x3211[2]011.5jjzcj-3-3-4-60015x1-30[1]01-2104x1.510.50.5100.53jjzcj30-100303x1-30101-204x12.50.501-0.51.5jjzcj000011．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．（17分）由表1-2可知，检验数均大于等于0，所以最优解为T,,,,,X）（001100*，最优值为0z。由于人工变量065xx，则原问题的基可行解为T,,,X）（1100*，故第二阶段计算如下：表1-3jc5-23-6iBCBXb1x2x3x4x35x1-3010-66x12.50.501jjzcj29160．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．（19分）由上表可知，检验数均大于等于0，所以得到最优解为T,,,X）（1100*，最优值为3z。．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．（20分）二、【运输问题】（20分）某化肥公司下设A、B、C三个加工厂，其每年的产量分别为200万吨、100万吨、300万吨。该公司把这些产品分别运往甲乙丙丁四个销售点。各销售点每年的销售量分别为：120万吨、180万吨、160万吨、140万吨。由公司至各销售点的单位运价（万元/万吨）如下表所示。问该公司应如何调运产品，在满足各销售点的需求量的前提下，使总运费为最少。表2-1单位运价表加工厂销售点甲乙丙丁A81069B127156C651012解：解题思路（1）画出问题的产销平衡表和单位运价表（2）用最小元素法或伏格尔法算出初始基可行解（3）用位势法检验（4）用闭回路法调整由题意可得如下单位运价表和产销平衡表，表2-2单位运价表和产销平衡表加工厂销售点产量甲乙丙丁A81069200B127156100C651012300销量120180160140由伏格尔法求初始调运方案表2-3初始产销平衡表加工厂销售点产量甲乙丙丁A016040200B100100C120180300销量120180160140表2-4初始单位运价表加工厂销售点行差额甲乙丙丁①②③④A810[6]92111B12715[6]11C[6][5]10121116列差额①2243②223③253④23．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．（10分）用位势法求检验数表2-4检验数表加工厂销售点iu甲乙丙丁A8630B6-3C65-2iv8769表2-5检验数表加工厂销售点iu甲乙丙丁A0831006030B71237121506-3C0605610512-2iv8769．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．（18分）因为表中所有检验数皆为非负，所以初始调运方案即为最优解。．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．（20分）三、【动态规划问题】（20分）请用逆推解法求解下列资源分配问题。现有资金4万元，全部用于投资A、B、C三个项目，三个项目的投资效益（万吨）与投入资金（万元）关系见下表：资金项目ABC1万1513112万2829303万4043454万515558问如何安排投资分配，使总投资效益最大？参考答案：1.阶段k：把拟投资的A、B、C三个项目看作三个阶段，321,,k；2.状态变量：设ks表示投资第k个项目前所拥有的资金；3.决策变量：设kx表示第k个项目投入的资金；4.决策允许集合：kksx0；5.状态转移方程：kkkxss1；6.阶段指标：)x,s(vkkk，如表所示；7.最优指标函数：设)s(fkk表示第k个项目前的资金处于ks阶段，从该阶段一直到第三个项目的总投资效益；8.递推公式：04411)s(f)s(f)x,s(vmax)s(fkkkkkkk．．．．．．．．．．．．．．．．（8分）由逆推解法：①当4k，044)s(f；②当3k，330sx，334xss，表3-13s3x)s(f)x,s(v44333)s(f33*3x000+0=0001111+0=111112230+0=303023345+0=454534458+0=58584．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．（10分）③当2k，220sx，223xss，表3-22s2x)s(f)x,s(v33222)s(f22*2x0000+0=00100+11=11131113+0=13*200+30=30*300113+11=24229+0=29300+45=45*450113+30=43229+11=40343+0=43400+58=58592113+45=58229+30=59*343+11=54455+0=55．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．（15分）④当1k，110sx，112xss，表3-31s1x)s(f)x,s(v22111)s(f11*1x400+59=59601115+45=60*228+30=58340+13=53451+0=51．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．（18分）反推可知，最优解为41s，1*1x，3112xss，0*2x，3223xss，3*3x，0334xss；即最佳投资计划为：项目A投资1万元，项目B投资0万元，项目C投资3万元；最大投资效益为60万吨。．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．（20分）四、【最短路问题】（20分）求图中1v到8v的最短路径和最短距离。解：①初始状态：0i令10vS，01)v(P，01)v(，其余)v(Ti，8765432,,,,,,i；044103310221Sv,A)v,v(Sv,A)v,v(Sv,A)v,v(166015501330414143131321212)v(,min)v(P,min)v(T)v(,min)v(P,min)v(T)v(,min)v(P,min)v(T，，，3653432,,)v(T),v(T),v(Tmin即32)v(P，21201v,vvSS，1k；．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．（2分）②1i211v,vS，01)v(P，32)v(P，01)v(，12)v(03320662055204410331Sv,A)v,v(Sv,A)v,v(Sv,A)v,v(Sv,A)v,v(Sv,A)v,v(274321073166024135062626525254141432321313)v(,min)v(P,min)v(T)v(,min)v(P,min)v(T)v(,min)v(P,min)v(T)v(,,min)v(P,)v(P,min)v(T，，，，4710646543,,,)v(T),v(T),v(T),v(Tmin即43)v(P，321312v,v,vvSS，2k；．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．（5分）③2i3212v,v,vS，01)v(P，32)v(P，43)v(P，01)v(，12)v(，23)v(06630443066205520441Sv,A)v,v(Sv,A)v,v(Sv,A)v,v(Sv,A)v,v(Sv,A)v,v(36244321073351460636326265252543431414)v(,,min)v(P,)v(P,min)v(T)v(,min)v(P,min)v(T)v(,,min)v(P,)v(P,min)v(T，，，56105654,,)v(T),v(T),v(Tmin即54)v(P，4321423v,v,v,vvSS，3k；．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．（7分）④3i43213v,v,v,vS，01)v(P，32)v(P，43)v(P，54)v(P，01)