清华大学《运筹学教程》胡运权主编课后习题答案(第一章).ppt

1 第一章习题解答 1 1用图解法求解下列线性规划问题 并指出问题具有惟一最优解 无穷多最优解 无界解还是无可行解 sdadsd 2 sdadsd 3 sdadsd 4 1 2将下述线性规划问题化成标准形式 sdadsd 5 sdadsd 6 sdadsd 7 1 3对下述线性规划问题找出所有基解 指出哪些是基可行解 并确定最优解 sdadsd 8 sdadsd 所有基可行解中最优解为X 0 3 0 0 3 5 0 T和X 0 0 1 5 0 8 0 T 9 sdadsd 10 所有基可行解中最优解为X 0 1 2 2 0 T和X 0 0 1 1 T sdadsd 11 1 4分别用图解法和单纯形法求解下述线性规划问题 并对照指出单纯形表中的各基可行解对应图解法中可行域的哪一顶点 sdadsd 0点 A1点 A2点 所以最优解为X 1 3 2 0 0 T 12 sdadsd 13 sdadsd 14 sdadsd 15 sdadsd l 5上题 1 中 若目标函数变为maxZ cx1 dx2 讨论c d的值如何变化 使该问题可行域的每个顶点依次使目标函数达到最优 16 sdadsd 17 式中 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考虑下述线性规划问题 sdadsd 18 目标函数最优值的上界为 21 解 上界对应的模型如下 c b取大 a取小 sdadsd 19 目标函数最优值 下界 为 6 4 解 下界对应的模型如下 c b取小 a取大 sdadsd 20 l 7分别用单纯形法中的大M法和两阶段法求解下列线性规划问题 并指出属哪 类解 sdadsd 21 sdadsd 22 sdadsd 23 sdadsd 24 sdadsd 25 sdadsd 26 sdadsd 27 sdadsd 28 sdadsd 见下表 29 sdadsd 30 sdadsd 31 sdadsd 方法一 大M法引入人工变量x6和x7 线性规划问题变为 32 sdadsd 0 0 M 4M 1 7M 4 0 1 0 2 1 4 0 0 0 1 3 4 6 M 1 0 0 1 3 3 M M 0 0 1 4 0 1 0 1 3 2 4 0 7M 3 4 3 0 M 5M 3 1 3 0 1 3 1 0 5 3 0 3 0 4 3 0 1 5 3 0 2 M 1 3 0 0 1 3 1 1 4 1 0 6 5 9 5 0 0 3 M 33 sdadsd M 8 5 0 1 5 0 0 1 1 1 0 0 1 0 4 5 0 3 5 1 0 6 5 1 3 5 0 1 5 0 1 3 5 4 M 0 0 1 4 1 5 3 5 1 3 1 M 1 5 M 7 5 1 5 0 0 0 1 1 1 0 0 1 0 1 5 3 5 0 1 0 5 9 1 2 5 1 5 0 0 1 2 5 4 0 1 M 0 M 由于上表中所有检验数都小于等于零 且非基变量检验数都小于0 因此已经得到唯一最优解 最优解为 34 sdadsd 方法二 两阶段法 第一阶段 35 sdadsd 0 0 1 4 7 0 1 0 2 1 4 0 0 0 1 3 4 6 1 1 0 0 1 3 3 1 1 0 0 0 0 0 1 0 1 3 2 4 0 7 3 0 1 5 3 0 1 3 1 0 5 3 0 3 0 4 3 0 1 5 3 0 2 1 1 3 0 0 1 3 1 1 0 1 0 6 5 9 5 0 0 3 1 36 sdadsd 1 0 0 0 0 1 1 1 0 0 1 0 4 5 0 3 5 1 0 6 5 0 3 5 0 1 5 0 1 3 5 0 M 0 0 0 0 1 5 3 5 1 1 M 该模型最优解为X 3 5 6 5 0 1 0 0 T 其基变量不含人工变量 说明原问题的一个基可行解为X 3 5 6 5 0 1 T 转入第二阶段 37 sdadsd 0 1 5 0 0 1 1 0 0 1 0 0 3 5 1 0 6 5 1 0 1 5 0 1 3 5 4 0 0 1 4 3 1 5 0 0 0 1 1 0 0 1 0 3 5 0 1 0 5 9 1 1 5 0 0 1 2 5 4 由于上表中所有检验数都小于等于零 且非基变量检验数都小于0 因此已经得到唯一最优解 最优解为 1 38 sdadsd 39 sdadsd 40 sdadsd 41 sdadsd 42 sdadsd 43 1 8已知某线性规划问题的初始单纯形表和用单纯形法迭代后得到下面表格 试求括弧中未知数a l值 b 2 c 4 d 2 g 1 h 0 f 3 i 5 e 2 l 0 sdadsd 7 1 c b a 7 1 2a a 3 j 2 d b a j 2 3 5 k 1 b a k 3 2 44 sdadsd 45 1 9若X 1 X 2 均为某线性规划问题的最优解 证明在这两点连线上的所有点也是该问题的最优解 sdadsd 46 sdadsd 47 1 10线性规划问题maxZ CX AX b X 0 设X0为问题的最优解 若目标函数中用C 代替C后 问题的最优解变为X 求证 C C X X0 0 sdadsd 48 sdadsd 49 1 11考虑线性规划问题 模型中 为参数 要求 1 组成两个新的约束 i i ii ii ii 一2 i 根据 i ii 以x1 x2为基变量 列出初始单纯形表 sdadsd 50 解 sdadsd 51 2 在表中 假定 0 则 为何值时 x1 x2为问题的最优基变量 解 如果 0 则当3 a 0且a 4 0时 即3 a 4时 x1 x2为问题的最优基变量 3 在表中 假定 3 则 为何值时 x1 x2为问题的最优基 解 如果a 3 则当3 3 0且1 0时 即 1 1时 x1 x2为问题的最优基变量 sdadsd 52 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 sdadsd 53 1 13某饲养场饲养动物出售 设每头动物每天至少需700g蛋白质 30g矿物质 100mg维生素 现有五种饲料可供选用 各种饲料每kg营养成分含量及单价如下表所示 sdadsd 54 要求确定既满足动物生长的营养需要 又使费用最省的选用饲料的方案 建立这个问题的线性规划模型 不求解 sdadsd 55 1 14某医院护士值班班次 每班工作时间及各班所需护士数如下页表格所示 sdadsd 56 1 若护士上班后连续工作8h 该医院最少需多少名护士 以满足轮班需要 解 sdadsd 57 2 若除22 00上班的护士连续工作8h外 取消第6班 其他班次护士由医院排定上1 4班的其中两个班 则该医院又需多少名护士满足轮班需要 解 sdadsd 58 1 15 艘货轮分前 中 后三个舱位 它们的容积与最大允许载重量见后面的表格 现有3种货物待运 已知有关数据列于后面的表格 又为了航运安全 前 中 后舱的实际载重量大体保持各舱最大允许载重量的比例关系 具体要求 前 后舱分别与中舱之间载重量比例的偏差不超过15 前 后舱之间不超过10 问该货轮应装载A B C各多少件运费收入才最大 试建立这个问题的线性规划模型 sdadsd 59 解 设xij表示第i种商品在第j舱的数量 sdadsd 60 sdadsd 61 1 16时代服装公司生产 款新的时装 据预测今后6个月的需求量如下表所示 每件时装用工2h和10元原材料费 售价40元 该公司1月初有4名工人 每人每月可工作200h 月薪2000元 该公司可于任何 个月初新雇工人 但每雇1人需 次性额外支出1500元 也可辞退工人 但每辞退1人需补偿1000元 如当月生产数超过需求 可留到后面月份销售 但需付库存费每件每月5元 当供不应求时 短缺数不需补上 试帮助该公司决策 如何使6个月的总利润达到最大 sdadsd 62 解 设xi表示第i个月的工人数量 yi表示第i个月生产产品的数量 pi表示第i个月初新雇工人数量 di表示第i个月初解雇工人数量 ppi表示第i个月月末的库存量 ddi表示第i个月的短缺量 sdadsd 63 sdadsd 64 1 17童心玩具厂下一年度的现金流 万元 如下表所示 表中负号表示该月现金流出大于流人 为此该厂需借款 借款有两种方式 一是于上一年末借一年期贷款 一次得全部贷款额 从1月底起每月还息1 于12月归还本金和最后一次利息 二是得到短期贷款 每月初获得 于月底归还 月息1 5 当该厂有多余现