2013《运筹学》考试题及其答案

1、3x1%23（1）4%3x26s.t.X12x23（3）%1,X20minz 4x1 x24x1 z是斜率为 4的一族平行直线，由线性规划的X2沿其法线方向逐渐向上平移，直至A2012-2013学年第1学期运筹学考试题答案要求:第一题必做（50分），二三四题任选两题（每题各 25 分） 一、考虑下面线性规划问题（1）用图解法求解该问题；（2）写出该问题的标准形式；（3）求出该问题的松弛变量和剩余变量的 值；（4）用单纯形法求解。【解答】图中阴影部分为此线性规划问题的可行域，目标函数z 4x1 x2，即 x2性质知，其最值在可行域的顶点取得，将直线z 4x1点,A点的坐标为（3,6）,所以min

2、z 4 3 6 185 55 55此线性规划问题有唯一解X13，X26。55给等式（2）左端添加剩余变量X3，给等式3）左端添加松弛变量X4，则得到该问题的标准型为:maxz4x1%20x3 0X43x1%23,4X13x2X36,s.t.X12x2X43,X1,X2,X3,X4（1）（3）在上面标准型中令X1-，X26，得到剩余变量X3=0，松弛变量X4=0。55（4）先在上面标准型中约束条件（1）、（2）中分别加入人工变量X5,x6，得到如下数学模型,4x1 x2 0x3 0x4 Mx5 Mx63x1X2X53,4xi3x2X3X6s.t.Xi2x2X43,maxzXi,X2,X3,%,X

3、5,X6(1)6, (3)0由此列出单纯形表逐步迭代，用大 M法求解计算结果如下表所示-4-100-M-MX1X2X3X4X5X6bi-MX5【3】1001031-MX643-100163/20X412010033rj7M 44M 1-M0009M-4X111/3001/3013-MX60【5/3】-10-4/3126/50X405/301-1/3026/5rj(-z)0(5M+1)/3-M0(-7M+4)/304-2M-4X1101/503/5-1/53/51/3-1X201-3/50-4/53/56/50X400【1】11100rj(-z)001/50M+8/5-M-1/5-18/5-4X

4、1100-1/52/503/5-1X20103/5-1/506/50X300111-10rj(-z)000-1/5M+7/5-M-18/5表中所有检验数rj 0,根据最优解定理，冋题存在唯一的最优解X(, ,0,0,0,0)T，目标函5 5数的最优值maxz 4 3 18。555试用表上作业法求解下列运输问题的最优解'产销地B1B2B3B4产量A148846A295634A33114212销量16277【解答】：显然该问题是一个供需平衡问题，利用伏格法求出初始方案，如下表所示。BiB2B3B4产量Ai648846A29256234A303ii7452i2销量6277用位势法求出各非基变

5、量（即空格）的检验数，如下表所示。BiB2B3B4UiAi64(3)8(3)8(i)4ui=0A2(5)925(i)623u2 =0A303(7)ii7452U3 = iVjvi =4v2=5V3 =5V43因为所有非基变量的检验数均为非负的，故表中的解为最优解。按照此种方案调运，最小费用为:6X 4+2X 5+2 X 3+0 X 3+7X 4+5 X 2= 78用标号算法求解下图中从 Vi到各点的最短路vio【解答】：此为最短路问题，权数为正，用Dijksta算法的计算步骤如下:ViV2V3V4VV6V7V8V VioVii初始值T()000000000000000000000iP( )+W

6、ij0+20+80+ 00 + 00+ 00+ 00+ 00+ 00+ 00+ 0T()28000000oo00002P( )+Wij2+62+ o2+12+ 02+ 02+ 02+ 02+ 02+ 0T()800：3ooOO00003P( )+Wij3+53+ o3+ 03+ 03+ 03+13+ 03+ 0T()800OO004004P( )+Wij4+ g4+ o4+64+ 04+74+ 04+ 0T()80010011005P( )+Wij8+78+ 08+ 08+ 08+ 08+ 0T()1510011006P( )+Wij10+o10+410+010+ 010+ 0T()15141

7、1007P( )+Wij11+011+011+ 011+9T()15140208P( )+Wij14+o14+114+ 0T()1515119P( )+Wij15+4T()19由上表的迭代过程可得：Sq Vi ,V2 ,V , V9,V3,V6 ,V8 ,V7 ,V4,V10 ,V11d(Vi ,V2)=2，最短路：(Vi, V2);d(Vi, V5 )=3,最短路：(ViWs);d(Vi,V9)=4,最短路：(Vi, V2 ,V5, V9); d(Vi ,V6)=10,最短路：(Vi ,V2,V5, V9, V6);d(Vi ,V3)=8，最短路:(Vi, V3 )或(Vi,V2,V3 )或

8、(Vi,V2,V5，V3 )；d(Vi ,V8)=ii最短路：(Vi ,V2, V5, V9, V8); d(Vi ,V7)=14 最短路：(Vi, v? , V5, V9, V6, V7);d(Vi ,V4)= 15，最短路:(Vi ,V3 ,V4 )或(Vi, V2,V3 ,V4 )或(Vi ,V2 ,V5, V3,V4 );d(Vi ,Vio)=i5,最短路：(Vi,V2,V5, V9, V6, V7,Vi0)；d( Vi , Vii ) = i9,最短路：(Vi , V2 , V5 , V9 , V6 , V7 , Vio , Vii );四、某公司面对四种自然状态的三种备选行动方案收

9、益表如下，假定状态概率未知，试分别用悲观准则、等可能性准则、后悔值准则和乐观系数准则（0=0.6 ）进行决策收、状态Of'9 i9 29 39 4Ai1580-6A241483A3141012【解答】：（1）应用悲观准则:min15,8,0 ,-6t max min4,14,8 ,3 max -6,3,13 /. S2为最佳方案。min1,4,10 ,12 应用等可能性准则：1E（A2）-（4 144117E(A1)-(15 80 6),442918 3), E(A3)(1 4 10 12)27T17 29 2729max7,T,T 7E（ A2） , - S2为最佳方案。061018

10、max0,6,10,18B 11029 -. min max11,0,2,9min18,11,1411141000max14,10,0,0（3）应用后悔值准则：先求出后悔值矩阵应用乐观系数准则（0=0.6）:先计算各个方案的折中益损值:I S2为最佳方案。44E(AJ0.6150.4(6)6.6,Ef)0.6140.439.6E(A3)0.6120.417.6max6.6,9.6,7.69.6E(Q-S2为最佳方案已知下表为求解某目标函数为极大化线性规划问题的最终单纯形表，表中X4 ,X5为松弛变量，问题的约束为形式（共8分）X2X3X4X5X35/201/211/20x5/211/201/6

11、1/3Cj Zj0-4042（1）写出原线性规划问题；（4分）（2）写出原问题的对偶问题；（3分）（3）直接由上表写出对偶问题的最优解。（1 分）四、用单纯形法解下列线性规划问题（16分）max Z 2x1 x2 x3s. t.3 xi+ X2 + X360x i -x 2 + 2 x 3I0x i +x 2- x 320x i,x 2 , x 30五、求解下面运输问题。（18分）某公司从三个产地Ai、A2、A3将物品运往四个销地Bi、B2、B3、B4,各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如表所示：问：应如何调运，可使得总运输费最小？产地销地BiB2B3B4产量AI056

12、725A827625A3934850销量i5203035I00六、灵敏度分析（共 8分）线性规划 max z = 10xi + 6x2 + 4x3s.t.xi +x2 +X3I00IOxi +4 x2 +5 x36002xi +2 x2 +6 x3300xi , X2 ,X30的最优单纯形表如下:6X2200/305/6i5/3-I/60I0xiI00/3iI/60-2/3I/600X6i00040-20ij0-8/30-I0/3-2/30（1）Ci在何范围内变化，最优计划不变？（4分）（2）bi在什么范围内变化，最优基不变？（4分）七、试建立一个动态规划模型。（共8分）某工厂购进I00台机器

13、，准备生产pi , p2两种产品。若生产产品pi ，每台机器每年可收入 45万元, 损坏率为65% ;若生产产品 p2，每台机器每年可收入35万元，损坏率为 35% ;估计三年后将有新 的机器出现，旧的机器将全部淘汰。试问每年应如何安排生产，使在三年内收入最多？八、 求解对策问题。（共I0分）某种子商店希望订购一批种子。据已往经验，种子的销售量可能为500，I000，I500或2000公斤。假定每公斤种子的订购价为 6元，销售价为9元，剩余种子的处理价为每公斤3元。要求：（1）建立损益矩阵；（3分）（2） 用悲观法决定该商店应订购的种子数。（2分）（3） 建立后悔矩阵，并用后悔值法决定商店应订

14、购的种子数。（5分）九、求下列网络计划图的各时间参数并找出关键问题和关键路径。（8分）解：用X1, X2，X3分别表示大豆、玉米、麦子的种植公顷数；X4，X5分别表示奶牛和鸡的饲养数；X6，X7分别表示秋冬季和春夏季的劳动力（人日）数，则有maxZ 3000x14100x24600x3 900x420x520x625x7x1xX31.5x4100（土地限制）400x4 3x515000（资金限制）20x135x210x3 100x40.6X5x63500（劳动力限制）50x1175x240x350x40.3x5x74000（劳动力限制）x4200（牛栏限制）x51500（鸡舍限制）Xj0 (j

15、1,2,7)三、对偶问题。共计-8分X22X253x1 x2X310X1 , X20；4分(2)原问题的对偶规划问题为：min w 5y1 10y23y26y1 y222y1 y2 10*20 ；3分(3)对偶规划问题的最优解为：Y(4,2)To1分四、单纯形表求解线性规划。共计16分解：引入松弛变量 X4、X5、X6,标准化得，maxZ2x1X2X3s. t.3 X1+ X2 + X3+ X4=60X 1 -X 2 + 2 X 3+ X5=10X l+x 2- X 3+ X6= 0X 1, x 2 , X 3, X4、X5、X6, > 03 分建初始单纯形表，进行迭代运算： 分CbXb

16、b'2-110000X1X2X3X4X5X60X460311100200X5101-1201010*0X62011-100120102*-110000X43004-51-307.52X1101-120100X61002-30-115*22001*-30-200X4100011-1-22X115100.500.50.5-1X2501-1.50-0.50.532500-1.50-1.5-0.5由最优单纯形表可知，原线性规划的最优解为:(15,5,0)T 分最优值为：z*=25 。五、求解运输问题。共计18分解：(1)最小元素法：(也可以用其他方法，酌情给分)设 Xij 为由 Ai 运往 B

17、j 的运量(i=1,2,3;j=1,2,3,4)列表如下：销地产地B1B2B3B4产量1202525215305253550销 以，基本的初始可行解为：X14 =25 ； X22=20 ； X24 =5 ；X31 =15 ； X33 =30；X34=5其余的Xij=o。3分(2)求最优调运方案：1会求检验数，检验解的最优性：11=2 ; 12=2 ;13=3 ;21=1 ;23=5;32= - 13 分2会求调整量进行调整：=52分销地产地B1B2B3B4产量12315155302510252550销 量152030351003再次检验4能够写出正确结论解为：X14=

18、25; X22 =15X24 =10X31 =15, X32 =5X33=30其余的最少运费为： 535 1六、灵敏度分析。共计 8分(1)(4分)(2)40Xij=0。分。8/32/3(4max ,-1/6 1/6200/3B1ax10 , 5J3 10C min4b1 c1min10/32/3100/3100c11 15?七、建动态规划模型。共计8分解：(1)设阶段变量k表示年度，因此，阶段总数n =3。(2) 状态变量sk表示第k年度初拥有的完好机床台数，同时也是第k(3) 决策变量uk，表示第k年度中分配于生产产品p1的机器台数。于年度末时的完好机床数量。 sk -uk便为该年度中分配于生产产品p1的机器台数.(4) 状态转移方程为(5) 允许决策集合 i，在第35ku段为).65視6屮)山0 uk sk(6) 目标函数。设gk(sk,uk)为第k年度的产量，则k kgk(sk,uk) = 45uk + 35(sk -uk),因此，目标函数为(7)条件最优目标函数递推方程。fk(Sk)k max(uk(Sk)令fk(sk