清华大学运筹学教程胡运权主编课后习题答案.ppt

1 同样适合第三版黄皮版 运筹学教程 第二版 习题解答 安徽大学管理学院洪文 3 第一章习题解答 1 1用图解法求解下列线性规划问题 并指出问题具有惟一最优解 无穷多最优解 无界解还是无可行解 4 第一章习题解答 5 第一章习题解答 6 第一章习题解答 1 2将下述线性规划问题化成标准形式 7 第一章习题解答 8 第一章习题解答 9 第一章习题解答 1 3对下述线性规划问题找出所有基解 指出哪些是基可行解 并确定最优解 10 第一章习题解答 11 第一章习题解答 12 第一章习题解答 1 4分别用图解法和单纯形法求解下述线性规划问题 并对照指出单纯形表中的各基可行解对应图解法中可行域的哪一顶点 13 第一章习题解答 14 第一章习题解答 l 5上题 1 中 若目标函数变为maxZ cx1 dx2 讨论c d的值如何变化 使该问题可行域的每个顶点依次使目标函数达到最优 解 得到最终单纯形表如下 15 第一章习题解答 当c d在3 10到5 2之间时最优解为图中的A点 当c d大于5 2且c大于等于0时最优解为图中的B点 当c d小于3 10且d大于0时最优解为图中的C点 当c d大于5 2且c小于等于0时或当c d小于3 10且d小于0时最优解为图中的原点 16 第一章习题解答 式中 1 c1 3 4 c2 6 1 a11 3 2 a12 5 8 b1 12 2 a21 5 4 a22 6 10 b2 14 试确定目标函数最优值的下界和上界 l 6考虑下述线性规划问题 17 第一章习题解答 最优值 上界 为 21 解 上界对应的模型如下 c b取大 a取小 18 第一章习题解答 最优值 下界 为 6 4 解 下界对应的模型如下 c b取小 a取大 19 第一章习题解答 l 7分别用单纯形法中的大M法和两阶段法求解下列线性规划问题 并指出属哪 类解 20 第一章习题解答 21 第一章习题解答 22 第一章习题解答 23 第一章习题解答 1 8已知某线性规划问题的初始单纯形表和用单纯形法迭代后得到下面表格 试求括弧中未知数a l值 b 2 c 4 d 2 g 1 h 0 f 3 i 5 e 2 l 0 a 3 j 5 k 1 5 24 第一章习题解答 1 9若X 1 X 2 均为某线性规划问题的最优解 证明在这两点连线上的所有点也是该问题的最优解 25 第一章习题解答 1 10线性规划问题maxZ CX AX b X 0 设X0为问题的最优解 若目标函数中用C 代替C后 问题的最优解变为X 求证 C C X X0 0 26 第一章习题解答 1 11考虑线性规划问题 模型中 为参数 要求 1 组成两个新的约束 i i ii ii ii 一2 i 根据 i ii 以x1 x2为基变量 列出初始单纯形表 27 第一章习题解答 28 第一章习题解答 2 在表中 假定 0 则 为何值时 x1 x2为问题的最优基变量 解 如果 0 则当3 a 4时 x1 x2为问题的最优基变量 3 在表中 假定 3 则 为何值时 x1 x2为问题的最优基 解 如果a 3 则当 1 1时 x1 x2为问题的最优基变量 29 第一章习题解答 1 12线性规划问题maxZ CX AX b X 0 如X 是该问题的最优解 又 0为某一常数 分别讨论下列情况时最优解的变化 1 目标函数变为maxZ CX 2 目标函数变为maxZ C X 3 目标函数变为maxZ C X 约束条件变为AX b 解 1 最优解不变 2 C为常数时最优解不变 否则可能发生变化 3 最优解变为 X 30 第一章习题解答 1 13某饲养场饲养动物出售 设每头动物每天至少需700g蛋白质 30g矿物质 100mg维生素 现有五种饲料可供选用 各种饲料每kg营养成分含量及单价如下表所示 31 第一章习题解答 要求确定既满足动物生长的营养需要 又使费用最省的选用饲料的方案 建立这个问题的线性规划模型 不求解 32 第一章习题解答 1 14某医院护士值班班次 每班工作时间及各班所需护士数如下页表格所示 33 第一章习题解答 1 若护士上班后连续工作8h 该医院最少需多少名护士 以满足轮班需要 34 第一章习题解答 2 若除22 00上班的护士连续工作8h外 取消第6班 其他班次护士由医院排定上1 4班的其中两个班 则该医院又需多少名护士满足轮班需要 解 第5班一定要30个人 35 第一章习题解答 36 第一章习题解答 1 15 艘货轮分前 中 后三个舱位 它们的容积与最大允许载重量见后面的表格 现有3种货物待运 已知有关数据列于后面的表格 又为了航运安全 前 中 后舱的实际载重量大体保持各舱最大允许载重量的比例关系 具体要求 前 后舱分别与中舱之间载重量比例的偏差不超过15 前 后舱之间不超过10 问该货轮应装载A B C各多少件运费收入才最大 试建立这个问题的线性规划模型 37 第一章习题解答 38 第一章习题解答 MAX 1000 X 1 1 X 1 2 X 1 3 700 X 2 1 X 2 2 X 2 3 600 X 3 1 X 3 2 X 3 3 SUBJECTTOX i j 表示第商品i在舱j的装载量 i j 1 2 3商品数量约束 1 X 1 1 X 1 2 X 1 3 6002 X 2 1 X 2 2 X 2 3 10003 X 3 1 X 3 2 X 3 3 800 39 第一章习题解答 商品容积约束 4 10X 1 1 5X 2 1 7X 3 1 40005 10X 1 2 5X 2 2 7X 3 2 54006 10X 1 3 5X 2 3 7X 3 3 1500最大载重量约束 7 8X 1 1 6X 2 1 5X 3 1 20008 8X 1 2 6X 2 2 5X 3 2 30009 8X 1 3 6X 2 3 5X 3 3 1500 40 第一章习题解答 重量比例偏差约束 10 8X 1 1 6X 2 1 5X 3 1 2 3 1 0 15 8X 1 2 6X 2 2 5X 3 2 12 8X 1 3 6X 2 3 5X 3 3 1 2 1 0 15 8X 1 2 6X 2 2 5X 3 2 14 8X 1 3 6X 2 3 5X 3 3 3 4 1 0 1 8X 1 1 6X 2 1 5X 3 1 41 第一章习题解答 1 16某厂生产I 两种食品 现有50名熟练工人 每名熟练工人每h可生产食品110kg或食品 6kg 由于需求量将不断增长 见下页表格 该厂计划到第8周末前培训出50名新工人 组织两班生产 已知一名工人每周工作40h 一名熟练工人用2周时间可培训出不多于3名新工人 培训期间熟练工人和被培训人员均不参加生产 熟练工人每周工资360元 新工人培训期间工资每周120元 新工人培训结束后工作每周工资240元 且生产效率同熟练工人 培训过渡期 工厂将安排部分熟练工人加班 加班1h另加付12元 又生产食品不能满足订货需求 推迟交货的赔偿费分别为 食品I为0 50元 kg 周 食品 为0 60元 kg 周 工厂应如何全面安排 使各项费用总和最小 试建立线性规划模型 42 第一章习题解答 设x i y i 表示从事两个产品生产的人数 xx i yy i 表示从事生产两个产品的加班小时数 f1 i f2 i 表示两个产品推迟交货的数量 r1 i r2 i 表示两个产品的需求数量 w i n i 分别表示开始从事培训工作的人数和新接受培训的工人人数 43 第一章习题解答 MIN 360X i 360Y i 360W i 12XX i 12yy i 0 5 f1 i 0 6 f2 i 120 120 n i 240 7 i n i n i nx i ny i N 8 0 3W i N i 0XX i 1000YY i 1000 44 第一章习题解答 400 X i 10 XX i 116000240 y i 6 yy i 79200400 x 1 10 xx 1 f1 1 10000 400 x 1 x 2 10 xx 1 xx 2 f1 2 20000 for a i i ge 3 and i le s 400 x 1 400 x 2 10 xx 1 10 xx 2 sum a j j le i and j gt 2 400 x j nx j 2 10 xx j f1 i sum a j j le i r1 j f1 s 0 45 第一章习题解答 240 y 1 6 yy 1 f2 1 6000 240 y 1 y 2 6 yy 1 yy 2 f2 2 13200 for a i i ge 3 and i le s 240 y 1 240 y 2 6 yy 1 6 yy 2 sum a j j le i and j gt 2 240 y j ny j 2 6 yy j f2 i sum a j j le i r2 j f2 s 0 46 第一章习题解答 x 1 y 1 w 1 50 x 2 y 2 w 1 w 2 50 for a i i gt 2 x i y i w i 1 w i 50 sum a i i le s n i 50 for a i gin x i for a i gin y i for a i gin w i for a i gin n i 47 第一章习题解答 1 17时代服装公司生产 款新的时装 据预测今后6个月的需求量如下表所示 每件时装用工2h和10元原材料费 售价40元 该公司1月初有4名工人 每人每月可工作200h 月薪2000元 该公司可于任何 个月初新雇工人 但每雇1人需 次性额外支出1500元 也可辞退工人 但每辞退1人需补偿1000元 如当月生产数超过需求 可留到后面月份销售 但需付库存费每件每月5元 当供不应求时 短缺数不需补上 试帮助该公司决策 如何使6个月的总利润达到最大 48 第一章习题解答 max 30 y1 y2 y3 y4 y5 y6 1500 p1 p2 p3 p4 p5 p6 1000 d1 d2 d3 d4 d5 d6 5 pp1 pp2 pp3 pp4 pp5 pp6 2000 x1 x2 x3 x4 x5 x6 1000 x6 x0 4 x表示工人人数 y表示产品产量 p表示新工人人数d表示辞退工人人数p1 d1 x1 x0 p2 d2 x2 x1 p3 d3 x3 x2 p4 d4 x4 x3 p5 d5 x5 x4 p6 d6 x6 x5 49 第一章习题解答 pp0 0 pp表示库存量 dd表示缺损额pp1 dd1 y1 pp0 500 pp2 dd2 y2 pp1 600 pp3 dd3 y3 pp2 300 pp4 dd4 y4 pp3 400 pp5 dd5 y5 pp4 500 pp6 dd6 y6 pp5 800 生产能力约束 y1 100 x1 y2 100 x2 y3 100 x3 y4 100 x4 y5 100 x5 y6 100 x6 总产量约束 y1 y2 y3 y4 y5 y6 3100 gin y1 gin y2 gin y3 gin y4 gin y5 gin y6 gin x1 gin x2 gin x3 gin x4 gin x5 gin x6 50 第一章习题解答 1 18童心玩具厂下一年度的现金流 万元 如下表所示 表中负号表示该月现金流出大于流人 为此该厂需借款 借款有两种方式 一是于上一年末借一年期贷款 一次得全部贷款额 从1月底起每月还息1 于12月归还本金和最后一次利息 二是得到短期贷款 每月初获得 于月底归还 月息1 5 当该厂有多余现金时 可短期存款 月初存人 月末取出 月息0 4 问该厂应如何进行存贷款操作 既能弥补可能出现的负现金流 又可使年末现金总量为最大 51 第一章习题解答 MAX 1 004Z 12 1 01y 1 015W 12 SUBJECTTO1 Y Z 1 W 1 122 01Y 1 004Z 1 1015W 1 Z 2 W 2 103 01Y 1 004Z 2 1015W 2 Z 3 W 3 84 01Y 1 004Z 3 1015W 3 Z 4 W 4 105 01Y 1 004Z