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

其它数学规划问题其它数学规划问题 1 内容提要内容提要 1.1.整数规划整数规划 2.2.非线性规划非线性规划 3.3.目标规划目标规划（下次课讲）（下次课讲）2 整数规划整数规划 3 整数规划的基本概念整数规划的基本概念 在一些应用中，决策变量只有在它们是整数的情在一些应用中，决策变量只有在它们是整数的情况下才有实际意义，例如人员、设备数量。况下才有实际意义，例如人员、设备数量。若无特别说明，整数规划指整数线性规划。若无特别说明，整数规划指整数线性规划。管理问题用整数规划表示和用线性规划表示是一管理问题用整数规划表示和用线性规划表示是一样的，只是加了一个约束：样的，只是加了一个约束：部分或所有的决策变部分或所有的决策变量必须是整数。量必须是整数。（不再符合线性规划的可分性假不再符合线性规划的可分性假设设:决策变量可以是在满足一定函数约束和非负约决策变量可以是在满足一定函数约束和非负约束下包括分数在内的所有实数。束下包括分数在内的所有实数。）4 整数规划的基本概念整数规划的基本概念 整数规划的分类整数规划的分类 纯整数规划：要求全体变量为纯整数规划：要求全体变量为整数整数 混合整数规划：仅要求部分变量为混合整数规划：仅要求部分变量为整数整数 0 01 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 01 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 线性规划的图解法线性规划的图解法 3210123SLFeasible regionNumber of large airplanes purchasedNumber of small airplanes purchased(2,1)=Rounded solution (Profit=7)(2,1.8)=Optimal solutionProfit=11=S+5 L9.13 整数规划数学模型整数规划数学模型 Maximize Profit=S+5L($millions)subject to 5S+50L 100 ($millions)S 2 S 0,L 0 S,L 是整数是整数 S=购买小飞机数量购买小飞机数量 L=购买大飞机购买大飞机数量数量 整数规划数学模型整数规划数学模型 9.14 整数规划的图解法整数规划的图解法 3210123SLNumber of large airplanes purchasedNumber 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 01 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)0011135010196010197010198010199001113100011131101111712011117130111171410111915101119 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时，产量时，产量00；y=0y=0时，产量时，产量=0=0 添加约束添加约束:产量产量M*yM*y，M M是一个比最小可接受系数大的数，即是一个比最小可接受系数大的数，即不对产量施加额外的非期望限制。（求最大的目标排除不对产量施加额外的非期望限制。（求最大的目标排除了发了发生固定成本但产量为生固定成本但产量为0 0的不合理做法）的不合理做法）改变改变目标函数目标函数:减去固定成本减去固定成本 27 9.28 辅助辅助0 0-1 1变量变量 02462468Production quantity for windows(0,0)gives P=0(4,0)gives P=500(4,3)gives P =500+200Production quantity for doors(2,6)gives P=-100+1700(0,6)gives P=17008=1600=700WD9.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变量变量 02462468Production rate for windows(0,0)gives P=0(4,0)gives P=1,200Production rate for doors(0,6)gives P=3,000P=300 D+500 WEither D=0 or W=08WD 互斥产品问题：互斥产品问题：伟恩德公司案例变形伟恩德公司案例变形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变量变量 02424680242468(a)Choose Plant 3(b)Choose Plant 4(2,6)gives P=3,600(4,5)gives P=3,700Feasible regionFeasible regionWWDD9.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.SFOLAX 1 1 1 1 2.SFODEN 1 1 1 1 3.SFOSEA 1 1 1 1 4.LAXORD 2 2 3 2 3 5.LAXSFO 2 3 5 5 6.ORDDEN 3 3 4 7.ORDSEA 3 3 3 3 4 8.DENSFO 2 4 4 5 9.DENORD 2 2 2 10.SEASFO 2 4 4 5 11.SEALAX 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)ProfitProfitProfitProfit边际收益递减边际收益递减 边际收益递减的分段线性关系边际收益递减的分段线性关系 10.47 非线性规划的特点非线性规划的特点 边际收益递减，除不连续点之外边际收益递减，除不连续点之外 边际收益递增边际收益递增 Level of an activity(a)Level of an activity(b)Level of an activityLevel of an activity(c)(d)ProfitProfitProfitProfit10.48 非线性规划的特点非线性规划的特点 12345678ABCConstructing a Nonlinear FormulaLevel of ActivityProfit2$164$245$287$3010$33 拟合非线性公式与曲线拟合非线性公式与曲线 假定公式的一般形式假定公式的一般形式 找出合理的参数值（找出合理的参数值（Excel中的曲线拟合方法）中的曲线拟合方法）y=-0.3002x2+5.661x+6.1477$0$5$10$15$20$25$30$35024681012活动水平和利润活动水平和利润 参见参见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 非线性规划的特点非线性规划的特点 1234567ABCDEA Simple NLPMaximumx=0.371=5Profit=0.5x5-6x4+24.5x3-39x2+20 x=$3.19 从从 x=0开始运行开始运行Solver 10.51 非线性规划的特点非线性规划的特点 1234567ABCDEA Simple NLPMaximumx=3.126=5Profit=0.5x5-6x4+24.5x3-39x2+20 x=$6.13 从从 x=3开始运行开始运行Solver 10.52 非线性规划的特点非线性规划的特点 1234567ABCDEA Simple NLPMaximumx=5.000=5Profit=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)ProfitProfitProfitProfit边际收益边际收益递减递减 边际收益递减边际收益递减分段线性关系分段线性关系 边际收益递减非线性规划问题边际收益递减非线性规划问题 边际收益递减（边际成本递增）边际收益递减（边际成本递增）的生产问题的生产问题 例例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($)024D200400600 8001,0001,2000246W2004006008001,0001,200 1,4001,6001,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 边际收益递减非线性规划问题边际收益递减非线性规划问题 252627282930313233343536373839BCDEFGRiskExpectedMin ReturnStock 1Stock 2Stock 3(St.Dev.)Return40.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%边际收益递减可分离规划问题边际收益递减可分离规划问题 可分离规划可分离规划技术技术 对于违背比例性假设的任一活动对于违背比例性假设的任一活动,将其利润曲线将其利润曲线划分成多段划分成多段,使得每一段都为直线线段使得每一段都为直线线段。为活动利润曲线上的每一直线段引入新的决策变为活动利润曲线上的每一直线段引入新的决策变量量,以代替原来用单一决策变量代表的活动。以代替原来用单一决策变量代表的活动。每一直