运筹学期末试卷(A)卷

1 福建农林大学考试试卷福建农林大学考试试卷 A 卷 卷 2010 2011 学年 第 1 学期 课程名称 运 筹 学 考试时间 专业 年级 班 学号 姓名 说明 答案可以写在试卷空白处 含试卷背面 题号一二三四五六七八九总得分 得分 评卷人签字复核人签字 得分一 填空题 每空 2 分 共 10 分 说明 空格长短不一定代表答案的长短 1 目标规划模型中 目标约束的正偏差变量和负偏差变量的乘积为 非负 2 在求极大化的线性规划问题中 有最优解的判别特征是 所有检验数非正且最优值为常数 第一阶段最优值为零 3 基变量的检验数变化后 最优单纯形表主体数据 中 tr x tr c 0 tttt bAz 和 不发生变化 ttt Bt bA 和 4 存贮论的确定性存贮模型中不含 随机 变量 5 最大流问题可以用 标号法 线性规划法等方法 求解 得分二 单项选择题 选择正确答案的字母填入括号 每小题 2 分 共 10 分 1 线性规划的基本解中 变量取 C 值 A 零 B 非零 C 非负 D 非正 2 2 增广链对应的流是 B A 零流 B 可行流 C 不可行流 D 非零流 3 线性规划单纯形法中 如果无约束 则以代替它 那么 D j x 0 jjjj xxxx A 都可能是基变量 B 都不可能是基变量 jj xx和 jj xx和 C 都不是基变量 D 中至多只有一个变量是基变 jj xx和 jj xx和 量 4 目标规划模型中要求尽可能接近目标值的目标函数是 A A B minZdd minZd C D minZd minZdd 5 网络计划中 FFij是不影响 B 下aij所具有的机动时间 A B j L j E C D i L i E 得分三 判断题 正确打 错误打 每小题 2 分 共 10 分 1 如果线性规划的原问题有无穷多最优解 则其对偶问题也一定具有无穷多最优解 2 如果线性规划的可行域非空有界 则其任可行域可以用全部基本可行解的凸组合表示 3 产销平衡运输问题的求解结果的一种可能是无可行解 4 动态规划解要求决策变量满足无后效性 3 5 网络计划的网络图中 总时差为零的工序构成的线路就是关键路线 得分四 问答题 每小题 5 分 共 20 分 1 闭回路的定义与应用 答 在产销平衡表中取偶数个点 若这些点满足 jpipjiji xxx 1 10 0 01 12 23 34 1 0 iijj iijj i pip jpj 或满足 01 12 23 34 1 0 jjii jjii j pjp ipi 则称这些点构成一条闭回路 在表上作业法中 闭回路用于计算检验数 方案调整和判断可行解是否基本可行解 2 单纯形法的求解过程 答 求解过程 确定一个可行域顶点 如果尚未求得所有的最优顶点 则在目标函数值不劣 化的前提下 寻找新顶点 直至求得所有的最优顶点或判定解无界为止 为保证求解过程的合理实现 又有 每个基本可行解对应可行域的一个顶点 待求解的 问题必须经过变换 保证其格式符合一定的要求 有可行解 规定每个基下模型的标准格式 在此基础上建立解的判别准则 3 目标规划模型目标约束的结构和特点 4 答 模型结构 11 1 1 min 1 2 1 2 01 2 01 2 LK llkklkk lk n kjjkkk j n ijji j j kk zPw dw d c xddgkK a xbimst xjn ddkK 式中 为第 个优先等级的优先因子 为优先等级个数 为第 k 个目标 l Pl 1 0 ll PP L k d 约束的负偏差变量 为第 k 个目标约束的正偏差变量 为目标约束个数 为下 k dK lk w l P 的权系数 为下的权系数 为第k个目标约束的决策值 为第 k 个 k d lk w l P k d j n j kjx c 1 k g 目标约束的目标值 其余系数同线性规划 模型特点 约束条件硬约束 含偏差变量非负约束 和目标约束两类 前者是必须绝对满足的约 束 后者是目标约束 它们是形成目标函数的约束基础 由于和优化方向的特别设置 使得寻优一开始就按第 1 个优先等级的目标函数在可 l P 行域上确定最优区域 后续的优先等级在前一个优先等级的最优区域上展开寻优 最后一个 优先等级的最优区域就是问题最优解 满意解 所在的区域 模型结构是线性的 每个优先等级都有自身的目标函数 因而可以在线性规划单纯形 法的基础上建立目标规划的单纯形法 4 灵敏度分析的任务 5 答 设为最优基 以为对应的规范标准型 t B tP 灵敏度分析的任务是以作为计算的起点模型 考虑模型单个参数或参数简单组合的 tP 变动 确定新解 或考虑维持最优解或最优基不变 确定相关参数的取值范围 得分五 第一小题 2 分 第二小题 5 分 第三小题 3 分 共 10 分 对 要求 P 1 写出 D 2 用单纯形法或对偶单纯形法确定或的最优解 P D 3 从或的最终表出发 据对偶理论直接确定或的解 P D D P P 12 2 12 12 max 15 10 0 zxx x stxx x x 1 1 D 12 2 12 12 min1510 1 1 0 wyy y styy y y 2 用单纯形法求解 cj 1 1 1 1 0 0 0 0 cBxBbx1 x2 x3 x4 0 0 0 0 x3 x4 1515 1010 0 0 1 1 1 1 0 0 1 1 0 0 1 1 1 1 1515 1010 0 0 z 0 01 1 1 1 0 0 0 0 6 cj 1 1 1 1 0 0 0 0 cBxBbx1 x2 x3 x4 0 0 1 1 x3 x1 1515 1010 0 0 1 1 1 1 0 0 1 1 0 0 1 1 1 1 1515 1010 1 1 z 10 100 0 0 0 0 0 1 1 cj 1 1 1 1 0 0 0 0 cBxBbx1 x2 x3 x4 0 0 1 1 x3 x2 5 5 1010 1 1 0 0 1 1 1 1 1 1 0 0 1 1 1 1 1515 1010 2 2 z 10 100 0 0 0 0 0 1 1 12 1 0 1 10 xxxz 3 2 2 1122 0 1 10 ss yy 得分六 对图 1 求网络图的最大流 共 10 分 7 vs vt v1 v2 v3 9 0 8 0 2 0 8 0 4 0 8 0 8 0 cij fij 图 1 解 1 取 用标号法确定如图 2 所示 由图 2 知 00 0 0fv f 0 见图 3 00100 011330 8 8 stt aaalvv fv f 1 f 用标号法确定如图 3 所示 由图 3 知 1 见图 4 11211 1221 8 16 stt aal vv fv f 2 f 用标号法确定如图 4 所示 由图 4 知 2 不存在 故 2 2 ff vs vt v1 v2 v3 0 9 0 8 0 2 0 8 0 4 0 8 0 8 0 ijij fc 图 2 vs 8 5 v1 8 5 v3 8 5 8 vs vt v1 v2 v3 0 9 8 8 0 2 8 8 0 4 0 8 8 8 1 ijij fc 图 3 vs 9 5 v2 8 5 vs vt v1 v2 v3 8 9 8 8 0 2 8 8 0 4 8 8 8 8 2 ijij fc 图 4 vs 1 5 v2 1 5 2 上述求解过程也可以标示在一个图上 如图 5 所示 9 vsvt v1 v2 v3 0 8 0 8 0 0 1 ij ijij ij f cf f 图 5 0 1 2 vs 1 2 5 v2 1 2 5 0 ijt tt ijijt t ijt a fa a vs 8 1 5 v1 8 1 5 v2 8 0 5 v3 8 1 5 vs 8 0 5 0 2 0 0 0 8 0 8 0 8 0 8 0 4 0 0 0 8 8 0 0 8 8 0 2 01 016 v fv f 得分七 计算题三 10 分 某工厂要对一种产品制定今后四个时期的生产计划 据 估 计今后四个时期内 市场对该产品的需求量如下表所示 假定该厂生产每批产品的固定成本为 5 千元 若不生产就为零 每单位产品成本为 2 千元 每个时期生产能力所允许的最大生产批量为不超过 6 个单位 每个期末库存的产品 每单位需付存贮费 1 千元 还假定开始和终了的库存量均为零 试问该厂应如何安排各个时 期的生产与库存 才能在满足市场需求的条件下 使总成本最小 时期 k 1234 需求量 dk 6341 解 动态规划求解 模型建立 10 设阶段变量k表示计划期的第k时期 因此 阶段总数n 4 状态变量sk表示第k时期初的库存量 同时也是第k 1时期末时的库存量 决策变量uk 表示第k时期的生产量 状态转移方程为 1kkkk ssud 阶段效应函数 1 0 521 1 2 6 6 kkkk kkkkkkkk k sudu v s uusudu u 递推方程 令fk sk 表示由第k时期的状态sk出发 采取最优生产存储方案到第 4 时期结束这段 时间的最优生产存储费用 根据最优化原理有以下递推关系 11 min 4 3 2 1 05 kkk kkkkk uDs kk v s ufsk fs k 边界条件 s1 0 s5 0 分阶段求解见下表 逆序分阶段求解 k u k k s 11 kkkkk sfusv k u kk sf 0 1 2 3 4 5 6 41 0 0 0 00 11 0 7 0 0 17 3 7 0 7 9 1 0 210 2 9 0 7 11 1 0 312 1 11 0 7 13 1 0 414 3 0 13 0 7 15 1 0 516 20 11 0 16 13 1 14 15 2 12 17 3 10 327 10 17 0 27 644 顺推得 1 4 0 6 3 50p 1 0 44f 再生产点求解 c j i i fj 1 c j i fi j i i j i j 1234000 117 10 1717111 2 11 20 17 1128222 3 13163 0 17 28 13 413 4 740 17 28 16 41 744343 11223344 6 3 4 15 0 xdxdxddx 12 得分八 对表 1 用动态规划方法确定最优策略 共 10 分 考虑一辆汽车三年的设备更新策略 开始时现有汽车的机龄为 2 年 取 1 其余 有关数据见下表 试制定三年中的设备更新策略 使三年内的净收入最大 年代期 前第一年第二年第三年 阶 段 1 2 31 2 32 3 3 机 龄 2 3 40 1 20 1 0 收 入 21 20 1822 21 2027 2530 运行费用 10 11 129 10 115 64 更新费用 38 39 4033 35 3731 3534 解 模型假设 计划期的第年对应第阶段 kk3 2 1k 代表第阶段开始时 设备更新决策及其实施前 设备的役龄 机龄 k sk 决策变量 k R u K 更新 不更新 状态转移方程 1 1 1 k k kk uR s suK 阶段效应函数 0 0 kkkk kkk kkkkk IOC suR vs u IsO suK 为第年从出发 子过程的最大净收入 kk sfk k sk 11 min 3 2 1 04 kkk kkkkk uDs kk v s ufsk fs k 14 2 0ss 13 逆序分阶段求解如下表 Kuk Ruk k k s 1 1 kkkkkk sfsOsI 1 0 0 1 kkkkk fsCOI kk sf k u 4 18 12 030 4 40 0 6 K 2 20 11 030 4 37 0 9 K 3 1 25 6 030 4 35 0 19 K 3 20 11 627 5 39 19 15 K 2 1 21 10 927 5 35 19 20 K 12 21 10 1522 9 38 20 26 K 顺序推得 1 3 2 pK K K 1 3 26f 得分九 10 分 下表是某厂原材料和产品规格的基础数据 要求建立一个线性规划 模 型 以确定净收入最大的产品方案 不求解 解 变量假设 产品规格要求 甲 乙 丙 原料成本 单价 元 kg 可用量 kg 原 材 料 A B C 90 50 60 20 60 50 3 00 2 00 1 00 2000 2500 2500 加工费 元 kg 0 50 0 40 0 30 售价 元 kg 3 60 2 85 2 25 14 123456789 147258369 123456789 max 3 1 2 45 3 0 11 12 10 550 451 451 050 050 95 z xxxxxxxxx xxxxxxxxx xxxxxxxxx 产品销售收入 原材料成本 1 95 2 约束条件 约束条件 产品产品 A A 规格要求 规格要求 1123 2123 3123 0 9 0 6 0 2 xxxx xxxx xxxx 产品产品 B B 规格要求 规格要求 4456 6456 0 5 0 6 xxxx xxxx 产品产品 C C 规格要求 规格要