6其它数学规划问题(1).pdf

其它数学规划问题其它数学规划问题 1 内容提要内容提要 1 1 整数规划整数规划 2 2 非线性规划非线性规划 3 3 目标规划目标规划 下次课讲 下次课讲 2 整数规划整数规划 3 整数规划的基本概念整数规划的基本概念 在一些应用中 决策变量只有在它们是整数的情在一些应用中 决策变量只有在它们是整数的情 况下才有实际意义 例如人员 设备数量 况下才有实际意义 例如人员 设备数量 若无特别说明 整数规划指整数线性规划 若无特别说明 整数规划指整数线性规划 管理问题用整数规划表示和用线性规划表示是一管理问题用整数规划表示和用线性规划表示是一 样的 只是加了一个约束 样的 只是加了一个约束 部分或所有的决策变部分或所有的决策变 量必须是整数 量必须是整数 不再符合线性规划的可分性假不再符合线性规划的可分性假 设设 决策变量可以是在满足一定函数约束和非负约决策变量可以是在满足一定函数约束和非负约 束下包括分数在内的所有实数 束下包括分数在内的所有实数 4 整数规划的基本概念整数规划的基本概念 整数规划的分类整数规划的分类 纯整数规划 要求全体变量为纯整数规划 要求全体变量为整数整数 混合整数规划 仅要求部分变量为混合整数规划 仅要求部分变量为整数整数 0 0 1 1整数规划整数规划 整数变量整数变量只有只有两个值两个值 0 0或或1 1 指派问题是指派问题是0 0 1 1整数规划的特例整数规划的特例 一般整数规划 整数变量取值不受一般整数规划 整数变量取值不受0 0或或1 1限制限制 5 整数规划的基本概念整数规划的基本概念 整数规划求解整数规划求解 对对线性规划的解进行 舍入化整 常常不行 或线性规划的解进行 舍入化整 常常不行 或 者不是可行解 或者不是者不是可行解 或者不是最优解 最优解 舍入化整 舍入化整 可能可能可行可行的时候的时候 当数值大 当数值大 114 286114 286 化整为 化整为 114114 舍入化整 不可行 舍入化整 不可行的时候的时候 当数值小 当数值小 2 6 2 6 化整为 化整为 2 2 或 或 3 3 当是当是0 0 1 1变量变量 当想化整许多非整数值时当想化整许多非整数值时 整数规划整数规划有自己的算法有自己的算法 分支定界法分支定界法 割平面法 隐枚举法割平面法 隐枚举法 6 整数规划的基本概念整数规划的基本概念 整数规划整数规划 的可行解的可行解 是相应的是相应的 线性规划线性规划 可行解的可行解的 子集 子集 7 可行域可行域 整数规划的基本概念整数规划的基本概念 整数规划 整数规划 IPIP 的可行解也是原 的可行解也是原 线性规划 线性规划 LPLP 整数规划问题的整数规划问题的 LPLP放宽放宽 的可行解 的可行解 若原线性规划 若原线性规划 LPLP 有最优解 有最优解 且解是整数 则它也是整数规划且解是整数 则它也是整数规划 IPIP 的最优解 的最优解 8 一般整数规划 一般整数规划 IP IP 9 TBATBA 航空公司问题航空公司问题 小型飞机小型飞机 大型飞机大型飞机 可用资金可用资金 每架飞机的年净利润每架飞机的年净利润 100万美元万美元 500万美元万美元 飞机的单位购买成本飞机的单位购买成本 500万美元万美元 5000万美元万美元 1亿美元亿美元 最多购买数量最多购买数量 2 没有限制没有限制 TBATBA 航空公司是一家使用小飞机经营短途航线的小航空公司是一家使用小飞机经营短途航线的小 型区域性企业 该公司的经营一直非常顺利 其管型区域性企业 该公司的经营一直非常顺利 其管 理层决定拓展经营领域 理层决定拓展经营领域 管理层面临的决策 采购更多小型飞机来开辟一些管理层面临的决策 采购更多小型飞机来开辟一些 新的短途航线 还是通过为一些跨地区航线购买大新的短途航线 还是通过为一些跨地区航线购买大 型飞机来进军全国市场 或同时采取两种策略 型飞机来进军全国市场 或同时采取两种策略 为了最大化年净利润 应该购买多少每种类型飞机 为了最大化年净利润 应该购买多少每种类型飞机 9 11 TBA TBA 航空公司航空公司问题问题 Maximize Profit S 5L millions subject to 5S 50L 100 millions S 2 S 0 L 0 S 购买小飞机数量购买小飞机数量 L 购买购买大飞机大飞机数量数量 线性规划数学模型线性规划数学模型 9 12 线性规划的图解法线性规划的图解法 3 2 1 0 123S L Feasible region Number of large airplanes purchased Number of small airplanes purchased 2 1 Rounded solution Profit 7 2 1 8 Optimal solution Profit 11 S 5 L 9 13 整数规划数学模型整数规划数学模型 Maximize Profit S 5L millions subject to 5S 50L 100 millions S 2 S 0 L 0 S L 是整数是整数 S 购买小飞机数量购买小飞机数量 L 购买大飞机购买大飞机数量数量 整数规划数学模型整数规划数学模型 9 14 整数规划的图解法整数规划的图解法 3 2 1 0 123S L Number of large airplanes purchased Number of small airplanes purchased 2 1 Rounded solution Profit 7 2 1 8 Optimal solution for the LP relaxation Profit 11 Profit 10 S 5 L 0 2 Optimal solution for the integer programming problem Profit 10 一般整数规划一般整数规划 整数规划的计算机整数规划的计算机求解求解 在在EXCEL SolverEXCEL Solver中 设定可变单元格要满足整数中 设定可变单元格要满足整数 约束 约束 INTINT表示整数 表示整数 BINBIN表示表示0 0 1 1变量 二进制 变量 二进制 注意 求解注意 求解IPIP更难 即使有最优解 在有限时间内更难 即使有最优解 在有限时间内 也不一定能求出 也不一定能求出 注意 整数规划没有敏感性报告 注意 整数规划没有敏感性报告 参见参见 TBATBA航空公司问题航空公司问题 xlsxls 15 一般整数规划一般整数规划 可以用舍入的方法求解吗可以用舍入的方法求解吗 例例 MAX 100X1 200X2MAX 100X1 200X2 ST aX1ST aX1 X2 0X2 0 2aX12aX1 X2 aX2 0X1 X2 0 LPLP最优解最优解 1 1 a a IPIP的最优解 的最优解 若若a a为正整数 为正整数 1 1 a a 若若a a为正分数 如为正分数 如 10000 510000 5 最优解 最优解 0 0 0 0 16 0 0 1 1整数规划 整数规划 BIPBIP 17 0 0 1 1变量变量 0 0 1 1决策变量决策变量 因为因为0 0 1 1变量只提供两种选择 所以变量只提供两种选择 所以 适合作为表示是非 是否 的决策变量 适合作为表示是非 是否 的决策变量 是否开展某一特定项目是否开展某一特定项目 是否进行某一项固定投资是否进行某一项固定投资 是否将设备安置在某一特定地点是否将设备安置在某一特定地点 应用举例 应用举例 n n个候选方案个候选方案中中只能选择只能选择m m个 个 m m n n个候选方案中最多选择个候选方案中最多选择m m个 个 m m 只有方案只有方案i i被选中时方案被选中时方案j j才可能被选中 才可能被选中 Xj Xi Xi i 1 2 n 是是0 1变量变量 18 0 0 1 1变量变量 辅助辅助0 0 1 1变量变量 为了方便建立模型而引入模型中的附加为了方便建立模型而引入模型中的附加 变量 可以把有各种情况需要分别分析的问题统一在一变量 可以把有各种情况需要分别分析的问题统一在一 个模型中分析和求解 个模型中分析和求解 应用举例 应用举例 固定成本问题 决定生产某种产品时才会发生相关的固定成本 固定成本问题 决定生产某种产品时才会发生相关的固定成本 y y是是0 0 1 1变量 发生固定成本时变量 发生固定成本时 1 1 否则为 否则为0 0 添加添加约束约束 产量产量 M y M y M M是大数或当是大数或当y 1y 1时不改变原来约束的数 时不改变原来约束的数 相互排斥的约束 不同情况下不同约束起作用 相互排斥的约束 不同情况下不同约束起作用 设有设有n n个个 约束 每个约束右端添加 约束 每个约束右端添加 M yM yi i 其中 其中M M是一个大是一个大 数 数 y yi i是是0 0 1 1变量 变量 当当有有m m个约束起作用时 要求个约束起作用时 要求 n n m m 只有 只有 y yi i等于等于0 0的约束起作用 的约束起作用 19 0 0 1 1决策变量决策变量 案例 加利福尼亚制造公司选址问题案例 加利福尼亚制造公司选址问题 问题 问题 背景 建工厂 建一个仓库背景 建工厂 建一个仓库 可选地点 洛杉矶 旧金山 两个地点都可可选地点 洛杉矶 旧金山 两个地点都可 以建工厂 仓库与工厂应该设在同一地点 以建工厂 仓库与工厂应该设在同一地点 如果不设立新厂就不需要建仓库 如果不设立新厂就不需要建仓库 约束 可使用的资金总量约束 可使用的资金总量 目标 投资的净现值最大化目标 投资的净现值最大化 进一步分析可用资金量对净现值的影响进一步分析可用资金量对净现值的影响 20 加利福尼亚制造公司选址问题加利福尼亚制造公司选址问题 决策序列号决策序列号 是非问题是非问题 决策变量决策变量 净现值净现值 百万美元 百万美元 所需资金所需资金 百万美元 百万美元 1 在洛杉矶建工厂在洛杉矶建工厂 x1 建 建 否 否 1 0 8 6 2 在旧金山建工厂在旧金山建工厂 x2 建 建 否 否 1 0 5 3 3 在洛杉矶建仓库在洛杉矶建仓库 x3 建 建 否 否 1 0 6 5 4 在旧金山建仓库在旧金山建仓库 x4 建 建 否 否 1 0 4 2 可用资金 可用资金 1000万美元万美元 加利福尼亚制造公司选址问题加利福尼亚制造公司选址问题 数学模型数学模型 Maximize NPV 8x1 5x2 6x3 4x4 subject to 6x1 3x2 5x3 2x4 10 互斥方案 互斥方案 x3 x4 1 相依决策 相依决策 x3 x1 x4 x2 x1 x2 x3 x4 是是0 1变量变量 参见参见 加利福尼亚制造公司选址问题加利福尼亚制造公司选址问题 xlsxls 加利福尼亚制造公司选址问题加利福尼亚制造公司选址问题 敏感性分析敏感性分析 整数规划不能生成敏感性分析报告 因为影子整数规划不能生成敏感性分析报告 因为影子 价格和可行域在这里不再适用 价格和可行域在这里不再适用 试算法 不断改变资金约束后 每次都用整数试算法 不断改变资金约束后 每次都用整数 规划求解 规划求解 系统化的试算法 系统化的试算法 Solver TableSolver Table 23 9 24 加利福尼亚制造公司选址问题加利福尼亚制造公司选址问题 Capital Available Warehouse WarehouseFactoryFactoryTotal NPV millions in LA in SF in LA in SF millions 001113 501019 601019 701019 801019 9001113 10001113 11011117 12011117 13011117 14101119 15101119 Solver TableSolver Table结果结果 0 0 1 1决策变量的其他一些应用决策变量的其他一些应用 投资分析 是否应当进行定额投资投资分析 是否应当进行定额投资 选址 某一地点是否应该被选为选址 某一地点是否应该被选为 设计制造和分销网络 是否维持特定工厂 或设计制造和分销网络 是否维持特定工厂 或配送中心配送中心 的 的 运营运营 货物配送 是否为一辆卡车选择特定路线 出发时间等 货物配送 是否为一辆卡车选择特定路线 出发时间等 为相互关联的活动进行排程 为相互关联的活动进行排程 一个特定活动是否应当在特定的时间开始一个特定活动是否应当在特定的时间开始 安排资产出售 安排资产出售 在一个特定的时间段里是否应当持有一种特定的资产在一个特定的时间段里是否应当持有一种特定的资产 在航空业中的应用在航空业中的应用 是否应该指派特定类型的飞机去飞特定的航线是否应该指派特定类型的飞机去飞特定的航线 是否应当将特定序列的航班指派给一名空勤人员是否应当将特定序列的航班指派给一名空勤人员 25 辅助辅助0 0 1 1变量变量 净利润 美元 净利润 美元 产品数量产品数量 门门 窗窗 0 0 300 0 0 0 500 0 0 1 1 300 700 400 1 500 1 300 800 2 2 300 700 100 2 500 1 300 300 3 3 300 700 200 3 500 1 300 200 4 4 300 700 500 4 500 1 300 700 5 不可行不可行 5 500 1 300 1 200 6 不可行不可行 6 500 1 300 1 700 固定成本问题 固定成本问题 伟恩德公司案例变形伟恩德公司案例变形1 1 变化变化1 1 生产则有固定成本发生 不生产则没有 每种产 生产则有固定成本发生 不生产则没有 每种产 品品的的净净利润利润不再与产量成比例 目标函数 不再与产量成比例 目标函数 辅助辅助0 0 1 1变量变量 变化变化2 2 生产批次在一个星期后即终止 因此决策变量是生产 生产批次在一个星期后即终止 因此决策变量是生产 总量 应该是整数 而不是每周的生产率 总量 应该是整数 而不是每周的生产率 变化变化1 1和和2 2导致这个导致这个问题不再是线性规划或整数规划问题不再是线性规划或整数规划问题 需要问题 需要 使用辅助使用辅助0 0 1 1变量变量 对于对于每一个准备成本 只有两种可能 发生或者不每一个准备成本 只有两种可能 发生或者不发生 因发生 因 此此为每个准备成本定义一个为每个准备成本定义一个0 0 1 1变量变量y y y 1y 1代表 做准备 代表 做准备 y 0y 0代表 不做准备 代表 不做准备 y 1y 1时 产量时 产量 0 0 y 0y 0时 产量时 产量 0 0 添加约束添加约束 产量产量 M yM y M M是一个比最小可接受系数大的数 即是一个比最小可接受系数大的数 即 不对产量施加额外的非期望限制 求最大的目标排除不对产量施加额外的非期望限制 求最大的目标排除了发了发 生固定成本但产量为生固定成本但产量为0 0的不合理做法 的不合理做法 改变改变目标函数目标函数 减去固定成本减去固定成本 27 9 28 辅助辅助0 0 1 1变量变量 0246 2 4 6 8 Production quantity for windows 0 0 gives P 0 4 0 gives P 500 4 3 gives P 500 200 Production quantity for doors 2 6 gives P 100 1700 0 6 gives P 1700 8 1600 700 W D 9 29 辅助辅助0 0 1 1变量变量 数学模型数学模型 D 生产门的数量生产门的数量 W 生产窗的数量生产窗的数量 y1 1 准备生产门 否则准备生产门 否则 0 y2 1 准备生产窗 否则准备生产窗 否则 0 Maximize P 300D 500W 700y1 1300y2 subject to 工厂工厂1 D 4 工厂工厂2 2W 12 工厂工厂3 3D 2W 18 门门 D 99y1 窗窗 W 99y2 D 0 W 0 D 和和W是整数 是整数 y1和和y2 是是0 1变量变量 参见参见 伟恩德公司固定成本问题伟恩德公司固定成本问题 xlsxls 9 30 辅助辅助0 0 1 1变量变量 0246 2 4 6 8 Production rate for windows 0 0 gives P 0 4 0 gives P 1 200 Production rate for doors 0 6 gives P 3 000 P 300 D 500 W Either D 0 or W 0 8 W D 互斥产品问题 互斥产品问题 伟恩德公司案例变形伟恩德公司案例变形2 2 不考虑变形不考虑变形1 1 变化 两种新产品门和窗具有相同的用户 变化 两种新产品门和窗具有相同的用户 所以相互竞争 因此管理者决定只选择其中一种生产 所以相互竞争 因此管理者决定只选择其中一种生产 D 0 D 0 或者或者 W 0 W 0 或者两者都为或者两者都为0 0 9 31 辅助辅助0 0 1 1变量变量 y1 1 如果生产门 否则如果生产门 否则 0 y2 1 如果生产窗 否则如果生产窗 否则 0 Maximize P 300D 500W subject to D 4 2W 12 3D 2W 18 D 99y1 W 99y2 互斥关系 互斥关系 y1 y2 1 D 0 W 0 y1 和和 y2 是是0 1变量变量 参见参见 伟恩德公司互斥产品问题伟恩德公司互斥产品问题 xlsxls 辅助辅助0 0 1 1变量变量 单位产品的生产时间 小时 单位产品的生产时间 小时 每周可用生产时间每周可用生产时间 工厂工厂 门门 窗窗 1 1 0 4 2 0 2 12 3 3 2 18 4 2 4 28 单位利润单位利润 美元 美元 300 500 二选一约束问题 二选一约束问题 伟恩德公司案例变形伟恩德公司案例变形3 3 不考虑变形不考虑变形1 1和和2 2 变化 公司最近建了一个与工厂 变化 公司最近建了一个与工厂3 3类似类似 的新厂 工厂的新厂 工厂4 4 也可以生产两种新产品 管理者决定只在 也可以生产两种新产品 管理者决定只在 工厂工厂3 3和和4 4中选择一个生产新产品 并且使利润最大 中选择一个生产新产品 并且使利润最大 9 33 辅助辅助0 0 1 1变量变量 024 2 4 6 8 024 2 4 6 8 a Choose Plant 3 b Choose Plant 4 2 6 gives P 3 600 4 5 gives P 3 700 Feasible region Feasible region WW DD 9 34 辅助辅助0 0 1 1变量变量 数学模型数学模型 y 1 如果使用工厂如果使用工厂4 y 0 如果使用工厂如果使用工厂3 Maximize P 300D 500W subject to 工厂工厂1 D 4 工厂工厂2 2W 12 工厂工厂3 3D 2W 18 99y 工厂工厂4 2D 4W 28 99 1 y D 0 W 0 y是是0 1变量变量 参见参见 伟恩德公司二选一约束问题伟恩德公司二选一约束问题 xlsxls 0 0 1 1变量的几个应用变量的几个应用 单位产品生产时间 小时 单位产品生产时间 小时 每周可用生产时每周可用生产时 间 小时 间 小时 工厂工厂 产品产品 1 产品产品 2 产品产品 3 1 3 4 2 30 2 4 6 2 40 单位利润单位利润 5 7 3 1000美元 美元 可售出数量可售出数量 7 5 9 每周数量 每周数量 增加管理方面约束 例增加管理方面约束 例1 固特产品公司问题 固特产品公司问题 研发部开发了研发部开发了3种新产品 管理层决定 种新产品 管理层决定 1 在 在3种新产品中 最多生产种新产品中 最多生产2种种 2 从可以生产的 从可以生产的2个工厂中选择个工厂中选择1个生产新产品个生产新产品 练习题 9 36 0 0 1 1变量的几个应用变量的几个应用 数学模型数学模型 xi 每周产品每周产品 i 生产数量生产数量 i 1 2 3 yi 1 如果产品如果产品 i 被生产 否则被生产 否则 0 i 1 2 3 y4 1 如果工厂如果工厂2被使用 被使用 y4 0 如果工厂如果工厂1被使用被使用 Maximize Profit 5x1 7x2 3x3 subject to 产品产品 1 x1 7y1 产品产品 2 x2 5y2 产品产品 3 x3 9y3 y1 y2 y3 2 工厂工厂 1 3x1 4x2 2x3 30 99y4 工厂工厂 2 4x1 6x2 2x3 40 99 1 y4 xi 0 i 1 2 3 yi 是是0 1变量 变量 i 1 2 3 4 0 0 1 1变量的几个应用变量的几个应用 利润 百万美元 利润 百万美元 电视广告数量电视广告数量 产品产品 1 产品产品 2 产品产品 3 0 0 0 0 1 1 0 1 2 3 2 2 3 3 3 4 不符合比例性要求 例不符合比例性要求 例2 Supersuds公司问题公司问题 为新产品制定营销计划 准备在全国电视网上购买为新产品制定营销计划 准备在全国电视网上购买5个个 商业广告来促销商业广告来促销3种产品 每个广告只针对一种产品 每种种产品 每个广告只针对一种产品 每种 产品最多可以有产品最多可以有3个广告 最少可以不做广告 如何将个广告 最少可以不做广告 如何将5个个 广告分配给广告分配给3种产品 种产品 9 38 0 0 1 1变量的几个应用变量的几个应用 数学模型数学模型 yij 1 如果产品如果产品 i 有有 j个电视广告 否则个电视广告 否则 0 i 1 2 3 j 1 2 3 Maximize Profit y11 3y12 3y13 2y22 3y23 y31 2y32 4y33 subject to 产品产品 1 y11 y12 y13 1 产品产品 2 y21 y22 y23 1 产品产品 3 y31 y32 y33 1 可用广告数 可用广告数 y11 2y12 3y13 y21 2y22 3y23 y31 2y32 3y33 5 yij 是是0 1变量变量 i 1 2 3 j 1 2 3 参见参见 SupersudsSupersuds公司问题公司问题 xlsxls 9 39 0 0 1 1变量的几个应用变量的几个应用 Seattle SEA San Francisco SFO Los Angeles LAX Denver DEN Chicago ORD 航空公司人员排程问题 例航空公司人员排程问题 例3 西南航空公司 西南航空公司 把以旧金山 把以旧金山 SFO 为基地的 为基地的3队机组人员分配给队机组人员分配给11个航班 个航班 3个机组个机组 应该被分配给哪三个飞行序列才能让应该被分配给哪三个飞行序列才能让11个航班都被覆盖而且成本最低 个航班都被覆盖而且成本最低 0 0 1 1变量的几个应用变量的几个应用 可行的航班次序可行的航班次序 航航 班班 1 2 3 4 5 6 7 8 9 10 11 12 1 SFO LAX 1 1 1 1 2 SFO DEN 1 1 1 1 3 SFO SEA 1 1 1 1 4 LAX ORD 2 2 3 2 3 5 LAX SFO 2 3 5 5 6 ORD DEN 3 3 4 7 ORD SEA 3 3 3 3 4 8 DEN SFO 2 4 4 5 9 DEN ORD 2 2 2 10 SEA SFO 2 4 4 5 11 SEA LAX 2 2 4 4 2 成本 千美元 成本 千美元 2 3 4 6 7 5 7 8 9 9 8 9 9 41 0 0 1 1变量的几个应用变量的几个应用 数学模型数学模型 xj 1 如果航班序列如果航班序列j 被分配给机组 否则被分配给机组 否则 0 j 1 2 12 Minimize Cost 2x1 3x2 4x3 6x4 7x5 5x6 7x7 8x8 9x9 9x10 8x11 9x12 subject to 航班航班1被覆盖 被覆盖 x1 x4 x7 x10 1 航班航班2被覆盖 被覆盖 x2 x5 x8 x11 1 航班航班11被覆盖 被覆盖 x6 x9 x10 x11 x12 1 3个机组个机组 x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11 x12 3 xj 是是0 1变量 变量 j 1 2 12 参见参见 西南航空公司问题西南航空公司问题 xlsxls 非线性规划非线性规划 42 非线性规划的特点非线性规划的特点 在线性规划和整数规划模型中 所有函数 包括在线性规划和整数规划模型中 所有函数 包括 目标函数和函数约束 的数学关系都是线性的 目标函数和函数约束 的数学关系都是线性的 只要模型中存在一个非线性关系 该模型就成为只要模型中存在一个非线性关系 该模型就成为 非线性规划 非线性规划 在在EXECL中 线性模型的输出单元格 包括目中 线性模型的输出单元格 包括目 标单元格 中的公式仅包含加总 或数值 数据标单元格 中的公式仅包含加总 或数值 数据 单元格 和可变单元格的乘积 如果包含了其他单元格 和可变单元格的乘积 如果包含了其他 运算 例如可变单元格的乘法或除法 这样产运算 例如可变单元格的乘法或除法 这样产 生的模型就不是线性的 生的模型就不是线性的 43 10 44 非线性规划的特点非线性规划的特点 线性公式线性公式 非线性公式非线性公式 SUMPRODUCT D4 D6 C4 C6 D1 D2 D3 C4 IF D2 2 2 C3 3 C4 SUMIF D1 D6 4 C1 C6 SUM D4 D6 2 C1 3 C4 C6 C1 C2 C3 SUMPRODUCT C4 C6 C1 C3 C1 C2 C3 D4 IF C2 2 2 C3 3 C4 SUMIF C1 C6 4 D1 D6 ROUND C1 MAX C1 0 MIN C1 C2 ABS C1 SQRT C1 C1 C2 C1 C2 C1 2 D1 D6是数据单元格 是数据单元格 C1 C6 是可变单元格是可变单元格 非线性规划的特点非线性规划的特点 管理者有时会碰到一些无法应用线性模型的问题 管理者有时会碰到一些无法应用线性模型的问题 通常是因为通常是因为目标函数目标函数需要是非线性的需要是非线性的 活动水平活动水平 和总体绩效测度指标之间是非比例关系 和总体绩效测度指标之间是非比例关系 使用非线性规划的最大好处在于其精确性 使用非线性规划的最大好处在于其精确性 建立和求解非线性规划模型通常比建立和求解线性建立和求解非线性规划模型通常比建立和求解线性 规划模型更具有挑战性 规划模型更具有挑战性 确定函数形式困难 确定函数形式困难 求解困难 求解困难 即使获得一个解 有时也不能保证其是最优的 即使获得一个解 有时也不能保证其是最优的 45 10 46 非线性规划的特点非线性规划的特点 Level of an activity a Level of an activity b Level of an activityLevel of an activity c d Profit Profit Profit Profit 边际收益递减边际收益递减 边际收益递减的分段线性关系边际收益递减的分段线性关系 10 47 非线性规划的特点非线性规划的特点 边际收益递减 除不连续点之外边际收益递减 除不连续点之外 边际收益递增边际收益递增 Level of an activity a Level of an activity b Level of an activityLevel of an activity c d Profit Profit Profit Profit 10 48 非线性规划的特点非线性规划的特点 1 2 3 4 5 6 7 8 ABC Constructing a Nonlinear Formula Level of ActivityProfit 2 16 4 24 5 28 7 30 10 33 拟合非线性公式与曲线拟合非线性公式与曲线 假定公式的一般形式假定公式的一般形式 找出合理的参数值 找出合理的参数值 Excel中的曲线拟合方法 中的曲线拟合方法 y 0 3002x2 5 661x 6 1477 0 5 10 15 20 25 30 35 024681012 活动水平和利润活动水平和利润 参见参见 Constructing Nonlin Formula xls 10 49 非线性规划的特点非线性规划的特点 对以下非线性模型求解对以下非线性模型求解 Maximize Profit 0 5x5 6x4 24 5x3 39x2 20 x subject to x 5 x 0 参见参见 Multiple Local Maxima xls 10 50 非线性规划的特点非线性规划的特点 1 2 3 4 5 6 7 ABCDE A Simple NLP Maximum x 0 371 5 Profit 0 5x5 6x4 24 5x3 39x2 20 x 3 19 从从 x 0开始运行开始运行Solver 10 51 非线性规划的特点非线性规划的特点 1 2 3 4 5 6 7 ABCDE A Simple NLP Maximum x 3 126 5 Profit 0 5x5 6x4 24 5x3 39x2 20 x 6 13 从从 x 3开始运行开始运行Solver 10 52 非线性规划的特点非线性规划的特点 1 2 3 4 5 6 7 ABCDE A Simple NLP Maximum x 5 000 5 Profit 0 5x5 6x4 24 5x3 39x2 20 x 0 00 从从 x 4 7开始运行开始运行Solver 10 53 非线性规划的特点非线性规划的特点 Profit x 利润图利润图 非线性规划的特点非线性规划的特点 ExeclExecl SolverSolver求解非线性规划问题的算法可以求解非线性规划问题的算法可以 看成是一个爬山的过程 它从输入可变单元格看成是一个爬山的过程 它从输入可变单元格 的初始值出发开始爬山 直到到达顶点 或到的初始值出发开始爬山 直到到达顶点 或到 达了约束条件规定的边界而停止 并报告结达了约束条件规定的边界而停止 并报告结 果 局部极大值 没有办法测试在目标曲线果 局部极大值 没有办法测试在目标曲线 的其他部分是否还有更高的山 的其他部分是否还有更高的山 54 非线性规划的特点非线性规划的特点 有些有些非线性规划模型的求解相对容易一些非线性规划模型的求解相对容易一些 类型类型1 1的特点的特点 与线性规划模型的约束条件相同 与线性规划模型的约束条件相同 目标函数是目标函数是非线性非线性函数 函数 违背违背线性规划比例性假设的每一活动表现为边际线性规划比例性假设的每一活动表现为边际 收益收益递减 要求最大化的目标函数应当是凹的 递减 要求最大化的目标函数应当是凹的 而要求最小化的目标函数应当是凸的 而要求最小化的目标函数应当是凸的 边际收益递减曲线只有一个山坡 局部极大值边际收益递减曲线只有一个山坡 局部极大值 极小值 也是全局最大值 最小值 极小值 也是全局最大值 最小值 55 非线性规划的特点非线性规划的特点 类型类型2 2的特点 的特点 活动是边际收益递减活动是边际收益递减 活动的利润或成本曲线是分段线性活动的利润或成本曲线是分段线性 即由一系即由一系 列连接在一起的直线段组成 列连接在一起的直线段组成 利润 或成本 来自活动的分段线性利润 或利润 或成本 来自活动的分段线性利润 或 成本 之和 成本 之和 由于每段利润或成本曲线都是直线段 所以这由于每段利润或成本曲线都是直线段 所以这 一技术将非线性问题转换为线性规划模型 一技术将非线性问题转换为线性规划模型 56 10 57 非线性规划的特点非线性规划的特点 Level of an activity a Level of an activity b Level of an activityLevel of an activity c d Profit Profit Profit Profit 边际收益边际收益递减递减 边际收益递减边际收益递减分段线性关系分段线性关系 边际收益递减非线性规划问题边际收益递减非线性规划问题 边际收益递减 边际成本递增 边际收益递减 边际成本递增 的生产问题的生产问题 例例1 1 伟恩德公司需要确定 伟恩德公司需要确定门和门和窗的每周生产率 窗的每周生产率 D D和和W W 目标是让总净利润最大化 目标是让总净利润最大化 营销营销成本与产量的平方成正比成本与产量的平方成正比 门的门的营销营销成本成本 25D 25D2 2 窗窗的的营销成本营销成本 200 3 W 200 3 W2 2 毛利润毛利润 门的毛利润门的毛利润 375 375美元美元 窗的毛利润窗的毛利润 700 700美元美元 净净利润利润 门的净利润门的净利润 375D 375D 25D25D2 2 窗窗的净利润的净利润 700W 700W 200 3 W 200 3 W2 2 58 10 59 边际收益递减非线性规划问题边际收益递减非线性规划问题 Weekly profit Weekly profit 024D 200 400 600 800 1 000 1 200 0246 W 200 400 600 800 1 000 1 200 1 400 1 600 1 800 Production rate for doors Production rate for windows 边际收益递减非线性规划问题边际收益递减非线性规划问题 边际收益递减 边际成本递增 边际收益递减 边际成本递增 的生产问题的生产问题 MAX 净利润净利润 375D 25 D2 700 W 200 3 W2 ST D 4 2W 12 3D 2W 18 S1 S2 S3 1 S1 S2 S3 0 参见参见 Portfolio Selection xls 63 每两股票收每两股票收 益协方差益协方差 期望收益满期望收益满 足最低要求足最低要求 各种股票占总各种股票占总 投资的比例投资的比例 风险最风险最 小化小化 每股票期每股票期 望收益望收益 每股票收益每股票收益 标准差标准差 10 64 边际收益递减非线性规划问题边际收益递减非线性规划问题 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 BCDEFG RiskExpected Min ReturnStock 1Stock 2Stock 3 St Dev Return 40 2 21 7 38 1 15 4 18 0 8 7 1 3 7 89 1 3 9 9 7 10 8 1 4 3 87 6 3 9 10 0 12 16 2 8 6 75 2 5 6 12 0 14 24 2 13 0 62 8 8 6 14 0 16 32 2 17 3 50 5 12 0 16 0 18 40 2 21 7 38 1 15 4 18 0 20 48 2 26 1 25 7 18 9 20 0 22 56 2 30 4 13 4 22 5 22 0 24 64 2 34 8 1 0 26 1 24 0 26 44 4 55 6 0 0 30 8 26 0 28 22 2 77 8 0 0 37 3 28 0 30 0 0 100 0 0 0 45 0 30 0 边际收益递减可分离规划问题边际收益递减可分离规划问题 可分离规划可分离规划技术技术 对于违背比例性假设的任一活动对于违背比例性假设的任一活动 将其利润曲线将其利润曲线 划分成多段划分成多段 使得每一段都为直线线段使得每一段都为直线线段 为活动利润曲线上的每一直线段引入新的决策变为活动利润曲线上的每一直线段引入新的决策变 量量 以代替原来用单一决策变量代表的活动 以代替原来用单一决策变量代表的活动 每一直线段的新决策变量符合比例性假设每一直线段的新决策变量符合比例性假设 因此因此 可以为这些变量建立线性规划模型可以为这些变量建立线性规划模型 65 边际收益递减可分离规划问题边际收益递减可分离规划问题 每周最大产量每周最大产量 单位产品利润 美元 单位产品利润 美元 Product Regular Time Overtime Total Regular Time Overtime Doors 3 1 4 300 200 Windows 3 3 6 500 100 边际收益递减可分离规划边际收益递减可分离规划的生产问题的生产问题 例例3 3 为了充分利用工厂的产能 伟恩德公司的工厂 为了充分利用工厂的产能 伟恩德公司的工厂1 1和工厂和工厂2 2需要工需要工 人加班 由于加班需要额外费用 所以在正常时间和加班时间里所人加班 由于加班需要额外费用 所以在正常时间和加班时间里所 生产产品的单位利润不同 因此改变了总利润函数 在这种情况下 生产产品的单位利润不同 因此改变了总利润函数 在这种情况下 每周应该生产多少门和窗 每周应该生产多少门和窗 10 67 边际收益递减可分离规划问题边际收益递减可分离规划问题 900 1 100 Weekly profit 34 0 Production rate for doors 036 Production rate for windows 1 500 1 800 Weekly profit D W 边际收益递减可分离规划问题边际收益递减可分离规划问题 决策变量变化为 决策变量变化为 D DR R 正常工作正常工作时间每周生产门的产量时间每周生产门的产量 D DO O 加班工作加班工作时间每周生产门的产量时间每周生产门的产量 W WR R 正常工作正常工作时间每周生产窗的产量时间每周生产窗的产量 W WO O 加班工作加班工作时间每周生产窗的产量时间每周生产窗的产量 SolverSolver选项选择 假设为线性模型 选项选择 假设为线性模型 可分离规划仅适用于边际收益递减 可分离规划仅适用于边际收益递减 为什么为什么 参见参见 Wyndor with Overtime xlsWyndor with Overtime xls 边际收益递减可分离规划问题边际收益递减可分离规划问题 每周最大产量每周最大产量 单位产品毛利润 美元 单位产品毛利润 美元 Product Regular Time Overtime Total Regular Time Overtime Marketing Costs Doors 3 1 4 375 275 25D2 Windows 3 3 6 700 300 662 3W2 对光滑利润曲线应用可分离规划对光滑利润曲线应用可分离规划 将曲线近似为一系列直线段 为每一直线段引入一个新变量 将曲线近似为一系列直线段 为每一直线段引入一个新变量 例例4 4 综合 综合考虑考虑例例1 1和例和例3 3的情况 即考虑非线性营销成本和加班需求 的情况 即考虑非线性营销成本和加班需求 10 70 边际收益递减可分离规划问题边际收益递减可分离规划问题 Level of activity Profit Profit graph Approximation 边际收益递减可分离规划问题边际收益递减可分离规划问题 D Gross Profit Marketing Costs Profit Incremental Profit 0 0 0 0 1 375 25 350 350 2 750 100 650 300 3 1 125 225 900 250 4 1 400 400 1 000 100 生产门的每周利润情况生产门的每周利润情况 分成分成4个直线段个直线段 边际收益递减可分离规划问题边际收益递减可分离规划问题 W Gross Profit Marketing Costs Profit Incremental Profit 0 0 0 0 1 700 662 3 6331 3 6331 3 2 1 400 2662 3 1 1331 3 500 3 2 100 600 1 500 3662 3 4 2 400 1 0662 3 1 3331 3 1662 3 5 2 700 1 6662 3 1 0331 3 300 6 3 000 2 400 600 4331 3 生产窗的每周利润情况生产窗的每周利润情况 分成分成4个个直线段 绿色区域直线段 绿色区域 作为一个线段 取平均值作为一个线段 取平均值 参见参见 WyndorWyndor OT M Separable xlsOT M Separable xls 可分离规划可分离规划 参见参见 WyndorWyndor OT M Nonlinear xlsOT M Nonlinear xls 非线性规划非线性规划 复杂的非线性规划问题复杂的非线性规划问题 复杂的非线性规划问题复杂的非线性规划问题 可能的情况可能的情况 当目标是最大化总利润时 活动的