管理运筹学试题及答案线性规划,运输问题,动态规划,最短路最大流.pdf

管理管理运筹学运筹学试题及参考试题及参考答案答案 一、【线性规划【线性规划】 （20 分）分）请用大 M 法和两阶段法求解下列线性规划问题。 0 322 7432 6325min 4321 4321 4321 4321 x ,x ,x ,x xxxx xxxx . t . s xxxxz 参考答案：参考答案： 大 M 法：把原问题化为标准形式，在约束条件中加入人工变量 5 x， 6 x，得到： 0 322 7432 6325min 654321 64321 54321 654321 x ,x ,x ,x ,x ,x xxxxx xxxxx . t . s MxMxxxxxz .(2(2 分分) ) 这里 M 是一个任意大的正数。用单纯形法计算如下： 表表1-1 j c 5-23-6MM i B C B X b 1 x 2 x 3 x 4 x 5 x 6 x M 5 x71234101.75 M 6 x32112011.5 jj zc j 5-3M-2-3M3-4M-6-6M00 M 5 x1-30101-21 -6 4 x1.510.50.5100.53 jj zc j 11+3M16-M003M+3 3 3 x1-30101-2 -6 4 x12.50.501-0.51.5 jj zc j 29100M-6M+15 （8 8 分分） 因为 M 是一个很大的正数，所以此时检验数 j 均大于 0，因此该问题的最优解 T , ,X）（1100 * ，最优值为3 * z （9 9 分）分） 两阶段法： 在原问题的约束方程中加入人工变量 5 x， 6 x，得到第一阶段的数学模型： 0 322 7432 0000min 654321 64321 54321 654321 x ,x ,x ,x ,x ,x xxxxx xxxxx . t . s xxxxxx （1111 分）分） 用单纯形法计算如下： 表表1-2 j c 000011 i B C B X b 1 x 2 x 3 x 4 x 5 x 6 x 1 5 x71234101.75 1 6 x32112011.5 jj zc j -3-3-4-600 1 5 x1-30101-21 0 4 x1.510.50.5100.53 jj zc j 30-1003 0 3 x1-30101-2 0 4 x12.50.501-0.51.5 jj zc j 000011 （1717 分分） 由表 1-2 可知，检验数均大于等于 0，所以最优解为 T , , ,X）（001100 * ，最优值为 0z。由于人工变量0 65 xx，则原问题的基可行解为 T , ,X）（1100 * ，故第二阶段计 算如下： 表表1-3 j c 5-23-6 i B C B X b 1 x 2 x 3 x 4 x 3 5 x1-3010 -6 6 x12.50.501 jj zc j 29160 （1919 分）分） 由上表可知，检验数均大于等于 0，所以得到最优解为 T , ,X）（1100 * ，最优值为 3z。 （2020 分）分） 二、【运输问题【运输问题】 （20 分分）某化肥公司下设 A、B、C 三个加工厂，其每年的产量分别为 200 万吨、100 万吨、300 万吨。该公司把这些产品分别运往甲乙丙丁四个销售点。各销售点每 年的销售量分别为：120 万吨、180 万吨、160 万吨、140 万吨。由公司至各销售点的单位 运价（万元/万吨）如下表所示。问该公司应如何调运产品，在满足各销售点的需求量的前 提下，使总运费为最少。 表表 2-1单位运价表单位运价表 加工厂 销售点 甲乙丙丁 A81069 B127156 C651012 解：解： 解题思路 （1）画出问题的产销平衡表和单位运价表 （2）用最小元素法或伏格尔法算出初始基可行解 （3）用位势法检验 （4）用闭回路法调整 由题意可得如下单位运价表和产销平衡表， 表表 2-2单位运价表和产销平衡表单位运价表和产销平衡表 加工厂 销售点 产量 甲乙丙丁 A81069200 B127156100 C651012300 销量120180160140 由伏格尔法求初始调运方案 表表 2-3初始产销平衡表初始产销平衡表 加工厂 销售点 产量 甲乙丙丁 A016040200 B100100 C120180300 销量120180160140 表表 2-4初始单位运价表初始单位运价表 加工厂 销售点行差额 甲乙丙丁 A810692111 B12715611 C6510121116 列差 额 2243 223 253 23 （10 分分） 用位势法求检验数 表表 2-4检验数表检验数表 加工厂加工厂 销售点销售点 i u 甲甲乙乙丙丙丁丁 A A8630 B B6-3 C C65-2 i v8769 表表 2-5检验数表检验数表 加工厂加工厂 销售点销售点 i u 甲甲乙乙丙丙丁丁 A A 0 8 3 10 0 6 0 3 0 B B 7 12 3 7 12 15 0 6 -3 C C 0 6 0 5 6 10 5 12 -2 i v8769 （18 分分） 因为表中所有检验数皆为非负，所以初始调运方案即为最优解。 （20 分分） 三、【动态规划问题【动态规划问题】 （20 分分）请用逆推解法逆推解法求解下列资源分配问题。现有资金 4 万元，全 部用于投资 A、B、C 三个项目，三个项目的投资效益（万吨）与投入资金（万元）关系见 下表： 资 金 项目 ABC 1 万151311 2 万2829 30 3 万4043 45 4 万5155 58 问如何安排投资分配，使总投资效益最大？ 参考答案：参考答案： 1.阶段k：把拟投资的 A、B、C 三个项目看作三个阶段，321 ,k ； 2.状态变量：设 k s表示投资第k个项目前所拥有的资金； 3.决策变量：设 k x表示第k个项目投入的资金； 4.决策允许集合： kk sx 0； 5.状态转移方程： kkk xss 1 ； 6.阶段指标：)x ,s(v kkk ，如表所示； 7.最优指标函数：设)s(f kk 表示第k个项目前的资金处于 k s阶段，从该阶段一直到第三 个项目的总投资效益； 8.递推公式： 0 44 11 )s(f )s(f)x ,s(vmax)s(f kkkkkkk （8 分）分） 由逆推解法： 当4k，0 44 )s(f； 当3k， 33 0sx ， 334 xss， 表表 3-1 3 s 3 x)s(f)x ,s(v 44333 )s(f 33 * 3 x 000+0=000 1111+0=11111 2230+0=30302 3345+0=45453 4458+0=58584 （10 分分） 当2k， 22 0sx ， 223 xss， 表表 3-2 2 s 2 x)s(f)x ,s(v 33222 )s(f 22 * 2 x 0000+0=00 1 00+11=11 131 113+0=13* 2 00+30=30* 300113+11=24 229+0=29 3 00+45=45* 450 113+30=43 229+11=40 343+0=43 4 00+58=58 592 113+45=58 229+30=59* 343+11=54 455+0=55 （15 分分） 当1k， 11 0sx ， 112 xss， 表表 3-3 1 s 1 x)s(f)x ,s(v 22111 )s(f 11 * 1 x 4 00+59=59 601 115+45=60* 228+30=58 340+13=53 451+0=51 （18 分分） 反推可知， 最优解为4 1 s，1 * 1 x，3 112 xss，0 * 2 x，3 223 xss，3 * 3 x， 0 334 xss；即最佳投资计划为：项目 A 投资 1 万元，项目 B 投资 0 万元，项目 C 投 资 3 万元； 最大投资效益为 60 万吨。 （20 分分） 四、【最短路问题【最短路问题】 （20 分）分）求图中 1 v到 8 v的最短路径和最短距离。 解：解： 初始状态：0i 令 10 vS ，0 1 )v(P，0 1 )v(，其余)v(T i ，8765432,i ； 0441 0331 0221 Sv ,A)v ,v( Sv ,A)v ,v( Sv ,A)v ,v( 1660 1550 1330 41414 31313 21212 )v(,min)v(P,min)v(T )v(,min)v(P,min)v(T )v(,min)v(P,min)v(T ， ， ， 3653 432 ,)v(T),v(T),v(Tmin 即3 2 )v(P， 21201 v ,vvSS，1k； （2 分分） 1i 211 v ,vS ，0 1 )v(P，3 2 )v(P，0 1 )v(，1 2 )v( 0332 0662 0552 0441 0331 Sv ,A)v ,v( Sv ,A)v ,v( Sv ,A)v ,v( Sv ,A)v ,v( Sv ,A)v ,v( 2743 21073 1660 241350 62626 52525 41414 32321313 )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 ， ， ， ， 471064 6543 ,)v(T),v(T),v(T),v(Tmin 即4 3 )v(P， 321312 v ,v ,vvSS，2k； （5 分分） 2i 3212 v ,v ,vS ，0 1 )v(P，3 2 )v(P，4 3 )v(P，0 1 )v(，1 2 )v(，2 3 )v( 0663 0443 0662 0552 0441 Sv ,A)v ,v( Sv ,A)v ,v( Sv ,A)v ,v( Sv ,A)v ,v( Sv ,A)v ,v( 362443 21073 351460 63632626 52525 43431414 )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 ， ， ， 56105 654 ,)v(T),v(T),v(Tmin 即5 4 )v(P， 4321423 v ,v ,v ,vvSS，3k； （7 分）分） 3i 43213 v ,v ,v ,vS ，0 1 )v(P，3 2 )v(P，4 3 )v(P，5 4 )v(P，0 1 )v(， 1 2 )v(，2 3 )v(，3 4 )v( 0774 0664 0663 0662 0552 Sv ,A)v ,v( Sv ,A)v ,v( Sv ,A)v ,v( Sv ,A)v ,v( Sv ,A)v ,v( 41055 36352443 21073 74747 64643632626 52525 )v(,min)v(P,min)v(T )v(,min)v(P,)v(P,)v(P,min)v(T )v(,min)v(P,min)v(T ， ， ， 610610 765 ,)v(T),v(T),v(Tmin 即6 6 )v(P， 64321634 v ,v ,v ,v ,vvSS，3k； （10 分分） 4i 643214 v ,v ,v ,v ,vS ，0 1 )v(P，3 2 )v(P，4 3 )v(P，5 4 )v(P，6 6 )v(P， 0 1 )v(，1 2 )v(，2 3 )v(，3 4 )v(，3 6 )v( 0776 0886 0556 0774 0552 Sv ,A)v ,v( Sv ,A)v ,v( Sv ,A)v ,v( Sv ,A)v ,v( Sv ,A)v ,v( 61596 671655 682673 86868 76764747 56562525 )v(,min)v(P,min)v(T )v(,min)v(P,)v(P,min)v(T )v(,min)v(P,)v(P,min)v(T ， ， ， 71578 875 ,)v(T),v(T),v(Tmin 即7 7 )v(P， 764321745 v ,v ,v ,v ,v ,vvSS，6k； （12 分分） 5i 643215 v ,v ,v ,v ,vS ，0 1 )v(P，3 2 )v(P，4 3 )v(P，5 4 )v(P，6 6 )v(P， 7 7 )v(P，0 1 )v(，1 2 )v(，2 3 )v(，3 4 )v(，3 6 )v(，6 7 )v( 0887 0886 0556 0552 Sv ,A)v ,v( Sv ,A)v ,v( Sv ,A)v ,v( Sv ,A)v ,v( 7125796 682673 87876868 56562525 )v(,min)v(P,)v(P,min)v(T )v(,min)v(P,)v(P,min)v(T ， ， 8128 85 ,)v(T),v(Tmin 即8 5 )v(P， 5764321556 v ,v ,v ,v ,v ,v ,vvSS，6k； （15 分分） 6i 57643216 v ,v ,v ,v ,v ,v ,vS ，0 1 )v(P，3 2 )v(P，4 3 )v(P，5 4 )v(P，6 6 )v(P， 7 7 )v(P，8 5 )v(P，0 1 )v(，1 2 )v(，2 3 )v(，3 4 )v(，3 6 )v(， 6 7 )v(，5 6 )v( 0887 0886 0885 Sv ,A)v ,v( Sv ,A)v ,v( Sv ,A)v ,v( 12579668 7876865858 ,min)v(P,)v(P,)v(P,min)v(T 7 8 )v(，12 8 )v(P， 85764321867 v ,v ,v ,v ,v ,v ,v ,vvSS，7k； （18 分分） 综上，当算法终止时：综上，当算法终止时： 0 1 )v(P，3 2 )v(P，4 3 )v(P，5 4 )v(P，6 6 )v(P，7 7 )v(P，8 5 )v(P， 12 8 )v(P,0 1 )v(，1 2 )v(，2 3 )v(，3 4 )v(，3 6 )v(，6 7 )v(， 7 8 )v( 构成两条路径： 856321 vvvvvv，距离为 14； 876321 vvvvvv，距离为 12； 比较可知，最短路径为 876321 vvvvvv，最短距离为 12。 （20 分分） 五、【最大流问题】 （20 分）请用标号法求图中的网络最大流。弧旁的数值是 ijij f ,c。 图 1 解：解： （1）标号过程 首先给 s v标上）（ , 0； 检查 s v邻接点 2 v， 1 v， 在弧）（ 2 v ,vs上，3 22 ss cf，不满足标号条件； 在弧）（ 1 v ,vs上，64 11 ss cf，则给 1 v以标号）（)v( l ,vs 1 ，其中 2 111 ）)fc(),v( lmin)v( l sss ，即 1 v记作）（2 ,vs； 检查 1 v邻接点 2 v， 3 v， 在弧）（ 12 v ,v上，02 21 f，则给 2 v以标号）（）（2 12111 ,vf),v( lmin,v； 在弧）（ 31 v ,v上，6 1313 cf，不满足标号条件； 检查 2 v邻