线性规划试题及参考答案

习题 一 人类资源分配问题 红旗商场为一中心百货商场 它对售货人员需求经过统计分析如表所示 为保证售货人员 的休息 每连续工作五天后 休息两天 问 如何安排售货人员作息 即可满足工作需要 又使配备售货人员数最少 答 设 x1 为星期一开始上班的人数 x2 为星期二开始上班的人数 x7 星期日开始 上班的人数 我们就可得到如下的数学模型 min x1 x2 x3 x4 x5 x6 x7 x3 x4 x5 x6 x7 28 x4 x5 x6 x7 x1 15 x5 x6 x7 x1 x2 24 x6 x7 x1 x2 x3 25 x7 x1 x2 x3 x4 19 x1 x2 x3 x4 x5 31 x2 x3 x4 x5 x6 28 x1 x2 x3 x4 x5 x6 x7 0 该问题的最优解为 x1 8 x2 0 x3 12 x4 0 x5 11 x6 5 x7 0 目标函数的最 小值为 36 Lingo 中的调试 min x1 x2 x3 x4 x5 x6 x7 x1 x2 x3 x4 x5 28 x2 x3 x4 x5 x6 15 x3 x4 x5 x6 x7 24 x4 x5 x6 x7 x1 25 x5 x6 x7 x1 x2 19 时间所需售货人员数 星期天28 星期一15 星期二24 星期三25 星期四19 星期五31 星期六28 x6 x7 x1 x2 x3 31 x7 x1 x2 x3 x4 28 二 市场应用 某公司投资 3 万元进行媒体广告宣传 希望吸引观众购买本公司产品 现有五种媒体供选 择 相关信息如下表 媒体被告知潜在顾客 数 人 次 广告费用 元 次 媒体最高使用次 数 每次宣传质量 日间电视100015001565 夜间电视200030001090 日周末新闻杂志25001000460 电台广播3001003020 对广告宣传 公司有下列要求 1 至少进行 10 次电视广告宣传 2 至少有 5 万名潜在观众 被告知 3 电视广告投入不超过 18000 元 问 如何进行媒体组合 才使广告质量最高 答 问题中媒体组合实际上就是要决定每种媒体的使用次数 设 x1 x2 x3 x4 x5 分别 表示表中日间电视 夜间电视 日报 周末新闻杂志 电台广播五种媒体的使用次数 该问题的线性规划模型为 max z 65x1 90 x2 40 x3 60 x4 20 x5 1500 x1 3000 x2 400 x3 1000 x4 100 x5 30000 1000 x1 2000 x2 1500 x3 2500 x4 300 x5 50000 x x2 10 1500 x1 3000 x2 18000 x1 15 x2 10 x3 25 x4 4 x5 30 x1 x2 x3 x4 x5 0 lingo 中的调试 三 金融计划 某公司有 68 名员工申请提前退休 公司必须在此后 8 年内对这些员工分期支付一定数量 现金 如表所示 年份12345678 现金支 付 千 元 430210222231240195225225 为完成这项现金支付任务 公司财务人员为此需制定一项投资计划 投资由政府债券和银 行储蓄组成 而政府债券又有三种类型可供选择 如表所示 债券价格 元 利率 到期年限 111508 8755 210005 5006 3135011 7507 三种债券票面价均为 1000 元 到期时按票面价进行支付 利率也以票面价为基准 银行储 蓄年利率为 4 问 如何安排投资计划 使公司以最小投资完成对退休员工现金支付任 务 答 设 F 为完成投资计划所需要的总资金额 x1 x2 x3 分别表示债券 1 2 3 的购 买量 yi i 1 8 表示第 i 年初银行储蓄的投资额 目标就是使满足要求的投资额最小 即 Minz F 综合有如下数学模型 Minz F F 1 15x1 1x2 1 35x3 y1 430 0 08875x1 0 055x2 0 1175x3 1 04y1 y2 210 0 08875x1 0 055x2 0 1175x3 1 04y2 y3 222 0 08875x1 0 055x2 0 1175x3 1 04y3 y4 231 0 08875x1 0 055x2 0 1175x3 1 04y4 y5 240 1 08875x1 0 055x2 0 1175x3 1 04y5 y6 195 1 055x2 0 1175x3 1 04y6 y7 225 1 1175x3 1 04y7 y8 255 x1 x2 x3 0 yi 0 i 1 8 lingo 中的调试 min F F 1 15 x1 x2 1 35 x3 y1 430 0 08875 x1 0 055 x2 0 1175 x3 1 04 y1 y2 210 0 08875 x1 0 055 x2 0 1175 x3 1 04 y2 y3 222 0 08875 x1 0 055 x2 0 1175 x3 1 04 y3 y4 231 0 08875 x1 0 055 x2 0 1175 x3 1 04 y4 y5 240 1 08875 x1 0 055 x2 0 1175 x3 1 04 y5 y6 195 1 055 x2 0 1175 x3 1 04 y6 y7 225 1 1175 x3 1 04 y7 y8 255 调试 Global optimal solution found Objective value 1728 794 Total solver iterations 11 Variable Value Reduced Cost F 1728 794 0 000000 X1 144 9881 0 000000 X2 187 8558 0 000000 X3 228 1879 0 000000 Y1 636 1479 0 000000 Y2 501 6057 0 000000 Y3 349 6818 0 000000 Y4 182 6809 0 000000 Y5 0 000000 0 6402516E 01 Y6 0 000000 0 1261360E 01 Y7 0 000000 0 2131823E 01 Y8 0 000000 0 6708394 Row Slack or Surplus Dual Price 1 1728 794 1 000000 2 0 000000 1 000000 3 0 000000 0 9615385 4 0 000000 0 9245562 5 0 000000 0 8889964 6 0 000000 0 8548042 7 0 000000 0 7603645 8 0 000000 0 7189912 9 0 000000 0 6708394 四 生产计划问题 某公司有 1 2 两种产品 预计其市场需求量分别为 3000 和 4000 件 该产品均由 A B C 三个部件组成 各个部件生产消耗工时和自制 外购成本如表所示 部件单位部件制造工时 分钟 自制成本 元 分钟 购买成本 元 小时 A1 00 500 60 产品 13 03 754 00B 产品 22 53 303 90 产品 11 00 600 65C 产品 21 50 750 78 由于生产能力有限 公司只有 200 个正常制造工时 50 个加班工时可用产品生产 每个加班 工时需额外支付 9 元 问 如何安排部件自制和外购数量 使总成本最低 答 设 xa xb1 xb2 xc1 xc2 分别表示 a 部件 用于产品 的 b 部件 用于产品 的 b 部件 用于产品 的 c 部件 用于产品 的 c 部件的自制量 相应地 设 ya yb1 yb2 yc1 yc2 分别为各部件的外购量 设 y0 为加班工时数 目标是使总成本最小 即 Min z 0 5xa 0 6ya 3 75xb1 4yb1 3 3xb2 3 9yb2 0 6xc1 0 65yc1 0 75 xc2 0 78yc2 9y0 因此 该问题的数学模型为 Min z 0 5xa 0 6ya 3 75xb1 4yb1 3 3xb2 3 9yb2 0 6xc1 0 65yc1 0 75 xc2 0 78yc2 9y0 xa ya 7000 xb1 yb1 3000 xb2 yb2 2000 xc1 yc1 3000 xc2 yc2 2000 y0 50 xa 3xb1 2 5xb2 xc1 1 5xc2 60 y0 12000 xa xb1 xb2 xc1 xc2 yb1 yb2 yc1 yc2 y0 0 lingo 中的调试 min 0 5 xa 0 6 ya 3 75 xb1 4 yb1 3 3 xb2 3 9 yb2 0 6 xc1 0 65 yc1 0 75 xc2 0 78 yc2 9 y0 xa ya 7000 xb1 yb1 3000 xb2 yb2 4000 xc1 yc1 3000 xc2 yc2 4000 y0 50 xa 3 xb1 2 5 xb2 xc1 1 5 xc2100 2 x3 2 x4 x5 100 3 x1 x2 2 x3 3 x5 100 测试 Global optimal solution found Objective value 90 00000 Total solver iterations 4 Variable Value Reduced Cost X1 30 00000