《运筹学》 期末考试 试卷A 答案

《运筹学》试题样卷（一）题号 .二三四五六七八九十总分得分、判断题（共计10分，每小题1分，对的打J,错的打X）无孤立点的图一定是连通图。对于线性规划的原问题和其对偶问题，若其中一个有最优解，另一个也一定有最优解。如果一个线性规划问题有可行解，那么它必有最优解。4．对偶问题的对偶问题一定是原问题。O>05．用单纯形法求解标准形式（求最小值）的线性规划问题时，与j对应的变量都可以被选作换入变量。6．若线性规划的原问题有无穷多个最优解时，其对偶问题也有无穷多个最优解。度为0的点称为悬挂点。表上作业法实质上就是求解运输问题的单纯形法。一个图G是树的充分必要条件是边数最少的无孤立点的图。10.任何线性规划问题都存在且有唯一的对偶问题。①②③④⑤⑥⑦⑧⑨、建立下面问题的线性规划模型（8分）某农场有100公顷土地及15000元资金可用于发展生产。农场劳动力情况为秋冬季3500人日；春夏季4000人日。如劳动力本身用不了时可外出打工，春秋季收入为25元/人日，秋冬季收入为20元/人日。该农场种植三种作物：大豆、玉米、小麦，并饲养奶牛和鸡。种作物时不需要专门投资，而饲养每头奶牛需投资800元，每只鸡投资3元。养奶牛时每头需拨出1.5公顷土地种饲料，并占用人工秋冬季为100人日，春夏季为50人日，年净收入900元/每头奶牛。养鸡时不占用土地，需人工为每只鸡秋冬季0.6人日，春夏季为0.3人日，年净收入2元/每只鸡。农场现有鸡舍允许最多养1500只鸡，牛栏允许最多养200头。三种作物每年需要的人工及收入情况如下表所示：大豆玉米麦子秋冬季需人日数203510春夏季需人日数507540年净收入（元/公顷）300041004600试决定该农场的经营方案，使年净收入为最大。

xx三、已知下表为求解某目标函数为极大化线性规划问题的最终单纯形表，表中“4,“5为松弛变量，问题的约束为形式（共8分）x1x2x3x4x5x35/201/211/20X15/21—1/20—1/61/3c.-z.j j0—40—4—2（1）写出原线性规划问题；（4分）（2）写出原问题的对偶问题；（3分）（3）直接由上表写出对偶问题的最优解。（1分）四、用单纯形法解下列线性规划问题（16分）maxZ-2x-x+x123s.t. 3x1+x2+x3<60x1x2+2x3< 10x1+x2-x3<20x1,x2,x3-0五、求解下面运输问题。（18分）某公司从三个产地A1、A2、A3将物品运往四个销地B1、B2、B3、B4,各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如表所示：问：应如何调运，可使得总运输费最小?产地销地B1B2B3B4产量A1056725A827625A3934850销、灵敏度分析（共8分）线性规划maxz=10x1+6x2+4x3s.t.xs.t.x1+x2+ x3<10010x1+4x2+5x3<6002x1+2x2+6x3<300x1,xx1,x2,x3-0的最优单纯形表如下：6X。2200/305/615/3-1/6010X1100/311/60-2/31/600x6100040-2010-8/30 -10/3-2/30（1）Ci在何范围内变化，最优计划不变？（4分）⑵bi在什么范围内变化，最优基不变？（4分）七、试建立一个动态规划模型。（共8分）某工厂购进100台机器，准备生产p1,p2两种产品。若生产产品p1，每台机器每年可收入45万元，损坏率为65%；若生产产品p2，每台机器每年可收入35万元，损坏率为35%；估计三年后将有新的机器出现，旧的机器将全部淘汰。试问每年应如何安排生产，使在三年内收入最多？八、求解对策问题。（共10分）某种子商店希望订购一批种子。据已往经验，种子的销售量可能为500，1000，1500或2000公斤。假定每公斤种子的订购价为6元，销售价为9元，剩余种子的处理价为每公斤3元。要求：（1）建立损益矩阵；（3分）（2）用悲观法决定该商店应订购的种子数。（2分）（3）建立后悔矩阵，并用后悔值法决定商店应订购的种子数。（5分）九、求下列网络计划图的各时间参数并找出关键问题和关键路径。（8分）工序代号工序^时间最早开工时间最早完工时间最晚开工时间最晚完工时间机动时间1-281-37

1-462-432-553-423-634-534-674-745-796-78十、用标号法求V1到V6的最短路。（6分）运筹学样卷（一）答案

判断题。共计10分，每小题1分①②③④⑤⑥⑦⑧⑨10XVXVVVXVXV二、建线性规划模型。共计8分(酌情扣分)解：用X-X2,x3分别表示大豆、玉米、麦子的种植公顷数；x4,x5分别表示奶牛和鸡的饲养数；x6,x7分别表示秋冬季和春夏季的劳动力（人日）数，则有maxZ=3000x+4100x+4600x+900x+20x+20x+25x1 2 3 4567‘xi+x2+x3+1.5x4 <100 （土地限制）400x4+3x5 <15000 （资金限制）20x1+35x2+10x3+100x4+0.6x5+x6<3500（劳动力限制）<50x1+175x2+40x+50x4+0.3x+x7<4000（劳动力限制）2 3 x4 5<200 （牛栏限制）x5 <1500 （鸡舍限制）x.>0（j=1,2,…,7）j三、对偶问题。共计8分m/■,、 kti.4.njx.i、-1m maxz—6x—2x+10x解：（1）原线性规划问题： 1 2 3x+2x<522<3x一x+x<101234分3分1分x4分3分1分12(2)原问题的对偶规划问题为:minw—5y1+10y23y2>6y1-y2>-22「y2>10|…2>0(3)对偶规划问题的最优解为：Y*=(4,2)t。四、单纯形表求解线性规划。共计16分解：引入松弛变量尤4、尤5、龙6,标准化得，maxZ—2x-x+x123

s.t.3x1+x2+x3+x4 =60x1-x2+2x3+x5 =10x1+x2-x3 +x6=0X1，X2，X3x4x5x6三0 3分建初始单纯形表，进行迭代运算： 9分CBXbb’2-110009x1X2X3X4X5X60X460311100200X510[1]-1201010*0X62011-100120o102*-110000X43004-51-307.52X1101-12010---0X6100[2]-30-115*%2001*-30-200X4100011-1-22X115100.500.50.5-1X2501-1.50-0.50.5032500-1.50-1.5-0.5由最优单纯形表可知，原线性规划的最优解为：（15,5,0）t…？分最优值为：z*=25。 2分五、求解运输问题。共计18分解：（1）最小元素法：（也可以用其他方法，酌情给分）设Xij为由Ai运往Bj的运量（i=1,2,3;j=1,2,3,4）,列表如下：销地产地B1B2B3B4产量1252522052531530550销3分所以，基本的初始可行解为："14=25；x22=20；x24=5；TOC\o"1-5"\h\zX31=15；x33=30；x34=5

其余的xij=0 3分（2）求最优调运方案：1会求检验数，检验解的最优性：o11=2；o12=2；o13=3；o21=1；o23=5；o32=-1 3分2会求调整量进行调整：=5 2分销地产地B1B2B3B4产量12525215102531553050销OC\o"1-5"\h\z…3分3再次检验 2分4能够写出正确结论解为：x14=25；x22=15；x24=10 x31=15，x32=5 x33=30其余的xij=0。 ……1分最少运费为：535 1分。六、灵敏度分析。共计8分(1)(4分)卜8/3-2/3Jmax<,><Ac[1/6 1/6J1—4<Ac<5,6=10—4<c+Ac<10+5=151 11（2）（4分）f—200/31 … .f-100/3-1001max<-8,><Ab<mm<,>[ 5/3J1 [-2/3 -2J-40<Ab=101七、建动态规划模型。共计8分解：（1）设阶段变量k表示年度，因此，阶段总数n=3。（2）状态变量sk表示第k年度初拥有的完好机床台数，同时也是第k-1年度末时的完好机床数量。（3）决策变量uk，表示第k年度中分配于生产产品p1的机器台数。于是sk-uk便为该年度中分配于生产产品p1的机器台数.（4）状态转移方程为s=0.35u+0.65(s-u)k+1 k kk(5)允许决策集合，在第k段为U(s)={u|0<u<s}kkkkk(6)目标函数。设gk(sk,uk)为第k年度的产量，则gk(sk,uk)=45uk+35(sk-uk)因此，目标函数为因此，目标函数为g(s,u)kkk(7)条件最优目标函数递推方程。f(s)=max(u(s))kk kkueUkk令fk(sk)表示由第k年的状态sk出发，采取最优分配方案到第3年度结束这段时间的产品产量，根据最优化原理有以下递推关系：(8).边界条件为{[45u+35(s—u)]+f[0.35u+0.65(s—(8).边界条件为{[45u+35(s—u)]+f[0.35u+0.65(s—uk kk k+1 k k)]}八、解决对策问题。共10分f3+1(s3+1)=0(1)益损矩阵如下表所示：……3分销售S1500S21000S31500S42000订购A15001500150015001500A210000300030003000A31500-1500150045004500A42000—3000030006000(2)悲观法：A1，订购500公斤。……2分(3)后悔矩阵如下表所示：……3分S1S2S3S4最大后悔值A101500300045004500A215000150030003000A330001500015003000A445003000150004500按后悔值法商店应取决策为A2或A3，即订购1000公斤或1500公斤。……2分九、求网络计划图的各时间参数。(8分)工序代号工序时间最早开工时间1-280工时间8023 /9——最早完种瓶开时间0工时间0最晚完工时间8541-37072921-460651162-