第4章--数学规划模型-姜启源

第第 4 4 章章 数学规划模型数学规划模型 在上一章中我们看到 建立优化模型要确定优化的目标和寻求的决策 用表示决决x 策变量 策变量 表示目标函数目标函数 实际问题一般对决策变量的取值范围有限制 不妨记作 xfx 称为可行域可行域 优化问题的数学模型可表示为x xxfMaxMin 或 在第 3 章 x 通常是 1 维或 2 维变量 通常是 1 维或 2 维的非负域 实际中的优化问题通常有多个决策变量 用维向量表示 目n T n xxxx 21 标函数是多元函数 可行域 比较复杂 常用一组不等式 也可以有等式 xf 0 1 2 来界定 称为约束条件约束条件 一般地 这类模型可表述成如下形式 xgiim zMin x xf s t xgimi 2 1 0 这里的 s t subject to 是 受约束于 的意思 显然 上述模型属于多元函数的条件极值问题的范围 然而许多实际问题归结出的 这种形式的优化模型 其决策变量个数和约束条件个数一般较大 并且最优解往往nm 在可行域的边界上取得 这样就不能简单地用微分法求解 数学规划是解决这类问题的 有效方法 需要指出的是 本章无意涉及数学规划 或运筹学 的具体计算方法 仍然着重于 从数学建模的角度 介绍如何建立若干实际优化问题的模型 并且在用现成的数学软件 求解后 对结果作一些分析 4 1 奶制品的生产和销售 企业内部的生产计划有各种不同的情况 从空间层次来看 在工厂级要根据外部需 求和内部设备 人力 原料等条件 以最大利润为目标制订产品的生产计划 在车间级 则要根据产品生产计划 工艺流程 资源约束及费用参数等 以最小成本为目标制订生 产批量计划 从时间层次看 若在短时间内认为外部需求和内部资源等不随时间变化 可制订单阶段生产计划 否则就要制订多阶段生产计划 本节选择几个单阶段生产计划的实例 说明如何建立这类问题的数学规划模型 并 利用软件求解的输出对结果作一些分析 例例 1 加工奶制品的生产计划加工奶制品的生产计划 问题问题 一奶制品加工厂用牛奶生产两种奶制品 1 桶牛奶可以在设备甲上用 21 A A 12 小时加工成 3 公斤 或者在设备乙上用 8 小时加工成 4 公斤 根据市场需求 1 A 2 A 生产的 全部能售出 且每公斤获利 24 元 每公斤获利 16 元 现在加工厂 1 A 2 A 1 A 2 A 每天得到 50 桶牛奶的供应 每天正式工人总的劳动时间为 480 小时 并且设备甲每天至 多能加工 100 公斤 设备乙的加工能力没有限制 试为该场制订一个生产计划 使每 1 A 天获利最大 并进一步讨论以下 3 个附加问题 1 若用 35 元可以买到 1 桶牛奶 应否作这项投资 若投资 每天最多购买多少桶牛 奶 2 若可以聘用临时工人以增加劳动时间 付给临时工人的工资最多是每小时几元 3 由于市场需求的变化 每公斤的获利增加到 30 元 应否改变生产计划 1 A 问题分析问题分析 这个优化问题的目标是使每天获利最大 要作的决策是生产计划 即每 天用多少桶牛奶生产 用多少桶牛奶生产 也可以是每天生产多少公斤 多少 1 A 2 A 1 A 公斤 决策受到 3 个条件的限制 原料 牛奶 供应 劳动时间 设备甲的加工能 2 A 力 按题目所给 将决策变量 目标函数和约束条件用数学符号及式子表示出来 就可 得到下面的模型 基本模型基本模型 决策变量 决策变量 设每天用桶牛奶生产 用桶牛奶生产 1 x 1 A 2 x 2 A 目标函数 目标函数 设每天获利为元 桶牛奶可生产 3公斤 获利 24 3 桶z 1 x 1 x 1 A 1 x 2 x 牛奶可生产 4公斤 获利 16 4 故 2 x 2 A 2 x 21 6472xxz 约束条件 约束条件 原料供应原料供应 生产 的原料 牛奶 总量不得超过每天的供应 即 50 1 A 2 A 21 xx 桶 劳动时间劳动时间 生产 的总加工时间不得超过每天正式工人总的劳动时间 即 1 A 2 A 480 小时 21 812xx 设备能力设备能力 的产量不得超过设备甲每天的加工能力 即 100 1 A 1 3x 非负约束非负约束 均不能为负值 即 0 0 1 x 2 x 1 x 2 x 综上可得 1 Max 21 6472xxz s t 50 2 21 xx 480 3 21 812xx 100 4 1 3x 0 0 5 1 x 2 x 这就是该问题的基本模型 由于目标函数和约束条件对于决策变量而言都是线性的 所 以称为线性规划线性规划 Linear Programming 简记作 LP 模型分析与假设模型分析与假设 从本章下面的实例可以看到 许多实际的优化问题的数学模型都是线性规划 特别 是在像生产计划这样的经济管理领域 这不是偶然的 让我们分析一下线性规划具有哪 些特征 或者说 实际问题具有什么性质 其模型才是线性规划 比例性比例性 每个决策变量对目标函数的 贡献 与该决策变量的取值成正比 每个 决策变量对每个约束条件右端项的 贡献 与该决策变量的取值成正比 可加性可加性 各个决策变量对目标函数的 贡献 与其它决策变量的取值无关 各个 决策变量对每个约束条件右端项的 贡献 与其它变量的取值无关 连续性连续性 每个决策变量的取值是连续的 比例性和可加性保证了目标函数和约束条件对于决策变量的线性性 连续性则允许 得到决策变量的实数最优解 对于本例 能建立上面的线性规划模型 实际上是事先作了如下的假设 1 两种奶制品每公斤的获利是与它们各自产量无关的常数 每桶牛奶加工 1 A 2 A A1 A2的数量和所需的时间是与它们各自的产量无关的常数 2 每公斤的获利是与它们相互间产量无关的常数 每桶牛奶加工出 1 A 2 A 1 A 的数量 2 A 和所需的时间是与它们相互间产量无关的常数 3 加工 的牛奶的桶数可以是任意实数 1 A 2 A 这 3 条假设恰好保证了上面的 3 条性质 当然 在现实生活中这些假设只是近似成 立 的 比如 的产量很大时 自然会使它们每公斤的获利有所减少 1 A 2 A 由于这些假设对于书中给出的 经过简化的实际问题是如此明显地成立 本章下面 的例题就不再一一列出类似的假设了 不过 读者在打算用线性规划模型解决现实生活 中实际问题时 应该考虑上面 3 条性质是否近似的满足 模型求解模型求解 图解法图解法 这个线性规划模型的决策变量为 2 维 用图解法既简单 又便于直观地把 握线性规划的基本性质 将约束条件 2 5 中的不等号改为等号 可知它们是平面上的 5 条直线 21x Ox 依次记为 L1 L5 如图 1 其中 L4 L5分别是轴和轴 并且不难判断 2 5 2 x 2 x 式界定的可行域是 5 条直线上的线段所围成的 5 边形 OABCD 容易算出 5 个顶点的坐 标为 0 0 0 50 20 30 100 3 10 100 3 0 OABCD 目标函数 1 中的取不同数值时 在图 1 中表示一组平行直线 虚线 称等值z 线族 如是过点的直线 是过点的直线 是过点的直0 zO2400 zD3040 zC 线 可以看出 当这族平行线向右上方移动到过点时 达到最大值 B3360 z 所以点的坐标 20 30 即为最优解 B30 20 21 xx 2 x A L1 B L4 L2 L3 C L5 OD 1 x z 0 z 2 400 z 3 360 图 1 模型的图解法 我们直观地看到 由于目标函数和约束条件都是线性函数 在 2 维情形 可行域为 直线段围成的凸多边形 目标函数的等值线都为直线 于是最优解一定在凸多边行的某 个顶点取得 推广到维情形 可以猜想 最优解会在约束条件所界定的一个凸多面体 可行域 n 的某个顶点取得 线性规划的理论告诉我们 这个猜想是正确的 软件实现软件实现 求解线性规划有不少现成的数学软件 比如用 LINDO 软件就可以很方便 地实现 在 LINDO6 1 版本下打开一个新文件 像书写模型 1 5 一样 直接输入 max 72x1 64x2 st 2 x1 x2 50 3 12x1 8x2 480 4 3x1 100 end 注注 LINDO 中已规定所有决策变量均为非负 故 5 式不必输入 乘号省略 式中 不能有括号 右端不能有数学符号 模型中符号 用 形式输入 它们与 等效 输入文件中第 1 行为目标函数 2 3 4 是为了标示各约束条件 便于 从输出结果中查找相应信息 程序最后以 end 结束 将文件存储并命名后 选择菜单 Solve 并对提示 DO RANGE SENSITIVITY ANALYSIS 灵敏性分析 回答 是 即可得到如下输出 LP OPTIMUM FOUND AT STEP 2 OBJECTIVE FUNCTION VALUE 1 3360 000 VARIABLE VALUE REDUCED COST X1 20 000000 0 000000 X2 30 000000 0 000000 ROW SLACK OR SURPLUS DUAL PRICES 2 0 000000 48 000000 3 0 000000 2 000000 4 40 000000 0 000000 NO ITERATIONS 2 RANGES IN WHICH THE BASIS IS UNCHANGED OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 72 000000 24 000000 8 000000 X2 64 000000 8 000000 16 000000 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 50 000000 10 000000 6 666667 3 480 000000 53 333332 80 000000 4 100 000000 INFINITY 40 000000 上面结果的第 3 5 6 行明确的告诉我们 这个线性规划的最优解为 最优值为 即用 20 桶牛奶生产 30 桶牛奶生产 可获30 20 21 xx3360 z 1 A 2 A 最大利润 3360 元 注注 若对提示 DO RANGE SENSITIVITY ANALYSIS 回答 否 得到的是上 面结果的前 11 行 结果分析结果分析 上面的输出中除了告诉我们问题的最优解和最优值以外 还有许多对分析结果有用 的信息 下面结合题目中提出的 3 个附加问题 并利用图解法的直观给予说明 1 3 个约束条件的右端不妨看作 3 种 资源 原料 劳动时间 设备甲的加工 能力 输出第 7 10 行 SLACK OR SURPPLUS 给出这 3 种资源在最优解下是否有剩余 2 原料 3 劳动时间的剩余均为零 4 设备甲尚余 40 公斤加工能力 这与图解法的 如下结果一致 最优解在点 图 1 中约束条件 2 3 所定义的直线和的交点 取B 1 L 2 L 得 表明原料 劳动时间已用完 而设备甲的能力有余 一般称 资源 剩余为零的约 束为紧约束 有效约束 紧约束 有效约束 2 目标函数可以看作 效益 成为紧约束的 资源 一旦增加 效益 必然跟 着增加 输出第 7 10 行 DUAL PRICES 给出 3 种资源在最优解下 资源 增加 1 个 单位时 效益 的增量 2 原料增加 1 个单位 1 桶牛奶 时利润增长 48 元 3 劳动 时间增加 1 个单位 1 小时 时利润增长 2 元 而增加非紧约束 4 设备甲的能力显然不 会使利润增长 这里 效益 的增量可以看作 资源 的潜在价值 经济学上称为影子影子 价格价格 即 1 桶牛奶的影子价格为 48 元 1 小时劳动的影子价格为 2 元 设备甲的影子价 格为零 读者可以用直接求解的办法验证上面的结论 即将输入文件中原料约束 2 右端的 50 改为 51 看看得到的最优值 利润 是否恰好增长 48 元 用影子价格的概念很容易回答附加问题 1 用 35 元可以买到 1 桶牛奶 低于 1 桶 牛奶的影子价格 当然应该作这项投资 回答附加问题 2 聘用临时工人以增加劳动时 间 付给的工资低于劳动时间的影子价格才可以增加利润 所以工资最多是每小时 2 元 3 目标函数的系数发生变化时 假定约束条件不变 最优解和最优值会改变吗 这个问题不能简单的回答 从图 1 看 目标函数的系数决定了等值线族的斜率 原题中 该斜率 取绝对值 下同 为 72 64 9 8 介于直线的斜率 1 与斜率 4 3 之间 最优 1 L 2 L 解自然在和的交点取得 并且 只要目标函数系数的变化使得等值线族的斜率仍 1 L 2 LB 然在 1 4 3 范围内 这个最优解就不会改变 而当目标函数系数的变化使得等值线族 的斜率小于 1 时 最优解将在点取得 大于 4 3 时 最优解将在点取得 AC 上面输出的第 13 17 行 CURRENT COEF 的 ALLOEABLE INCREASE 和 ALLOW ABLE DECREASE 给出了最优解不变条件下目标函数系数的允许变化范围 的系数为 72 8 72 24 即 64 96 的系数为 64 16 64 8 即 1 x 2 x 48 72 注意 系数的允许范围需要系数 64 不变 反之亦然 1 x 2 x 用这个结果很容易回答附加问题 3 若每公斤的获利增加到 30 元 则系数变 1 A 1 x 为 30 3 90 在允许范围内 所以不应改变计划 4 对 资源 的影子价格作进一步的分析 从图 1 看 随着原料 牛奶 的增加 直线向右上方平移 与的交点 它仍是最优解 向点靠近 在这个过程中 1 L 1 L 2 LBA 每增加 1 桶牛奶利润增加 48 元 影子价格 但是 当点与点重合后再增加牛奶就BA 不可能使利润增长了 这就是说 影子价格的作用 即在最优解下 资源 增加 1 个单 位时 效益 的增量 是有限制的 上面输出的第 18 23 行 CURRENT RHS 的 ALLOWABLE INCREASE 和 ALLOWABLE DECREASE 给出了影子价格有意 义条件下约束右端的限制范围 2 原料最多增加 10 桶牛奶 3 劳动时间最多增加 53 个小时 现在可以回答附加问题 1 的第 2 问 虽然应该批准用 35 元买一桶牛奶的投资 但 每天最多购买 10 桶牛奶 顺便指出 可以用低于每小时 2 元的工资聘用临时工人以增加 劳动时间 但最多增加 53 小时 评注评注 本例在产品利润 加工时间等参数均可设为常数的情况下 建立了线性规划 模型 线性规划模型的三要素是 决策变量 目标函数和约束条件 线性规划模型可以 方便地用 LINDO 软件求解 得到内容丰富的输出 利用其中的影子价格和灵敏性分析 可对模型结果作进一步的研究 它们对实际问题常常是十分有益的 例例 2 奶制品的生产销售计划奶制品的生产销售计划 问题问题 例 1 给出的 两种奶制品的生产条件 利润 及工厂的 资源 限制 1 A 2 A 全部不变 为增加工厂的获利 开发了奶制品的深加工技术 用 2 小时和 3 元加工费 可将 1 公斤加工成 0 8 公斤高级奶制品 也可将 1 公斤加工成 0 75 公斤高级奶 1 A 1 B 2 A 制品 每公斤能获利 44 元 每公斤能获利 32 元 试为该厂制订一个生产销售 2 B 1 B 2 B 计划 使每天的净利润最大 并讨论以下问题 1 投资 30 元可以增加供应 1 桶牛奶 投资 3 元可以增加 1 小时劳动时间 应否作 这些投资 若每天资 150 元 可赚回多少 2 每公斤高级奶制品 的获利经常有 10 的波动 对制订的生产销售计划有 1 B 2 B 无影响 若每公斤的获利下降 10 计划应该变化吗 1 B 问题分析问题分析 要求制订生产销售计划 决策变量可以像例 1 那样 取作每天用多少桶 牛奶生产 再添上用多少公斤加工 用多少公斤加工 但是问题要 1 A 2 A 1 A 1 B 2 A 2 B 分析 的获利对生产销售计划的影响 所以决策变量取作 每天 1 B 2 B 1 A 2 A 1 B 2 B 的销售量更方便 目标函数是工厂每天的净利润 的获利之和扣除深加 1 A 2 A 1 B 2 B 工费用 约束条件基本不变 只是要添上 深加工时间的约束 在例 1 类似的假定 1 A 2 A 下用线性规划模型解决这个问题 基本模型基本模型 决策变量决策变量 设每天销售公斤 公斤 公斤 公斤 用公 1 x 1 A 2 x 2 A 3 x 1 B 4 x 2 B 5 x 斤加工 公斤加工 增设 可使下面的模型简单 1 A 1 B 6 x 2 A 2 B 5 x 6 x 目标函数目标函数 设每天净利润为 容易写出z 654321 3332441624xxxxxxz 约束条件约束条件 原料供应原料供应 每天生产公斤 用牛奶桶 每天生产 1 A 51 xx 3 51 xx 2 A 公斤 用牛奶桶 二者之和不得超过每天的供应量 50 桶 62 xx 4 62 xx 劳动时间劳动时间 每天生产 的时间分别为和 加工 1 A 2 A 4 51 xx 2 62 xx 1 B B2的时间分别为和 二者之和不得超过总的劳动时间 480 小时 2 B 5 2x 6 2x 设备能力设备能力 的产量不得超过设备甲每天的加工能力 100 公斤 1 A 51 xx 非负约束非负约束 均为非负 621 xxx 附加约束附加约束 1 公斤加工成 0 8 公斤 故 类似地 1 A 1 B 53 8 0 xx 64 75 0 xx 由此得基本模型 6 Max 654321 3332441624xxxxxxz s t 50 7 43 6251 xxxx 480 8 656251 22 2 4xxxxxx 100 9 51 xx 10 53 8 0 xx 11 64 75 0 xx 0 12 654321 xxxxxx 这仍然是一个线性规划模型 模型求解模型求解 用 LINDO 软件求解 输入文件时应将 7 式改写为 600 7 6521 3434xxxx 8 式改写为 480 8 6521 4624xxxx 可得如下输出 LP OPTIMUM FOUND AT STEP 2 OBJECTIVE FUNCTION VALUE 1 3460 800 VARIABLE VALUE REDUCED COST X1 0 000000 1 680000 X2 168 000000 0 000000 X3 19 200001 0 000000 X4 0 000000 0 000000 X5 24 000000 0 000000 X6 0 000000 1 520000 ROW SLACK OR SURPLUS DUAL PRICES 2 0 000000 3 160000 3 0 000000 3 260000 4 76 000000 0 000000 5 0 000000 44 000000 6 0 000000 32 000000 NO ITERATIONS 2 RANGES IN WHICH THE BASIS IS UNCHANGED OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 24 000000 1 680000 INFINITY X2 16 000000 8 150000 2 100000 X3 44 000000 19 750002 3 166667 X4 32 000000 2 026667 INFINITY X5 3 000000 15 800000 2 533334 X6 3 000000 1 520000 INFINITY RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 600 000000 120 000000 280 000000 3 480 000000 253 333328 80 000000 4 100 000000 INFINITY 76 000000 5 0 000000 INFINITY 19 200001 6 0 000000 INFINITY 0 000000 最优解为最优解为 0 24 0 2 19 168 0 654321 xxxxxx 8 3460 z 即每天生产销售 168 公斤和 19 2 公斤 不出售 可获净利润 3460 8 元 2 A 1 B 1 A 2 B 为此 需用 8 桶牛奶加工成 42 桶加工成 并将得到的 24 公斤全部加工成 1 A 2 A 1 A 1 B 和例 1 一样 原料 牛奶 劳动时间为紧约束 结果分析结果分析 利用输出中的影子价格和灵敏性分析讨论以下问题 1 上述结果给出 约束 2 3 的影子价格分别为 3 16 和 3 26 注意到约束 2 的影子价格为 13 右端增加 1 单位目标函数的增量 由 7 式可知 增加 1 桶牛奶可 使净利润增长 3 16 12 37 92 元 约束 3 的影子价格则说明 增加 1 小时劳动时间可使 净利润增长 3 26 元 所以应该投资 30 元增加供应 1 桶牛奶 或投资 3 元增加 1 小时劳动 时间 若每天投资 150 元 增加供应 5 桶牛奶 可赚回 37 92 5 189 6 元 但是通过投 资增加牛奶的数量是有限制的 输出结果表明 约束 2 右端的允许变化范围为 600 280 600 120 相当于 7 式右端的变化范围为 50 23 3 50 10 即最多 增加供应 10 桶牛奶 2 上述结果给出了最优解不变条件下目标函数系数的允许变化范围 的系数为 3 x 44 3 17 44 19 75 的系数为 32 32 2 03 所以当的获利向下波动 10 4 x 1 B 或的获利向上波动 10 时 上面得到的生产销售计划不再是最优的 应该重新制订 2 B 如若每公斤的获利下降 10 应将原模型 6 式中的系数改为 39 6 重新计算 1 B 3 x 得到的最优解为最优值为 40 0 30 0 160 0 654321 xxxxxx3400 z 即 50 桶牛奶全部加工成 200 公斤 出售其中 160 公斤 将其余 40 公斤加工成 30 公 2 A 斤出售 获净利润 3400 元 可见计划变化很大 这就是说 最优 生产计划对或 2 B 1 B 获利的波动是很敏感的 你有办法改变这种状况吗 2 B 评注评注与例 1 相比 例 2 多了两种产品 它们的销售量与 的加工量 1 B 2 B 1 A 2 A 之间存在等式关系 10 11 虽然可以据此消掉 2 个变量 但是会增加人工计算 并 使模型变得复杂 我们建模的原则是尽可能利用原始的数据信息 而把尽量多的计算留 给计算机去做 4 2 自来水输送与货机装运 钢铁 煤炭 水电等生产 生活物资从若干供应点运送到一些需求点 怎样安排输 送方案使运费最小 或者利润最大 各种类型的货物装箱 由于受体积 重量等的限制 如何相互搭配装载 使获利最高 或者装箱数量最少 本节通过两个例子讨论用数学规 划模型解决这类问题的方法 例例 1自来水输送问题自来水输送问题 问题问题某市有甲 乙 丙 丁四个居民区 自来水由 三个水库供应 四ABC 个区每天必须得到保证的基本生活用水量分别为 30 70 10 10 千吨 但由于水源紧张 三个水库每天最多只能分别供应 50 60 50 千吨自来水 由于地理位置的差别 自来水 公司从各水库向各区送水所需付出的引水管理费不同 见表 1 其中水库与丁区之间C 没有输水管道 其他管理费用都是 450 元 千吨 根据公司规定 各区用户按照统一标准 900 元 千吨收费 此外 四个区都向公司申请了额外用水量 分别为每天 50 70 20 40 千吨 该公司应如何分配供水量 才能获利最多 为了增加供水量 自来水公司正在考虑进行水库改造 使三个水库的每天的最大供 水量都提高一倍 问那时供水方案应如何改变 公司利润可增加到多少 引水管理费 元 千吨 甲乙 丙 丁 A160 130 220 170 B140 130 190 150 C190 200 230 表表 1从水库向各区送水的引水管理费从水库向各区送水的引水管理费 问题分析问题分析分配供水量就是安排从三个水库向四个区送水的方案 目标是获利最多 而从题目给出的数据看 三个水库的供水量 160 千吨 不超过四个区的基本ABC 生活用水量与额外用水量之和 300 千吨 因而总能全部卖出并获利 于是自来水公司每 天的总收入是 900 50 60 50 144000 元 与送水方案无关 同样 公司每天的其他 管理费用是 450 50 60 50 72000 元也与送水方案无关 所以 要使利润最大 只 需使引水管理费最小即可 另外 送水方案自然要受三个水库的供应量和四个区的需求 量的限制 模型建立模型建立 很明显 决策变量为 三个水库 1 2 3 分别向甲 乙 丙 丁四ABCi 个区 1 2 3 4 的供水量 设水库 向区的供水量为 由于水库与丁区之jij ij xC 间没有输水管道 即 0 因此只有 11 个决策变量 34 x 由上分析 问题的目标可以从获利最多转化为引水管理费最少 于是有 3332312423222114131211 230200190150190130140170220130160 xxxxxxxxxxxMinZ 1 约束条件有两类 一类是水库的供应量限制 另一类是各区的需求量限制 由于供水量总能卖出并获利 水库的供应量限制可以表示为 2 50 14131211 xxxx 3 60 24232221 xxxx 4 50 333231 xxx 考虑到各区的基本生活用水量与额外用水量 需求量限制可以表示为 30 80 5 312111 xxx 70 140 6 322212 xxx 10 30 7 332313 xxx 10 50 8 2414 xx 模型求解模型求解 1 8 构成一个线性规划模型 当然要加上 xij的非负约束 输入 LINDO 求 解 得到如下输出 OBJECTIVE FUNCTION VALUE 1 24400 00 VARIABLE VALUE REDUCED COST X11 0 000000 30 000000 X12 50 000000 0 000000 X13 0 000000 50 000000 X14 0 000000 20 000000 X21 0 000000 10 000000 X22 50 000000 0 000000 X23 0 000000 20 000000 X24 10 000000 0 000000 X31 40 000000 0 000000 X32 0 000000 10 000000 X33 10 000000 0 000000 送水方案为 水库向乙区供水 50 千吨 水库向乙 丁区分别供水 50 10 千吨 AB 水库向甲 丙分别供水 40 10 千吨 引水管理费为 24400 元 利润为C 144000 72000 24400 47600 元 讨论讨论 如果 三个水库每天的最大供水量都提高一倍 则公司总供水能力ABC 为 320 千吨 大于总需求量 300 千吨 水库供水量不能全部卖出 因而不能像前面那样 将获利最多转化为引水管理费最少 此时我们首先需要计算 三个水库分别向ABC 甲 乙 丙 丁四个区供应每千吨水的净利润 即从收入 900 元中减去其他管理费 450 元 再减去表 1 中的引水管理费 得表 2 净利润 元 千吨 甲乙 丙 丁 A 290320 230 280 B 310320 260 300 C 260250 220 表表 2 从水库向各区送水的净利润从水库向各区送水的净利润 于是决策目标为 3332312423222114131211 220250260300260320310280230320290 xxxxxxxxxxxMinZ 9 由于水库供水量不能全部卖出 所以上面约束 2 4 的右端增加一倍的同时 应将等号改成小于 等于号 即 100 14131211 xxxx 10 120 24232221 xxxx 11 100 333231 xxx 12 约束 5 8 不变 将 5 12 构成线性规划模型输入 LINDO 求解得到 OBJECTIVE FUNCTION VALUE 1 88700 00 VARIABLE VALUE REDUCED COST X11 0 000000 20 000000 X12 100 000000 0 000000 X13 0 000000 40 000000 X14 0 000000 20 000000 X21 30 000000 0 000000 X22 40 000000 0 000000 X23 0 000000 10 000000 X24 50 000000 0 000000 X31 50 000000 0 000000 X32 0 000000 20 000000 X33 30 000000 0 000000 送水方案为 水库向乙区供水 100 千吨 水库向甲 乙 丁区分别供水AB 30 40 50 千吨 水库向甲 丙区分别供水 50 30 千吨 总利润为 88700 元 C 其实 由于每个区的供水量都能完全满足 所以上面 5 8 每个式子左边的约 束可以去掉 右边小于 等于号可以改写成等号 作这样的简化后得到的解没有任何变 化 评注评注 本题考虑的是将某种物质从若干供应点运往一些需求点 在供需量约束条件 下使总费用最小 或总利润最大 这类问题一般称为运输问题运输问题 是线性规划应用最广泛 的领域之一 在标准的运输问题中 供需量通常是平衡的 即供应点的总供应量等于需 求点的总需求量 本题中供需量量不平衡 但这并不会引起本质的区别 一样可以方便 地建立线性规划模型求解 例例 2 货机装运货机装运 问题问题 某架货机有三个货舱 前仓 中仓 后仓 三个货舱所能装载的货物的最大 重量和体积都有限制 如表 3 所示 并且 为了保持飞机的平衡 三个货舱中实际装载 货物的重量必须与其最大容许重量成比例 前仓 中仓 后仓 重量限制 吨 10 16 8 体积限制