《运筹学》_期末考试_试卷A_答案.pdf

《《运筹学》_期末考试_试卷A_答案.pdf》由会员分享，可在线阅读，更多相关《《运筹学》_期末考试_试卷A_答案.pdf（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、一、判断题（共计 10 分，每小题 1 分,对的打，错的打 X）1。无孤立点的图一定是连通图.2.对于线性规划的原问题和其对偶问题，若其中一个有最优解，另一个也一定有最优解.3。如果一个线性规划问题有可行解，那么它必有最优解。4对偶问题的对偶问题一定是原问题.5用单纯形法求解标准形式（求最小值)的线性规划问题时，与j 0对应的变量都可以被选作换入变量。6若线性规划的原问题有无穷多个最优解时,其对偶问题也有无穷多个最优解。7.度为 0 的点称为悬挂点.8。表上作业法实质上就是求解运输问题的单纯形法。9。一个图 G 是树的充分必要条件是边数最少的无孤立点的图。10.任何线性规划问题都存在且有唯一的

2、对偶问题。二、建立下面问题的线性规划模型（8 分）某农场有 100 公顷土地及 15000 元资金可用于发展生产。农场劳动力情况为秋冬季3500 人日;春夏季 4000 人日.如劳动力本身用不了时可外出打工，春秋季收入为25 元/人日,秋冬季收入为 20 元/人日。该农场种植三种作物：大豆、玉米、小麦，并饲养奶牛和鸡。种作物时不需要专门投资，而饲养每头奶牛需投资800 元，每只鸡投资3 元。养奶牛时每头需拨出 1.5 公顷土地种饲料，并占用人工秋冬季为 100 人日，春夏季为 50 人日，年净收入 900 元/每头奶牛。养鸡时不占用土地，需人工为每只鸡秋冬季0.6 人日,春夏季为 0。3 人日

3、，年净收入 2 元/每只鸡。农场现有鸡舍允许最多养 1500 只鸡,牛栏允许最多养 200 头。三种作物每年需要的人工及收入情况如下表所示：大豆玉米麦子秋冬季需人日数春夏季需人日数年净收入（元/公顷）试决定该农场的经营方案，使年净收入为最大.205030003575410010404600 x,x三、已知下表为求解某目标函数为极大化线性规划问题的最终单纯形表，表中45为松弛变量，问题的约束为 形式（共 8 分）x1x21/21/2x3100 x41/21/6x51/3x3x15/25/2010cj zj（1)写出原线性规划问题；（4 分）（2)写出原问题的对偶问题；（3 分）(3）直接由上表写

4、出对偶问题的最优解。(1 分)四、用单纯形法解下列线性规划问题（16 分）max Z 2x1 x2 x3s.t.3 x1+x2+x360 x 1 x 2+2 x 310 x 1+x 2 x 320 x 1,x 2,x 30五、求解下面运输问题。（18 分）某公司从三个产地 A1、A2、A3将物品运往四个销地 B1、B2、B3、B4，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如表所示：问：应如何调运,可使得总运输费最小?BB2销 地1产 地B3B4产量252550100A1A2A3108915523206743076835销量六、灵敏度分析（共 8 分）线性规划 max z=10

5、 x1+6x2+4x3s.t.x1+x2+x310010 x1+4 x2+5 x36002x1+2 x2+6 x3300 x1，x2,x30的最优单纯形表如下：6100 x2x1x6j200/3100/310001005/61/648/310005/32/3-2-10/3 1/61/60 2/30010（1）C1在何范围内变化，最优计划不变？(4 分)（2)b1在什么范围内变化,最优基不变？（4 分)七、试建立一个动态规划模型。（共 8 分）某工厂购进 100 台机器，准备生产 p1，p2 两种产品。若生产产品 p1，每台机器每年可收入 45 万元，损坏率为 65；若生产产品 p2，每台机器每

6、年可收入 35 万元，损坏率为 35；估计三年后将有新 的机器出现，旧的机器将全部淘汰.试问每年应如何安排生产，使在三年内收入最多？八、求解对策问题.（共 10 分）某种子商店希望订购一批种子。据已往经验,种子的销售量可能为 500，1000，1500 或 2000 公斤。假定每公斤种子的订购价为 6 元,销售价为 9 元，剩余种子的处理价为每公斤3 元.要求：(1）建立损益矩阵；（3 分）（2)用悲观法决定该商店应订购的种子数。（2 分）（3）建立后悔矩阵,并用后悔值法决定商店应订购的种子数。(5 分）九、求下列网络计划图的各时间参数并找出关键问题和关键路径。（8 分)1工序代号12131-

7、424253-4364-54-647576773工序时间87635233749886234723最早完工时间6最晚开工时间8最晚完工时间机动时间534597最早开工时间十、用标号法求 V1到 V6的最短路。（6 分)V2436V1656V34V4834V5V6运筹学样卷（一）答案一、判断题。共计 10 分，每小题 1 分XXXX10二、建线性规划模型。共计8 分(酌情扣分）解：用x1,x2,x3分别表示大豆、玉米、麦子的种植公顷数;x4,x5分别表示奶牛和鸡的饲养数;x6,x7分别表示秋冬季和春夏季的劳动力（人日）数，则有maxZ 3000 x1 4100 x2 4600 x3900 x4 2

8、0 x5 20 x6 25x7100(土地限制)x1 x2 x31.5x4400 x43x515000(资金限制)20 x135x210 x3100 x40.6x5 x6 3500(劳动力限制)50 x1175x2 40 x350 x40.3x5 x7 4000(劳动力限制)x4 200(牛栏限制)x51500(鸡舍限制)x 0(j 1,2,7)j三、对偶问题。共计 8 分解：（）原线性规划问题:max z 6x12x210 x3x22x2 53x1 x2 x310 x,x 021;4 分（)原问题的对偶规划问题为：minw 5y110y23y2 6y y 2122y1 y210y,y 012

9、；3 分Y(4,2)T。1 分（）对偶规划问题的最优解为:四、单纯形表求解线性规划。共计16 分解：引入松弛变量 x4、x5、x6,标准化得，maxZ 2x1 x2 x3s.t。3 x1+x2+x3+x4=60 x 1 x 2+2 x 3+x5=10 x 1+x 2-x 3+x6=0 x 1，x 2,x 3，x4、x5、x6，03 分建初始单纯形表,进行迭代运算:9分CBXbb2x1-1x21x30 x40 x50 x60001020202-13x4x5x660102003112*010001001-1114121001012-1152-3-310。5-1。51。510001000100001

10、00-31-1-210。5-0。500100010-20.50。52010*207.5-5*x4x1x630101020 x4x1x21015525-1。50。5由最优单纯形表可知，原线性规划的最优解为:（15,5,0）T2 分最优值为：z=25。2 分五、求解运输问题。共计18 分解:(1）最小元素法:（也可以用其他方法，酌情给分)设 xij为由 Ai运往 Bj的运量(i=1,2,3；j=1,2,3，4）,列表如下：销 地B1B2B3B4产 量产 地1231520302555252550销量152030351003 分所以，基本的初始可行解为：x14=25；x22=20;x24=5；X31=

11、15；x33=30；x34=5其余的 xij=0。3 分（2）求最优调运方案：1 会求检验数，检验解的最优性：11=2；12=2；13=3;21=1；23=5;32=13 分2 会求调整量进行调整：=52 分销 地B1B2B3B4产 量产 地123销量15151552030302510352525501003 分3 再次检验2 分4 能够写出正确结论解为:x14=25；x22=15；x24=10 x31=15，x32=5x33=30其余的 xij=0。1 分最少运费为：535 1 分。六、灵敏度分析。共计 8 分(1）（4 分)8/3 2/310/3max,c1 min1/61/62/34 c

12、1 5,6 104 c1c1105 15（2）（4 分）200/3100/3 100max,b min,15/32/3240 b110七、建动态规划模型。共计8 分解：(1)设阶段变量 k 表示年度，因此，阶段总数n=3。(2）状态变量 sk 表示第 k 年度初拥有的完好机床台数，同时也是第 k1 年度末时的完好机床数量。（3）决策变量 uk,表示第 k 年度中分配于生产产品 p1 的机器台数。于是 sk uk 便为该年度中分配于生产产品 p1的机器台数(4）状态转移方程为s sk k 1 1 0 0.3535u uk k 0 0.6565(s sk k u uk k)（5)允许决策集合,在第

13、 k 段为U Uk k(s sk k)u uk k0 u uk k s sk k（6）目标函数。设 gk(sk,uk）为第 k 年度的产量，则gk（sk，uk)=45uk+35(skuk）,因此，目标函数为3 3R R g g(s s,u u)k ki i k kk kk kk k(7）条件最优目标函数递推方程。f fk k(s sk k)maxmax(u uk k(s sk k)u uk k U Uk k令 fk(sk）表示由第 k 年的状态 sk 出发，采取最优分配方案到第3 年度结束这段时间的产品产量，根据最优化原理有以下递推关系：4545u uk k 3535(s sk k u uk

14、k)f fk k 1 1 0 0.3535u uk k 0 0.6565(s sk k u uk k)（8）。边界条件为f f3 3 1 1(s s3 3 1 1)0 0八、解决对策问题。共 10 分（1）益损矩阵如下表所示：3 分销 售S1S2S3S4订 购500100015002000 A1500A21000A31500A420001500015003000150030001500015003000450030001500300045006000（2）悲观法：A1，订购 500 公斤。2 分(3）后悔矩阵如下表所示:3 分A1A2A3S1015003000S2150001500S33000

15、15000S4450030001500最大后悔值450030003000A445003000150004500按后悔值法商店应取决策为A2或 A3,即订购 1000 公斤或 1500 公斤。2 分九、求网络计划图的各时间参数。(8 分）1481405825893311026004614726071172833679180工序工序最早开最早完最晚开最晚完 18机动代号时间工时间工时间工时间工时间时间121-31-42-42-53-43-64-54-6475-767876352337498000887711111114188761113910141815232602589915111122171889111114111814182626260260128001130关键问题是：；2；6；6关键线路是：1评分标准：能正确给各顶点标号并填表。.。.。.。.4 分正确写出关键问题.。.。.。.。.2 分正确画出关键线路。.。.。.。.。分24167十、用标号法求 v1到 v6的最短路。（6 分）(4,v1)(9,v3)V26V4(10,v2)547(0,0)1V12832最短路为:v1,v2，v3,v4,v5,v6长度为：12V3(6,v2)7V5(10,v4)正确标号：4 分；正确写出结论：（8,v12）分(11,v2)(13,v3)V6(12,v5)(14,v4)