《运筹学》-期末考试-试卷A-答案(1)

1、精品文档1欢迎下载运筹学试题样卷（一）题号-一- -二二三四五六七八九十总分得分、判断题（共计 10 分，每小题 1 分，对的打，错的打 X）1.无孤立点的图一定是连通图。2.对于线性规划的原问题和其对偶问题，若其中一个有最优解，另一个也一定有最优解。3.如果一个线性规划问题有可行解，那么它必有最优解。4对偶问题的对偶问题一定是原问题。05 用单纯形法求解标准形式（求最小值）的线性规划问题时，与j 0对应的变量都可以被选作换入变量。6 若线性规划的原问题有无穷多个最优解时，其对偶问题也有无穷多个最优解。7.度为 0 的点称为悬挂点。8.表上作业法实质上就是求解运输问题的单纯形法。9.一个图 G

2、 是树的充分必要条件是边数最少的无孤立点的图。10.任何线性规划问题都存在且有唯一的对偶问题。、建立下面问题的线性规划模型（8 分）某农场有 100 公顷土地及 15000 元资金可用于发展生产。 农场劳动力情况为秋冬季3500人日；春夏季 4000 人日。如劳动力本身用不了时可外出打工，春秋季收入为 25 元/人日，秋冬季收入为 20 元/人日。该农场种植三种作物：大豆、玉米、小麦，并饲养奶 牛和鸡。种作物时不需要专门投资，而饲养每头奶牛需投资800 元，每只鸡投资 3 元。养奶牛时每头需拨出1.5 公顷土地种饲料，并占用人工秋冬季为 100 人日，春夏季为 50人日，年净收入 900 元/

3、每头奶牛。养鸡时不占用土地，需人工为每只鸡秋冬季0.6人日，春夏季为 0.3 人日，年净收入 2 元/每只鸡。农场现有鸡舍允许最多养1500 只鸡，牛栏允许最多养 200 头。三种作物每年需要的人工及收入情况如下表所示：大豆玉米麦子秋冬季需人日数203510春夏季需人日数507540年净收入（元/公顷）300041004600精品文档2欢迎下载试决定该农场的经营方案，使年净收入为最大。三、已知下表为求解某目标函数为极大化线性规划问题的最终单纯形表，表中 松弛变量，问题的约束为形式（共 8 分）X!X2X3X4X5X35/201/211/20X15/211/201/61/3CjZj0-4042（

4、1）写出原线性规划问题；（4 分）（2）写出原问题的对偶问题；（3 分）（3）直接由上表写出对偶问题的最优解。（1 分）四、用单纯形法解下列线性规划问题（16 分）max Z2x1X2X3s. t.3X1+X2+X360X1-X2+2X310X1+X2-X320X1,X2,X30五、求解下面运输问题。（18 分）某公司从三个产地 A、A、A 将物品运往四个销地B1、B2、凶、B4,各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如表所示:问：应如何调运，可使得总运输费最小？销地产地B1B2B3B4产量A1056725A2827625A3934850销、灵敏度

5、分析（共 8 分）线性规划max z = 10 Xi+ 6X2+ 4 X3S.t.X1+X2+X310010X1+4X2+ 5X3600X4,X5为精品文档3欢迎下载2X1+2 X2+ 6X3300精品文档1334欢迎下载X1, X2,X30的最优单纯形表如下：6X2200/305/615/31/6010X1100/311/60-2/31/600X6100040-201j0-/30-10/32/30（1）C1在何范围内变化，最优计划不变？（4 分）（2）bi在什么范围内变化，最优基不变？（4 分）七、试建立一个动态规划模型。（共 8 分）某工厂购进 100 台机器，准备生产 pl , p2 两

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

7、数。（5 分）九、求下列网络计划图的各时间参数并找出关键问题和关键路径。（8 分）精品文档1335欢迎下载52 58 934672开 最早完最晚完工序工序最早开机动工时间工时间工时间工时间代号精品文档6欢迎下载运筹学样卷（一）答案判断题。共计 10 分，每小题 1 分10XXVVXVXV1-281-371-462-432-553-423-634-534-674-745-796-78短路。（6 分）十、用标号法求 V至 U V6 的最精品文档5欢迎。下载二、建线性规划模型。共计 8 分（酌情扣分）y1,y2四、单纯形表求解线性规划。共计16 分解：引入松弛变量X4、X5、X6，标准化得，maXZ

8、 2X1X2X3s. t.3X1+X2+X3+X4=60X1-X2+2X3+X5=10X1+X2-X3+X6=0X1,X2,X3,X4、X5、X6,0.3 分建初始单纯形表，进行迭代运算：.9 分maXZ 3000X14100X24600X3900X420X520X625X7X1X2X31.5X4100（土地限制）400X43X515000（资金限制）20X135X210X3100X40.6X5X63500（劳动力限制）50X1175X240X350X40.3X5X74000（劳动力限制）X4200（牛栏限制）X51500（鸡舍限制）Xj0 ( j1,2,7)三、对偶问题。共计8 分解：（1）

9、原线性规划问题：maXz 6X12X210X3X22X253X1X2X310X1,X20；.4 分则有（2）原问题的对偶规划问题为:min w 5y110y23y26y1y22y1y210（3）对偶规划问题的最优解为:Y (4,2)T。1 分解：用Xi，X2，X3分别表示大豆、玉米、麦子的种植公顷数； 饲养数；x6,x7分别表示秋冬季和春夏季的劳动力（人日）数，X4，X5分别表示奶牛和鸡的3 分精品文档8欢迎下载CBXb2-110000X1X2X3X4X5X60X460311100200X5101-1201010*0X62011-100120102*-110000X43004-51-307.5

10、2X1101-12010-0X61002-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 )T2 分最优值为：z*=25。. 2 分五、求解运输问题。共计18 分解：(1)最小元素法：(也可以用其他方法，酌情给分)设Xj为由 Ai运往B的运量(i=1,2,3; j=1,2,3,4),列表如下：销地产地B1B2BsB4产量1252522052531530550销量152030351003分所以，基本的初始可行解为：.

11、X14 =25;X22=20;X24 =5；X31 =15;X33 =30;X34=5其余的Xij=o。.3分(2)求最优调运方案：精品文档5欢迎。下载1 会求检验数，检验解的最优性：1 仁 2;12=2;13=3;精品文档10欢迎下载21=1;23=5 ;32= - 1 .3分.2分销地产地B1B2B3B4产量12525215102531553050销 量152030351003 再次检验4 能够写出正确结论X24 =10X31 =15，X32 =5X33=30其余的Xij=0最少运费为：535 .1分。六、灵敏度分析。共计 8 分(1) (4 分)max -8/32/31/6 1/64C1

12、 5 ,6 10(2) (4 分)max200/375/310/3G min -2/34 C1C110 5 15b1min2/3240b110七、建动态规划模型。共计8 分解：(1)设阶段变量k表示年度，因此，阶段总数n=3。(2) 状态变量sk表示第k年度初拥有的完好机床台数，同时也是第 k-1完好机床数量。(3) 决策变量uk,表示第k年度中分配于生产产品p1 的机器台数。于是该年度中分配于生产产品p1 的机器台数.(4)状态转移方程为Sk10.35uk0.65( Skuk)(5)允许决策集合,在第 k 段为 uouj 0 UkSk(6) 目标函数。设gk(sk,uk)为第k年度的产量，则

13、gk(sk,uk) = 45uk+ 35(sk -uk),因此，目标函数为Rkgk(sk,uk)i k(7)条件最优目标函数递推方程。2 会求调整量进行调整：=5解为：Xl4=25；X22 =15年度末时的sk-uk便为精品文档11欢迎下载fk(Sk) max(Uk(Sk)ukUk令fk(sk)表示由第k年的状态sk出发，采取最优分配方案到第 3 年度结束这段时间 的产品产量，根据最优化原理有以下递推关系：45山35(SkuQfk 10.35山0.656 uQ(8).边界条件为f3 1(S3 1)0八、解决对策问题。共10 分(1 )益损矩阵如下表所示：3 分销售SS2S3S4订购500100

14、015002000A15001500150015001500A 10000300030003000A 15001500150045004500A 20003000030006000(2)悲观法：A ,订购 500 公斤。2 分(3). 后悔矩阵如下表所示： .3 分1111SS2S3S4最大后悔值A101500300045004500A15000150030003000A30001500015003000A45003000150004500按后悔值法商店应取决策为A 或 A，即订购 1000 公斤或 1500 公斤。2 分九、求网络计划图的各时间参数。（8分）/奁 8 AA52 t-精品文档12欢迎下载工序 代号工序 时间 最早开 工时间最早完 工时间最晚开 工时间最晚完 工时间机动 时间1-28080801-3707292精品文档13欢迎下载评分标准：能正确给各顶点标号并填表 . 4分2正确写出关键问题 .2分3正确画出关键线路. 2 分1-46