2022年《运筹学》期末考试试卷A答案.docx

名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -优秀学习资料 欢迎下载运筹学试题样卷（一）题号一二三四五六七八九十总分得分一、判定题（共计 10 分,每道题 1 分,对的打,错的打 X）1. 无孤立点的图肯定是连通图；2. 对于线性规划的原问题和其对偶问题,如其中一个有最优解,另一个也肯定有最优解；3.假如一个线性规划问题有可行解,那么它必有最优解；j0对应的变量4对偶问题的对偶问题肯定是原问题；5用单纯形法求解标准形式（求最小值）的线性规划问题时,与都可以被选作换入变量；6如线性规划的原问题有无穷多个最优解时,其对偶问题也有无穷多个最优解；7. 度为 0 的点称为悬挂点；8. 表上作业法实质上就是求解运输问题的单纯形法；9. 一个图 G 是树的充分必要条件是边数最少的无孤立点的图；10.任何线性规划问题都存在且有唯独的对偶问题；二、建立下面问题的线性规划模型（8 分）某农场有 100 公顷土地及 15000 元资金可用于进展生产；农场劳动力情形为秋冬季 3500人日； 春夏季 4000 人日； 如劳动力本身用不了时可外出打工,春秋季收入为 25 元 / 人日,秋冬季收入为 20 元 / 人日；该农场种植三种作物：大豆、玉米、小麦,并饲养奶牛和鸡；种作物时不需要特地投资,而饲养每头奶牛需投资 800 元,每只鸡投资 3 元；养奶牛时每头需拨出 1.5 公顷土地种饲料,并占用人工秋冬季为 100 人日, 春夏季为 50人日,年净收入 900 元 / 每头奶牛；养鸡时不占用土地,需人工为每只鸡秋冬季 0.6人日,春夏季为 0.3 人日,年净收入 2 元 / 每只鸡；农场现有鸡舍答应最多养 1500 只鸡,牛栏答应最多养 200 头；三种作物每年需要的人工及收入情形如下表所示：大豆 玉米 麦子秋冬季需人日数 20 35 10 春夏季需人日数 50 75 40 年净收入 （元 /公顷）3000 4100 4600 试打算该农场的经营方案,使年净收入为最大；细心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 1 页,共 9 页 - - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -优秀学习资料欢迎下载x4,x5为三、已知下表为求解某目标函数为极大化线性规划问题的最终单纯形表,表中放松变量,问题的约束为形式（共 8 分）x 51xx 23xx 4x 35/2 0 1/2 1 1/2 x 15/2 1 1/2 0 1/6 1/3 cjzj0 0 1 写出原线性规划问题； （4 分）2 写出原问题的对偶问题；（3 分）B1、 B2、B3、B4,各产地的产量、各3 直接由上表写出对偶问题的最优解；（1 分）四、用单纯形法解以下线性规划问题（16 分）maxZ2x 1x2x3s. 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 分）某公司从三个产地A 1、A2、A 3 将物品运往四个销地销地的销量和各产地运往各销地每件物品的运费如表所示：问：应如何调运,可使得总运输费最小. B 3B 4产量销 地B 1B2产 地A 1A 210 8 5 6 7 25 2 7 6 25 A 39 3 4 8 50 销量15 20 30 35 100 六、灵敏度分析（共8 分）线性规划 max z = 10x1 + 6x2 + 4x3细心整理归纳 精选学习资料 s.t. x1 + x2 + x3 100 第 2 页,共 9 页 10x1 +4 x2 + 5 x3 600 2x1 +2 x2 + 6 x3 300 x1 , x2 , x3 0 - - - - - - - - - - - - - - - - - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -优秀学习资料 欢迎下载的最优单纯形表如下：6 x2 200/3 0 5/6 1 5/3 1/6 0 10 x1 100/3 1 1/6 0 -2/3 1/6 0 0 x6 100 0 4 0 -2 0 1 j 0 8/3 0 -10/3 2/3 0 1C 1在何范畴内变化,最优方案不变？4 分 2b1在什么范畴内变化,最优基不变？4 分 七、试建立一个动态规划模型；（共 8 分）某工厂购进 100 台机器, 预备生产 p1 , p2 两种产品； 如生产产品 p1 ,每台机器每年可收入 45 万元,损坏率为 65% ；如生产产品 p2 ,每台机器 每年可收入 35 万元,损坏率为 35% ；估量三年后将有新 产,使在三年内收入最多？的机器显现, 旧的机器将全部剔除；试问每年应如何支配生八、求解计策问题； （共 10 分）某种子商店期望订购一批种子；据已往体会, 种子的销售量可能为 500,1000,1500 或 2000 公斤；假定每公斤种子的订购价为 6 元,销售价为 9 元,剩余种子的处理价为每公斤 3 元；要求：（1）建立损益矩阵； （3 分）（2）用悲观法打算该商店应订购的种子数；（2 分）7 （5 分）（3）建立懊悔矩阵,并用懊悔值法打算商店应订购的种子数；九、求以下网络方案图的各时间参数并找出关键问题和关键路径；（8 分）2 5 5 8 3 3 9 1 6 4 4 7 细心整理归纳 精选学习资料 工序7 工序3 2 3 最早完6 最晚开8 机动 第 3 页,共 9 页 最晚完最早开代号时间工时间工时间工时间工时间时间1-2 8 1-3 7 - - - - - - - - - - - - - - - - - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -1-4 6 优秀学习资料欢迎下载2-4 3 V 1 到 V 6 的最短路；（6 分）V 4 2-5 5 3-4 2 3-6 3 4-5 3 4-6 7 4-7 4 5-7 9 6-7 8 十、用标号法求V 2 4 8 V 1 3 5 6 6 3 V 6 6 4 V 3 4 V 5 运筹学样卷（一）答案一、判定题；共计10 分,每道题1 分10 XXXX二、建线性规划模型；共计8 分（酌情扣分）细心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 4 页,共 9 页 - - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -解：用x 1,x2,x3优秀学习资料欢迎下载x 4, x 5分别表示奶牛和鸡的分别表示大豆、玉米、麦子的种植公顷数；饲养数；x 6,x 7 分别表示秋冬季和春夏季的劳动力（人日）数,就有max Z 3000 x 1 4100 x 2 4600 x 3 900 x 4 20 x 5 20 x 6 25 x 7x 1 x 2 x 3 1 . 5 x 4 100 土地限制 400 x 4 3 x 5 15000 资金限制 20 x 1 35 x 2 10 x 3 100 x 4 0 . 6 x 5 x 6 3500 劳动力限制 50 x 1 175 x 2 40 x 3 50 x 4 0 . 3 x 5 x 7 4000 劳动力限制 x 4 200 牛栏限制 x 5 1500 鸡舍限制 x j 0 j 1 , 2 , , 7 三、对偶问题；共计 8 分解：（）原线性规划问题：max z 6 x 1 2 x 2 10 x 3x 2 2 x 2 53 x 1 x 2 x 3 10x 1 , x 2 0； 4 分（）原问题的对偶规划问题为：min w 5 y 1 10 y 23 y 2 6y 1 y 2 22 y 1 y 2 10y 1 , y 2 0； 3 分（）对偶规划问题的最优解为：Y 4 , 2 T ； 1 分四、单纯形表求解线性规划；共计 16 分解：引入放松变量 x4、 x5、 x6,标准化得,max Z 2 x 1 x 2 x 3s. 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,0 3 分建初始单纯形表,进行迭代运算： 9分Xb b2 -1 1 0 0 0 细心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 5 页,共 9 页 - - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -C Bx1优秀学习资料欢迎下载x6x2x3x4x50 x4 60 3 1 1 1 0 0 20 0 x5 10 1 -1 2 0 1 0 10* 0 x6 20 1 1 -1 0 0 1 20 1 0 2* -1 1 0 0 0 0 x4 30 0 4 -5 1 -3 0 7.5 2 x1 10 1 -1 2 0 1 0 - 0 x6 10 0 2 -3 0 -1 1 5* 2 20 0 1* -3 0 -2 0 0 x4 10 0 0 1 1 -1 -2 2 x1 15 1 0 0.5 0 0.5 0.5 -1 x2 5 0 1 -1.5 0 -0.5 0.5 3 25 0 0 -1.5 0 -1.5 -0.5 由最优单纯形表可知,原线性规划的最优解为： 15 , 5 , 0 T 2 分最优值为：z*=25 ； 2 分五、求解运输问题；共计 18 分解：（1）最小元素法： （也可以用其他方法,酌情给分）产 量25 25 50 100 设 xij 为由 Ai 运往 Bj 的运量（ i=1,2,3; 列表如下：j=1,2,3,4 ）, 产 地销 地B 1B2B3B 41 25 2 20 5 3 15 30 5 销量15 20 30 35 3 分所以,基本的初始可行解为：x14 =25； x22=20 ； x24 =5 ；X31 =15； x33 =30； x34=5 其余的 xij=0 ；（2）求最优调运方案：1 会求检验数,检验解的最优性： 3 分 11=2； 12=2； 13=3；21=1； 23=5； 32= - 1 3 分2 会求调整量进行调整：=5 2 分 第 6 页,共 9 页 细心整理归纳 精选学习资料 - - - - - - - - - - - - - - - - - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -产 地销 地B 1B优秀学习资料欢迎下载2B3B 4产 量销1 量15 15 30 25 25 2 10 25 3 5 50 15 20 30 35 100 3 分3 再次检验 2 分4 能够写出正确结论解为： x14=25 ； x22 =15 ； x24 =10 x31 =15, x32 =5 x33=30 其余的 xij=0 ； 1 分最少运费为：535 1 分；六、灵敏度分析；共计8 分（1）（4 分）max8/3,2/3101cminc 110/35151/61/62/34c 15,64c 110（2）（4 分）max , 200 / 3 1b min 100 / 3 , 1005 / 3 2 / 3 240 b 1 10七、建动态规划模型；共计 8 分解： 1设阶段变量 k 表示年度,因此,阶段总数 n=3；2状态变量 sk 表示第 k 年度初拥有的完好机床台数,同时也是第 k1 年度末时的完好机床数量；3决策变量 uk,表示第 k 年度中安排于生产产品 p1 的机器台数；于是 sk uk 便为该年度中安排于生产产品 p1 的机器台数（4） 状态转移方程为s k10.35uk0 .65 s kuk0u ks k（5）答应决策集合,在第 k 段为 U k s k u kgksk,uk为第 k 年度的产量,就（6）目标函数；设gksk,uk = 45uk + 35skuk , 因此,目标函数为3R kg ks k,uk3 年度终止这段时间i k（ 7）条件最优目标函数递推方程；fks kmax u k U ku ks k令 fksk表示由第k 年的状态sk 动身,实行最优安排方案到第的产品产量,依据最优化原理有以下递推关系：细心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 7 页,共 9 页 - - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -45u k35s ku优秀学习资料35欢迎下载s kukkfk10.uk0.65（8）.边界条件为1f31s 30八、解决计策问题；共10 分26 第 8 页,共 9 页 （1）益损矩阵如下表所示： 3 分销 售S1 S2 S3 S4订 购500 1000 1500 2000 A1500 1500 1500 1500 1500 A21000 0 3000 3000 3000 A31500 1500 1500 4500 4500 A42000 3000 0 3000 6000 （2）悲观法： A 1 ,订购 500 公斤； 2 分（3）懊悔矩阵如下表所示： 3 分S1S2S3S4最大懊悔值A10 1500 3000 4500 4500 A21500 0 1500 3000 3000 A33000 1500 0 1500 3000 A44500 3000 1500 0 4500 按懊悔值法商店应取决策为A2或 A3 ,即订购 1000 公斤或 1500 公斤； 2 分九、求网络方案图的各时间参数；（8 分）80 2 8 5 14 5 14 00 1 8 6 3 11 3 4 9 260 7 4 0 7 7 3 2 11 7 6 8 3 9 180 18 工序工序最早开最早完最晚开最晚完机动代号时间工时间工时间工时间工时间时间1-2 8 0 8 0 8 0 1-3 7 0 7 2 9 2 1-4 6 0 6 5 11 6 2-4 3 8 11 8 11 0 2-5 5 8 13 9 14 1 3-4 2 7 9 9 11 2 细心整理归纳 精选学习资料 - - - - - - - - - - - - - - - - - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -3-6 3 7 优秀学习资料15 欢迎下载18 8 10 4-5 3 11 14 11 14 0 关键问题是： 4-6 7 11 18 11 18 0 4-7 4 11 15 22 26 11 5-7 9 14 23 17 26 3 6-7 8 18 26 18 26 0 ； 2； ； 6；6关键线路是：1 2 41 6 7 分评分标准：能正确给各顶点标号并填表.4正确写出关键问题. 2分V 4 9,v3 正确画出关键线路. 分十、用标号法求v1 到 v6 的最短路；（ 6 分）4,v1 V2 6 10,v2 5 4 7 0,0 V1 8 V3 2 3 V 5 1 V 6 6,v2 2 12,v5 14,v4 7 10,v4 （8,v1）11,v2 13,v3 最短路为： v1,v2,v3,v4,v5,v6 长度为： 12 正确标号： 4 分；正确写出结论：2 分 第 9 页,共 9 页 细心整理归纳 精选学习资料 - - - - - - - - - - - - - - - - - - - - - - - -