《《运筹学》期末考试试卷A答案.pdf》由会员分享，可在线阅读，更多相关《《运筹学》期末考试试卷A答案.pdf（9页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、一、判 断 题（共 计 1 0 分，每小题I 分，对的打J,错的打X）1 .无孤立点的图一定是连通图。2 .对于线性规划的原问题和其对偶问题，若其中一个有最优解，另一个也一定有最优解。3 .如果一个线性规划问题有可行解，那么它必有最优解。4 .对偶问题的对偶问题一定是原问题。5 .用单纯形法求解标准形式（求最小值）的线性规划问题时，与对应的变量都可以被选作换入变量。6 .若线性规划的原问题有无穷多个最优解时，其对偶问题也有无穷多个最优解。7.度为0的点称为悬挂点。8 .表上作业法实质上就是求解运输问题的单纯形法。9 .一个图G是树的充分必要条件是边数最少的无孤立点的图。1 0 .任何线性规划问
2、题都存在且有唯一的对偶问题。二、建立下面问题的线性规划模型（8分）某农场有1 0 0 公顷土地及1 5 0 0 0 元资金可用于发展生产。农场劳动力情况为秋冬季3 5 0 0 人日；春夏季4 0 0 0 人日。如劳动力本身用不了时可外出打工，春秋季收入为2 5 元/人日，秋冬季收入为2 0 元/人日。该农场种植三种作物：大豆、玉米、小麦，并饲养奶牛和鸡。种作物时不需要专门投资，而饲养每头奶牛需投资8 0 0 元，每只鸡投资3元。养奶牛时每头需拨出1.5 公顷土地种饲料，并占用人工秋冬季为1 0 0 人日，春夏季为5 0 人日，年净收入9 0 0元/每头奶牛。养鸡时不占用土地，需人工为每只鸡秋冬
3、季0.6 人日，春夏季为0.3 人 I I,年净收入2 元/每只鸡。农场现有鸡舍允许最多养1 5 0 0 只鸡，牛栏允许最多养2 0 0 头。三种作物每年需要的人工及收入情况如下表所示：试决定该农场的经营方案，使年净收入为最大。大豆玉米麦子秋冬季需人日数2 03 51 0春夏季需人日数5 0754 0年净收入（元/公顷）3 0 0 04 1 0 04 6 0 0三、已知下表为求解某目标函数为极大化线性规划问题的最终单纯形表，表中“4为松弛变量，问题的约束为_形式（共 8分）（1）写出原线性规划问题；（4分）X乃了3X4X5尤 3 5/201/211/20为 5/21一 1/201/61/3CJ
4、-ZJ0-40-4-2（2）写出原问题的对偶问题；（3分）（3）直接由上表写出对偶问题的最优解。（1分）四、用单纯形法解下列线性规划问题（1 6分）max Z=2 3-x2+x3s.t.3 X i +x2+x3 6 0 xx 2 +2 X 3 4 1 0X +X 2_ x3 0五、求解下面运输问题。（1 8分）某公司从三个产地Ai、A?、A3将物品运往四个销地&、B?、B 3、B4,各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如表所示：问：应如何调运，可使得总运输费最小？销 地产 地纥B2鸟当产 量A1 05672 5482762 5A3934850销 量1 52 030351
5、0 0六、灵敏度分析（共8分）线性规划 m a x z =1 0 x i +6x2+4x3X|,X2,x3 0s.t.X1+x2+X31 0 01 0 x i +4 X 2 +5x 360 02 x +2 x2+6 X 330 0的最优单纯形表如下:6X22 0 0/305/615/3-1/601 0Xl1 0 0/311/60-2/31/600X61 0 0040-201 j0-8/30-1 0/3-2/30（1）G在何范围内变化，最优计划不变？（4分）（2）也在什么范围内变化，最优基不变？（4分）七、试建立一个动态规划模型。（共8分）某工厂购进1 0 0台机器，准备生产p l,p 2两种产
6、品。若生产产品pl ,每台机器每年可收入4 5万元，损坏率为6 5%；若生产产品p2 ,每台机器 每年可收入3 5万元，损坏率为3 5%；估计三年后将有新的机器出现，旧的机器将全部淘汰。试问每年应如何安排生产，使在三年内收入最多？八、求解对策问题。（共 1 0 分）某种子商店希望订购一批种子。据已往经验，种子的销售量可能为50 0,1 0 0 0,1 50 0 或 2 0 0 0 公斤。订购价为6 元，销售价为9 元，剩余种子的处理价为每公斤3 元。要求：（1）建立损益矩阵；（3 分）（2）用悲观法决定该商店应订购的种子数。（2分）（3）建立后悔矩阵，并用后悔值法决定商店应订购的种子数。（5
7、分）九、求下列网络计划图的各时间参数并找出关键问题和关键路径。（8 分）假定每公斤种子的十、用标号法求Vi至 I V6的最短路。（6 分）工序代号工/时间最早开工时间最早完工时间也 开工时间最晚完工时间机动时间1-281-371-462-432-553-423-634-534-674-745-796-78运筹学样卷（一）答案一、判断题。共 计 1 0 分，每小题I 分1 0XXVVXXV二、建线性规划模型。共计8 分（酌情扣分）解：用修，内 分别表示大豆、玉米、麦子的种植公顷数；4,无 5分别表示奶牛和鸡的饲养数；，尤 7 分别表示秋冬季和春夏季的劳动力（人日）数，则有max Z=3000$+
8、4100%2+4600%3+900%4+20 x5+20 x6+25巧尤 1+%2 +无 3 +1.5%4 410（）（土 地 限 制）40014+3%15000（资 金 限 制）20阳+35x2+10 x3+100 x4+0.6x5+x6 3500（劳 动 力 限 制）50占+175电+4（）g+504+3%+巧4 4000（劳 动 力 限 制）4 200（牛 栏 限 制）x5 0（人1,2,7）三、对偶问题。共计8 分解：（1 ）原线性规划问题：maxz=6x）-2%2+10%3x2+2X2 5v 3 2一工2 +与4 10X ,2 ”。；.4 分（2）原问题的对偶规划问题为：min 卬=
9、5月+10y23y2 2 6力 一 为1 22yl+-2 210，为 2 0；*3分（3）对偶规划问题的最优解为：丫*=（4,2）T。1 分四、单纯形表求解线性规划。共 计 1 6 分解：引入松弛变量X 4、x5.X 6.标准化得，max Z=2修-x2+x3s.t.3 X!+x2+x3+x4=6 0X I-X 2+2 x 3 +X5=10X 1+X 2-X 3+x6=0 x 1,x2,x3,X4、X5、X6，2 0.3 分建初始单纯形表，进行迭代运算：.9 分b 2-11000eCBX bX Ix2X 3X 4X5x60X 46 03111002 00X 51 0 1-120101 0*0X
10、 62 011-10012 0602*-110000 x43 004-51-307.52X j1 01-12010 0X 61 00 2-30-115*62 001*-30-200X41 00011-1-22X 1 5100.500.50.5-1x2501-1.50-0.50.562 500-1.50-1.5-0.5由最优单纯形表可知，原线性规划的最优解为：（1 5,5,0 ）1.2分最优值为：z*=2 5。.2分五、求解运输问题。共 计1 8分解：（1）最小元素法：（也可以用其他方法，酌情给分）设 X g 为由 A运往 B j 的 运 量（i=l,2,3；j=l,2,3,4）,列表如下：所以
11、，基本的初始可行解为：X”=2 5：X2 2=2 0：X 2 4 =5 s销 地产 地4为为产 量12 52 522 052 531 53 055 0销 量1 52 03 03 51 0 0.3分X 3 1 =1 5：X 3 3 =3 0：X 3 4=5其余的X ij=o，.3分（2）求最优调运方案：1会求检验数,检验解的最优性：0 1 1=2；0 1 2=2；0 1 3=3；CT2 1=1；b 2 3=5；a 3 2=-1.3 分2会求调整量进行调整：=5 .2分销 地产 地坊4%产 量121 52 51 02 52 531553050销 量15203035100.3 分3 再次检验.2 分
12、4 能够写出正确结论解为：X14=25：X2 2=1 5，x24=10 X31=15-X32=5 33=30其余的X.1 分最少运费为：535.1 分。六、灵敏度分析。共计8 分(1)(4 分)ma x 出,3 wcm i nI 1/6 1/6-1 0/3)-2/3 J-4 A C)5 ,6 =1 0 4 K j+?1 0 +5 =1 5(2)(4 分)ma x-2 0 0/3-0 0,-5/3 kb、min-1 0 0/3 -1 0 0一2/3 -2-4 0 A/?!=1 0七、建动态规划模型。共计8 分解：(1)设阶段变量k 表示年度，因此，阶段总数n=3。(2)状态变量sk表示第k 年度
13、初拥有的完好机床台数，同时也是第k-1 年度末时的完好机床数量。(3)决策变量u k,表示第k 年度中分配于生产产品p l 的机器台数。于是sk-uk便为该年度中分配于生产产品pl的机器台数.(4)状态转移方程为sk+l=0.35%+0.65(s*-uk)(5)允许决策集合，在 第 k 段 为 t7*(sA)=wlt|0 sk(6)目标函数。设 gk(sk,uk)为第k 年度的产量，W Jgk(sk,uk)=45uk+35(sk-uk),因此，目标函算为R k=g k(Sk，Uk)i=k(7)条件最优目标函数递推方程。fk(sk)=max(uk(sk)以叫令 fk(sk)表示由第k 年的状态s
14、k 出发，采取最优分配方案到第3 年度结束这段时间的产品产量，根据最优化原理有以下递推关系：45%+35(-%)+/*+J0.35“*+0.65(s*-“*)(8).边界条件为/3+1($3+1)=八、解决对策问题。共 10分(1)益损矩阵如下表所示：3 分订销 售购Si500S21000S31500s42000A5001500150015001500A?10000300030003000A31500-1500150045004500A4 2 0 0 0-3 0 0 003 0 0 06 0 0 0（2）悲观法：Ai ,订购5 0 0 公斤。2分（3）后悔矩阵如下表所示：3分按后悔值法商店应取
15、决策为A2 或 A3 ,即订购1 0 0 0 公斤或1 5 0 0 公斤。2分S1S2S3S4最大后悔值A101 5 0 03 0 0 04 5 0 04 5 0 0A21 5 0 001 5 0 03 0 0 03 0 0 0A33 0 0 01 5 0 001 5 0 03 0 0 0A44 5 0 03 0 0 01 5 0 004 5 0 0九、求网络计划图的各时间参数。（8分）AAA53|1 12Z/n7)/2 6 工序代号工序时间最早开工时间最早兑一工时间开工时间最 晚 完L工时间场 动时间1-28080801-37072921-460651 162-4381 181 102-5581 391 413-427991 123-6371 01 51 884-531 11 41 11 404-671 11 81 11 804-741 11 52 22 61 15-791 42 31 72 636-781 82 61 82 60关键问题是：f；2-；一；一6；6 f 关键线路是：/。评分标准：能正确给各顶点标号并填表.4分正确写出关键问题.2分正确画出关键线路.2分十、用标号法求“到V 6的最短路。（6分）(4.vl)V2 6(9.v3)V(IO,v2)4